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).

Seminars


Mardi 10 mai 2016

Séminaire à 14 h 30 en GI042 présenté par Christophe DENIS, Chargé de Formation et de Recherche au Centre de mathématiques et de leurs applications (CMLA), ENS Cachan. « Verificarlo : checking the floating point accuracy of scientific codes »


Lundi 14 mars 2016

Séminaire à 9 h en GI042, présenté par Ahcène Bounceur, Maître de conférence, HDR, à l’Université de Bretagne Occidentale (UBO). « CupCarbon : A New Platform for Simulating Smart Wireless Sensor Networks (SWSN) »


Mardi 9 février 2016

Séminaire à 14 h en GI042 présenté par Fabio D’Andreagiovanni, Chercheur senior et Directeur de projet au département d’optimisation de Zuse Institute Berlin (ZIB), Berlin (Allemagne). « Multiband Robust Optimization : theory and applications »


Jeudi 28 janvier 2016

Séminaire à 15 h 30 en GI042 présenté par Said Tabli, stagiaire au sein du laboratoire Heudiasyc. « Trust Management in Clustered Wireless Sensor Networks »


Pages 1 | 2 | 3 | 4 | 5 | 6 | 7




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



FR SHIC 3272

Collegium UTC/CNRS