Opérateurs de variation généralisés pour les heuristiques de recherche aléatoire – VARIATION

Motivés par des travaux récents montrant un important potentiel inexploité dans la conception d'opérateurs de variation pour des heuristiques de recherche aléatoire, nous relevons le défi d'analyser la puissance et les limites de la généralisation de leur conception.

Les heuristiques de recherche aléatoire sont des algorithmes d'optimisation à usage général, conçus pour fournir de bonnes solutions aux problèmes qui ne peuvent être résolus par des approches exactes --- par exemple, parce que la qualité des solutions candidates ne peut être évaluée que par des simulations ou des expériences physiques ou parce que nous manquons le temps ou les connaissances nécessaires pour concevoir une solution adaptée au problème. De telles situations sont omniprésentes dans notre vie quotidienne, de sorte que de nombreux progrès scientifiques et industriels dépendent d'heuristiques de recherche efficaces.

Les opérateurs de variation sont un élément clé des heuristiques de recherche aléatoire. Ils déterminent comment de nouvelles solutions candidates sont générées à partir de celles précédemment évaluées. Les opérateurs de variation diffèrent dans la façon dont ils équilibrent le compromis entre les petits mouvements locaux avec une probabilité décente d'amélioration par rapport à la meilleure solution actuelle et un échantillonnage plus risqué à de plus grandes distances, dans l'espoir d'identifier des zones plus prometteuses de l'espace de recherche. Des travaux récents, en partie motivés par le PI, indiquent que les opérateurs de variation de pointe sont trop averses au risque, avec des effets graves sur les performances globales des heuristiques de recherche aléatoires.

L'objectif du projet VARIATION est d'identifier des opérateurs de variation optimaux avec des garanties de performances éprouvées. À cette fin, nous formulerons leur conception sous la forme d'un problème de méta-optimisation, que nous analyserons par une analyse algorithmique rigoureuse et des approches théoriques de la complexité. Nous utiliserons nos connaissances théoriques pour dériver des opérateurs de variation dont les gains de performance seront validés empiriquement sur divers ensembles de références communes d'optimisation et d'apprentissage automatique ainsi que sur des applications réelles de la biologie des systèmes et de l'industrie automobile.