Open Access Open Access  Restricted Access Subscription or Fee Access

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

Eneko Osaba, Fernando Diaz, Enrique Onieva, Roberto Carballedo, Asier Perallos

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.

Keywords


Adaptive Evolutionary Algorithm, Metaheuristic, Multi-crossover, Genetic Algorithm, Combinatorial Optimization.

Full Text:

PDF


Disclaimer/Regarding indexing issue:

We have provided the online access of all issues and papers to the indexing agencies (as given on journal web site). It’s depend on indexing agencies when, how and what manner they can index or not. Hence, we like to inform that on the basis of earlier indexing, we can’t predict the today or future indexing policy of third party (i.e. indexing agencies) as they have right to discontinue any journal at any time without prior information to the journal. So, please neither sends any question nor expects any answer from us on the behalf of third party i.e. indexing agencies.Hence, we will not issue any certificate or letter for indexing issue. Our role is just to provide the online access to them. So we do properly this and one can visit indexing agencies website to get the authentic information.