Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Soft Computing
Published in: Soft Computing 17/2020

07-02-2020 | Methodologies and Application

A novel ODV crossover operator-based genetic algorithms for traveling salesman problem

Authors: P. Victer Paul, C. Ganeshkumar, P. Dhavachelvan, R. Baskaran

Published in: Soft Computing | Issue 17/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The genetic algorithm is a popular meta-heuristic optimization technique whose performance depends on the quality of the initial population and the crossover operator used to manipulate the individuals to obtain the final optimal solution. It is evident that when similar principle is followed for population seeding and crossover operators, it can enhance the speed of convergence and the quality of final individuals. The recent and popular population seeding technique for combinatorial genetic algorithm is ordered distance vector-based population seeding which works best with respect to convergence rate and diversity. However, the technique could not achieve the zero error rate convergence for the large-sized test instances. Thus, in this paper, an ordered distance vector-based crossover operator is proposed that exclusively exploits the advantages of individuals’ generated using the same initialization methods to attain the complete convergence, particularly for most of the large-sized test instances considered. One of the famous combinatorial problems of traveling salesman problem obtained from standard library is chosen as the testbed. From the experimental results, the proposed genetic algorithm model outshines the other existing and popular working genetic algorithm models in the literature.

Graphic abstract

previous article Energy-efficient multipath routing in networking aid of clustering with OGFSO algorithm
next article Evolving semantic object segmentation methods automatically by genetic programming from images and image processing operators

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Literature
Andal JG, Sathiamoorthy S (2001) A hybrid genetic algorithm: a new approach to solve traveling salesman problem. Int J Comput Eng Sci 2(2):339–355
Arthi J, Nanthini R, Sridevi S, Victer Paul P (2015) Enhanced ODV based population seeding technique for ATSP. In: International conference on innovations in information, embedded and communication systems (ICIIECS), India, pp 1–4
Chen SM, Chien CY (2011) Solving the travelling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Syst Appl 38:14439–14450
Chuan KT(2007) Multi-parent extension of edge recombination. In: Proceedings of the 9th annual ACM conference on genetic and evolutionary computation (GECCO ‘07), pp 1535–1535
Deng Y, Liu Y, Zhou D (2015) An improved genetic algorithm with initial population strategy for symmetric TSP. Mathematical Problems in Engineering 2015
Eiben A (2002) Multiparent recombination in evolutionary computing. In: Advances in evolutionary computing, Springer, pp 175–192
Eiben A, Raué P-E, Ruttkay Z (1994) Genetic algorithms with multi-parent recombination. In: Parallel problem solving from nature—PPSN III. LNCS, vol 866, pp 78–87, Springer
El-Mihoub TA, Hopgood AA, Nolle L, Battersby A (2006) Hybrid genetic algorithms: a review. Eng Lett 13(2):124–137
Fei L, Guangzhou Z (2009) Study of genetic algorithm with reinforcement learning to solve the TSP. Expert Syst Appl 36:6995–7001
Hains DR (2012) Generalized partition crossover for the traveling salesman problem. Diss. Colorado State University, Libraries
Katayama K, Sakamoto H, Narihisa H (2000) The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem. Math Comput Model 31:197–203MathSciNetMATH
Kaur D, Murugappan MM (2008) Performance enhancement in solving travelling salesman problem using hybrid genetic algorithm. In: Annual meeting of the North American fuzzy information processing society, NAFIPS 2008, pp 1–6
Liu G, Yuanxiang L, Xin N, Hao Z (2012) A novel clustering-based differential evolution with 2 multi-parent crossovers for global optimization. Appl Soft Comput 12(2012):663–681
Maaranen H, Miettinen K, Makela MM (2004) Quasi-random initial population for genetic algorithms. Comput Math Appl 47:1885–1895MathSciNetMATH
Marinakis Y, Marinaki M (2010) A hybrid genetic–particle swarm optimization algorithm for solving the vehicle routing problem. Expert Syst Appl 37(2):1446–1455MATH
Masafumi K, Kunihito Y, Masaharu M, Moritoshi Y, Ikuo Y (2010) Development of a novel crossover of hybrid genetic algorithms for large-scale traveling salesman problems. Artif Life Robot 15:547–550
Mathias K, Whitley D (1992) Genetic operators, the fitness landscape and the traveling salesman problem. In: Manner R, Manderick B (eds) Parallel problem solving from nature. North Holland, Elsevier, pp 219–228
Moganarangan N, Raju R, Ramachandiran R, Paul PV, Dhavachelvan P, Venkatachalapathy VS (2014) Efficient crossover operator for genetic algorithm with ODV based population seeding technique. Int J Appl Eng Res 9:3885–3898
Nagata Y, Kobayashi S (1997) Edge assembly crossover: a high-power genetic algorithm for the traveling salesman problem. In: Proceeding of the seventh international conference on genetic algorithms (ICGA), pp 450–457
Pan G et al (2016) Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP. Soft Comput 20(2):555–566
Pandey HM et al. (2016) Evaluation of genetic algorithm’s selection methods. In: Information systems design and intelligent applications. Springer, New Delhi, pp 731–738
Paul PV, Ramalingam A, Baskaran R, Dhavachelvan P, Vivekanandan K, Subramanian R, Venkatachalapathy VS (2013a) Performance analyses on population seeding techniques for genetic algorithms. Int J Eng Technol 5(3):2993–3000
Paul PV, Dhavachelvan P, Baskaran R (2013b) A novel population initialization technique for genetic algorithm. In: IEEE international conference on circuit, power and computing technologies (ICCPCT), India, pp 1235–1238. ISBN: 978-1-4673-4921-5
Paul PV, Ramalingam A, Baskaran R, Dhavachelvan P, Vivekanandan K, Subramanian R (2014) A new population seeding technique for permutation-coded genetic algorithm: service transfer approach. J Comput Sci 5(2):277–297
Paul PV, Moganarangan N, Kumar SS, Raju R, Vengattaraman T, Dhavachelvan P (2015) Performance analyses over population seeding techniques of the permutation-coded genetic algorithm: An empirical study based on traveling salesman problems. Applied Soft Computing. 32:383–402
Poon PW, Carter JN (1995) Genetic algorithm crossover operators for ordering applications. Comput Oper Res. 22(1):135–147MATH
Porumbel DC, Jin-Kao H, Pascale K (2010) An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Comput Oper Res 37(2010):1822–1832MATH
Rong Y (1997) Solving large travelling salesman problems with small populations. In: Genetic algorithms in engineering systems: innovations and applications, Conference Publication No. 446, pp 157–162
Shanmugam M, SaleemBasha MS, Victer Paul P, Dhavachelvan P, Baskaran R (2013) Performance assessment over heuristic population seeding techniques of genetic algorithm: benchmark analyses on traveling salesman problems. Int J Appl Eng Res 8(10):0973–4562
Shubhra SR, Sanghamitra B, Sankar KP (2007) Genetic operators for combinatorial optimization in TSP and microarray gene ordering. J Appl Intell 26(3):183–195MATH
Sivanandam SN, Deepa SN (2008) Introduction to genetic algorithms. Springer, BerlinMATH
Ting CK (2005) Design and analysis of multi-parent genetic algorithms, Ph.D. thesis, University of Paderborn, Germany
Ting JZ (2013) A genetic algorithm for finding a path subject to two constraints. Appl Soft Comput 13(2):891–898
Ting CK, Chien-Hao S, Chung-Nan L (2010) Multi-parent extension of partially mapped crossover for combinatorial optimization problems. Expert Syst Appl 37:1879–1886
Tsai HK, Yang JM, Tsai YF, Kao CY (2004) An evolutionary algorithm for large traveling salesman problems. IEEE Trans Syst Man Cybern Part B 34(4):1718–1729
Tsutsui S, Ghosh A (1998) A study on the effect of multi-parent recombination in real coded genetic algorithms. In: Proceedings of international conference on evolutionary computation, pp 828–833
Tsutsui S, Jain L (1998) On the effect on multi-parent recombination in real coded genetic algorithms. In: Proceedings of the 2nd international conference on knowledge-based intelligent electronic systems, pp 155–160
Tsutsui S, Yamamura M, Higuchi T (1999) Multi-parent recombination with simplex crossover in real coded genetic algorithms. Proc Genet Evolut Comput Conf 1:657–664
Wang Y (2014) The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem. Comput Ind Eng 70:124–133
Wang J et al (2016) Multi-offspring genetic algorithm and its application to the traveling salesman problem. Appl Soft Comput 43:415–423
Whitely D, Starkweather T, D’Ann F (1989) Scheduling problems and traveling salesman: the genetic edge recombination operator. In: Proceedings 3rd international conference genetic algorithms, pp 133–140
Whitley D, Hains D, Howe A (2009) Tunneling between optima: partition crossover for the traveling salesman problem. In: Proceedings of the 11th annual conference on genetic and evolutionary computation, pp 915–922. ACM
Whitley D, Hains D, Howe A (2010) A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover. In: Schaefer R, Cotta C, Kolodziej J, Rudolph G (eds) PPSN XI LNCS, vol 6238. Springer, Heidelberg, pp 566–575
Metadata
Title
A novel ODV crossover operator-based genetic algorithms for traveling salesman problem
Authors
P. Victer Paul
C. Ganeshkumar
P. Dhavachelvan
R. Baskaran
Publication date
07-02-2020
Publisher
Springer Berlin Heidelberg
Published in
Soft Computing / Issue 17/2020
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-020-04712-2

Other articles of this Issue 17/2020

Soft Computing 17/2020 Go to the issue

Methodologies and Application

Self-adaptive weight vector adjustment strategy for decomposition-based multi-objective differential evolution algorithm

Methodologies and Application

Multivariate bounded support Laplace mixture model

Methodologies and Application

Clustering of the body shape of the adult male by using principal component analysis and genetic algorithm–BP neural network

Methodologies and Application

Evolving semantic object segmentation methods automatically by genetic programming from images and image processing operators

Methodologies and Application

Optimal electrical load forecasting for hybrid renewable resources through a hybrid memetic cuckoo search approach

Methodologies and Application

Enhanced decision support system to predict and prevent hypertension using computational intelligence techniques

Premium Partner

    Image Credits