Reti neurali attraverso algoritmi genetici in C++. Parte IV
9 December 2008 da Francesco
Le classi Chromosome e Population.
Abbiamo finito l’implementazione della rete ed ora possiamo passare alla parte relativa all’addestramento della stessa, che come ho già detto, verrà realizzata tramite algoritmi genetici. Vediamo la classe Chromosome:
class Chromosome {
public:
Chromosome(int c_w);
Chromosome(vector<double> weights); // overload
void setWeight(int i, double val);
double getWeight(int i) const;
void setFitness(double fit);
double getFitness() const;
int getWeightsNum() const;
void mutate();
private:
vector<double> DNA;
double fitness;
};
Innanzitutto essa possiede due costruttori. Il primo serve nel caso volessimo inizializzare un cromosoma con pesi random specificando solamente il numero dei pesi (in pratica la lunghezza del DNA); il secondo serve quando vogliamo creare un cromosoma con dei pesi ben precisi passandogeli come argomento: quest’ultimo viene usato per implementare una funzione che permette di salvare i pesi dopo che la rete neurale è allenata e di poterli caricare per evitare di dover ripetere ogni volta l’allenamento.
Come potete vedere le funzioni getWieght(int) e setWeight(int, double) hanno dei compiti abbastanza evidenti così come setFitness(double) e getFitness().
La funzione mutate() applica il famoso operatore genetico delle mutazione al cromosoma, vediamone il codice:
void Chromosome::mutate() {
if (dRand() <= MUTATION_RATE) {
DNA[rand()%DNA.size()] += wRand()*MAX_PERTURBATION;
}
}
Viene generato un numero random compreso tra 0 e 1 e se è minore del valore di MUTATION_RATE la mutazione viene effettuata. Nella parte sugli algoritmi genetici avevamo visto che, quando il DNA è codificato in forma binaria la mutazione agisce semplicemente trasformando uno 0 in un 1 o viceversa. Nel nostro caso, invece, la mutazione non fa altro che aggiungere o sottrarre un piccolo valore compreso tra 0 e MAX_PERTURBATION ad un peso qualsiasi del DNA (wRand() genera infatti un numero compreso tra -1 e 1 quindi il valore di MAX_PERTURBATION può essere sottratto o aggiunto, a seconda del numero generato da wRand()).
La classe Population ingloba un array di oggetti Chromosome* cioè la popolazione vera e propria, più una serie di metodi come la riproduzione, il crossover, etc… ecco il codice:
class Population {
public:
Population(int c_num, int c_numw);
void crossover(Chromosome* a1, Chromosome* a2, Chromosome* b1, Chromosome* b2);
Chromosome* getChromosomeFromTournament();
void next();
Chromosome* best();
Chromosome* worst();
Chromosome* operator[](int i);
private:
int length;
vector<Chromosome*> popv;
};
Il costruttore è abbastanza semplice: prende come argomenti il numero di individui di cui è formata la popolazione, ed il numero di pesi per ogni individui cioè la lunghezza del DNA (che chiaramente è uguale per tutti gli individui).
Il metodo del crossover incrocia il DNA dei primi due cromosomi che gli passiamo come argomento e lo mette negli ultimi due, sempre se il numero random generato sia minore della costante CROSSOVER_RATE: un valore di quest’ultima costante pari a 0.7, per esempio, vuol dire che nel 70% dei casi il crossover viene effettuato. Se ciò non avviene gli individui si riproducono così come sono.
void Population::crossover(Chromosome* a1, Chromosome* a2, Chromosome* b1, Chromosome* b2) {
if (dRand() <= CROSSOVER_RATE) {
int crosspoint = rand()%length;
for (int i = 0; i < crosspoint; i++) {
b1->setWeight(i, a1->getWeight(i));
b2->setWeight(i, a2->getWeight(i));
b1->setWeight(length-(i+1),
a1->getWeight(length-(i+1)));
b2->setWeight(length-(i+1),
a2->getWeight(length-(i+1)));
}
} else { // Se non fa il crossover riproduce gli stessi cromosomi.
b1 = a1;
b2 = a2;
}
}
La funzione getChromosomeFromTournament() svolge il cosiddetto “torneo” fra i cromosomi e seleziona quello con il miglior fitness. Essa non è altro che il nostro metodo di selezione:
Chromosome* Population::getChromosomeFromTournament() {
vector<Chromosome*> r;
for (int i = 0; i < NUM_TOUR; i++) {
r.push_back(popv[rand()%popv.size()]);
}
sort(r.begin(), r.end(), compareChromosomes);
return r[0];
}
Per svolgere il “torneo” viene creato un vettore che conterrà i cromosomi scelti casualmente dalla popolazione: NUM_TOUR è un’altra costante che definisce quanti cromosomi saranno scelti. Più NUM_TOUR è alta più basse saranno le probabilità degli individui più deboli di sopravvivere e ricordate che questo può non essere sempre un vantaggio; nel caso estremo in cui NUM_TOUR sia uguale alla grandezza della popolazione verrebbe sempre e solo scelto il cromosoma migliore della prima generazione (che poi tanto buono non è visto che nella prima generazione il DNA è random) portando così a tutt’altro che la soluzione del problema.
L’array così ottenuto viene ordinato in base al fitness (la funzione compareChromosomes() non fa altro che restituire il cromosoma che ha il fitness minore tra i due che riceve come argomento) e così l’elemento 0 dell’array conterrà quello con il fitness più basso (ricordate che per noi fitness più basso equivale ad errore più basso e quindi a punteggio migliore) mentre l’ultimo quello con fitness più alto. Questa funzione, insieme a quella del crossover, viene utilizzata nel metodo next() che effettua la riproduzione dell’intera popolazione finchè non si ha una nuova popolazione con lo stesso numero di individui della precedente.
void Population::next() {
vector<Chromosome*> newPop;
sort(popv.begin(), popv.end(), compareChromosomes);
Chromosome* b1 = new Chromosome(length);
Chromosome* b2 = new Chromosome(length);
// Garantisce la sopravvivenza dell'inviduo con il fitness piu' alto
// della popolazione precedente.
for (int i = 0; i < ELITISM; i++) {
newPop.push_back(popv[0]);
}
while (newPop.size() < popv.size()) {
Chromosome* a1 = getChromosomeFromTournament();
Chromosome* a2 = getChromosomeFromTournament();
crossover(a1, a2, b1, b2);
b1->mutate();
b2->mutate();
newPop.push_back(b1); newPop.push_back(b2);
}
popv = newPop;
}
Viene creato inizialmente un nuovo vettore che conterrà i nuovi individui ed il vettore contenente la popolazione viene ordinato in ordine di fitness (come abbiamo fatto nel metodo per svolgere il “torneo”): questo serve per mettere in atto un procedimento particolare definito elitismo. L’elisitmo consiste nel fare sopravvivere sempre, nella generazione successiva, una o più copie dell’elemento che nella generazione precedente aveva totalizzato il punteggio migliore: questo ci garantisce che, quali che siano le ricombinazioni che vengono effettuate sui nuovi individui, non perderemo mai il risultato raggiunto, e inoltre, queste copie possono fornire un aiuto decisivo al raggiungimento della soluzione. ELITISM è una costante che definisce quante copie del miglior cromosma vadano inserite nella nuova popolazione. Nel ciclo while vengono selezionati due cromosomi dal “torneo”, viene fatto su di loro il crossover e sui nuovi individui generati viene effettuata una mutazione (sempre con la percentuale che abbiamo stabilito nella costante MUTATION_RATE) e poi vengono inseriti nel nuovo vettore. Quando questo vettore raggiunge le dimensioni della vecchia popolazione, si esce dal ciclo ed esso viene copiato sulla popolazione originale.
Le altre funzioni della classe sono abbastanza ovvie: best() serve a selezionare il cromosoma con il fitness migliore, worst() il peggiore e l’overloading dell’operatore [] ci permette di accedere ai membri della popolazione come se fossero elementi di un array senza dover scrivere un apposita funzione del tipo getChromosome(int i) (come quella che abbiamo usato per i neuroni: volendo anche lì si può fare infatti l’overloading dell’operatore []).
Manca solo una classe per riunire tutto il codice che abbiamo fatto fino ad ora e la nostra rete sarà utilizzabile (anche se, in pratica, e’ utilizzabile anche da adesso con qualche sforzo in più): la vedremo nella prossima parte, intanto vi do i link a tutte le parti precedenti:
- Reti neurali e algoritmi genetici I
- Reti neurali e algoritmi genetici II
- Reti neurali e algoritmi genetici III
Alla prossima…
Tags: Algoritmi genetici, Intelligenza artificiale, Reti neurali
Pubblicato in Informatica | Commenti (1)
11 December 2008 alle 16:47
Davvero interessanti questi articoli, debbo dire che la ricerca scientifica ha fatto notevoli passi in avanti. Pensa che quando io ero giovane, i computer riuscivano a malapena a completare un elevamento a potenza, ed ora cosa mi ritrovo? Gli algoritmi genetici.
Bè, che dire, nel futuro ci sarà di che meravigliarsi.