Sommaire

Implémentation

Nous allons maintenant nous intéresser à l’implémentation en Java d’un algorithme génétique générique qui est ici utilisé pour résoudre deux problèmes abordés précédemment :

  • Le voyageur de commerce, qui consiste à trouver la route la plus courte pour relier un ensemble de villes.

  • Le labyrinthe, en donnant la suite d’instructions à suivre pour aller de l’entrée à la sortie.

Le code proposé ici est disponible en téléchargement. Le programme contenant la fonction main est une application console.

1. Implémentation générique d’un algorithme

a. Spécifications

Nous voulons coder un moteur générique pour un algorithme génétique, qui est ensuite appliqué à deux problèmes différents, en écrivant le moins de code possible pour passer de l’un à l’autre.

Il est donc important de bien fixer les besoins. Le processus évolutionnaire en lui-même, le cœur du système, s’occupe d’initialiser la population, puis lance l’évaluation, la sélection des parents et la création des descendants et enfin la survie. On reboucle ensuite sur l’évaluation, et ce jusqu’à ce qu’un critère d’arrêt soit atteint.

On va donc définir deux critères d’arrêt possibles : ...