Séminaire (organisé par l’équipe de recherche RO)

Dang DUC-CUONG

Chercheur, Université de Nottingham


Complexité temporelle des algorithmes évolutionnaires


Vendredi 26 septembre 2014 à 15 h 30 en salle A212

Résumé :

Inspirés du processus de l’évolution naturelle, les Algorithmes Évolutionnaires (Evolutionary Algorithms, EA) sont très connus pour leur capacité générique à résoudre des problèmes d’optimisation difficiles dans plusieurs domaines, notamment en Recherche Opérationnelle. Ce séminaire introduit les méthodologies permettant de prouver la complexité en moyenne des EAs et plus généralement les recherches heuristiques randomisées dans un espace de recherche discret. La première partie de la présentation se consacre à des configurations simples pour introduire les méthodes fondamentales permettant le calcul de la complexité, notamment l’approche se basant sur la partition de l’espace de recherche et sur les probabilités de transition (Fitness-level Technique) et l’approche des martingales (Drift Analysis). Dans la deuxième partie, nous présentons notre méthode développée pour prouver la complexité temporelle des EAs qui emploient des populations non-élitistes. Nous discutons l’usage de ce nouvel outil sur des configurations complexes, plus précisément l’optimisation en présence d’aléas. Un résultat surprenant est qu’il n’est pas nécessaire pour les EAs de connaître exactement la valeur de la fonction objectif à chaque évaluation d’une solution pour pouvoir optimiser la fonction. Autrement dit, avec les populations, les EAs deviennent très robustes face aux événements incertains. A la fin du séminaire, nous discutons la généralisation de la méthode permettant d’analyser rigoureusement des processus évolutionnaires plus complexes, incluant ceux engendrés par l’Algorithme Génétique (Genetic Algorithm, GA) et l’Algorithme à Estimation de Distribution (Estimation Distribution Algorithm, EDA).



Actualités
Vidéothèque
Téléchargements
Annuaire



FR SHIC 3272

Collegium UTC/CNRS