Remerciez-le!

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

Methodes d x27 oprtimisation algorithme genetiques exercice corrige tsp

Méta heuristique Algorithme Génétique Présenté par Me Derkaoui Orkia Université Docteur Moulay TAHAR de Saida derkaouiorkia gmail com CPlan ? Aperçu globale sur Algorithme Génétique AG ? Exemple illustratif Application de l ? AG au Problème du voyageur de commerce TSP CL ? Algorithme Génétique est une Métaheuristique basée sur une approche à population Les métaheuristiques utilisent deux approches principales pour résoudre un problème ? La première est nommée approche à population Elle désigne les algorithmes qui traitent plusieurs solutions à la fois Elles maintiennent et améliorent plusieurs solutions candidates en même temps Algorithme Génétique AG Algorithme de fourmis ACO Optimisation par Essaim Particulaire PSO etc ? La seconde est nommée approche de trajectoire Elle représente les algorithmes qui font évoluer une fonction objectif unique à chaque itération La stratégie est basée sur la recherche locale Recherche Tabou RT Recuit Simulé RS etc ? CILLUSTRATION GRAPHIQUE Techniques de recherche des métaheuristiques ?gure empruntée à CLes Algorithme Génétiques ? L ? idée d ? un algorithme génétique est déduite de de la théorie darwinienne de l ? évolution ? L ? algorithme utilise la notion de sélection naturelle sur une population de solutions potentielles ? Chaque groupe d ? individus appelé aussi population donne lieu à une nouvelle génération par reproduction ? Cette population subit une sélection métaphore de la sélection naturelle seuls les individus les mieux adaptés à l ? environnement survivent ? Cette génération consiste à croiser les individus entre eux pour donner des descendants possédant les caractères des deux parents ? En plus de ce croisement des mutations de caractères interviennent aléatoirement dans la génération de la population suivante ? En ?n à son tour cette population donnera lieu par le même processus à une CFormalisme ? Les individus sont représentés par des chromosomes chromosome cha? ne d ? informations sur un alphabet ?ni des cha? nes d'ADN ? L'élément de base des chromosomes est un gène ? La position d'un gène sur le chromosome est son locus ? L'ensemble des gènes d'un individu est son génotype ? L ? ensemble du patrimoine génétique d'une espèce est le génome ? Les di ?érentes versions d'un même gène sont appelées allèles CCodage ? Pour les algorithmes génétiques un des facteurs les plus importants est la façon dont sont codées les solutions chromosomes c'est-à- dire les structures de données qui coderont les gènes ? Il faut trouver une manière de coder chaque allèle di ?érent de façon unique ? Un principe de codage de l ? élément de population Après la modélisation mathématique du problème traité Cette étape associe à chacun des points de l ? espace d ? état une structure de données ? Le codage des données conditionne le succès des algorithmes génétiques CTypes de Codage Codage Binaire Son principe est de coder la solution selon une cha? ne de bits et le plus utilisé proche du réel Codage réel il y ? a des cas ou le codage binaire n ? est pas possible Chaque chromosome est