Recent Evolutionary Algorithm Variants for Combinatorial Optimization Problem
Keywords:
Combinatorial optimization problem, Evolutionary algorithm, Hybrid mechanisms.Abstract
The evolutionary algorithm has been extensively used to solve a range of combinatorial optimization problems. The adaptability of evolutionary algorithm mechanisms provides diverse approaches to handle combinatorial optimization challenges. This survey paper aims to comprehensively review the recent evolutionary algorithm variants in addressing combinatorial optimization problems. Research works published from the year 2018 to 2022 are identified in terms of problem representation and evolutionary strategies adopted. The mechanisms and strategies used in evolutionary algorithms to address different types of combinatorial optimization problems are discovered. Two main aspects are used to classify the evolutionary algorithm variants: population-based and evolutionary strategies (variation and replacement). It is observed that the hybrid evolutionary algorithm is mostly applied in addressing the problems. Hybridization in evolutionary algorithm mechanisms such as initialization methods, local searches, specific design operators, and self-adaptive parameters enhance the algorithm’s performance. Other metaheuristic approaches such as genetic algorithm, differential evolution algorithm, particle swarm optimization, and ant colony optimization are still preferable to address combinatorial optimization problems. Challenges and opportunities of evolutionary algorithms in combinatorial optimization problems are included for further exploration in the field of optimization research.References
A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015.
E. K. Burke and G. Kendall, Search Methodologies. Boston, MA: Springer US, 2014.
J. Lin, L. Zhu and K. Gao, A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem, Expert Systems with Applications, 140, 2020, 112915.
H. R. Maier, S. Razavi, Z. Kapelan, L. S. Matott, J. Kasprzyk and B. A. Tolson, Introductory overview: Optimization using evolutionary algorithms and other metaheuristics, Environmental Modelling & Software, 114, 2019, 195-213.
Y. Qu, Z. Ma, A. Clausen and B. N. Jorgensen, A comprehensive review on evolutionary algorithm solving multi-objective problems, 22nd IEEE International Conference on Industrial Technology (ICIT), Valencia, Spain, 2021.
B. Doerr and F. Neumann, A survey on recent progress in the theory of evolutionary algorithms for discrete optimization, ACM Transactions on Evolutionary Learning, 1(4), 2021, 1-43.
K. Sastry, D. E. Goldberg and G. Kendall, Genetic algorithms, in Search Methodologies, Boston, MA: Springer US, 2014, 93-117
A. E. Eiben and J. E. Smith, Popular evolutionary algorithm variants, in Introduction to Evolutionary Computing, Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, 99-116.
S. Yuan, T. Li and B. Wang, A co-evolutionary genetic algorithm for the two-machine flow shop group scheduling problem with job-related blocking and transportation times, Expert Systems with Applications, 152, 2020, 113360.
L. Cruz-Piris, M. A. Lopez-Carmona and I. Marsa-Maestre, Automated optimization of intersections using a genetic algorithm, IEEE Access, 7, 2019, 15452-15468.
F. M. Defersha and D. Rooyani, An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time, Computers & Industrial Engineering, 147, 2020, 106605.
A. Ghannami, J. Li, A. Hawbani and A. Al-Dubai, Stratified opposition-based initialization for variable-length chromosome shortest path problem evolutionary algorithms, Expert Systems with Applications, 170, 2021, 114525.
G. Kobeaga, M. Merino and J. A. Lozano, An efficient evolutionary algorithm for the orienteering problem, Computers & Operations Research, 90, 2018, 42-59.
H. Park, D. Son, B. Koo and B. Jeong, Waiting strategy for the vehicle routing problem with simultaneous pickup and delivery using genetic algorithm, Expert Systems with Applications, 165, 2021, 113959.
L. F. Plata-González, I. Amaya, J. C. Ortiz-Bayliss, S. E. Conant-Pablos, H. Terashima-Marín and C. A. Coello, Evolutionary-based tailoring of synthetic instances for the Knapsack problem, Soft Computing, 23(23), 2019, 12711-12728.
E. Ruiz, V. Soto-Mendoza, A. E. Ruiz Barbosa and R. Reyes, Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm, Computers & Industrial Engineering, 133, 2019, 207-219.
A. R. Komijan, P. Ghasemi, K. Khalili-Damghani and F. HashemiYazdi, A new school bus routing problem considering gender separation, special students and mix loading: a genetic algorithm approach, Journal of Optimization in Industrial Engineering, 14(2), 2021, 23-39.
E. C. Pérez, O. M. Rios, D. P. Bautista, S. S. Sanchez and F. A. Acevedo, A genetic algorithm solution for scheduling problem, XVII International Engineering Congress (CONIIN), Queretaro, Mexico, 2021.
I. A. Abduljabbar and S. M. Abdullah, An evolutionary algorithm for solving academic courses timetable scheduling problem, Baghdad Science Journal, 19(2), 2022, 398-408.
M. Mahjoob, S. S. Fazeli, S. Milanlouei, L. S. Tavassoli and M. Mirmozaffari, A modified adaptive genetic algorithm for multi-product multi-period inventory routing problem, Sustainable Operations and Computers, 3, 2022, 1-9.
A. Neumann, Y. Xie and F. Neumann, Evolutionary algorithms for limiting the effect of uncertainty for the knapsack problem with stochastic profits, Lecture Notes in Computer Science, 198, 2022, 294-307.
Z. Zeng, M. Zhang, T. Chen and Z. Hong, A new selection operator for differential evolution algorithm, Knowledge-Based Systems, 226, 2021, 107150.
W. Deng, S. Shang, X. Cai, H. Zhao, Y. Song and J. Xu, An improved differential evolution algorithm and its application in optimization problem, Soft Computing, 25(7), 2021, 5277-5298.
Q. -K. Pan, P. N. Suganthan, L. Wang, L. Gao and R. Mallipeddi, A differential evolution algorithm with self-adapting strategy and control parameters, Computers & Operations Research, 38(1), 2021, 394-408.
K. R. Opara and J. Arabas, Differential evolution: A survey of theoretical analyses, Swarm and Evolutionary Computation, 44, 2019, 546-558.
I. M. Ali, D. Essam and K. Kasmarik, Novel binary differential evolution algorithm for knapsack problems, Information Sciences, 542, 2021, 177-194.
L. He, Y. Cao, W. Li, J. Cao and L. Zhong, Optimization of energy-efficient open shop scheduling with an adaptive multi-objective differential evolution algorithm, Applied Soft Computing, 118, 2022, 108459.
M. de F. Morais, M. H. D. M. Ribeiro, R. G. da Silva, V. C. Mariani and L. dos S. Coelho, Discrete differential evolution metaheuristics for permutation flow shop scheduling problems, Computers & Industrial Engineering, 166, 2022, 107956.
R. Hu, X. Wu, B. Qian, J. Mao and H. Jin, Differential evolution algorithm combined with uncertainty handling techniques for stochastic reentrant job shop scheduling problem, Complexity, 2022, e9924163.
Z. Gao, M. Zhang and L. Zhang, Ship-unloading scheduling optimization with differential evolution, Information Sciences, 591, 2022, 88-102.
W. B. Langdon, R. Poli, N. F. McPhee and J. R. Koza, Genetic programming: an introduction and tutorial, with a survey of techniques and applications, Computational Intelligence: A Compendium, 115, 2008, 927-1028.
R. Braune, F. Benda, K. F. Doerner and R. F. Hartl, A genetic programming learning approach to generate dispatching rules for flexible shop scheduling problems, International Journal of Production Economics, 243, 2022, 108342.
Sk. Imran Hossain, M. A. H. Akhand, M. I. R. Shuvo, N. Siddique and H. Adeli, Optimization of university course scheduling problem using particle swarm optimization with selective search, Expert Systems with Applications, 127, 2019, 9-24.
J. Shi, J. Zhang, K. Wang and X. Fang, Particle swarm optimization for split delivery vehicle routing problem, Asia-Pacific Journal of Operational Research, 35, 2018, 1840006.
D. Merkle and M. Middendorf, Swarm Intelligence, Springer eBooks, 2013, 213-242.
T. Thepphakorn, S. Sooncharoen and P. Pongcharoen, Particle swarm optimisation variants and its hybridisation ratios for generating cost-effective educational course timetables, SN Computer Science, 2, 2021, 4.
I. Dahmani, M. Hifi, T. Saadi and L. Yousef, A swarm optimization-based search algorithm for the quadratic knapsack problem with conflict Graphs, Expert Systems with Applications, 148, 2020, 113224.
L. F. Mingo López, N. Gómez Blas A. Arteta Albert, Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations, Soft Computing, 22(8), 2017, 2567-2582.
S. D. Gulcu and H. K. Ornek, Solution of multiple travelling salesman problem using particle swarm optimization based algorithms, International Journal of Intelligent Systems and Applications in Engineering, 7(2), 2019, 72-82.
M. K. Marichelvam, M. Geetha and Ö. Tosun, An improved particle swarm optimization algorithm to solve hybrid flowshop scheduling problems with the effect of human factors – A case study, Computers & Operations Research, 114, 2020, 104812.
J. S. Tan, S. L. Goh, S. Sura, G. Kendall, and N. R. Sabar, Hybrid particle swarm optimization with particle elimination for the high school timetabling problem, Evolutionary Intelligence, 1, 2021, 1915-1930.
J. -L. Deneubourg, S. Aron, S. Goss and J. M. Pasteels, The self-organizing exploratory pattern of the argentine ant, Journal of Insect Behavior, 3(2), 1990, 159-168.
S. Goss, S. Aron, J. L. Deneubourg and J. M. Pasteels, Self-organized shortcuts in the Argentine ant, Naturwissenschaften, 76(12), 1989, 579-581.
M. Dorigo and C. Blum, Ant colony optimization theory: A survey, Theoretical Computer Science, 344(2-3), 2005, 243-278.
Y. -H. Jia, Y. Mei and M. Zhang, Confidence-based ant colony optimization for capacitated electric vehicle routing problem with comparison of different encoding schemes, IEEE Transactions on Evolutionary Computation, 26(6), 2022, 19-1408.
S. Li, Y. Wei, X. Liu, H. Zhu and Z. Yu, A New fast ant colony optimization algorithm: the saltatory evolution ant colony optimization algorithm, Mathematics, 10(6), 2022, 925.
Y. Wang and Z. Han, Ant colony optimization for traveling salesman problem based on parameters optimization, Applied Soft Computing, 107, 2021, 107439.
D. Thiruvady, S. Nguyen, F. Shiri, N. Zaidi and X. Li, Surrogate-assisted population based ACO for resource constrained job scheduling with uncertainty, Swarm and Evolutionary Computation, 69, 2022, 101029.
H. Zhao and C. Zhang, An ant colony optimization algorithm with evolutionary experience-guided pheromone updating strategies for multi-objective optimization, Expert Systems with Applications, 201, 2022, 117151.
D. Karaboga, B. Gorkemli, C. Ozturk and N. Karaboga, A comprehensive survey: artificial bee colony (ABC) algorithm and applications, Artificial Intelligence Review, 42(1), 2012, 21-57.
K. Zhu, L. D. Li and M. Li, School Timetabling Optimisation using artificial bee colony algorithm based on a virtual searching space method, Mathematics, 10(1), 2021, 73.
M. Shehab, A. T. Khader and M. A. Al-Betar, A survey on applications and variants of the cuckoo search algorithm, Applied Soft Computing, 61, 2017, 1041-1059.
Z. Zhang and J. Yang, A discrete cuckoo search algorithm for traveling salesman problem and its application in cutting path optimization, Computers & Industrial Engineering, 169, 2022, 108157.
X. -S. Yang and S. Deb, Cuckoo search: recent advances and applications, Neural Computing and Applications, 24(1), 2013, 169-174.
S. Nesmachnow et al., Traffic lights synchronization for bus rapid transit using a parallel evolutionary algorithm, International Journal of Transportation Science and Technology, 8(1), 2019, 53-67.
A. Rezaeipanah, S. S. Matoori and G. Ahmadi, A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search, Applied Intelligence, 51, 2021, 67-92.
T. Yiğit and C. Altıntaş, Analysing the effects of classroom utilisation with a self-generating multimeme memetic algorithm for the exam timetabling problem, Advances in Artificial Intelligence Research (AAIR), 1(2), 2021, 43-51.
N. Wang, Y. Sun and H. Wang, An adaptive memetic algorithm for dynamic electric vehicle routing problem with time-varying demands, Mathematical Problems in Engineering, 2021, 1-10.
S. Liu, K. Tang and X. Yao, Memetic search for vehicle routing with simultaneous pickup-delivery and time windows, Swarm and Evolutionary Computation, 66, 2021, 100927.
H. Jiang, M. Lu, Y. Tian, J. Qiu and X. Zhang, An evolutionary algorithm for solving capacitated vehicle routing problems by using local information, Applied Soft Computing, 117, 2022, 108431.
A. T. Al- Taani and L. M. Al-Afifi, Solving the multiple traveling salesman problem using memetic algorithm, Artificial Intelligence Evolution, (1), 2022, 27-40.
S. Afsar, J. J. Palacios, J. Puente, C. R. Vela and I. González-Rodríguez, Multi-objective enhanced memetic algorithm for green job shop scheduling with uncertain times, Swarm and Evolutionary Computation, 68, 2022, 101016.
A. Nikfarjam, A. Neumann and F. Neumann, Evolutionary diversity optimisation for the traveling thief problem, Proceedings of the Genetic and Evolutionary Computation Conference, Boston, Massachusetts, 2022.
H. I. Calvete, C. Galé and J. A. Iranzo, Approaching the Pareto front in a biobjective bus route design problem dealing with routing cost and individuals’ walking distance by using a novel evolutionary algorithm, Mathematics, 10(9), 2022, 1390.
J. Zhang, F. Yang and X. Weng, An evolutionary scatter search particle swarm optimization algorithm for the vehicle routing problem with time windows, IEEE Access, 6, 2018, 63468-63485.
A. Maskooki, K. Deb and M. Kallio, A customized genetic algorithm for bi-objective routing in a dynamic network, European Journal of Operational Research, 297(2), 2022, 615-629.
Y. Lu, U. Benlic and Q. Wu, A highly effective hybrid evolutionary algorithm for the covering salesman problem, Information Sciences, 564, 2021, 144-162.
D. F. Dofadar, R. H. Khan, S. Hasan, T. A. Taj, A. Shakil and M. Majumdar, A hybrid evolutionary approach to solve university course allocation problem, 2021 International Conference on Artificial Intelligence and Blockchain Technology, Beijing, China, 2021.
İ. İlhan, An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem, Swarm and Evolutionary Computation, 64, 2021, 100911.
O. A. Arık, Population-based Tabu search with evolutionary strategies for permutation flow shop scheduling problems under effects of position-dependent learning and linear deterioration, Soft Computing, 25(2), 2020, 1501-1518.
A. Agrawal, N. Ghune, S. Prakash and M. Ramteke, Evolutionary algorithm hybridized with local search and intelligent seeding for solving multi-objective Euclidian TSP, Expert Systems with Applications, 181, 2021, 115192.
Y. Lu, U. Benlic and Q. Wu, A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem, Computers & Operations Research, 144, 2022, 105799.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:Authors hold and retain copyright, and grant the journal right of first publication, with the work after publication simultaneously licensed under a Creative Commons Attribution 4.0 License CC BY that permits any use, reproduction and distribution of the work and article without further permission provided that the original work is properly cited.
Authors are permitted and encouraged to post their work online in institutional repositories, website and other social media before and after publication, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
