Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: Memetic Computing 1/2020

01.07.2019 | Regular Research Paper

A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem

verfasst von: Anton V. Eremeev, Yulia V. Kovalenko

Erschienen in: Memetic Computing | Ausgabe 1/2020

Einloggen, um Zugang zu erhalten
share
TEILEN

Abstract

We propose a new memetic algorithm with optimal recombination for the asymmetric travelling salesman problem (ATSP). The optimal recombination problem (ORP) is solved in a crossover operator based on a new exact algorithm that solves the ATSP on cubic digraphs. A new mutation operator makes random jumps in 3-opt or 4-opt neighborhoods. The initial population is constructed by means of greedy constructive heuristics. The 3-opt local search is used to improve the initial and the final populations. A computational experiment on the TSPLIB instances shows that the proposed algorithm yields results competitive to those of other well-known algorithms for ATSP and confirms that the ORP may be used successfully in memetic algorithms.
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Zurück zum Zitat Brown BW, Hollander M (1977) Statistics: a biomedical introduction. Wiley, New York CrossRef Brown BW, Hollander M (1977) Statistics: a biomedical introduction. Wiley, New York CrossRef
2.
Zurück zum Zitat Buriol LS, Franca PM, Moscato P (2004) A new memetic algorithm for the asymmetric traveling salesman problem. J Heuristics 10:483–506 CrossRef Buriol LS, Franca PM, Moscato P (2004) A new memetic algorithm for the asymmetric traveling salesman problem. J Heuristics 10:483–506 CrossRef
3.
Zurück zum Zitat Burke EK, Cowling PI, Keuthen R (2001) Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem. In: Boers EJW (ed) EvoWorkshop 2001, applications of evolutionary computing, LNCS, vol 2037. Springer, Berlin, pp 203–212 Burke EK, Cowling PI, Keuthen R (2001) Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem. In: Boers EJW (ed) EvoWorkshop 2001, applications of evolutionary computing, LNCS, vol 2037. Springer, Berlin, pp 203–212
4.
Zurück zum Zitat Dongarra JJ (2014) Performance of various computers using standard linear equations software. Technical report CS-89-85. University of Manchester Dongarra JJ (2014) Performance of various computers using standard linear equations software. Technical report CS-89-85. University of Manchester
6.
Zurück zum Zitat Eremeev AV (2019) A restarting rule based on the \(\text{Schnabel}\) census for genetic algorithms. In: Battiti R, Brunato M, Kotsireas I, Pardalos PM (eds) Learning and Intelligent Optimization, LNCS, vol 11353. Springer, Cham, pp 337–351 Eremeev AV (2019) A restarting rule based on the \(\text{Schnabel}\) census for genetic algorithms. In: Battiti R, Brunato M, Kotsireas I, Pardalos PM (eds) Learning and Intelligent Optimization, LNCS, vol 11353. Springer, Cham, pp 337–351
7.
Zurück zum Zitat Eremeev AV, Kovalenko JV (2014) Optimal recombination in genetic algorithms for combinatorial optimization problems: part II. Yugoslav J Oper Res 24(2):165–186 MathSciNetCrossRef Eremeev AV, Kovalenko JV (2014) Optimal recombination in genetic algorithms for combinatorial optimization problems: part II. Yugoslav J Oper Res 24(2):165–186 MathSciNetCrossRef
8.
Zurück zum Zitat Eremeev AV, Kovalenko JV (2016) Experimental evaluation of two approaches to optimal recombination for permutation problems. In: Chicano F, Hu B, García-Sánchez P (eds) Evolutionary computation in combinatorial optimization, LNCS, vol 9595. Springer, Cham, pp 138–153 CrossRef Eremeev AV, Kovalenko JV (2016) Experimental evaluation of two approaches to optimal recombination for permutation problems. In: Chicano F, Hu B, García-Sánchez P (eds) Evolutionary computation in combinatorial optimization, LNCS, vol 9595. Springer, Cham, pp 138–153 CrossRef
9.
Zurück zum Zitat Eremeev AV, Kovalenko YV (2018) Genetic algorithm with optimal recombination for the asymmetric travelling salesman problem. In: Lirkov I, Margenov S (eds) Large-scale scientific computing, LNCS, vol 10665. Springer, Cham, pp 341–349 CrossRef Eremeev AV, Kovalenko YV (2018) Genetic algorithm with optimal recombination for the asymmetric travelling salesman problem. In: Lirkov I, Margenov S (eds) Large-scale scientific computing, LNCS, vol 10665. Springer, Cham, pp 341–349 CrossRef
10.
Zurück zum Zitat Freisleben B, Merz P (1996) A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In: IEEE international conference on evolutionary computation. IEEE Press, pp 616–621 Freisleben B, Merz P (1996) A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In: IEEE international conference on evolutionary computation. IEEE Press, pp 616–621
11.
Zurück zum Zitat Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco MATH Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco MATH
12.
Zurück zum Zitat Goldberg D, Thierens D (1994) Elitist recombination: an integrated selection recombination GA. In: First IEEE world congress on computational intelligence, vol 1. IEEE Service Center, Piscataway, pp 508–512 Goldberg D, Thierens D (1994) Elitist recombination: an integrated selection recombination GA. In: First IEEE world congress on computational intelligence, vol 1. IEEE Service Center, Piscataway, pp 508–512
13.
Zurück zum Zitat Johnson DS, McGeorch LA (1997) The traveling salesman problem: a case study. In: Aarts E, Lenstra JK (eds) Local search in combinatorial optimization. Wiley, New York, pp 215–336 Johnson DS, McGeorch LA (1997) The traveling salesman problem: a case study. In: Aarts E, Lenstra JK (eds) Local search in combinatorial optimization. Wiley, New York, pp 215–336
14.
Zurück zum Zitat Kanellakis PC, Papadimitriou CH (1980) Local search for the asymmetric traveling salesman problem. Oper Res 28:1086–1099 MathSciNetCrossRef Kanellakis PC, Papadimitriou CH (1980) Local search for the asymmetric traveling salesman problem. Oper Res 28:1086–1099 MathSciNetCrossRef
15.
Zurück zum Zitat Mood AM, Graybill FA, Boes DC (1974) Introduction to the theory of statistics. McGraw-Hill, New York MATH Mood AM, Graybill FA, Boes DC (1974) Introduction to the theory of statistics. McGraw-Hill, New York MATH
16.
Zurück zum Zitat Nagata Y, Soler D (2012) A new genetic algorithm for the asymmetric TSP. Expert Syst Appl 10:8947–8953 CrossRef Nagata Y, Soler D (2012) A new genetic algorithm for the asymmetric TSP. Expert Syst Appl 10:8947–8953 CrossRef
17.
Zurück zum Zitat Neri F, Cotta C (2012) Memetic algorithms and memetic computing optimization: a literature review. Swarm Evol Comput 2:1–14 CrossRef Neri F, Cotta C (2012) Memetic algorithms and memetic computing optimization: a literature review. Swarm Evol Comput 2:1–14 CrossRef
18.
Zurück zum Zitat Neri F, Cotta C, Moscato P (2012) Handbook of memetic algorithms. Springer, Berlin, Heidelberg CrossRef Neri F, Cotta C, Moscato P (2012) Handbook of memetic algorithms. Springer, Berlin, Heidelberg CrossRef
19.
Zurück zum Zitat Neri F, Toivanen J, Cascella GL, Ong YS (2007) An adaptive multimeme algorithm for designing HIV multidrug therapies. IEEE/ACM Trans Comput Biol Bioinf 4:264–278 CrossRef Neri F, Toivanen J, Cascella GL, Ong YS (2007) An adaptive multimeme algorithm for designing HIV multidrug therapies. IEEE/ACM Trans Comput Biol Bioinf 4:264–278 CrossRef
20.
Zurück zum Zitat Norman M, Moscato P (1991) A competitive and cooperative approach to complex combinatorial search. In: 20th joint conference on informatics and operations research. Buenos Aires, pp 3.15–3.29 Norman M, Moscato P (1991) A competitive and cooperative approach to complex combinatorial search. In: 20th joint conference on informatics and operations research. Buenos Aires, pp 3.15–3.29
22.
23.
Zurück zum Zitat Reeves CR, Eremeev AV (2004) Statistical analysis of local search landscapes. J Oper Res Soc 55(7):687–693 CrossRef Reeves CR, Eremeev AV (2004) Statistical analysis of local search landscapes. J Oper Res Soc 55(7):687–693 CrossRef
24.
Zurück zum Zitat Rego C, Gamboa D, Glover F (2016) Doubly-rooted stem-and-cycle ejection chain algorithm for the asymmetric traveling salesman problem. Networks 68(1):23–33 MathSciNetCrossRef Rego C, Gamboa D, Glover F (2016) Doubly-rooted stem-and-cycle ejection chain algorithm for the asymmetric traveling salesman problem. Networks 68(1):23–33 MathSciNetCrossRef
26.
Zurück zum Zitat Tinós R, Whitley D, Ochoa G (2014) Generalized asymmetric partition crossover (GAPX) for the asymmetric TSP. In: The 2014 annual conference on genetic and evolutionary computation. ACM, New York, pp 501–508 Tinós R, Whitley D, Ochoa G (2014) Generalized asymmetric partition crossover (GAPX) for the asymmetric TSP. In: The 2014 annual conference on genetic and evolutionary computation. ACM, New York, pp 501–508
27.
Zurück zum Zitat Turkensteen M, Ghosh D, Goldengorin B, Sierksma G (2008) Tolerance-based branch and bound algorithms for the ATSP. Eur J Oper Res 189:775–788 MathSciNetCrossRef Turkensteen M, Ghosh D, Goldengorin B, Sierksma G (2008) Tolerance-based branch and bound algorithms for the ATSP. Eur J Oper Res 189:775–788 MathSciNetCrossRef
28.
Zurück zum Zitat Whitley D, Starkweather T, Shaner D (1991) The traveling salesman and sequence scheduling: quality solutions using genetic edge recombination. In: Davis L (ed) Handbook of genetic algorithms. Van Nostrand Reinhold, New York, pp 350–372 Whitley D, Starkweather T, Shaner D (1991) The traveling salesman and sequence scheduling: quality solutions using genetic edge recombination. In: Davis L (ed) Handbook of genetic algorithms. Van Nostrand Reinhold, New York, pp 350–372
29.
Zurück zum Zitat Xing LN, Chen YW, Yang KW, Hou F, Shen XS, Cai HP (2008) A hybrid approach combining an improved genetic algorithm and optimization strategies for the asymmetric TSP. Eng Appl Artif Intell 21(8):1370–1380 CrossRef Xing LN, Chen YW, Yang KW, Hou F, Shen XS, Cai HP (2008) A hybrid approach combining an improved genetic algorithm and optimization strategies for the asymmetric TSP. Eng Appl Artif Intell 21(8):1370–1380 CrossRef
30.
Zurück zum Zitat Yagiura M, Ibaraki T (1996) The use of dynamic programming in genetic algorithms for permutation problems. Eur J Oper Res 92:387–401 CrossRef Yagiura M, Ibaraki T (1996) The use of dynamic programming in genetic algorithms for permutation problems. Eur J Oper Res 92:387–401 CrossRef
31.
Zurück zum Zitat Zhang W (2000) Depth-first branch-and-bound versus local search: a case study. In: 17th national conference on artificial intelligence. Austin, pp 930–935 Zhang W (2000) Depth-first branch-and-bound versus local search: a case study. In: 17th national conference on artificial intelligence. Austin, pp 930–935
Metadaten
Titel
A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem
verfasst von
Anton V. Eremeev
Yulia V. Kovalenko
Publikationsdatum
01.07.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
Memetic Computing / Ausgabe 1/2020
Print ISSN: 1865-9284
Elektronische ISSN: 1865-9292
DOI
https://doi.org/10.1007/s12293-019-00291-4

Weitere Artikel der Ausgabe 1/2020

Memetic Computing 1/2020 Zur Ausgabe

Editorial

Editorial

Premium Partner