In questo ultimo articolo della serie viene presentata la progettazione possibile di un algoritmo genetico, concentrando l‘attenzione sul modello di dominio e sulla pseudocodifica Java degli algoritmi utilizzati.

Introduzione

Come abbiamo visto nel corso della serie, gli algoritmi genetici sono strumenti di intelligenza artificiale ispirati alla teoria dell’evoluzione di Darwin. Le leggi della selezione naturale e della genetica guidano l’evoluzione di una popolazione di organismi biologici in modo da adattarne le caratteristiche all’ambiente circostante. Dato che gli individui meglio adattati all’ambiente hanno maggiori probabilità di sopravvivenza e di procreazione, la forza media (o l’adattamento medio) della popolazione cresce di generazione in generazione.

Gli algoritmi genetici applicano questo paradigma alla soluzione di problemi di ottimizzazione difficili da un punto di vista computazionale. Ogni possibile soluzione del problema è rappresentata come un individuo, la cui forza corrisponde alla qualità della soluzione. Iniziando da una popolazione di individui, o soluzioni, i meccanismi dell’evoluzione vengono applicati ciclicamente per trovare sempre soluzioni migliori al problema dato.

In questo ultimo articolo viene presentata la possibile implementazione in Java di un algoritmo genetico. Concentremo la nostra attenzione sulla progettazione e sugli algoritmi utilizzati fornendo la loro la pseudocodifica.

Progettazione dei modelli

La modellazione degli oggetti di dominio corrisponde a un passo importante per l’esecuzione dell’algoritmo genetico. Come si può vedere dalla figura 1, i possibili oggetti che possono essere utilizzati sono:

• Chromosome: modella l’entità minima del dominio;
• Gene: corrisponde ad un’aggregazione di cromosomi;
• Entity: un’entità rappresenta una possibile soluzione del problema, quindi un insieme coerente di geni;
• Population: la popolazione contiene l’aggregazione di tutte le entità sottoposte alla lavorazione dell’algoritmo.

Le classi Gene e Chromosome hanno la caratteristica di essere classi astratte: in questo modo può essere utilizzato il meccasimo dell’ereditarietà per poter applicare l’algoritmo a domini differenti. La caratteristica comune di ogni classe è che ognuna di essere contiene un oggetto BitSet, ossia la codifica binaria dell’entità modellata. In questo modo è possibile utilizzare la modellazione degli oggetti di dominio per codificare ogni possibile problema da sottoporre all’algoritmo semplicemente implementando un opportuno algoritmo di conversione da oggetto di dominio a valori binari. È inoltre da notare che nella modellazione presentata, l’oggetto padre obbliga le estensioni ad implementare infatti il metodo di conversione da oggetto di modello a bitset e viceversa.

Questo genere di modellazione è utile ai fini di performance dell’algoritmo: infatti, come si è visto nei precedenti articoli, per implementare gli operatori di selezione e riproduzione, risulta molto comodo e veloce lavorare con stringhe binarie, per poter agevolmente effettuare i tagli di crossover e selezionare le zone di mutazione.
La classe Gene, inoltre, è particolare in quanto obbliga le classi estese a implementare anche il metodo di valutazione del gene stesso. Il metodo evaluate() infatti deve contenere l’algoritmo di valutazione che usa la funzione di fitness per assegnare un valore di forza alla soluzione rappresentata dal gene. Questo metodo ha anche la funzione di eliminare da subito i geni non coerenti che è possibile ottenere attraverso una generazione randomica della popolazione.

Generazione della popolazione

L’operazione fondamentale per lo start del’algoritmoè la generazione della popolazione iniziale. La popolazione è costituita da un’insieme di entità, ognuna delle quali corrisponde a una possibile soluzione al problema. La popolazione rappresenta quindi nel suo insieme lo spazio di ricerca dell’algoritmo.
Questa può essere generata in diversi modi. In generale si può adottare la strada della generazione randomica, in cui viene fornito all’algoritmo di generazione il size  masssimo della popolazione stessa, che corrisponde quindi al numero di entità che la popolazione deve contenere. In questo tipo di approccio, si lavora principalmente sugli oggetti bitset: questo significa che esisterà un algoritmo che genera casualmente stringhe binarie e le sottopone alla lavorazione. Una volta che l’algoritmo ha completato il suo lavoro, l’entità selezionata come soluzione migliore viene riconvertita in oggetto di modello per poter interpretare la soluzione trovata.
Un secondo metodo per la generazione della popolazione potrebbe essere quello di partire da un dataset stabilito. In questo tipo di approccio si può fornire all’algoritmo una sorgente di dati che corrispondono agli oggetti di modello definiti sopra, e quest’ultimo avrà il compito di verificare la correttezza del dataset e convertire lo stesso in stringhe binarie.

Come si può vedere dalla figura 2, il package di generazione contiene un’interfaccia pubblica IGenerator  che espone all’esterno solo il metodo execute(Population p). Tutte le classi che hanno la responsabilità della creazione della popolazione devono implementare questa interfaccia e, tramite il polimorfismo, possono quindi gestire la creazione della popolazione iniziale seguendo i diversi metodi.

Selezione delle entità

È possibile definire algoritmi diversi per i diversi tipi di selezione ammessi dall’algoritmo genetico. Nella figura 3 sono presentati ad esempio 3 tipi di selezione di cui viene presentata anche la pseudo codifica.

Figura 3 – Package Selection

Elitism Selection

La selezione per elitismo (cioè dell’elite) permette di selezionare gli individui che presentano una fitness maggiore di una certa soglia, impostata da configurazione. L’elitismo quindi è un metodo che prima copia il miglior cromosoma (o i pochi migliori) nella nuova popolazione, e il resto della selezione viene effettuato nella maniera classica. L’elitismo può far crescere rapidamente le performance degli algoritmi genetici perche’ evita la perdita della soluzione migliore trovata. Di seguito viene presentata la pseudocodifica dell’algoritmo:

Roulette Wheel Selection

La Roulette Wheel Selection è una tecnica utilizzata per effettuare la selezione degli individui da inserire nella mating pool per l’accoppiamento. Questa tecnica è detta “campionamento stocastico con sostituzione” in quando gli individui vengono campionati in base all’inverso del loro valore di fitness, e quindi risultano avere un peso più alto, aumentando così le loro probabilità di selezione.Nella roulette wheel selection, viene assegnata ad ogni individuo una certa probabilità di essere selezionati che risulta proporzionale al loro valore di fitness. Due individui sono scelti in maniera randomica, basandosi sulle loro probabilità. La pseudo codifica dell’algoritmo è la seguente:

Parent Selection

L’algoritmo di Parent Selection opera sugli individui presenti nella mating pool, e seleziona i genitori per sottoporli agli operatori genetici, quali crossover e mutazione.
Gli individui della mating pool hanno la probabilità di essere selezionati in base al valore della loro fitness, anche se risulta comunque presenea nell’algoritmo una componente randomica.
I criteri principali su cui opera la parent selection sono:

• gli individui migliori hanno maggiore probabilità di essere selezionati;
• la scelta è comunque probabilistica;
• anche l’individuo peggiore ha una probabilità di essere selezionato;

Il criterio di rendere partecipi della selezione anche gli individui peggiori permette all’algoritmo genetico di riuscire ad uscire dai minimi locali.

Operatori di riproduzione

Al fine di rendere possibile l’implementazione di diversi tipi di operatori di riproduzione, sarebbe utile definire una classe astratta JeneticOperator che obbliga le classi estese ad implementare il metodo execute.
Gli operatori definiti in questa serie, mostrati in figura 7, sono:

• Crossover: di tipo single point, double point e uniform, che opera su due individui selezionati;
• Mutation: che opera sull’intera popolazione, mutando un bit selezionato in maniera randomica.

Algoritmo Genetico

L’implementazione dell’algoritmo genetico si modella su un pattern comportamentale basato su classi: il pattern Template Method. Questo pattern permette di definire la struttura di un algoritmo lasciando alle sottoclassi il compito di implementarne alcuni passi come preferiscono. In questo modo si può ridefinire e personalizzare parte del comportamento nelle varie sottoclassi senza dover riscrivere più volte il codice in comune. Template Method è uno dei design pattern fondamentali della programmazione orientata agli oggetti, di quelli definiti originariamente dalla cosiddetta Gang of Four, ossia i quattro autori del fondamentale libro Design Patterns [4].

Il pattern è adatto nei seguenti casi:

• quando si vuole implementare la parte invariante di un algoritmo una volta sola e lasciare che le sottoclassi implementino il comportamento che può variare;
• quando il comportamento comune di più classi può essere fattorizzato in una classe a parte per evitare di scrivere più volte lo stesso codice;
• per avere modo di controllare come le sottoclassi ereditano dalla superclasse, facendo in modo che i metodi template chiamino dei metodi gancio (hook) e impostarli come unici metodi sovrascrivibili.

Il pattern è costituito da una classe astratta e una o più classi concrete che la estendono con il meccanismo dell’ereditarietà, che, utilizzando il principio di Hollywood (non chiamarci, ti chiamiamo noi), vengono chiamate dalla classe genitrice.
In questo contesto, la classe che implementa l’algoritmo genetico rispetta i principi di questo pattern e presenta quindi 3 classi di metodi interni:

• Metodi do absolutely this: metodi che definiscono passi necessari all’algoritmo; vengono normalmente implementati solo nella superclasse e non sono visibili alle sottoclassi;
• Metodi primitive operation: metodi che devono essere necessariamente ridefiniti nelle sottoclassi;
• Metodi hook: metodi che possono essere ridefiniti nelle sottoclassi ma, se manca questa implementazione, viene eseguita quella della superclasse.

Di seguito viene presentata l’implementazione generale dell’algoritmo:

public final Entity execute(double fitnessThreshold){
    this.configureGAParameter();
    //begin t-> 0
    //Inizializza una popolazione di cromosomi P(t)
    Population actualGeneration = this.initPopulation(GAConfiguration.populationSize);
    while(actualGeneration.bestEntity().getFitnessScore()<fitnessThreshold){
        //Valuta P(t) usando una funzione di fitness
        this.fitnessEvaluate(actualGeneration);
        //Elitism
        List bestEntities = this.elitism(actualGeneration);
        //Seleziona individui da P(t) e inseriscili nel mating Pool
        int matingPoolSize = actualGeneration.getEntities().size() - bestEntities.size();
        if(matingPoolSize<=0){
            matingPoolSize = 1;
        }
        Population matingPool
        = new Population(this.fitnessSelection(actualGeneration,matingPoolSize),
        matingPool.sumFitnessScore();
        matingPool.sumNormalizedFitnessScore();
        //Ciclo for per fare accoppiare la mating pool
        int couples = matingPoolSize/2;
        for(int i=0; i            //Seleziona due individui dalla MP per gli operatori
            List parents = this.parentSelection(matingPool);
            //Applica il crossover agli individui di MP formando P2
            this.crossover(parents.get(0), parents.get(1));
        }
        //Applica la mutazione agli individui di P2 formando P3
        this.mutation(matingPool);
        //forma P(t + 1) selezionando per rimpiazzamento individui da P3 e P(t)
        actualGeneration = this.replace(matingPool, bestEntities);
        //t -> t + 1
    }
    return actualGeneration.bestEntity();
}

Come si può vedere, la struttura generale dell’algoritmo rispetta in pieno la pseudocodifica proposta ( riportata in figura 9).

All’interno della codifica si possono individuare i metodi che rispettano il pattern template method.

/***** PRIMITIVE OPERATION *****/
/*Devono essere personalizzate nelle sottoclassi */
protected abstract void fitnessEvaluate(Population actualGeneration);
protected abstract void configureGAParameter();
Hook Method
/***** HOOK METHOD *****/
/*Possibilità di personalizzazione, altrimenti utilizza l'implementazione base*/
/**
* Random init of population
* @param entitySize
* @param int populationSize
* @return Population actualGeneration
1.7 Package Jenetic 14
*/
protected Population initPopulation(int populationSize){
    //begin t-> 0
    log.debug("GA Template implementation : random Generation");
    //Inizializza una popolazione di cromosomi P(t)
    IGenerator generator = new RandomGenerator(populationSize);
    return generator.execute();
}
/**
* Select entities for mating Pool from population that have a fitness score for all entities
* Use Roulette Wheel Selection
* @param matingPoolSize
* @param Population fitnessSelected
* @return
*/
protected List fitnessSelection(Population population, int matingPoolSize){
    log.debug("GA Template Implementation : fitness selection");
    ISelector selector = new RouletteWheelSelection (matingPoolSize);
    return selector.select(population);
}
Do Absolutely this
/***** DO ABSOLUTELY THIS *****/
//Passi necessari
/**
* Selezione dei genitori per l'accoppiamento
*/
private final List parentSelection(Population matingPool){
    ISelector selector = new ParentSelection ();
    return selector.select(matingPool);
}
/**
* Elitismo
* @param actualGeneration
* @return
1.7 Package Jenetic 15
*/
private final List elitism(Population actualGeneration) {
    ISelector selector = new ElitismSelection();
    return selector.select(actualGeneration);
}
/**
* Selection for replacing
* @param mutated
* @param bestEntities
* @return
*/
final Population replace(Population mutated, List bestEntities){
    Population nextGeneration = new Population();
    nextGeneration.getEntities().addAll(mutated.getEntities());
    nextGeneration.getEntities().addAll(bestEntities);
    nextGeneration.setSize(mutated.getSize());
    return nextGeneration;
}
/**
* Crossover
* @param entity
* @param entity2
* @return
*/
final List crossover(Entity entity, Entity entity2){
    Crossover crossover = new Crossover(GAConfiguration.crossoverType,entity,entity2);
    crossover.execute();
    return crossover.getOffsprings();
}
/**
* Mutation
* @param crossed
*/
final void mutation(Population crossed){
    Mutation mutation = new Mutation(crossed);
    mutation.execute();
}

Conclusioni

Con questo articolo, in cui abbiamo presentato la pseudocodifica di una possibile implementazione Java di tali algoritmi, si conclude la lunga serie dedicata al tema degli algoritmi genetici, un argomento importante nell’ambito del dibattito sull’intelligena artificiale.

Riferimenti

[1] D.B. Fogel, “Evolutionary computation: toward a new philosophy of machine intelligence”, IEEE Press, NewYork, 1995 ISBN 078035379X

[2] J.R Koza, “Genetic programming: on the programming of computers by means of natural selection”, MIT Press, Cambridge, MA, 1992 ISBN 0262111705

[3] Alden H. Wright, “Genetic Algorithms for Real Parameter Optimization”, 1991

[4] Erich Gamma, Richard Helm, Ralph Johnson, John M. Vlissides, “Design Patterns: Elements of Reusable Object-Oriented Software”, Addison-Wesley

Luana Rinaldi

Luana Rinaldi è nata a Napoli nel 1980. Si è laureata in Ingegneria Informatica presso l‘Università degli studi di Roma Tre, portando avanti una tesi di ricerca in bioinformatica.

Dal 2000 si occupa professionalmente di analisi, progettazione e sviluppo di applicazioni in linguaggio Java con una particolare attenzione alle tecnologie open source più innovative.