A Branch-and-Bound-Based Crossover Operator for the Traveling Salesman Problem

Thomas Weise, Yan Jiang, Qi Qi and Weichen Liu
Additional contact information
Thomas Weise: Institute of Applied Optimization, Hefei, China
Yan Jiang: University of Science and Technology of China, Shanghai, China
Qi Qi: University of Science and Technology of China, Hefei, China
Weichen Liu: University of Science and Technology of China, Hefei, China

International Journal of Cognitive Informatics and Natural Intelligence (IJCINI), 2019, vol. 13, issue 3, 1-18

Abstract: In this article, the new crossover operator BBX for Evolutionary Algorithms (EAs) for traveling salesman problems (TSPs) is introduced. It uses branch-and-bound to find the optimal combination of the (directed) edges present in the parent solutions. The offspring solutions created are at least as good as their parents and are only composed of parental building blocks. The operator is closer to the ideal concept of crossover in EAs than existing operators. This article provides the most extensive study on crossover operators on the TSP, comparing BBX to ten other operators on the 110 instances of the TSPLib benchmark set in EAs with four different population sizes. BBX, with its better ability to reuse and combine building blocks, surprisingly does not generally outperform the other operators. However, it performs well in certain scenarios. Besides presenting a novel approach to crossover on the TSP, the study significantly extends and refines the body of knowledge on the field with new conclusions and comparison results.

Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 18/IJCINI.2019070101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jcini0:v:13:y:2019:i:3:p:1-18

Access Statistics for this article

International Journal of Cognitive Informatics and Natural Intelligence (IJCINI) is currently edited by Kangshun Li

More articles in International Journal of Cognitive Informatics and Natural Intelligence (IJCINI) from IGI Global
Bibliographic data for series maintained by Journal Editor ().