Solving the Traveling Salesman Problem through Iterative Extended Changing Crossover Operators

The subject of the Genetic Algorithm (GA) is to devise methodologies that can efficiently locate the optimum solution which must satisfy the contrary requirements of preserving population diversity and speeding up convergence on the optimum solution. In this paper, a new hybrid method iterative Extended Changing Crossover Operators (i-ECXO) combining Edge Assembly Crossover (EAX) and Ant Colony Optimization (ACO) is proposed to solve the Traveling Salesman Problem (TSP). In EAX, parent A´s edge EA is exchanged for parent B´s edge EB finally to generate new off spring, where EA and EB alternate in forming so-called A-B cycles. ACO simulates swarm intelligence in ants´ feeding behavior. In ACO, ants tend to create various kinds of cyclic paths with different sequences of visiting cities in early stage of generations. In this paper, the diversity of generations is strictly measured by the entropy H in Thermo Dynamical Genetic Algorithm (TDGA). With the measure H, the validity of i-ECXO is experimentally verified by using medium sized TSP data.