Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems

摘要

The applications of genetic algorithms (GAs) in solving combinatorial problems are frequently faced with a problem of early convergence and the evolutionary processes are often trapped in a local 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 constantly 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 and to revolve again. A dynamic threshold control mechanism is built up during the evolutionary process to further improve the system performance. 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 other approaches.