A novel evolutionary algorithm for the traveling salesman problem

Chengjun Li, Yong Xia, Si Xu, Wei Zhan

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

The traveling salesman problem (TSP) is a famous NP-hard problem. The established evolutionary algorithms (EAs) cannot get satisfactory solutions of large or even medium scale TSP instances. To change this situation, a effective EA based on inver-over operator is introduced. In this algorithm, two novel crossover operators, the segment replacing crossover and the order adjusting crossover, are proposed. Moreover, a mechanism for changing the crossover and the mutation rate of the inver-over operator according to generations and a parameter, the critical value, is employed. The results of the experiment show that this new algorithm outperforms the basic EA based on the inver-over operator in all the 4 instances.
Original languageEnglish
Title of host publicationProceedings 2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011
Pages2515-2517
Number of pages3
DOIs
Publication statusPublished - 14 Oct 2011
Externally publishedYes
Event2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011 - Jilin, China
Duration: 19 Aug 201122 Aug 2011

Conference

Conference2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011
CountryChina
CityJilin
Period19/08/1122/08/11

Keywords

  • evolutionary algorithm
  • inver-over operator
  • order adjusting crossover
  • segment replacing crossover
  • traveling salesman problem

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Mechanical Engineering

Cite this