1. Publications
  2. Journal article
  3. RDF description AMCPA: A Population Metaheuristic With Adaptive Crossover Probability and Multi-Crossover Mechanism for Solving Combinatorial Optimization Problems

AMCPA: A Population Metaheuristic With Adaptive Crossover Probability and Multi-Crossover Mechanism for Solving Combinatorial Optimization Problems

Authors
  1. Eneko Osaba
  2. Fernando Díaz
  3. Enrique Onieva
  4. Roberto Carballedo
  5. Asier Perallos

 ≈ 470.1 KB

Abstract

Combinatorial optimization is a field that receives much attention in artificial intelligence. Many problems of this type can be found in the literature, and a large number of techniques have been developed to be applied to them. Nowadays, population algorithms have become one of the most successful metaheuristics for solving this kind of problems. Among population techniques, Genetic Algorithms (GA) have received most attention due to its robustness and easy applicability. In this paper, an Adaptive Multi-Crossover Population Algorithm (AMCPA) is proposed, which is a variant of the classic GA. The presented AMCPA changes the philosophy of the basic GAs, giving priority to the mutation phase and providing dynamism to the crossover probability. To prevent the premature convergence, in the proposed AMCPA, the crossover probability begins with a low value, which is adapted every generation. Apart from this, as another mechanism to avoid premature convergence, different crossover functions are used alternatively. In order to prove the quality of the proposed technique, it is applied to six different combinatorial optimization problems, and its results are compared with the ones obtained by a classic GA. Additionally, the convergence behaviour of both techniques are also compared. Furthermore, with the objective of performing a rigorous comparison, a statistical study is conducted to compare these outcomes. The problems used during the test are: Symmetric and Asymmetric Traveling Salesman Problem, Capacitated Vehicle Routing Problem, Vehicle Routing Problem with Backhauls, N-Queens, and the one-dimensional Bin Packing Problem.