Genetic algorithm for very large traveling salesman problems and its applications to practical applications

点击翻译按钮获取中文摘要

We have developed an genetic algorithm (GA) for the traveling salesman problem (TSP). The GA uses edge assembly crossover (EAX), which is known to be efficient and effective for solving TSPs. We first propose a modified EAX algorithm that can be executed more efficiently than the original, which is 2-7 times faster. We then propose a selection model that can efficiently maintain population diversity at negligible computational cost. The edge entropy measure is used as an indicator of population diversity. We further improved the performance of the GA with EAX, especially for large instances of more than 10,000 cities. Our method is highly competitive with existing approaches. Moreover, we have developed very efficient MAs for several vehicle routing problems by extending the GA developed for the TSP.