Algorithmes génétiques |
19 Avril 2006 |
Applications croisée entre l'informatique et la biologie (bio-informatique au sens large). En plus de la série d'articles sur la bio-informatique : Les algorithmes génétiques.
Ces algorithmes sont utilisés afin d'avoir des systèmes de recherche plus performants que les programmes traditionnels. Ces derniers n'étant pas très adaptables à tout type de recherche (sauf à y passer beaucoup plus de temps de recherche d'algorithmes et optimisation du code et aussi beaucoup de temps de calcul). Ce type d'heuristique (ou métaheuristique) est utilisé pour répondre en un temps correct à un problème donné.
Le but est de trouver la (ou les) meilleure(s) solution(s) à un problème donné grâce à un programme informatique sans que ce dernier ne les contienne explicitement. En d'autres termes, le programme génère une population «d'individus» qui sont autant de solutions potentielles pour le problème. Chaque individu étant codé pour le problème : le chemin pour sortir d'un labyrinthe ou autre application plus sérieuse...
Ensuite ces individus sont classés selon leur capacité à résoudre le problème, ceux en tête de liste seront favorisés (on les duplique au sein de la population) tandis que les derniers disparaissent. Au fil des générations,et de quelques «mutations» (modification aléatoire de leur code), les individus sont ainsi sélectionnés selon leur aptitude à être une (ou de) bonne(s) solution(s). Le problème est ainsi résolu...
Tant que l'on considère les ordinateurs comme des machines à qui l'on confie des suites d'opérations, que l'on a définies dans les moindres détails alors ils ne pourront nous surprendre. Une des voies pour dépasser l'ordinateur exécutant est l'algorithme génétique. Il possède deux qualités essentielles : les bonnes solutions qu'il obtient n'ont pas été fournies par le programmeur de façon explicite, mais ont été découvertes par l'algorithme. Il peut être en principe être appliqué à une classe assez large de problèmes, car son fonctionnement dépend peu du problème posé.
A chaque instant, un algorithme génétique garde en mémoire une population d'individus.Ces individus sont des solutions du problème posé. Au début ce sont de bien piètres solutions. Généralement, ils ont été tirés au hasard lors du début du processus. Mais comme dans la nature, l'important n'est pas d'être une bonne solution dans l'absolu, c'est d'être moins mauvais que les autres. Ces solutions sont essayées, les meilleurs se reproduisent entre elles à la manière des êtres vivants, par croisements génétiques. Les nouvelles solutions obtenues sont essayées, et ainsi de suite jusqu'à ce que de bonnes solutions soient découvertes.
Le principe de l'évolution par sélection naturelle n'est pas la seule caractéristique empruntée à l'idée de nature, bien que leur génome ne soit pas fait de molécule d'ADN, mais d'une succession d'instruction au sein d'un programme, d'un code source, du problème exprimé en une chaine de caractères ou plus basiquement d'un assemblage binaire (suite de 0 et de 1). Ce génome définit une tentative de solution «viable». En plus de la sélection, on utilise aussi avec les algorithmes génétiques le phénomène de recombinaison (ou crossing-over) et de mutation.
Pour son fonctionnement, l'algorithme nécessite un codage des paramètres du problème (suite d'instructions, suite de caractères alphanumériques...). Il est ensuite attribué une valeur à chaque individu de la population de départ. Par la suite, lors du déroulement de l'algorithme, chaque individu est évalué et noté par rapport aux autres, puis classé. Les individus les plus hauts classés sont réutilisés et reproduits (indépendamment du rang obtenu) pour l'étape suivante et ainsi de suite. La reproduction des individus peut être simple (copie) ou un croisement entre plusieurs individus, à la mutation (changement) appliquée près dans leur contenu (ceci permet l'apparition de nouvelles solutions potentiellement meilleures).
Quelques techniques utilisées pour la sélection des individus et l'arrivée vers les meilleurs résultats et solutions au problème : sélection par rang, par proportion à l'adaptation, par tournoi ou par probabilité sélection uniforme). Les applications des algorithmes génétiques sont multiples : recherche (exemple du voyageur de commerce), industrie (test des modifications logicielles), ou décision (à partir de données statistiques en modifiant telle ou telle donnée).
@+
Gaby
Publié dans la catégorie : Biologie
|
