the new scientific reference

Algorithmes génétiques : entre informatique et nature8 minutes de lecture

A

[et_pb_section bb_built= »1″ admin_label= »Section » fullwidth= »off » specialty= »off » transparent_background= »off » background_color= »#e5e5e5″ allow_player_pause= »off » inner_shadow= »off » parallax= »off » parallax_method= »on » make_fullwidth= »off » use_custom_width= »off » width_unit= »on » make_equal= »off » use_custom_gutter= »off »][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Introduction » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

[dropcap]V[/dropcap]ous avez sans doute déjà tous entendu parler de la sélection naturelle, l’un des principaux mécanisme de l’évolution des espèces. C’est grâce à ce phénomène que les espèces ont su s’adapter à leur environnement au cours de l’évolution. Il repose sur un postulat de base très simple : seuls les individus les mieux adaptés et présentant un ou des caractère(s) avantageux auront une descendance plus importante que les autres.

C’est ce principe qui est utilisé en informatique pour la résolution de problèmes complexes : on a alors recours à un algorithme génétique.

[/et_pb_text][/et_pb_column][/et_pb_row][/et_pb_section][et_pb_section bb_built= »1″ admin_label= »section »][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Origines » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Origines

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »row »][et_pb_column type= »4_4″][et_pb_text admin_label= »Texte » background_layout= »light » text_orientation= »left » text_text_color= »#1c0000″ use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Le principe de l’algorithme génétique a pour la première fois été étudié et exploité dans les années 1960 par John Holland et ses collègues à l’Universite du Michigan. 1

Ce concept a, depuis les années 1990, été largement popularisé et repris dans de nombreux ouvrages tel que le très réputé Intelligence Artificielle et Informatique Théorique 2. Il connaît un succès grandissant au fur et à mesure des années grâce à sa relative simplicité de mise en place et sa puissance lorsqu’il est parfaitement optimisé.

En outre, de tels algorithmes peuvent tout à fait tourner sur les ordinateurs grand public actuels, ce qui explique en partie leur démocratisation.

 

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Notions préliminaires » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Notions préliminaires

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Texte » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Un algorithme génétique repose sur les principales notions suivantes directement issues de la génétique :
– Génération : il s’agit d’un ensemble d’individus étant tous le résultat d’une « reproduction » à l’instant t
– Reproduction : il s’agit de la création de nouveaux individus à partir des individus actuels
– Individu : dans le cas de l’algorithme génétique, il s’agit d’un état du système avec ses propriétés propres (gènes)
– Gène : correspond à une variable du système qui peut prendre différentes valeurs (allèle)
– Allèle : correspond à une valeur spécifique d’un gène
– Mutation : modification d’un allèle de manière aléatoire.

 

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Principe » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Principe

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Texte » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Son principe est relativement simple : il est, comme tout algorithme itératif, constitué d’une initialisation, d’une exécution et d’une condition d’arrêt.

 

Etape 1 : Initialisation

Cette étape est essentielle : son rôle est de générer un nombre suffisant d’individus de manière totalement aléatoire afin d’avoir une grande diversité au début. Le codage de l’individu est généralement une suite binaire mais il peut tout aussi bien être une suite de caractères ASCII par exemple. Chaque bit ou groupe de bit correspond au codage d’un allèle. Ce groupe d’individus constitue la génération 0.

Etape 2 : Exécution

L’exécution est généralement une boucle qui exécute, dans l’ordre, les opérations suivantes :

– La Sélection : Cette étape est l’étape essentielle à tout algorithme génétique. C’est elle qui va définir l’efficacité de l’algorithme. Elle consiste généralement en une fonction d’estimation qui va retourner un « score » à un individu donné en fonction de ses caractères. A la fin de cette étape, elle choisi un nombre donné d’individus (les parents) qui ont le score le plus haut et supprime les autres.

– La Reproduction : Cette étape consiste à créer la génération suivante (les enfants) à partir des individus qui auront été sélectionnés préalablement. La création des nouveaux individus repose sur deux facteurs : le croisement entre deux parents voir plus (créer un enfant à partir de la moitié des allèles du père et la moitié des allèles de la mère par exemple). Le hasard dans le croisement de gènes est bien sur nécessaire pour éviter une convergence trop rapide vers une solution locale. Le deuxième mécanisme en jeu est la mutation (à utiliser avec parcimonie) qui consiste à modifier sur très peu d’enfants un bit au hasard. Elle est nécessaire pour permettre d’élargir le champs de convergence afin, encore, d’éviter une convergence vers un optimum local.

Etape 3 : Arrêt

La condition d’arrêt constitue généralement un seuil à dépasser pour le score de l’individu de la génération x. Les paramètres contenus dans cet individu forment donc une solution admise comme tolérables vis à vis du problème posé.

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Illustration » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Illustration

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Texte » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Vous pouvez retrouver le principe expliqué ci-dessus sous forme de schéma : 3

 

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Applications » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Applications

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Texte » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Les algorithmes génétiques se trouvent et s’emploient dans pleins de domaines d’applications dans lesquels les algorithmes traditionnels ne sont plus suffisants : on peut citer par exemple le célèbre problème du voyageur de commerce qui consiste à trouver le chemin le plus court pour relier toutes les villes d’une zone géographique.

On les retrouve également beaucoup dans toutes les applications liées à l’industrie, (trouver les paramètres idéaux pour le rendement maximal d’un moteur par exemple ou d’un système complexe avec de nombreuses variables à prendre en compte) et au machine learning (apprendre à une machine à exécuter une tâche par exemple).

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Conclusion » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Conclusion

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row admin_label= »Ligne »][et_pb_column type= »4_4″][et_pb_text admin_label= »Texte » background_layout= »light » text_orientation= »left » use_border_color= »off » border_color= »#ffffff » border_style= »solid »]

Les algorithmes génétiques présentent de nombreuses perspectives pour l’avenir : ils sont d’excellents outils pour résoudre des problèmes d’optimisations jugés trop complexes pour un algorithme dit classique.

Une application directe de ce type d’algorithme sera d’ailleurs le sujet d’un prochain article !

Stay Tuned!

[/et_pb_text][/et_pb_column][/et_pb_row][/et_pb_section]

  1. https://fr.wikipedia.org/wiki/Algorithme_g%C3%A9n%C3%A9tique
  2. Code ISBN : 2854285786
  3. https://genetic.io/introduction-aux-algorithmes-genetiques/

A propos de l'auteur

Corentin POTRON

Actuellement élève-ingénieur et rédacteur du site Science Exploits, j'aime partager ma passion pour les nouvelles technologies, l'informatique, et les sciences en général. Je suis un fervent adepte de la philosophie DIY et du logiciel libre. Je suis ici pour vous partager mes trouvailles, mes projets et mes intérêts du moment.

Par Corentin POTRON
the new scientific reference

Archives

Recevez nos derniers articles par mail !

Recevez nos derniers articles par mail !

Rejoignez notre liste pour recevoir notre newsletter hebdomadaire gratuitement avec les derniers articles du site Science Exploits !

Vous venez de vous inscrire avec succès, à bientôt !