Edge Assembly Crossover using Multiple Parents for Traveling Salesman Problem

摘要

This paper presents a new technique which improves the diversity in offspring generated by Edge Assembly Crossover (EAX) with multiple parents. EAX is the most promising crossover for solving Traveling Salesman Problems (TSP) among population-based evolutional approaches. In EAX, offspring are generated by combining edges of two parents' tours based on a set of closed cycles referred to AB-cycles that are constructed by tracing edges of the two tours alternately. AB-cycle is the most important component to assemble preferable traits observed in parents, and the diversity of traits in offspring or the next population is enhanced if the number of generated AB-cycles increases. Latest EAX introduces an entropy relevant to edge occurrence to the selection in order to improve the diversity of the population. In this paper, we propose a new EAX using more than two parents in one crossover in order to form a wide variety of AB-cycles. As introductory experiments, we evaluate the performance of our method in relatively small instances of TSP.