VT2021 BioInspiredAlgo fiche

Émilie Tondeux : emilie.tondeux@etu.univ-grenoble-alpes.fr

Bertrand Baudeur : bertrand.baudeur@etu.univ-grenoble-alpes.fr

Les algorithmes bio-inspirés

Résumé :

Les algorithme bio-inspirée sont une façon de résoudre des problèmes de recherche opérationnelle en imitant des phénomènes observés dans la nature. Ces algorithmes fortement basé sur l’aléatoire convergent petit à petit vers des solutions de bonne qualité, permettant ainsi de pallier au problème d’execution trop longue des algorithme de résolution exacte. Il en existe de nombreux qui se basent sur différentes observations de la nature, mais tous partagent de nombreux points commun. Cet article fait une brève présentation de ce concept en en donnant les fondements et les caractéristique ainsi qu’en donnant des exemples.

Mots clés : Algorithme, Recherche opérationnelle, Bio-inspiration, Optimisation, Algorithme Génétique, Algorithme de la colonie de fourmis.

Abstract :

Bio-inspired algorithms are a way to solve operational research problems through the imitation of phenomenons observed in nature. These algorithms are strongly based on randomness and are always converging slowly towards good solutions, allowing us to surpass the problem of exact resolution algorithm execution duration problem. There are many such algorithms that are based on different nature observations, but they all have a lot of common points. This article gives a short introduction to this concept by giving the bases and foundations whilst giving examples.

Key-words : Algorithm, Operationnal Research, Bio-Inspiration, Optimization, Genetic Algorithm, Ant Colony Algorithm.

I. Présentation générale

A. Concept

Les algorithmes bio inspirés sont des algorithmes dont le principe s’inspire de phénomènes que l’on peut observer dans la nature. Qu’il s’agisse de comportements d’animaux, de plantes, de phénomènes physiques ou de principes naturels.

Ils sont principalement utilisés dans la recherche opérationnelle pour résoudre des problèmes de décision dans des temps raisonnables. Certains sont souvent appliqués dans le domaine du machine learning pour entraîner des machines artificielles.

Le fonctionnement de ces algorithmes repose fortement sur le hasard. Ce qui rend la preuve de correction de ces algorithmes souvent impossible. Cependant, le fait de leur observation dans la nature nous assure leur fonctionnement dans une certaine mesure.

Tous les concepts que l’on observe pour s’en inspirer partagent le même environnement : notre planète. Le fait est que cet écosystème est dynamique et en constante évolution. De par cette règle tout ce qui peut être observé à un instant T est un concept qui a réussi à émerger du chaos et fonctionne pour répondre à une problématique. Si on prend l’exemple des animaux, tous ceux vivant actuellement sont le résultat d’une sélection qui a mené à ce que seuls les individus capables de se défendre, de trouver de la nourriture et de se reproduire sont présents aujourd’hui. Ils sont donc une proposition de réponse à un environnement sous contrainte. De par cette nature, leur comportement est en fait une bonne stratégie pour résoudre des problèmes. Et c’est de cela que l’on s’inspire pour résoudre nos problèmes de décision avec les algorithmes bio-inspirés.

La terre et ses dynamiques sont devenues un laboratoire géant dans lequel des expériences ont été mises en œuvre pendant plusieurs millions d’années. Nous, programmeur et chercheur, nous contentons d’observer le résultat actuel de ses expériences pour en tirer les concepts qui nous permettent de résoudre nos propres problèmes.

B. Un Exemple

Pour illustrer ce concept, nous expliquons ici le fonctionnement des colonies de fourmis dans la recherche d'itinéraires vers un point de nourriture.

Ici, leur problème est de trouver le chemin le plus court séparant leur fourmilière d’un lieu connu contenant de la nourriture.

Les fourmis communiquent via des phéromones (ce sont des sortes d’odeurs). Par exemple, elles indiquent le chemin qu’elles prennent en laissant des phéromones sur le sol sur tout le trajet qu’elles empruntent. Ces phéromones sont volatiles et ont une sorte de durée de vie.

Les fourmis vont donc emprunter différents chemins pour ramener de la nourriture provenant de ce lieu. Dans un même laps de temps, celles qui ont trouvé un chemin court auront le temps de faire plus d’aller-retour que celles qui empruntent un chemin plus long laissant plus de phéromones sur ce trajet et entretenant la trace qui ne disparaîtra pas. Ainsi, les prochaines fourmis qui vont chercher de la nourriture vont choisir leur trajectoire en fonction du chemin qui contient le plus de phéromones (celui le plus parcouru). Plus un chemin a de phéromones, plus il a de chance d’être choisi. Et c’est ainsi qu’elles trouvent la solution optimale à un problème de recherche de chemin le plus court dans un graphe.

II. Les grands principes communs

Les algorithmes bio inspirés partagent de nombreux points communs, notamment trois grands principes que nous allons détailler ici et mettre en reflet avec le problème de l’exemple précédent.

Les trois grands principes sont : -la fitness -l’exploration et l’exploitation -l’itération

A. Fitness

Tout d’abord la fitness, il s’agit d’une mesure qui indique à quel point une solution répond à notre problème. Il se base sur des paramètres observables d’une solution et se formule comme une fonction mathématique. Cette fonction peut avoir une infinité de formes, tout dépend des paramètres que vous voulez mettre en avant.

Si on reprend l’exemple des fourmis, on peut imaginer un problème ou on a plusieurs sources de nourriture, on pourrait alors évaluer deux paramètres, la longueur du chemin emprunté et la qualité de la source de nourriture qu’il atteint. La fonction mathématique peut être alors qualité-longueur. Donc ici plus la qualité sera grande, plus la fitness sera grande, à l’inverse plus la longueur sera grande, plus la fitness sera petite. Voici quelques exemples d’autres façon de tourner la fonction :

-f(sol) = qualité - (10*longueur) : La longueur a une grande importante.

-f(sol) = 2^(qualité) - longueur) : Plus la qualité est grande, moins la longueur a d’importance.

-f(sol) = qualité : On ne regarde que la qualité.

B. L’exploitation et l’exploration

L’exploration et l’exploitation sont les concepts qui régissent la façon dont on cherche parmi les solutions proposées.

L’exploitation est le fait de tourner autour de la meilleure solution connue pour essayer de la parfaire petit à petit.

L’exploration est le fait d’essayer de toute nouvelles solutions pour espérer trouver sur une nouvelle solution meilleure que celle connue.

Ces deux éléments doivent cohabiter dans un jeu d’équilibre. Ne faire que de l’exploitation mène à trouver des extremum locaux, c'est-à-dire le max d’un rayon restreint de solution. A l’inverse, trop d’exploration va empêcher la convergence vers une bonne solution, on va trouver beaucoup de solutions peu abouties. En effet les très bonnes solutions étant assez rares, tirer systématiquement au hasard laisse très peu de chance à la découverte d’une excellente solution.

Dans notre exemple des fourmis, l’exploitation est le fait de donner plus de chance aux chemins avec beaucoup de phéromones. L’exploration est le fait de ne pas systématiquement prendre le chemin avec le plus de phéromones.

C. Itération

Enfin, l’itération est le fait de répéter plusieurs fois les mêmes étapes de façon cyclique.

On part d’un ensemble de solutions. On en évalue la qualité à l’aide de la fitness. Si elles suffisent, on s’arrête. Autrement, on essaie de les améliorer via l’exploration et l’exploitation. Puis on réitère. Le principe d’itération passe souvent par un processus de discrétisation du phénomène observé, par exemple pour les fourmis, au lieu de les laisser se déplacer comme on veut, on les envoie par vague.

III. Application classique détaillées

A. L’évolution

Dans la nature, les espèces évoluent par générations qui se transmettent des gènes. Les individus ayant des gènes non adaptés à l’environnement ne survivront pas et ne pourront donc pas transmettre ces gènes non adaptés. De cette manière, seuls les individus répondant le mieux à l’environnement existent. La mutation et les croisements permettent de rechercher de meilleures espèces qui survivront encore plus.

B. Transformation sous forme d’algorithme.

On reprend le même concept que dans la nature, on fait la sélection naturelle basée sur la fitness, on fait ensuite des mix entre deux solutions pour en trouver de nouvelles, ces nouvelles solutions subissent enfin des mutations aléatoires.

Pour ce faire, on utilise des génomes, qui sont généralement un tableau de valeur, elles peuvent être booléennes, entières, réelles, qualitatives, etc… Ces tableaux représentent une solution.

Lors de la sélection, la solution représentée par le génome est évaluée, le génome se voit alors attribuer une valeur. On choisit ensuite la moitié des individus. Pour ce faire, on attribue à chacun une probabilité d’être tirée égale à sa fitness divisée par la totale des fitness. Une fois la moitié des individus sélectionnés, on se débarrasse des autres.

Vient ensuite le croisement. On tire aléatoirement des paires d’individus. Ces individus vont mélanger un certain pourcentage de leurs gènes, donc de leur case de tableau, pour créer deux nouveaux individus. Le pourcentage est appelé coefficient d’enjambement et est choisi à l’avance dans l’expérience. Il est un facteur d'exploration. On a donc deux nouveaux tableaux dont les gènes sont un mix de leurs deux parents.

Enfin vient la mutation. Pour chaque individu on fait changer avec une certaine probabilité leurs gênes. Cette probabilité est appelée coefficient de mutation et est généralement très faible. Les cases du tableau changées prennent un nouvelle valeur aléatoire parmi les valeurs possibles.

On a ainsi une nouvelle génération d’individus et il ne reste plus qu’à recommencer.

L’algorithme génétique est extrêmement utilisé en machine learning. Un individu représente alors un comportement de l’IA, on observe ensuite comment elle passe des épreuves que l’on lui donne pour évaluer sa fitness, en itérant un grand nombre de fois, plus d’une centaine de génération au moins, l’IA s’améliore.

C. Application à un problème concret

Problème du sac à dos :

Le problème du sac à dos est un problème classique dans la recherche d’optimisation.

Les éléments que nous possédons sont un sac avec une capacité de stockage ainsi qu’une liste d’objets qui ont deux paramètres associés : le poids de l’objet et sa valeur L’objectif de ce problème est de trouver la liste des objets à emporter dans ce sac qui répond le mieux aux critères définis. A savoir maximiser la valeur totale des objets emportés sans dépasser la capacité du sac.

Utilisation de l’algorithme génétique pour le résoudre :

Dans l’algorithme on va donc reprendre les grandes étapes de la génétique. Dans la première itération, comme aucune solution n’est proposée, aucun individu n’a de score fitness. On va donc prendre un ensemble d’individus qui vont choisir un ensemble d’objets à mettre dans le sac de manière aléatoire. Chaque objet choisi va faire office de gène qui se répand dans la population ou non. Le génome est composé d’un tableau dont chaque indice correspond à un objet précis. Si l’individu possède l’objet, sa valeur associé sera 1 sinon elle sera 0. Une fois que la population initiale est formée, on évalue les individus via la fonction fitness.

Ici on a choisi la formule suivante :

Ainsi, chaque individu possède un score fitness qui indique à quel point la solution qu’il propose est adaptée au problème. Puis vient la sélection. On ne garde que les individus ayant un bon score fitness. Il vont ensuite créer de nouveaux individus qui possèdent leurs gènes (croisement). La nouvelle population propose donc des solutions avec les objets qui répondent le mieux aux critères.

Enfin, vient la mutation qui ne s’opère que sur les individus créés à l’étape précédente et va apporter une part d’aléatoire et d’exploration. Nous voilà maintenant avec une nouvelle population et on peut recommencer l’itération.

IV. Conclusion :

Les algorithmes bio inspirés présentent l’avantage d’avoir un temps d’exécution court, même sur des problèmes de très grande taille contrairement aux algorithmes de résolution exacte qui souvent ont des complexités trop grandes. De plus, leur principe d’itération permet de tirer une solution du problème de l'exécution à tout moment. Ce qui permet de faire tourner l’algorithme jusqu’à ce qu’on ait besoin de la solution. De plus, la nature est une source d’inspiration quasiment illimitée qui ouvre des portes à de nombreux algorithmes. Ils offrent également une grande flexibilité, il suffit d’exprimer un problème en un format que l’algorithme peut utiliser pour résoudre n’importe quel problème.

Malgré tous ces avantages, ces algorithmes présentent quelques défauts comme l'impossibilité de prouver leur correction, ou encore le fait de n’avoir pas de garantie sur la qualité de la solution obtenue après exécution, car on ne sait pas s'il y avait une solution deux fois ou cent fois meilleure que celle obtenue. Enfin, leur mise en place n’est pas toujours aisée, ces algorithmes possèdent de nombreux paramètres, les valeurs de tirage au sort et la formule de fitness en sont des exemples. Il faut généralement tester à de multiples reprises avec différents paramètres avant d’avoir un résultat satisfaisant.

Références :

Un exemple d’application dans le machine learning : Neural network racing cars around a track - YouTube Icone de fourmis, de colonie de fourmis et de cupcake créé par Freepik et disponible sur Flaticon.

Fevrier Valdez , Oscar Castillo and Patricia Melin, “Bio-Inspired Algorithms and Its Applications for Optimization in Fuzzy Clustering”, Article Scientifique, https://www.mdpi.com/1999-4893/14/4/122 Explication sur les Fuzzy Clustering Algorithm.

Ashraf Darwish, “Bio-inspired computing: Algorithms review, deep analysis, and the scope of applications”, Article Scientifique, https://www.sciencedirect.com/science/article/pii/S2314728818300631 Liste d'algorithmes bio-inspirés.

“Algorithme génétique”, Article Wikipedia, https://fr.wikipedia.org/wiki/Algorithme_g%C3%A9n%C3%A9tique Détails de l’algorithme