結合外部自我演化機制改善基因演算法求解組合性最佳化問題

基因演算法(Genetic Algorithm)是最常用於求解組合性問題的演化式演算法，該方法在組合問題中具有不錯的求解效果。但隨著組合性問題(Combinatorial Problem)的維度(Dimension)漸漸變大，該方法易因演化運算後喪失族群多樣性(Diversity)而產生過早收斂或稱過早成熟的問題，使求得的解落於局部最佳解(Local Optimal)之中並且難以跳脫。為了解決此問題，大多數的學者均以改變演化的運算子或其機率，試圖藉由演化運算子之機率的不同改善過早收斂並跳脫出區域最佳解。本研究提出以衡量族群多樣性，及利用分群(Clustering)的概念，將族群依照多樣性分為多個不同的群體，在演化時從不同的群體中挑選出個體加以演化，以增加演化時染色體容易喪失多樣性而過早收斂的情況並擴大演化的搜尋空間，其後透過多階段突變(Multiple-Phases Mutation)策略演化法則，以不同突變方法探究搜尋空間，並於其中所產生出的基因資訊擁有較好基因片段的染色體加以保留，透過染色體多樣性的計算，將其放置於各群組之中，藉由此方式，一方面可以將在演化過程中出現過的較好基因片段加以保留，另一方面亦可藉由萃取出較好的染色體資訊增加收斂的速度。透過收集較佳的染色體資訊藉由排序多樣性評估後放入至適合的群組，可避免僅單方面增加收斂速度，而陷入區域最佳解的問題，藉此達到不失多樣性又兼具收斂速度的方法。本研究以旅行推銷員問題(Traveling Salesman Problem)來進行驗證，其結果証明本研究具有較為快速的收斂速度，並且仍能夠保持族群的多樣性另其不易陷入區域最佳解，而能夠獲得更好的求解品質。

關鍵字

多樣性；組合性最佳化問題；基因演算法；自我演化；分群；多階段突變策略

並列摘要

In this paper, a bionic algorithm based on Genetic Algorithms is proposed as a varietal GA, named External Self-evolving Multiple-archives (ESMA). The main idea of ESMA adopts clustering approach to cluster chromosomes with elitist chromosomes and high diversities. ESMA focuses on improving the efficiency of applying diversity for enhancing the solution quality via searching unexplored searching space. Therefore, this paper proposes three mechanisms for self-evolving Multiple-archives, which are Clustering Strategy, Switchable Mutation and Elitist Propagation. These mechanisms are designed based on the idea of increasing dynamic diversity for searching better solution space. Moreover, the proposed algorithm can effectively search satisfactory solution than several well-known algorithms with benchmark problems such as Simple Genetic Algorithm (SGA), Ant Colony Optimization (ACO) and Simulated Annealing (SA). The experimental results using Traveling Salesman Problem (TSP) instances which are KroA100, KroA150 and KroA200 for small problems to show the efficiency of convergence speed. Instance PR299 and PCB442 are applied to test the general complexity of problem. And the final instance, PR1002, PR2392, PCB1173 and PCB3038 show the robust of the proposed approach. The experimental results show that the proposed approach is more effective when searches global solution and it can prevent the solution trapped in local optimal when compared with the earlier approaches.

並列關鍵字

Diversity ； Combinatorial Problem ； Genetic Algorithm ； Self-evolving ； Clustering ； Multiple-phases Mutation Strategy

參考文獻

57. 吳泰熙、張欽智，「以禁忌搜尋法則求解推銷員行問題」，大葉學報，卷(6)1，1997。

58. 陳佑誠，「基因演算法之動態基因多樣性改善以延伸組合性問題之求解空間」，碩士論文，元智大學，2007。

59. 陳啟嘉，「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」，碩士論文，元智大學，2006。

2. Affenzeller, M., “New Variants of Genetic Algorithms Applied to Problems of Combinatorial Optimization,” Proceedings of the EMCSR 2002, vol.1, pp.75-80, 2002.

3. Backer, K. R.,” Introduction to Sequencing and Scheduling. John Wiley,” NY. 1974.

國際替代計量

結合外部自我演化機制改善基因演算法求解組合性最佳化問題

全文下載

主題瀏覽