A novel evolutionary algorithm for the traveling salesman problem

Chengjun Li; Yong Xia; Si Xu; Wei Zhan

doi:10.1109/MEC.2011.6026004

A novel evolutionary algorithm for the traveling salesman problem

Chengjun Li, Yong Xia, Si Xu, Wei Zhan

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-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 language	English
Title of host publication	Proceedings 2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011
Pages	2515-2517
Number of pages	3
DOIs	https://doi.org/10.1109/MEC.2011.6026004
Publication status	Published - 14 Oct 2011
Externally published	Yes
Event	2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011 - Jilin, China Duration: 19 Aug 2011 → 22 Aug 2011

Conference

Conference	2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011
Country/Territory	China
City	Jilin
Period	19/08/11 → 22/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

More information

10.1109/MEC.2011.6026004

Cite this

@inproceedings{8846c3bf870944ef898f9bdfb7385c73,

title = "A novel evolutionary algorithm for the traveling salesman problem",

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.",

keywords = "evolutionary algorithm, inver-over operator, order adjusting crossover, segment replacing crossover, traveling salesman problem",

author = "Chengjun Li and Yong Xia and Si Xu and Wei Zhan",

year = "2011",

month = oct,

day = "14",

doi = "10.1109/MEC.2011.6026004",

language = "English",

isbn = "9781612847221",

pages = "2515--2517",

booktitle = "Proceedings 2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011",

note = "2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011 ; Conference date: 19-08-2011 Through 22-08-2011",

}

Li, C, Xia, Y, Xu, S & Zhan, W 2011, A novel evolutionary algorithm for the traveling salesman problem. in Proceedings 2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011., 6026004, pp. 2515-2517, 2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011, Jilin, China, 19/08/11. https://doi.org/10.1109/MEC.2011.6026004

A novel evolutionary algorithm for the traveling salesman problem. / Li, Chengjun; Xia, Yong; Xu, Si et al.
Proceedings 2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011. 2011. p. 2515-2517 6026004.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - A novel evolutionary algorithm for the traveling salesman problem

AU - Li, Chengjun

AU - Xia, Yong

AU - Xu, Si

AU - Zhan, Wei

PY - 2011/10/14

Y1 - 2011/10/14

N2 - 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.

AB - 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.

KW - evolutionary algorithm

KW - inver-over operator

KW - order adjusting crossover

KW - segment replacing crossover

KW - traveling salesman problem

UR - http://www.scopus.com/inward/record.url?scp=80053921362&partnerID=8YFLogxK

U2 - 10.1109/MEC.2011.6026004

DO - 10.1109/MEC.2011.6026004

M3 - Conference article published in proceeding or book

SN - 9781612847221

SP - 2515

EP - 2517

BT - Proceedings 2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011

T2 - 2011 International Conference on Mechatronic Science, Electric Engineering and Computer, MEC 2011

Y2 - 19 August 2011 through 22 August 2011

ER -

A novel evolutionary algorithm for the traveling salesman problem

Abstract

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this