A Multi-parent Hybrid Order and Cost-based Sequential Constructive Crossover of Genetic Algorithm for the Traveling Salesman Problem
Authors: 
Zhida Liu, Biao Di, Juan LinAuthors Info & Claims
Pages 129 - 135
Abstract
We investigate Genetic Algorithm (GA) where multi-parent crossovers are involved to replace the traditional two-parent crossover operation in permutation-based problems. And we propose a new multiple-parent hybrid order and cost-based sequential constructive crossover (MPHOSCX) for the Traveling Salesman Problem (TSP). More genetic high-quality information is passed on through multiple parents, cost-based crossover ensures the efficiency of the operation. Further, a nearest neighbor inverse operation is used to enhance the overall capability of exploitation. Experimental results confirm the merits of using the multi-parent hybrid crossover. And the comparison results with other multi-parent GA and GAs for TSP demonstrate the superiority of the proposed operators.
References
[1]
Holland John, H.: Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press (1975)
[2]
Lotf, J.J., Azgomi, M.A., Dishabi, M.R.E.: An improved influence maximization method for social networks based on genetic algorithm. Physica A: Statistical Mechanics and its Applications 586, 126480 (2022)
[3]
Ahmed, Z.H.: A hybrid genetic algorithm for the bottleneck traveling salesman problem. ACM Transactions on Embedded Computing Systems (TECS) 12(1),1–10 (2013)
[4]
Davis, L., : Applying adaptive algorithms to epistatic domains. In: IJCAI. vol. 85, pp. 162–164 (1985)
[5]
Goldberg, D.E., Lingle, R., : Alleles, loci, and the traveling salesman problem. In: Proceedings of an international conference on genetic algorithms and their applications. vol. 154, pp. 154–159. Lawrence Erlbaum Hillsdale, NJ (1985)
[6]
Jünger, M., Reinelt, G., Rinaldi, G.: The traveling salesman problem. Handbooks in operations research and management science 7, 225–330 (1995)
[7]
Imai, A., Nishimura, E., Papadimitriou, S.: The dynamic berth allocation problem for a container port. Transportation Research Part B: Methodological 35(4), 401–417 (2001)
[8]
Watanabe, M., Ida, K., Gen, M.: A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Computers \& Industrial Engineering 48(4), 743–752 (2005)
[9]
Roychowdhury, S., Allen, T.T., Allen, N.B.: A genetic algorithm with an earliest due date encoding for scheduling automotive stamping operations. Computers \& Industrial Engineering 105, 201–209 (2017)
[10]
Eiben, A.E., Raue, P.E., Ruttkay, Z.: Genetic algorithms with multi-parent recombination. In: International conference on parallel problem solving from nature. pp. 78–87. Springer (1994).
[11]
Eiben, A.E.: Multi-parent recombination. Evolutionary computation 1, 289–307 (1997).
[12]
Arram, A., Ayob, M.: A novel multi-parent order crossover in genetic algorithm for combinatorial optimization problems. Computers & Industrial Engineering 133,.
[13]
Ting, C.K., Su, C.H., Lee, C.N.: Multi-parent extension of partially mapped crossover for combinatorial optimization problems. Expert Systems with Applications 37(3), 1879–1886 (2010)
[14]
Ho, W., Ji, P.: An integrated scheduling problem of pcb components on sequential pick-and-place machines: Mathematical models and heuristic solutions. Expert Systems with Applications 36(3), 7002–7010 (2009)
[15]
Skliarova, I., Ferrari, A.B.: Fpga-based implementation of genetic algorithm for the traveling salesman problem and its industrial application. In: International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. pp. 77–87. Springer (2002)
[16]
Ezziane, Z.: Applications of artificial intelligence in bioinformatics: A review. Expert Systems with Applications 30(1), 2–10 (2006)
[17]
Ahmed, Z.H.: Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator. International Journal of Biometrics \& Bioinformatics (IJBB) 3(6), 96 (2010)
[18]
Ahmed, Z.H.: Multi-parent extension of sequential constructive crossover for the travelling salesman problem. International Journal of Operational Research 11(3), 331–342 (2011)
[19]
Bryant, K., Benjamin, A.: Genetic algorithms and the traveling salesman problem by kylie bryant genetic algorithms and the traveling salesman problem by. In: Proc. 1st GNT Reg. Conf. Math. Stat. Appl. (2000)
[20]
Kaabi, J., Harrath, Y.: Permutation rules and genetic algorithm to solve the traveling salesman problem. Arab journal of basic and applied sciences 26(1), 283–291 (2019)
[21]
Hassanat, A., Almohammadi, K., Alkafaween, E., Abunawas, E., Hammouri, A., Prasath, V.S.: Choosing mutation and crossover ratios for genetic algorithms—a review with a new dynamic approach. Information 10(12), 390 (2019)
[22]
Osaba, E., Diaz, F., Onieva, E., Carballedo, R., Perallos, A.: Amcpa: A population metaheuristic with adaptive crossover probability and multi-crossover mechanism for solving combinatorial optimization problems. International Journal of Artificial Intelligence 12(2), 1–23 (2014)
[23]
Watanabe, M., Ida, K., Gen, M.: A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Computers & Industrial Engineering 48(4), 743–752 (2005)
Index Terms
- A Multi-parent Hybrid Order and Cost-based Sequential Constructive Crossover of Genetic Algorithm for the Traveling Salesman Problem
Recommendations
A novel multi-parent order crossover in genetic algorithm for combinatorial optimization problems
Highlights:- A new multi-parent crossover for solving optimization problems is proposed.
- ...
AbstractMany multi-parent crossovers have been proposed to solve specific combinatorial optimization problem and not applicable to solve other problems (i.e. cannot produce feasible solution). Only multi-parent partially mapped crossover (...
Copy and Paste: A Multi-offspring Genetic Algorithm Crossover Operator for the Traveling Salesman Problem
Advances in Swarm IntelligenceAbstractThe Multi-Offspring Genetic Algorithm (MOGA) is a GA variant that was proposed specifically for the Traveling Salesman Problem (TSP). Like the Base GA (BGA), the first genetic algorithm designed to solve the TSP, MOGA has a crossover operator ...
Application of a Genetic Algorithm with Random Crossover and Dynamic Mutation on the Travelling Salesman Problem
Travelling salesman problem is a combinatorial optimization problem with wide application background and important theoretical value. The traditional method is only suitable for solving small scale travelling salesman problems, thus limiting the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2023
284 pages
ISBN:9798400707735
DOI:10.1145/3617733
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 31 October 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- Nature Science Foundation of Fujian Province of P. R. China
Conference
ICCCM 2023
ICCCM 2023: 2023 The 11th International Conference on Computer and Communications Management
August 4 - 6, 2023
Nagoya, Japan
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 24Total Downloads
- Downloads (Last 12 months)24
- Downloads (Last 6 weeks)3
Reflects downloads up to 17 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format