Introduzione alla Biblioteca Jenetics

1. Introduzione

Lo scopo di questa serie è spiegare l'idea degli algoritmi genetici e mostrare le implementazioni più conosciute.

In questo tutorial, descriveremo una libreria Java Jenetics molto potente che può essere utilizzata per risolvere vari problemi di ottimizzazione.

Se ritieni di aver bisogno di saperne di più sugli algoritmi genetici, ti consigliamo di iniziare con questo articolo.

2. Come funziona?

Secondo i suoi documenti ufficiali, Jenetics è una libreria basata su un algoritmo evolutivo scritto in Java. Gli algoritmi evolutivi hanno le loro radici nella biologia, poiché utilizzano meccanismi ispirati all'evoluzione biologica, come la riproduzione, la mutazione, la ricombinazione e la selezione.

Jenetics è implementato utilizzando l' interfaccia Java Stream , quindi funziona senza problemi con il resto dell'API Java Stream .

Le caratteristiche principali sono:

  • riduzione al minimo senza attriti : non è necessario modificare o modificare la funzione fitness; possiamo solo cambiare la configurazione della classe Engine e siamo pronti per avviare la nostra prima applicazione
  • senza dipendenze : non sono necessarie librerie di terze parti runtime per utilizzare Jenetics
  • Predisposto per Java 8 : supporto completo per Stream e espressioni lambda
  • multithread : i passaggi evolutivi possono essere eseguiti in parallelo

Per utilizzare Jenetics, dobbiamo aggiungere la seguente dipendenza nel nostro pom.xml :

 io.jenetics jenetics 3.7.0 

L'ultima versione può essere trovata in Maven Central.

3. Casi d'uso

Per testare tutte le funzionalità di Jenetics, proveremo a risolvere vari noti problemi di ottimizzazione, partendo dal semplice algoritmo binario e terminando con il problema dello Knapsack.

3.1. Algoritmo genetico semplice

Supponiamo di dover risolvere il problema binario più semplice, in cui dobbiamo ottimizzare le posizioni dei bit 1 nel cromosoma costituito da 0 e 1. Per prima cosa, dobbiamo definire la fabbrica adatta al problema:

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

Abbiamo creato il BitChromosome con una lunghezza di 10 e la probabilità di avere 1 nel cromosoma uguale a 0,5.

Ora creiamo l'ambiente di esecuzione:

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

Il metodo eval () restituisce il conteggio dei bit:

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

Nella fase finale, iniziamo l'evoluzione e raccogliamo i risultati:

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

Il risultato finale sarà simile a questo:

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

Siamo riusciti a ottimizzare la posizione degli 1 nel gene.

3.2. Problema della somma dei sottoinsiemi

Un altro caso d'uso per Jenetics è risolvere il problema della somma dei sottoinsiemi. In breve, la sfida da ottimizzare è che, dato un insieme di numeri interi, dobbiamo trovare un sottoinsieme non vuoto la cui somma sia zero.

Ci sono interfacce predefinite in Jenetics per risolvere questi problemi:

public class SubsetSum implements Problem
    
      { // implementation }
    

Come possiamo vedere, implementiamo il Problema , che ha tre parametri:

  • - dimensioni del tipo di argomento della funzione problema di forma fisica, nel nostro caso un immutabile, ordinata, fissato Integer sequenza iseq
  • - il tipo di gene con cui sta lavorando il motore di evoluzione, in questo caso, geni Integer numerabili EnumGene
  • - il tipo di risultato della funzione fitness; qui è un numero intero

Per poter utilizzare l' interfaccia Problem , dobbiamo sovrascrivere due metodi:

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

Nel primo, definiamo la nostra funzione fitness, mentre il secondo è una classe contenente metodi di fabbrica per la creazione di codifiche di problemi comuni, ad esempio, per trovare il miglior sottoinsieme di dimensioni fisse da un dato insieme di base, come nel nostro caso.

Ora possiamo procedere alla parte principale. All'inizio, dobbiamo creare un sottoinsieme da utilizzare nel problema:

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

Tieni presente che stiamo utilizzando il generatore LCG64ShiftRandom fornito da Jenetics. Nella fase successiva, stiamo costruendo il motore della nostra soluzione:

Nella fase successiva, stiamo costruendo il motore della nostra soluzione:

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

Cerchiamo di minimizzare il risultato (in modo ottimale il risultato sarà 0) impostando l'età del fenotipo e gli alteratori utilizzati per alterare la prole. Nella fase successiva possiamo ottenere il risultato:

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

Si noti che stiamo utilizzando bySteadyFitness () che restituisce un predicato, che troncerà il flusso di evoluzione se non è stato possibile trovare un fenotipo migliore dopo il numero di generazioni specificato e raccogliere il miglior risultato. Se siamo fortunati e c'è una soluzione al set creato casualmente, vedremo qualcosa di simile a questo:

Se siamo fortunati e c'è una soluzione al set creato in modo casuale, vedremo qualcosa di simile a questo:

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

In caso contrario, la somma del sottoinsieme sarà diversa da 0.

3.3. Problema di primo adattamento dello zaino

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.

Per tutti gli articoli della serie, inclusi altri esempi di algoritmi genetici, controlla i seguenti link:

  • Come progettare un algoritmo genetico in Java
  • Il problema del venditore ambulante in Java
  • Ottimizzazione della colonia di formiche
  • Introduzione alla libreria Jenetics (questa)