Algorithme évolutionniste ou évolutionnaire

Un algorithme évolutionniste ou évolutionnaire (AE) met en œuvre des mécanismes inspirés de la nature pour résoudre des problèmes comme le feraient des organismes vivants. Il appartient aussi bien à l’informatique bio-inspirée qu'à l'informatique évolutionniste.

Les AE s'appuient sur les concepts de la théorie de l'évolution. Dans ces algorithmes, les solutions jouent le rôle des organismes individuels d'une population. Le panel des solutions possibles à un problème est d'abord une proposition aléatoire. La population est ensuite testée pour son aptitude à résoudre un problème correctement et rapidement. Puis les individus les plus adaptés sont sélectionnés pour la reproduction. Et le cycle recommence : on évalue le degré d'adaptation de la population et on élimine les individus les moins adaptés.

Comme les mécanismes des AE simulent les organismes vivants et leur évolution, ils font appel à des fonctions telles que la sélection, la reproduction, la mutation et la recombinaison. Le processus d'évolution qui consiste à choisir les meilleures solutions possibles à un problème selon un critère d'adaptation simule la sélection naturelle décrite par Darwin. Les solutions algorithmiques qui donnent les meilleurs résultats parmi les options proposées se reproduisent ; les moins adaptées sont éliminées et ne sont pas reproduites. Grâce à des tests mesurant le degré d'adaptation d'après les performances, l'optimisation s'opère sur plusieurs générations avec des fonctions comme la mutation.

Les AE sont un excellent outil d'optimisation de solutions. Toutefois, ces algorithmes ne trouvent pas nécessairement la solution optimale. En effet, ils ne cessent de trouver des solutions dont ils comparent les performances, ce qui peut ou non faire émerger LA meilleure solution. Il est également important de noter que les AE sont plutôt gourmands en ressources de calcul, notamment à cause de la complexité inhérente à la détermination du degré d'adaptation. Il est possible de réduire cette complexité par l'approximation de l'adaptation.