Apprentissage automatique pour la conception des opérateurs de reproduction dans un algorithme génétique

Les différentes industries mettent en place des processus complexes pour mener à bien leurs tâches. Par exemple, un service de livraison doit planifier les routes de ses différents livreurs, le réapprovisionnement de ses stocks, etc. Dans ce cadre, l’optimisation de ces processus est primordiale, car un gain de productivité de quelques pourcents peut avoir un impact économique, écologique ou sur le confort des employés important. Dans le du cas problème de tournées de véhicules avec capacités, la méthode à l’état de l’art actuelle est basée sur une recherche génétique hybride. Tout d’abord, un algorithme génétique maintient une population de solutions et croise les meilleurs individus afin de générer de nouveaux individus à ajouter à la population. Ensuite, une recherche locale est appliquée sur la solution nouvellement générée et l’améliore en effectuant des mouvements locaux. Cette méthode permet d’obtenir des solutions optimales pour des problèmes avec moins de 300 clients, mais peine à trouver la solution optimale pour des problèmes plus grands malgré une exécution de plusieurs dizaines de minutes. Elle donne néanmoins des solutions avec un écart à l’optimalité faible. Dans cette méthode, la sélection des parents à croiser et la façon de les croiser sont presque entièrement aléatoires. L’objectif de ce travail est d’ajouter une vision globale de la population dans la génération du nouvel enfant pour s’assurer qu’il apporte un génome permettant une convergence vers une bonne solution et rapidement. En sélectionnant les enfants sur un critère de diversité et de coût, on observe une convergence bien plus rapide en termes de nombre d’itérations vers des optimums non atteints auparavant. Cependant pour permettre de sélectionner cet enfant, il faut générer pour un couple donné tous les enfants possibles et leur appliquer une recherche locale ce qui augmente le temps d’exécution de manière quadratique. Ainsi, la seconde partie de ce projet a été de prédire pour un couple donné la manière de générer ce meilleur enfant en utilisant de l’apprentissage machine afin de ne pas avoir à générer tous les enfants du couple. Nos résultats montrent que nous avons été capables d’apprendre à un réseau de neurones sur graphes à déterminer le meilleur enfant selon un critère dépendant de sa diversité par rapport à la population et de son coût. Cependant, le critère que nous avons choisi intensifie trop et amène la population rapidement converger vers une solution. Ainsi, notre critère permet d’obtenir une meilleure solution pour un même nombre restreint d’itérations, mais sous-performe lorsque plus d’itérations sont effectuées. Elle peut donc être utile en début de recherche pour rapidement trouver une bonne solution.

Abstract

Different industries implement complex processes to accomplish their tasks. For example, a delivery service must plan the routes for its various drivers, manage its inventory, etc. In this context, optimizing these operations is crucial, as even a small productivity gain can have a significant economic, ecological, or employee comfort impact. In the case of the capacitated vehicle routing problem, the current state-of-the-art method is based on a hybrid genetic search. First, a genetic algorithm maintains a population of solutions and combines the best individuals to generate new ones to add to the population. Then, a local search is applied to the newly generated solution, improving it by making local moves. This method achieves optimal solutions for problems with fewer than 300 clients but struggles to find the optimal solution for larger problems, even with execution times of one hour. However, it still provides solutions with a small deviation from optimality. In this method, the selection of parents to combine and the way they are combined are almost entirely random. The objective of this work is to add a global view of the population in the generation of the new child to ensure it gives a genome leading to a faster convergence to good solutions. to a good solution quickly. By selecting children based on a diversity and a cost criteria, we observe a faster convergence in terms of the number of iterations towards previously unattained optima. However, to select this child, it is necessary to generate all possible children for a given couple and apply a local search to them, which increases the execution time quadratically. Therefore, the second part of this project was to predict the best way to generate this child for a given couple using machine learning to avoid generating all the children of the couple. Our results show that we are able to train a graph neural network to determine the best child based on a criterion dependent on its diversity relative to the population and its cost. However, the criterion we chose intensifies too much and causes the population to converge quickly to a solution. Thus, our criterion allows for finding a better solution in a limited number of iterations but underperforms when more iterations are carried out. It can, therefore, be useful at the beginning of the search to quickly find a good solution