DeepMeta project 2023 - 2024

Project leader: Olivier Goudet
Funding: Etoiles Montantes en Pays de la Loire
Region Pays de la Loire

Proposition

Combinatorial optimization involves finding the best solution from a finite, but very large, set of possible configurations. It is a branch of discrete mathematics and computer science with applications in many fields, including economics, logistics, energy and health.

Over the last ten years or so, LERIA (Laboratoire d'Etude et de Recherche en Informatique d'Angers) has been engaged in new exploratory work, breaking with conventional approaches to solving combinatorial optimization problems. A new generation of methods involving machine learning techniques has been proposed. The general aim of these methods is to make solving algorithms more autonomous, so that they can adapt in real time to the problem at hand. This work has produced promising results, and has already led to the publication of reference articles, notably on dynamic island models, pattern extraction in solutions and the development of reinforcement learning methods for graph coloring problems.

The aim of this project is to continue along this path, and this time to develop solution methods for combinatorial problems based on deep neural networks, in the same way as the spectacular advances made in recent years for combinatorial games such as go or chess with the AlphaZero algorithm. Very recent work has already proposed applying such deep learning methods to solve combinatorial optimization problems, such as travelling salesman or graph coloring problems. Nevertheless, these works exploit little or no specific knowledge of the problem, which greatly limits the interest and performance of these approaches. In fact, the results obtained by this type of method are currently a long way from the state-of-the-art results obtained mainly by memetic algorithms and simulated annealing algorithms.

The aim of this project is to develop a hybrid approach that combines deep neural networks with the best tools of "classical" metaheuristics in order to solve combinatorial optimization problems that are still resistant to today's best methods.

Recruitment

Mohamed Salim Amri Sakhri. 18-month postoc contract starting Jul. 2023.

Publications supported by the funding granted

Journal papers

  1. A Large Population Island Framework for the Unconstrained Binary Quadratic Problem (O Goudet, A Goëffon, JK Hao). 2024. Computers and Operations Research. Source Code .

Conference papers

  1. Emergence of Strategies for Univariate Estimation-of-Distribution Algorithms with Evolved Neural Networks (O. Goudet, A. Goëffon, F. Saubion, S. Verel). 2024. Proceedings of the Companion Conference on Genetic and Evolutionary Computation.
  2. Emergence of new local search algorithms with neuro-evolution (O. Goudet, M. S. Amri Sakhri, A. Goëffon, F. Saubion). 2024. Proceeding of the European Conference on Evolutionary Computation in Combinatorial Optimization (Part of EvoStar). Aberystwyth, United Kingdom. Source Code
  3. A memetic algorithm with adaptive operator selection for graph coloring (C. Grelier, O. Goudet, J-K Hao). 2024. Proceeding of the European Conference on Evolutionary Computation in Combinatorial Optimization (Part of EvoStar). Aberystwyth, United Kingdom. Source Code
  4. New Bounds and Constraint Programming Models for the Weighted Vertex Coloring Problem (O. Goudet, C. Grelier, D. Lesaint). 2023. IJCAI. Proceeding of the 32nd International Joint Conference on Artificial Intelligence. Source Code
  5. Monte Carlo Tree Search with Adaptive Simulation: A Case Study on Weighted Vertex Coloring (C. Grelier, O. Goudet, J-K Hao). 2023. Proceeding of the European Conference on Evolutionary Computation in Combinatorial Optimization (Part of EvoStar). Springer, Cham. Brno, Czech Republic. Source Code

Project-funded conference presentation

International talks

  1. Gecco. July 2024. Melbourne.
    • Talk: "Emergence of Strategies for Univariate Estimation-of-Distribution Algorithms with Evolved Neural Networks". Speaker: Olivier Goudet
  2. EvoStar. April 2024.. Aberystwyth, United Kingdom.
    • Talk: "Emergence of new local search algorithms with neuro-evolution". Speaker: Olivier Goudet
    • Talk: "A memetic algorithm with adaptive operator selection for graph coloring". Speaker: Cyril Grelier
  3. EvoStar. April 2023.. Brno, Czech Republic.
    • Talk: "Monte Carlo Tree Search with Adaptive Simulation: A Case Study on Weighted Vertex Coloring". Speaker: Cyril Grelier

National talks

  1. ROADEF. March 2024. 25ème édition du congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision. Amiens, France.
    • Talk: Étude de l'émergence de nouveaux algorithmes de recherche locale par neuro-évolution. Speaker: Olivier Goudet.
    • Talk: Algorithme mémétique avec sélection automatique d'opérateurs pour la coloration de graphe. Speaker: Cyril Grelier.
  2. PFIA. July 2023.. Strasbourg, France. Session FR@International. Talk: new Bounds and Constraint Programming Models for the Weighted Vertex Coloring Problem. Speaker: Olivier Goudet
  3. ROADEF. March 2023. 24ème édition du congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision. Rennes, France.