Quantitative evaluation of iterative extended changing crossover operators to solve the traveling salesman problem: Diversity measurement and its application to selection strategies in genetic algorithms

Efficiency to search for the optimum solutions of the traveling salesman problem (TSP) and controlling the diversity of the population are quantitatively evaluated for iterative Extended Changing Crossover Operators (i-ECXO), immune Genetic Algorithm (immune-GA) and Thermo Dynamical Genetic Algorithm (TDGA). i-ECXO is a hybrid method to unite Edge Assembly Crossover (EAX) to Ant Colony Optimization (ACO). It mixes chromosomes generated by ACO which has capability to create closed tours with different sequences of visiting cities with those generated by EAX which has capacity to search for the best local solutions efficiently. It makes EAX reproduce better individuals by reusing the mixed chromosomes as initial tours. In TDGA the diversity of the population is accurately calculated as entropy H and selects out individuals so that free energy F can be minimized. Immune-GA realizes Jerne´s network which harmonizes the immune system by making another antibodies work antigens for each antibody. Regards as capability of controlling the diversity of the population, above three methods are evaluated by using the edges´ entropy H in TDGA. C and Java experimental results using medium-sized TSPLIB data such as fl417 are reported in this paper.