文章基本信息

标题：New Approach of a Genetic Algorithm for TSP Using the Evaluation Function Considering Local Diversity Loss
本地全文：下载
作者：Yuichi Nagata
期刊名称：人工知能学会論文誌
印刷版ISSN：1346-0714
电子版ISSN：1346-8030
出版年度：2006
卷号：21
期号：2
页码：195-204
DOI：10.1527/tjsai.21.195
出版社：The Japanese Society for Artificial Intelligence
摘要：The edge assembly crossover (EAX) is considered the best available crossover for traveling salesman problems (TSPs). In this paper, a modified EAX algorithm is proposed. The key idea is to maintain population diversity by eliminating any exchanges of edges by the crossover that does not contribute to an improved evaluation value. For this, a new evaluation function is designed considering local diversity loss of the population. The proposed method is applied to several benchmark instances with up to 4461 cities. Experimental results show that the proposed method works better than other genetic algorithms using other improvements of the EAX. The proposed method can reach optimal solutions for most benchmark instances with up to 2392 cities with probabilities higher than 90%. For an instance called fnl4461, this method can reach an optimal solution with probability 60% when the population size is set to 300 -- an extremely small population compared to that needed in previous studies.
关键词：genetic algorithm ; TSP ; EAX ; local diversity loss ; evaluation function