L’informatique est une pratique de la précision. Le doute, l’approximation, l’imprévu n‘y ont pas leur place. Pourtant les algorithmes génétiques emploient les méthodes approximatives de l’évolution des espèces pour résoudre des problèmes complexes. Avec succès. Cette utilisation de stratégies d’évolution vient remplacer la pure approche mathématique, là où elle échoue. Usuellement, les programmes sont composés de séries d’instructions destinées à manipuler des données selon une routine entièrement déterministe que l’on nomme un algorithme. Cependant, la résolution de certains problèmes dits d’optimisation, c’est-à-dire tendant à fournir la meilleure solution, ou une solution passant un certain seuil de qualité, en réponse à un problème précis, demande soit une puissance de traitement démesurée, soit la composition d’algorithmes très complexes.
Des procédures d’optimisation et de maximisation de fonctions
Prenons l’exemple d’un voyageur de commerce qui doit visiter un certain nombre de villes. La manière la plus primaire (mais, il en existe d’autres) pour définir le meilleur itinéraire consiste à calculer tous les chemins possibles et à les comparer pour déterminer le plus court. Cette méthode est terriblement gourmande en puissance de calcul (le nombre des combinatoires est factorielle n, où n est le nombre de villes à parcourir). Aussi, depuis les années cinquante, les chercheurs en intelligence artificielle ont-ils privilégié d’autres voies. L’application de la théorie de l’évolution de Darwin et de ses successeurs en informatique, sous l’impulsion de John Holland, a donné naissance à la théorie des algorithmes génétiques. Au lieu de traiter un problème sur un mode massif et total, les algorithmes génétiques fonctionnent selon un principe évolutionniste : le problème est fragmenté en étapes pour lesquelles on cherche des populations de solutions optimisées que l’on fait évoluer. Les théoriciens parlent de procédures d’optimisation et de maximisation d’une fonction. Chaque solution est une cha”ne binaire (une série de 1 et de 0), que l’on peut assimiler à un gène. Le gène évolue de façon telle, qu’au bout d’un certain nombre de manipulations, la cha”ne binaire soit la mieux adaptée au problème à résoudre. Dans l’exemple du problème du voyageur de commerce, on code chaque ville par une cha”ne binaire de 4 caractères (ce qui permet de coder 24 = 16 villes), chaque groupe de 4 caractères est assimilé à un chromosome, c’est l’unité de base sur laquelle l’algorithme va travailler.
Dans le cas d’un traitement par algorithme déterministe, il faut calculer tous les chemins possibles, soit factoriel 16 (20 922 789 888 000 combinaisons), et déterminer le plus court. Dans le cas d’un algorithme génétique, on génère de façon aléatoire une première population de solutions (P1), composée de gènes, chacun comportant 16 chromosomes de 4 caractères. Dans cet exemple précis, aucun chromosome ne doit se répéter (puisque cela équivaudrait pour le voyageur de commerce à passer deux fois dans la même ville). Cet ensemble de gènes constitue la première génération P1. Sur ces n gènes de départ (P1), on sélectionne une population réduite (P1s) présentant les meilleures caractéristiques, c’est-à-dire des gènes dont l’expression se traduit par le trajet le plus court entre les 16 villes au sein des solutions de P1, et on élimine les autres. Les gènes sélectionnés sont ensuite recombinés entre eux, c’est-à-dire qu’ils échangent des séquences de 4 caractères selon diverses règles : par exemple, G1 et G2 vont échanger un gène sur deux, soit la moitié de leurs gènes. On obtient donc une population croisée, P1c, différente de P1s. Sur cette population croisée, on applique un facteur de mutation qui possède une probabilité très faible d’apparition (entre 1 % et 1 ä) et qui se manifeste par la substitution aléatoire de certaines cha”nes de 4 caractères par d’autres. Ce facteur de mutation ne présente pas de justification strictement rationnelle, il se trouve que le modèle évolutionniste montre qu’une part d’aléatoire améliore les résultats. Au total la population P1 une fois sélectionnée, recombinée et soumise à des événements aléatoires est de nouveau estimée. Puis le processus est reconduit en partant de cette population, jusqu’à atteindre un seuil de qualité suffisant du résultat.
🔴 Pour ne manquer aucune actualité de 01net, suivez-nous sur Google Actualités et WhatsApp.
