Concevoir un algorithme génétique en Java

1. Introduction

Le but de cette série est d' expliquer l'idée d'algorithmes génétiques .

Les algorithmes génétiques sont conçus pour résoudre des problèmes en utilisant les mêmes processus que dans la nature - ils utilisent une combinaison de sélection, de recombinaison et de mutation pour développer une solution à un problème.

Commençons par expliquer le concept de ces algorithmes en utilisant l'exemple d'algorithme génétique binaire le plus simple.

2. Comment fonctionnent les algorithmes génétiques

Les algorithmes génétiques font partie de l'informatique évolutive , qui est un domaine de l'intelligence artificielle en pleine croissance.

Un algorithme commence par un ensemble de solutions (représentées par des individus ) appelé population . Les solutions d'une population sont prises et utilisées pour former une nouvelle population , car il y a une chance que la nouvelle population soit meilleure que l'ancienne.

Les individus qui sont choisis pour former de nouvelles solutions ( progéniture ) sont sélectionnés en fonction de leur aptitude - plus ils sont adaptés, plus ils ont de chances de se reproduire.

3. Algorithme génétique binaire

Jetons un coup d'œil au processus de base d'un algorithme génétique simple.

3.1. Initialisation

Dans l'étape d'initialisation, nous générons une population aléatoire qui sert de première solution . Tout d'abord, nous devons décider de la taille de la population et de la solution finale que nous attendons:

SimpleGeneticAlgorithm.runAlgorithm(50, "1011000100000100010000100000100111001000000100000100000000001111");

Dans l'exemple ci-dessus, la taille de la population est de 50 et la solution correcte est représentée par la chaîne de bits binaire que nous pouvons modifier à tout moment.

Dans l'étape suivante, nous allons enregistrer la solution souhaitée et créer une population aléatoire :

setSolution(solution); Population myPop = new Population(populationSize, true);

Nous sommes maintenant prêts à exécuter la boucle principale du programme.

3.2. Vérification de la condition physique

Dans la boucle principale du programme, nous allons évaluer chaque individu par la fonction de remise en forme (en termes simples, plus l' individu est meilleur , plus la fonction de fitness est valorisée):

while (myPop.getFittest().getFitness() < getMaxFitness()) { System.out.println( "Generation: " + generationCount + " Correct genes found: " + myPop.getFittest().getFitness()); myPop = evolvePopulation(myPop); generationCount++; }

Commençons par expliquer comment nous obtenons l' individu le plus apte :

public int getFitness(Individual individual) { int fitness = 0; for (int i = 0; i < individual.getDefaultGeneLength() && i < solution.length; i++) { if (individual.getSingleGene(i) == solution[i]) { fitness++; } } return fitness; }

Comme nous pouvons l'observer, nous comparons deux objets individuels petit à petit. Si nous ne pouvons pas trouver une solution parfaite, nous devons passer à l'étape suivante, qui est une évolution de la population .

3.3. Progéniture

Dans cette étape, nous devons créer une nouvelle population . Tout d'abord, nous devons sélectionner deux objets individuels parents à partir d'une population, en fonction de leur aptitude. Veuillez noter qu'il est avantageux de permettre au meilleur individu de la génération actuelle de passer à la suivante, inchangé. Cette stratégie s'appelle un élitisme:

if (elitism) { newPopulation.getIndividuals().add(0, pop.getFittest()); elitismOffset = 1; } else { elitismOffset = 0; }

Afin de sélectionner deux meilleurs objets individuels , nous allons appliquer la stratégie de sélection des tournois :

private Individual tournamentSelection(Population pop) { Population tournament = new Population(tournamentSize, false); for (int i = 0; i < tournamentSize; i++) { int randomId = (int) (Math.random() * pop.getIndividuals().size()); tournament.getIndividuals().add(i, pop.getIndividual(randomId)); } Individual fittest = tournament.getFittest(); return fittest; }

Le gagnant de chaque tournoi (celui avec la meilleure condition physique) est sélectionné pour la prochaine étape, qui est Crossover :

private Individual crossover(Individual indiv1, Individual indiv2) { Individual newSol = new Individual(); for (int i = 0; i < newSol.getDefaultGeneLength(); i++) { if (Math.random() <= uniformRate) { newSol.setSingleGene(i, indiv1.getSingleGene(i)); } else { newSol.setSingleGene(i, indiv2.getSingleGene(i)); } } return newSol; }

Dans le crossover, nous échangeons des bits de chaque individu choisi à un endroit choisi au hasard. L'ensemble du processus s'exécute dans la boucle suivante:

for (int i = elitismOffset; i < pop.getIndividuals().size(); i++) { Individual indiv1 = tournamentSelection(pop); Individual indiv2 = tournamentSelection(pop); Individual newIndiv = crossover(indiv1, indiv2); newPopulation.getIndividuals().add(i, newIndiv); }

Comme nous pouvons le voir, après le croisement, nous plaçons une nouvelle progéniture dans une nouvelle population . Cette étape s'appelle l' acceptation.

Enfin, nous pouvons effectuer une mutation . La mutation est utilisée pour maintenir la diversité génétique d'une génération à l'autre d'une population . Nous avons utilisé le type de mutation par inversion de bits , où les bits aléatoires sont simplement inversés:

private void mutate(Individual indiv) { for (int i = 0; i < indiv.getDefaultGeneLength(); i++) { if (Math.random() <= mutationRate) { byte gene = (byte) Math.round(Math.random()); indiv.setSingleGene(i, gene); } } }

Tous les types de mutation et de croisement sont bien décrits dans ce tutoriel.

Nous répétons ensuite les étapes des sous-sections 3.2 et 3.3, jusqu'à ce que nous atteignions une condition de terminaison, par exemple, la meilleure solution.

4. Trucs et astuces

Afin de mettre en œuvre un algorithme génétique efficace , nous devons régler un ensemble de paramètres. Cette section devrait vous donner quelques recommandations de base pour commencer avec les paramètres les plus importants:

  • Taux de croisement - il devrait être élevé, environ 80% -95%
  • Taux de mutation - il devrait être très faible, autour de 0,5% -1% .
  • Taille de la population - une bonne taille de population est d'environ 20 à 30 , cependant, pour certains problèmes, les tailles de 50 à 100 sont meilleures
  • Sélection - la sélection de roue de roulette de base peut être utilisée avec le concept d' élitisme
  • Type de croisement et de mutation - cela dépend du codage et du problème

Veuillez noter que les recommandations pour le réglage sont souvent le résultat d'études empiriques sur les algorithmes génétiques, et elles peuvent varier en fonction des problèmes proposés.

5. Conclusion

Ce tutoriel présente les principes fondamentaux des algorithmes génétiques . Vous pouvez en apprendre davantage sur les algorithmes génétiques sans aucune connaissance préalable de ce domaine, n'ayant que des compétences de base en programmation informatique.

Le code source complet des extraits de code de ce didacticiel est disponible dans le projet GitHub.

Veuillez également noter que nous utilisons Lombok pour générer des getters et des setters. Vous pouvez vérifier comment le configurer correctement dans votre IDE dans cet article.

Pour d'autres exemples d'algorithmes génétiques, consultez tous les articles de notre série:

  • Comment concevoir un algorithme génétique? (celui-là)
  • Le problème du voyageur de commerce à Java