CoBRA: A Coevolutionary Meta-heuristic for Bi-level Optimization

François Legillon (1) , Arnaud Liefooghe (1, 2) , El-Ghazali Talbi (1)

1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
2 LIFL - Laboratoire d'Informatique Fondamentale de Lille

This article presents CoBRA, a new parallel coevolutionary algorithm for bi-level optimization. CoBRA is based on a coevolutionary scheme to solve bi-level optimization problems. It handles population-based meta-heuristics on each level, each one cooperating with the other to provide solutions for the overall problem. Moreover, in order to evaluate the relevance of CoBRA against more classical approaches, a new performance assessment methodology, based on rationality, is introduced. An experimental analysis is conducted on a bi-level distribution planning problem, where multiple manufacturing plants deliver items to depots, and where a distribution company controls several depots and distributes items from depots to retailers. The experimental results reveal significant enhancements with respect to a more classical approach, based on a hierarchical scheme.

Cet article présente CoBRA, un nouvel algorithme paralléle et coévolutionnaire pour l'optimisation bi-niveau. CoBRA se base sur un modèle coévolutionnaire pour faire face aux problèmes d'optimisation bi-niveau. Il manipule une méta-heuristique à base de population sur chaque niveau, chacune coopérant avec l'autre de manière à garder une vue générale sur le problème complet. De plus, afin d'étudier la pertinence de CoBRA par rapport aux approches plus classique, une nouvelle méthodologie, basée sur la rationalité est introduite. Est conduite ensuite une étude expérimentale sur un problème bi-niveau de distribution-production, dans lequel des usines contrôlées par une entreprise produisent des marchandises pour des dépôts, et une autre entreprise contrôlant les dépôts se charge de livrer les marchandises à des clients. Cet article se conclut sur l'observation d'un réel gain de performance par rapport à une approche plus classique, basée sur un modèle hiérarchique.

Mots clés: Coevolutionary algorithms; bilevel optimization; algorithm design and implementation; parallel algorithm; vehicule routing problem

Domaines: Algorithme et structure de données [cs.DS]

François Legillon, Arnaud Liefooghe, El-Ghazali Talbi. CoBRA: A Coevolutionary Meta-heuristic for Bi-level Optimization. [Research Report] RR-7741, INRIA. 2011, pp.21. ⟨inria-00625744⟩