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.