Introduction à la bibliothèque Jenetics

1. Introduction

Le but de cette série est d'expliquer l'idée d'algorithmes génétiques et de montrer les implémentations les plus connues.

Dans ce didacticiel, nous allons décrire une bibliothèque Java Jenetics très puissante qui peut être utilisée pour résoudre divers problèmes d'optimisation.

Si vous pensez avoir besoin d'en savoir plus sur les algorithmes génétiques, nous vous recommandons de commencer par cet article.

2. Comment ça marche?

Selon ses documents officiels, Jenetics est une bibliothèque basée sur un algorithme évolutif écrit en Java. Les algorithmes évolutifs ont leurs racines dans la biologie, car ils utilisent des mécanismes inspirés de l'évolution biologique, tels que la reproduction, la mutation, la recombinaison et la sélection.

Jenetics est implémenté à l'aide de l' interface Java Stream , de sorte qu'il fonctionne parfaitement avec le reste de l' API Java Stream .

Les principales caractéristiques sont:

  • minimisation sans friction - il n'est pas nécessaire de modifier ou d'ajuster la fonction de remise en forme; nous pouvons simplement changer la configuration de la classe Engine et nous sommes prêts à démarrer notre première application
  • sans dépendance - il n'y a pas de bibliothèques tierces d'exécution nécessaires pour utiliser Jenetics
  • Prêt pour Java 8 - prise en charge complète des expressions Stream et lambda
  • multithread - les étapes évolutives peuvent être exécutées en parallèle

Pour utiliser Jenetics, nous devons ajouter la dépendance suivante dans notre pom.xml :

 io.jenetics jenetics 3.7.0 

La dernière version peut être trouvée dans Maven Central.

3. Cas d'utilisation

Pour tester toutes les fonctionnalités de Jenetics, nous allons essayer de résoudre divers problèmes d'optimisation bien connus, en commençant par l'algorithme binaire simple et en terminant par le problème Knapsack.

3.1. Algorithme génétique simple

Supposons que nous ayons besoin de résoudre le problème binaire le plus simple, où nous devons optimiser les positions des 1 bits dans le chromosome constitué de 0 et de 1. Tout d'abord, nous devons définir l'usine adaptée au problème:

Factory
    
      gtf = Genotype.of(BitChromosome.of(10, 0.5));
    

Nous avons créé le BitChromosome avec une longueur de 10 et la probabilité d'avoir des 1 dans le chromosome égale à 0,5.

Maintenant, créons l'environnement d'exécution:

Engine engine = Engine.builder(SimpleGeneticAlgorithm::eval, gtf).build();

La méthode eval () renvoie le nombre de bits:

private Integer eval(Genotype gt) { return gt.getChromosome().as(BitChromosome.class).bitCount(); }

Dans la dernière étape, nous commençons l'évolution et collectons les résultats:

Genotype result = engine.stream() .limit(500) .collect(EvolutionResult.toBestGenotype());

Le résultat final ressemblera à ceci:

Before the evolution: [00000010|11111100] After the evolution: [00000000|11111111]

Nous avons réussi à optimiser la position des 1 dans le gène.

3.2. Problème de somme de sous-ensemble

Un autre cas d'utilisation de Jenetics est de résoudre le problème de la somme des sous-ensembles. En bref, le défi à optimiser est que, étant donné un ensemble d'entiers, nous devons trouver un sous-ensemble non vide dont la somme est nulle.

Il existe des interfaces prédéfinies dans Jenetics pour résoudre de tels problèmes:

public class SubsetSum implements Problem
    
      { // implementation }
    

Comme nous pouvons le voir, nous implémentons le problème , qui a trois paramètres:

  • - le type d'argument de la fonction de remise en forme du problème, dans notre cas une séquence d' entiers immuable, ordonnée et de taille fixe ISeq
  • - le type de gène avec lequel le moteur d'évolution travaille, dans ce cas, les gènes entiers dénombrables EnumGene
  • - le type de résultat de la fonction fitness; ici c'est un entier

Pour utiliser l' interface Problème , nous devons remplacer deux méthodes:

@Override public Function
    
      fitness() { return subset -> Math.abs(subset.stream() .mapToInt(Integer::intValue).sum()); } @Override public Codec
     
       codec() { return codecs.ofSubSet(basicSet, size); }
     
    

Dans le premier, nous définissons notre fonction de fitness, tandis que le second est une classe contenant des méthodes d'usine pour créer des codages de problèmes communs, par exemple, pour trouver le meilleur sous-ensemble de taille fixe à partir d'un ensemble de base donné, comme dans notre cas.

Nous pouvons maintenant passer à la partie principale. Au début, nous devons créer un sous-ensemble à utiliser dans le problème:

SubsetSum problem = of(500, 15, new LCG64ShiftRandom(101010));

Veuillez noter que nous utilisons le générateur LCG64ShiftRandom fourni par Jenetics. Dans l'étape suivante, nous construisons le moteur de notre solution:

Dans l'étape suivante, nous construisons le moteur de notre solution:

Engine
    
      engine = Engine.builder(problem) .minimizing() .maximalPhenotypeAge(5) .alterers(new PartiallyMatchedCrossover(0.4), new Mutator(0.3)) .build();
    

Nous essayons de minimiser le résultat (de manière optimale, le résultat sera 0) en définissant l'âge du phénotype et les altérateurs utilisés pour modifier la progéniture. Dans l'étape suivante, nous pouvons obtenir le résultat:

Phenotype
    
      result = engine.stream() .limit(limit.bySteadyFitness(55)) .collect(EvolutionResult.toBestPhenotype());
    

Veuillez noter que nous utilisons bySteadyFitness () qui renvoie un prédicat, qui tronquera le flux d'évolution si aucun meilleur phénotype n'a pu être trouvé après le nombre de générations donné et collectera le meilleur résultat. Si nous avons de la chance et qu'il existe une solution à l'ensemble créé aléatoirement, nous verrons quelque chose de similaire à ceci:

Si nous avons de la chance et qu'il existe une solution à l'ensemble créé aléatoirement, nous verrons quelque chose de similaire à ceci:

[85|-76|178|-197|91|-106|-70|-243|-41|-98|94|-213|139|238|219] --> 0

Sinon, la somme du sous-ensemble sera différente de 0.

3.3. Problème de premier ajustement du sac à dos

The Jenetics library allows us to solve even more sophisticated problems, such as the Knapsack problem. Briefly speaking, in this problem, we have a limited space in our knapsack, and we need to decide which items to put inside.

Let's start with defining the bag size and number of items:

int nItems = 15; double ksSize = nItems * 100.0 / 3.0;

In the next step, we'll generate a random array containing KnapsackItem objects (defined by size and value fields) and we'll put those items randomly inside the knapsack, using the First Fit method:

KnapsackFF ff = new KnapsackFF(Stream.generate(KnapsackItem::random) .limit(nItems) .toArray(KnapsackItem[]::new), ksSize);

Next, we need to create the Engine:

Engine engine = Engine.builder(ff, BitChromosome.of(nItems, 0.5)) .populationSize(500) .survivorsSelector(new TournamentSelector(5)) .offspringSelector(new RouletteWheelSelector()) .alterers(new Mutator(0.115), new SinglePointCrossover(0.16)) .build();

There are a few points to note here:

  • population size is 500
  • the offspring will be chosen through the tournament and roulette wheel selections
  • as we did in the previous subsection, we need also to define the alterers for the newly created offspring

There is also one very important feature of Jenetics. We can easily collect all statistics and insights from the whole simulation duration. We are going to do this by using the EvolutionStatistics class:

EvolutionStatistics statistics = EvolutionStatistics.ofNumber();

Finally, let's run the simulations:

Phenotype best = engine.stream() .limit(bySteadyFitness(7)) .limit(100) .peek(statistics) .collect(toBestPhenotype());

Please note that we are updating the evaluation statistics after each generation, which is limited to 7 steady generation and a maximum of 100 generations in total. In more detail there are two possible scenarios:

  • we achieve 7 steady generations, then the simulation stops
  • we cannot get 7 steady generations in less than 100 generations, so the simulation stops due to the second limit()

It's important to have maximum generations limit, otherwise, the simulations may not stop in a reasonable time.

The final result contains a lot of information:

+---------------------------------------------------------------------------+ | Time statistics | +---------------------------------------------------------------------------+ | Selection: sum=0,039207931000 s; mean=0,003267327583 s | | Altering: sum=0,065145069000 s; mean=0,005428755750 s | | Fitness calculation: sum=0,029678433000 s; mean=0,002473202750 s | | Overall execution: sum=0,111383965000 s; mean=0,009281997083 s | +---------------------------------------------------------------------------+ | Evolution statistics | +---------------------------------------------------------------------------+ | Generations: 12 | | Altered: sum=7 664; mean=638,666666667 | | Killed: sum=0; mean=0,000000000 | | Invalids: sum=0; mean=0,000000000 | +---------------------------------------------------------------------------+ | Population statistics | +---------------------------------------------------------------------------+ | Age: max=10; mean=1,792167; var=4,657748 | | Fitness: | | min = 0,000000000000 | | max = 716,684883338605 | | mean = 587,012666759785 | | var = 17309,892287851708 | | std = 131,567063841418 | +---------------------------------------------------------------------------+

This particular time, we were able to put items with a total value of 716,68 in the best scenario. We also can see the detailed statistics of evolution and time.

How to test?

It is a fairly simple process — just open the main file related to the problem and first run the algorithm. Once we have a general idea, then we can start playing with the parameters.

4. Conclusion

In this article, we covered the Jenetics library features based on real optimization problems.

The code is available as a Maven project on GitHub. Please note that we provided the code examples for more optimization challenges, such as the Springsteen Record (yes, it exists!) and Traveling Salesman problems.

Pour tous les articles de la série, y compris d'autres exemples d'algorithmes génétiques, consultez les liens suivants:

  • Comment concevoir un algorithme génétique en Java
  • Le problème du voyageur de commerce à Java
  • Optimisation des colonies de fourmis
  • Introduction à la bibliothèque Jenetics (ceci)