Les algorithmes génétiques: présentation et exemples

Thèmes abordés

Les algorithmes génétiques, génotypes, Un gène, Une génération, Fonction de fitness, population initiale, mutation, Chromosomes, bits, nouvelle population, séléction

Résumé du document

Les algorithmes génétiques sont des systèmes qui s'appuient sur les principes de sélection de Darwin et sur les méthodes de combinaison des gènes introduites par Mendel pour traiter des problèmes d'optimisation.
Les algorithmes génétiques fournissent des solutions aux problèmes n'ayant pas de solutions calculables en temps raisonnable de façon analytique ou algorithmique.

Extraits

[...] 6-Croisement 5-Sélection 8-Evaluation . 7-Mutation 9-remplacement 1-Sélection 2-Codage 5-Evaluation 3-Croisement 4-Mutation 6-remplacement Donc pour la création de la génération suivante il faut qu'on réitère les opérations précédentes jusqu'à ce qu'un critère d'arrêt soit satisfait. Différents critères d'arrêt de l'algorithme peuvent être choisis : nombre de générations fixé, limite de convergence de la population, population qui n'évolue plus suffisamment, etc. 6-Croisement 5-Sélection 8-Evaluation . 7-Mutation 9-remplacement Cet opérateur est le plus simple, son travail consiste à réintroduire les descendants obtenus par application successive des opérateurs de sélection, de croisement et de mutation la population de leurs parents On trouve essentiellement 2 méthodes de remplacement différentes : Le remplacement stationnaire. [...]

[...] Le croisement, qui symbolise la reproduction, est une des étapes importantes de l'A.G. C'est l'instrument majeur des innovations au sein de l'algorithme, c'est lui qui engendre le changement. Il peut être effectué de plusieurs manières mais la plus courante croise les chaines de caractères de deux individus parents pour former des chaines de caractère enfants. 6-Croisement 5-Sélection 8-Evaluation . 7-Mutation 9-remplacement Il faut maintenant assurer la survie de l'espèce et de renouveler la population. Choisir certains éléments parmi les individus sélectionnés précédemment et les faire se reproduire en utilisant l'opérateur de croisement. [...]

[...] Forme d'un algorithme génétique: Initialiser la population initiale P. Evaluer P. TantQue (Pas Convergence) faire : P ' = Sélection des Parents dans P P ' = Appliquer Opérateur de Croisement sur P ' P ' = Appliquer Opérateur de Mutation sur P ' P = Remplacer les Anciens de P par leurs Descendants de P ' Evaluer P FinTantQue déroulement d'un algorithme génétique : Population Initiale Evaluation des individus Sélection Croisements Mutations Evaluation des individus Nouvelle population Insertion dans la population Nouvelle itération La première étape d'un algorithme génétique consiste sur la création de la population initiale qui sera la base de l'algorithme. [...]

[...] certains individus subissent des modifications de leur ADN, certains disparaissent . Un algorithme génétique va reproduire ce modèle d'évolution dans le but de trouver des solutions pour un problème donné Les algorithmes génétiques sont des systèmes qui s'appuient sur les principes de sélection de Darwin et sur les méthodes de combinaison des gènes introduites par Mendel pour traiter des problèmes d'optimisation. Un AG va faire évoluer une population dans le but d'en améliorer les individus Et c'est donc, à chaque génération, un ensemble d'individus qui sera mis en avant et non un individu particulier. [...]

[...] Résultats de croisement et mutation: On peut dire alors que les opérateurs de l'algorithme génétique nous ont permit d'améliorer la population initiale. Donc Exemple de base : Les problèmes de l'algorithme génétique : le codage: L'un des problèmes les plus importants est le codage des données : C'est difficile de trouvée un bon codage adaptée à la structure du problème. L'application de la fonction de décodage lords l'évaluation de la fitness est coûteuse en temps de calcul. La dominance : La domination d'un chromosome provoque la disparition rapide de certains élément de la population. [...]