著者

永田 裕一 小林 重信

出版者

社団法人人工知能学会

雑誌

人工知能学会誌 (ISSN:09128085)

巻号頁・発行日

vol.14, no.5, pp.848-859, 1999-09-01

被引用文献数

21

---

In this paper, we propose a new crossover named Edge Assembly Crossover(EAX) for the Traveling Salesman Problern. EAX constructs intermediate individuals by assembling only edges of parents under the assignment relaxation that is one of TSP relaxations, and then modifies them into complete ones to satisfy the original constraint of TSP. EAX has two features. One is that EAX is excellent in chartacteristic preservation in view of preserving edges from parents to children. The other is that EAX can generate a wide variety of children from a pair of parents. We show by experiments that EAX generates new soltution candidates under a suitable trade-off between characteristic preservation and a variety of children, which brings better performance than other crossovers do. Finally, we show that EAX realizes global neighborhood search by comparing EAX with the traditional local search operators for TSP.