Une série d’articles dans laquelle vous allez découvrir les algorithmes génétiques. Ces algorithmes, fondés sur les principes de la génétique du vivant, sont très utiles pour trouver des solutions à des problèmes complexes par un système d’apprentissage.

Contributeur : Alexandre Castanet (enseignant de SVT,
chargé de mission à la DRANE PACA, pôle Aix-Marseille
et membre du groupe académique sur l'intelligence artificielle)

Avec les algorithmes génétiques, nous avons à la fois un exemple de biomimétisme et un exemple d’algorithme capable de trouver une solution originale, innovante. Toutes ces caractéristiques que nous allons détailler les font entrer dans le grand groupe des algorithmes d’intelligence artificielle. Dans ce premier article, nous nous attacherons à regarder leur efficacité.

Efficacité des algorithmes génétiques

Lorsqu’on évoque une catégorie d’algorithme, il est utile d’en dégager les caractéristiques ainsi que son usage.

Quelles sont donc les caractéristiques et l’usage d’un algorithme génétique ?

• Ils sont biomimétiques car ils utilisent les principes de la génétique du vivant : Les algorithmes génétiques sont tous fondés sur les principes de la génétique du vivant qui sont l’hérédité, la sélection et la mutation. Ils montrent l’efficacité des mécanismes du vivant pour trouver des solutions à un problème quelconque et ainsi font émerger de nouvelles possibilités voire de nouveaux cheminements.

• Ils sont capables d’apprendre de manière non-déterministe : Les algorithmes génétiques se distinguent des algorithmes classiques par le fait qu’ils trouvent une solution, mais il ne trouve pas forcément «la » solution. De plus, ils sont non-déterministes, c’est-à-dire que chaque recherche de solution par la machine, qui utilise cet algorithme, est susceptible d’emprunter un cheminement différent et ainsi d’arriver à un résultat différent. Ce sera alors à l’opérateur de la machine de juger si le résultat est acceptable.

• Ils permettent une évaluation du modèle évolutionniste : Ces algorithmes montrent la validité des principes la théorie de l’évolution. La modélisation de l’évolution à partir des principes qui s’appliquent à la perpétuation des espèces et à la reproduction des organismes vivants depuis des milliards d’années sur Terre montre son efficacité. Les règles de la génétique sont capables de trouver des solutions originales à un problème, c’est l’origine de la biodiversité. Les millions d’espèces sur Terre, sont autant de solutions trouvées par le vivant pour se perpétuer au cours du temps dans la diversité des milieux terrestres et marins. Sans intention, sans plan préalable.

Quelle est l’efficacité de tels algorithmes ?

Nous allons réaliser une comparaison de recherche de solutions dans le cadre d’un exemple bien connu : Le problème du voyageur de commerce.

C’est un problème d’optimisation qui consiste à déterminer à partir d’une liste de villes le plus court-chemin qui passe par chaque ville une fois. C’est un problème très complexe qui n’a pas de solution simple car il n’est pas possible d’évaluer toutes les possibilités pour un grand nombre de villes. Dans cet exemple, nous prendrons 18 villes.

Le saviez-vous ?

« Par exemple, si le calcul d'un chemin prend une microseconde, alors le calcul de tous les chemins pour 10 points est de 181 440 microsecondes soit 0,18 seconde, mais pour 15 points, cela représente déjà 43 589 145 600 microsecondes soit un peu plus de 12 heures et pour 20 points de 6 × 1016 microsecondes soit presque deux millénaires (1 901 années). Pour 25 villes, le temps de calcul dépasse l'âge de l'Univers. » https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce#Algorithmes

Pour résoudre donc ce problème avec 18 villes (nombre de chemins possibles : 6 402 373 705 728 000) nous allons mettre en concurrence 3 méthodes : le hasard, la force brute et l’algorithme génétique.

1. « Le hasard », on prend deux chemins au hasard, on compare et on recommence avec une autre possibilité jusqu’à ce que le résultat soit satisfaisant : https://editor.p5js.org/acastanet/sketches/N-ib1v6WC
2. « La méthode brute », c’est la même méthode que la précédente mais on prévoit d’examiner toutes les possibilités il y en a des milliards : https://editor.p5js.org/acastanet/sketches/lBkvtjJ9K
3. « La méthode bio-inspirée » elle permet faire "évoluer" une population de voyageurs pour trouver le plus court chemin : https://editor.p5js.org/acastanet/sketches/HTlRdvSee

Nous ne détaillerons pas dans cet exemple les algorithmes mais vous pouvez évaluer leur efficacité en remplissant un tableau pour voir qui atteint le mieux l’objectif avec des ressources raisonnables en temps et en puissance de calcul.

Méthodes	Hasard	Brute	Bio-inspiré
Distance la plus courte trouvée en 20s	3942	3255	1582
Distance la plus courte trouvée en 1000 coups
Distance la plus courte trouvée en 5000 coups