Théorie de l'heuristique d'optimisation itérative: de la complexité de la boîte noire à la conception d'algorithmes au contrôle des paramètres

Les heuristiques d’optimisation fond ́ees sur l’ ́echantillonnage sont des algorithmes qui visent `a trouver de bonnes solutions aux probl`emes ne pouvant pas ˆetre r ́esolus par des strat ́egies de solution ex- actes. Elles sont particuli`erement utiles pour l’optimisation de probl`emes qui ne sont pas d ́ecrites par des formules closes explicites, mais qui n ́ecessitent des simulations informatiques ou des exp ́eriences physiques pour ́evaluer la qualit ́e d’une solution propos ́ee. Dans de tels contextes, les heuristiques d’optimisation fond ́ees sur l’ ́echantillonnage sont essentiellement le seul moyen d’obtenir de bonnes so- lutions. Une autre application importante des heuristiques d’optimisation fond ́ees sur l’ ́echantillonnage est l’optimisation des probl`emes qui sont trop complexes pour ˆetre r ́esolus de mani`ere analytique et qui qui n’admettent pas des des algorithmes sp ́ecifiques. Une sous-classe importante d’heuristiques d’optimisation fond ́ees sur l’ ́echantillonnage sont les heuris- tiques d’optimisation it ́erative (I.O.H.). Les IOH cherchent `a trouver de bonnes solutions par un processus s ́equentiel d’ ́evaluation de solutions candidates, en utilisant les informations obtenues pour ajuster la strat ́egie par laquelle les candidates suivants sont produites, et en it ́erant ce processus jusqu’`a ce qu’un crit`ere de terminaison soit satisfait. Avec mes recherches, je mefforce de contribuer `a notre compr ́ehension des principes op ́erationnels qui d ́eterminent la performance des IOH. Plus pr ́ecis ́ement, je cherche `a comprendre quelles strat ́egies fonctionnent bien pour quels types de probl`emes. Pour cela, j’ ́etudie l’efficacit ́e des IOH existants, et je compare ces performances `a celle d’un meilleur solveur possible pour le probl`eme donn ́e. Pour ces derniers, je d ́eveloppe et analyse des mod`eles de complexit ́e qui permettent de quantifier l’influence de certains choix algorithmiques, comme la taille de la m ́emoire utilis ́ee, la strat ́egie par laquelle les solutions peuvent ˆetre ́echantillonn ́ees, le type d’informations utilis ́ees pour s ́electionner les prochaines strat ́egies d’ ́echantillonnage, etc. Ce manuscrit r ́esume certains de mes r ́esultats de recherche obtenus au cours des neuf derni`eres ann ́ees, depuis la fin de mes ́etudes de doctorat. Nous d ́erivons d’abord des bornes am ́elior ́ees (et souvent serr ́ees) pour la complexit ́e en boˆıte noire des deux probl`emes de r ́ef ́erence les plus connus dans la th ́eorie des IOH : OneMax et LeadingOnes, et ce pour divers mod`eles en boˆıte noire. Nous d ́emontrons ensuite comment les informations obtenues `a partir de ces ́etudes de complexit ́e en boˆıte noire peuvent inspirer la conception de techniques d’optimisation efficaces. Un r ́esultat important obtenu grˆace `a cette approche est un exemple rigoureux de situation dans laquelle un choix non statique des param`etres de contrˆole d’une IOH produit un gain de performance super-constant par rapport `a tous les r ́eglages de param`etre statique possibles. Ce r ́esultat a relanc ́e la recherche th ́eorique sur le contrˆole des param`etres, qui a connu des avanc ́ees significatives depuis. Nous discutons quelques exemples dans ce manuscrit. Nous concluons en discutant le rˆole du benchmarking d’algorithmes comme pont entre la recherche th ́eorique et empirique des IOH.

4 Doctorants (Direction de recherche / Co-encadrement)

• CLÉMENT François : Algorithmes efficaces pour la sélection de sous-ensembles à faible discrépance
• FOURQUET Océane : Modèles intégratifs pour un système d'aide à la décision dans le traitement du cancer de l'ovaire
• SANTARELLI Mara : Resistant subpopulations in ovarian cancer: Computational tools for their identification and treat-ment selection in clinical data using single-cell technology
• SANTONI Maria Laura : Black-Box Optimization Benchmarking on Real-World Industrial Applications

3 Docteurs 2018 - 2022