Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours 4 1 Gloutons EDA Ant Colony Optimization ACO Car sequencing ACO Subset selection Cours de Master Recherche Spe ? cialite ? CODE Re ? solution de proble mes combinatoires Christine Solnon LIRIS UMR CNRS Universite ? Lyon CGloutons EDA Ant Colony Opti

Gloutons EDA Ant Colony Optimization ACO Car sequencing ACO Subset selection Cours de Master Recherche Spe ? cialite ? CODE Re ? solution de proble mes combinatoires Christine Solnon LIRIS UMR CNRS Universite ? Lyon CGloutons EDA Ant Colony Optimization Rappel du plan du cours ACO Car sequencing ACO Subset selection - Introduction Qu ? est-ce qu ? un probleme complexe Exemples de proble mes complexes - Approches completes Structuration de l ? espace de recherche en Arbre Structuration de l ? espace de recherche en Treillis - Approches incomple tes base ? es sur les instances Recherche locale Algorithmes ge ? ne ? tiques - Approches incompletes base ? es sur les mode les Algorithmes gloutons ale ? atoires Algorithmes par estimation de distribution EDA Optimisation par colonies de fourmis ACO CGloutons EDA Ant Colony Optimization ACO Car sequencing Approches base ? es sur les mode les ACO Subset selection Principe ge ? ne ? ral Approches constructives constructions incre ? mentales de combinaisons Utilisation d ? un ??modele ? heuristique de choix du composant a ajouter Modeles statiques vs dynamiques Mode les statiques Algorithmes gloutons ale ? atoires Modeles dynamiques modi ?er le mode le expe ? rience passe ? e Algorithmes par estimation de distribution statistiques sur les expe ? riences passe ? es Algorithmes a base de colonies de fourmis expe ? rience passe ? e compile ? e sous forme de phe ? romone CGloutons EDA Ant Colony Optimization ACO Car sequencing Approches base ? es sur les mode les ACO Subset selection Principe ge ? ne ? ral Approches constructives constructions incre ? mentales de combinaisons Utilisation d ? un ??modele ? heuristique de choix du composant a ajouter Modeles statiques vs dynamiques Mode les statiques Algorithmes gloutons ale ? atoires Modeles dynamiques modi ?er le mode le expe ? rience passe ? e Algorithmes par estimation de distribution statistiques sur les expe ? riences passe ? es Algorithmes a base de colonies de fourmis expe ? rience passe ? e compile ? e sous forme de phe ? romone CGloutons EDA Ant Colony Optimization ACO Car sequencing ACO Subset selection Principe ge ? ne ? ral des algorithmes gloutons Construction incre ? mentale d ? une combinaison e ?? E e combinaison vide Cand ensemble des composants de combinaisons tant que Cand ? faire Choisir le meilleur composant de Cand et l ? ajouter ae Heuristique de choix gloutonne Mettre a jour l ? ensemble Cand des composants pouvant e tre ajoute ? s ae Retourner e Pour certains proble mes algorithme optimal Simplex proble mes line ? aires Dijkstra plus court chemin CGloutons EDA Ant Colony Optimization ACO Car sequencing ACO Subset selection Comment concevoir un algorithme glouton Soit un probleme d ? optimisation E f E ensemble des combinaisons candidates f fonction objectif a maximiser points ade ? ?nir Identi ?er les composants des combinaisons De ? ?nir une fonction mettant a jour l ? ensemble des candidats par rapport aune