algorithmes génétique

Introduction
Parmi tous les types d'algorithmes existants, certains ont la particularité de s'inspirer de l'évolution des espèces dans leur cadre naturel. Ce sont les algorithmes génétiques. Les espèces s'adaptent à leur cadre de vie qui peut évoluer, les individus de chaque espèce se reproduisent, créant ainsi de nouveaux individus, certains 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é. Il sera fait usage dans ce cours de termes empruntés au monde des biologistes et des généticiens et ceci afin de mieux représenter chacun des concepts abordés :


•Dans notre cas, une population sera un ensemble d'individus.
•Un individu sera une réponse à un problème donné, qu'elle soit ou non une solution valide du problème.
•Un gène sera une partie d'une réponse au problème, donc d'un individu.
•Une génération est une itération de notre algorithme.
Un algorithme génétique 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. Nous obtiendrons donc un ensemble de solutions pour un problème et pas une solution unique. Les solutions trouvées seront généralement différentes, mais seront d'une qualité équivalente. Nous reviendrons sur cette notion de qualité des solutions dans la partie 2.


Le déroulement d'un algorithme génétique peut être découpé en cinq parties :


1.La création de la population initiale
2.L'évaluation des individus
3.La création de nouveaux individus
4.L'insertion des nouveaux individus dans la population
5.Réitération du processus
Pour illustrer ce tutoriel, je montrerai comment appliquer un algorithme génétique au problème bien connu de "l'informaticien en vacances", inspiré du problème du voyageur de commerce. L'informaticien en vacances doit visiter plusieurs villes durant ses vacances : { A,B,C,D,E,F,G,H,I,J }. Il cherche donc le chemin le plus court pour passer par chacune d'elles. Il souhaite également assister à un maximum de festivals musicaux (ayant lieu dans les villes A,B et C). Il s'agit donc d'un problème bi-critères (la distance entre les villes à minimiser et le nombre de festivals auxquels il pourra assister à maximiser). Chaque festival a lieu à une date donnée. Nous connaissons aussi les distances entre toutes les villes.