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