基因演算法之動態基因多樣性改善以延伸組合性問題之求解空間

Dynamic Diversity Control in Genetic Algorithm for Extended Exploration of Solution Space in Combinatorial Problems

陳佑誠(Cycer Chen)

指導教授 ： 張百棧 ； 鍾雲恭

元智大學/工程學院/工業工程與管理學系/碩士(2008年)

https://doi.org/10.6838/YZU.2008.00004

摘要

基因演算法是最常用於求解組合性問題的一種演化式演算法，該方法在組合問題中具有不錯的求解。但隨組合性問題的維度變大，該方法易因演化運算後喪失族群多樣性而產生過早收斂或稱過早成熱的問題，使得求得的解落於次佳解(區域最佳解)之中並難以跳脫次佳解。
為了解決此問題，大多數的學者均以改變演化運算子或演化運算子的機率。在本研究中，提出以衡量族群多樣性，當族群多樣性不足時，注入人造染色體以提升族群多樣性使得基因演算法能有機會繼續演化。
該方法以旅行者問題來進行驗證，其結果証明當族群多樣性不足時，注入人造染色體的確能有效的跳脫次佳解並改善求解品質。

關鍵字

基因演算法、最佳化、多樣性、人造染色體、組合性問題、旅行者問題

並列摘要

The applications of genetic algorithms in solving combinatorial problems are frequently faced with a problem of early convergence and the evolutionary processes are often trapped into a local but not the global optimum. This premature convergence occurs when the population of a genetic algorithm reaches a suboptimal state that the genetic operators can no longer produce offspring with a better performance than their parents. In the literature, plenty of work has been investigated to introduce new methods and operators in order to overcome this essential problem of genetic algorithms.
As these methods and the belonging operators are rather problem specific in general. In this research, we take a different approach by observing the progress of the evolutionary process and when the diversity of the population dropping below a threshold level then artificial chromosomes with high diversity will be introduced to increase the average diversity level thus to ensure the process can jump out the local optimum.
The proposed method is implemented independently of the problem characteristics and can be applied to improve the global convergence behavior of genetic algorithms. The experimental results using TSP instances show that the proposed approach is very effective in preventing the premature convergence when compared with the earlier approaches.

並列關鍵字

Optimization ； Genetic Algorithm ； Diversity ； Artificial Chromosomes ； Combinatorial Problems ； TSP

參考文獻

[1] M.R. Garey, and D.S. Johnson. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman.

[2] F.-C. Yang, and Y.-P. Wang. (2007), Water flow-like algorithm for object grouping problems. Journal of the Chinese Institute of Industrial Engineers ,24, 475~488.

[3] D.R. Sule. (1997), Industrial Scheduling, PWS.

[5] A. Nagar, S.S. Heragu, and J. Haddock. (1995), A Branch-and-Bound Approach for a Two-Machine Flowshop Scheduling Problem Journal of the Operational Research Society ,46, 721-734.

[6] P. Mellor. (1966), A review of job shop scheduling. Operations Research Quarterly ,17, 161-171.