Abstract EN:

La sélection de valeurs adéquates pour les paramètres des algorithmes bio-inspirés est un processus crucial pour obtenir de bonnes performances. C’est un processus complexe étant donné que les valeurs des paramètres dépendent en général du problème que l’on cherche à résoudre. Il est de plus très coûteux en temps, et les paramètres ne sont pas complètement indépendants entre eux. La première contribution de cette thèse consiste en une étude comparative des caractéristiques et performances des différentes méthodes connues dans la littérature pour ajuster les paramètres, en analysant leurs avantages et leurs inconvénients. Le plus grand désavantage de ces méthodes est qu’elles sont très coûteuses en temps. Cependant, elles permettent d’obtenir de bonnes estimations pour les paramètres, en concentrant la recherche dans des régions statistiquement prometteuses. Nous présentons de plus une analyse du potentiel de ces techniques en tant qu’aide dans le processus de conception d’algorithmes évolutifs. Même si ces techniques aident à prendre des décisions quant à la conception de l’algorithme, elles ne sont pas capables d’éliminer de l’algorithme les éléments qui ne contribuent pas à son bon fonctionnement. La contribution principale de la thèse se situe sur la capacité de déterminer les valeurs des paramètres à la volée. Nous proposons deux nouvelles méthodes pour améliorer les performances des algorithmes évolutifs : Ac et Sac. Ac réalise un contrôle de la population dans lequel un opérateur reçoit une récompense en fonction de l’amélioration de performance issue de son application. Sac est quant à lui orienté à un contrôle individuel dans lequel le taux d’un opérateur qui correspond à un individu dépend de l’efficacité qu’a eue cet opérateur dans l’amélioration des générations précédentes. Ces deux méthodes peuvent être incorporées sans introduire un coût significatif, et sans changement important dans la conception d’origine de l’algorithme. Les décisions prises durant la recherche se basent ainsi sur les informations disponibles sur le comportement passé, à partir d’un processus permettant à l’algorithme d’effectuer des changements de valeurs de paramètres qu’il juge nécessaires. L’application de ces techniques a permis à l’algorithme d’éliminer des composants non nécessaires à sa recherche, grâce à une utilisation minimale de ceux-ci. Nous proposons également la stratégie (C,n)-strategy connue pour réaliser un contrôle dans l’algorithme immunitaire CLONAG, permettant de réduire en bonne partie le nombre de paramètres sur lesquels repose son exécution, ainsi que d’améliorer son comportement grâce à la modification à la volée du nombre de cellules sélectionnées pour le clonage, ainsi que le nombre de clones produits. Les techniques appliquées à l’algorithme évolutif, comme celle appliquée à l’algorithme immunitaire cherchent un équilibre entre l’exploration et l’exploitation de l’espace de recherche en utilisant les paramètres sélectionnés pour réaliser le contrôle. A partir du travail réalisé dans cette thèse, nous pouvons conclure que les techniques d’ajustement des paramètres permettent effectivement de trouver un ensemble de valeurs des paramètres qui offre une bonne performance de l’algorithme de recherche. Ces techniques demandent une analyse antérieure de la définition de l’espace de recherche pour les valeurs des paramètres, et requièrent de plus un temps d‘exécution considérable. Néanmoins, à partir des informations données par ces techniques d’ajustement, il est possible de prendre des décisions concernant la conception de l’algorithme que l’on veut ajuster. En ce qui concerne les techniques de contrôle de paramètres, nous pouvons conclure qu’elles permettent d’améliorer l’efficacité de l’algorithme et de réduire l’effort d’ajustement des paramètres car elles réduisent le nombre de paramètres à ajuster, qu’elles sont capables d’ajuster automatiquement les paramètres de l’algorithme sans modifier la conception d’origine de l’algorithme, et enfin, qu’elles ajoutent une quantité minime de paramètres additionnels à l’algorithme. Le développement de techniques capables de travailler avec n’importe quel type de paramètres demandant une définition de l’information d’entrée et qui soient capables de stopper à temps la recherche afin de ne pas perdre de ressources, reste un terme de recherche ouvert. Nous avons montré dans cette thèse qu’il est possible de réaliser un contrôle à la volée des paramètres des algorithmes basés sur des populations. Une perspective de recherche intéressante consiste à arriver à automatiser l’identification du rôle des composants de l’algorithme afin de pouvoir concevoir automatiquement les stratégies de contrôle.