A Varietal Genetic Algorithm by External Self-Evolving Multiple-Archives for Combinatorial Optimization Problems
Pei‐Chann Chang, Wei-Hsiu Huang, Ching‐Jung Ting, Wei-Je Chang · 2009
In this paper, a bionic algorithm based on Genetic Algorithms is proposed as a varietal GA, named External Self-evolving Multiple-archives (ESMA). ESMA focuses on improving the efficiency of applying diversity for enhancing the solution quality. 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 is applied to test the general complexity of problem. And the final instance, PCB442 shows 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.