Preventing Premature Convergence and Proving the Optimality in Evolutionary Algorithms

Vanaret, Charlie and Gotteland, Jean-Baptiste and Durand, Nicolas and Alliot, Jean-Marc

International Conference on Artificial Evolution (EA-2013-Bordeaux)

2013/10/21

----

Abstract:

Evolutionary Algorithms (EA) usually carry out an efficient exploration of the search-space, but get often trapped in local minima and do not prove the optimality of the solution. Interval-based techniques, on the other hand, yield a numerical proof of optimality of the solution. However, they may fail to converge within a reasonable time due to their inability to quickly compute a good approximation of the global minimum and their exponential complexity. The contribution of this paper is a hybrid algorithm called Charibde in which a particular EA, Differential Evolution, cooperates with a Branch and Bound algorithm endowed with interval propagation techniques. It prevents premature convergence toward local optima and outperforms both deterministic and stochastic existing approaches. We demonstrate its efficiency on a benchmark of highly multimodal problems, for which we provide previously unknown global minima and certification of optimality.

Keywords:

pdf PDF (439Kb)

BibTeX entry:

@InProceedings{ea13,
 title = {Preventing Premature Convergence and Proving the Optimality in
Evolutionary Algorithms},
 author = {Vanaret and Charlie and Gotteland and Jean-Baptiste and Durand and 
Nicolas and Alliot and Jean-Marc},
 BookTitle = { International Conference on Artificial Evolution (EA-2013-Bordeaux)},
 year = {2013}
}

[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive]