Recent Evolutionary Algorithm Variants for Combinatorial Optimization Problem

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.

Keywords

• combinatorial optimization problem
• evolutionary algorithm
• hybrid mechanisms