Title :
Dynamic Diversity Control in Genetic Algorithm for Extended Exploration of Solution Space in Multi-Objective TSP
Author :
Chang, Pei-Chann ; Huang, Wei-Hsiu ; Ting, Ching-Jung ; Fan, Chin-Yuan
Author_Institution :
Dept. of Inf. Manage., Yuan Ze Univ., Taoyuan
Abstract :
Premature convergence in the process of genetic algorithm (GA) for searching solution is frequently faced and the evolutionary processes are often trapped in a local but not global optimum. This phenomenon 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 observe 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 approach is implemented independently of the problem characteristics and can be applied to improve the global convergence behavior of genetic algorithms. We eventually apply this approach to solve Multi-Objective (MO) Traveling Salesman Problem (TSP) which were combined KroA with KroB, KroC, KroD and KroE to be trade-off problems. The result shows the solution quality to validate the adaptability of DDCGA for solving such problems.
Keywords :
convergence; genetic algorithms; mathematical operators; search problems; travelling salesman problems; artificial chromosomes; dynamic diversity control; evolutionary process; genetic algorithm; genetic operators; global convergence behavior; multiobjective TSP; premature convergence; searching solution space exploration; traveling salesman problem; Biological cells; Cities and towns; Control systems; Diversity reception; Engineering management; Genetic algorithms; Industrial engineering; Information management; Space exploration; Traveling salesman problems;
Conference_Titel :
Innovative Computing Information and Control, 2008. ICICIC '08. 3rd International Conference on
Conference_Location :
Dalian, Liaoning
Print_ISBN :
978-0-7695-3161-8
Electronic_ISBN :
978-0-7695-3161-8
DOI :
10.1109/ICICIC.2008.239