ABiDEvoCOM.dll:

La libreria è strutturata attraverso diverse cartelle raggruppanti le varie tipologie di operatori genetici, strategie evolutive (selezione, mutazione, crossover, etc.) ed utilità e strumenti di programmazione ad oggetti (interfacce, serializzatori, eventi, enumerazioni, etc.).

La classe Chromosome.cs rappresenta il cromosoma impiegato nell'algoritmo genetico (o configurazione nelle strategie evolutive in generale). Il cromosoma è composto da una lista di geni ed ha un valore di fitness associato; quest'ultimo valore indica la qualità del cromosoma come soluzione del problema che si stà cercando di risolvere.

La classe EvolutionaryAlgorithm.cs rappresenta l’algoritmo evolutivo nella sua completezza, definendone il metodo con cui verrà:

1. Inizializzato il problema; 2. Determinato il genotipo; 3. Costruito il DOE;

4. Definita la funzione di penalizzazione; 5. Condotta la selezione;

6. Elaborato il crossover; 7. Generata la mutazione;

8. Eseguita la sostituzione con riposizionamento.

Inoltre, sono caratterizzate le proprietà del numero delle configurazioni figlio, il numero delle generazioni e il numero delle configurazioni della generazione di partenza, i cui valori sono definiti nel core, come descritto nel paragrafo precedente.

Il flusso del codice è gestito all’interno della libreria dalla chiamata dell’unità principale a uno dei due metodi di risoluzione del problema definiti in EvolutionaryAlgorithm, ossia SolveWithImprovement e SolveWithoutImprovement: il primo esegue una risoluzione del problema in un numero di generazioni non predefinito facendo uso della tecnica di miglioramento, ossia l'algoritmo termina solo quando non ci sono altre soluzioni migliori per un numero n di generazioni sucessive1, restituendo in uscita il miglior individuo trovato; il secondo metodo esegue un numero di generazioni finito e al termine restituisce il miglior cromosoma determinato.

1 In caso venga scelto questo approccio il numero di generazioni in cui verrà eseguito il controllo sull’individuo migliore è definito dalla variabile d’impostazione

All’interno dei metodi prima descritti è definita la tipica sequenza di azioni svolta da una strategia evolutiva e nello specifico da un algoritmo genetico. Come in tutte le classi di definizione generale, anche per la classe definente l’algoritmo vi sono le validazioni dei parametri passati come argomenti nel costruttore, al fine di prevenire eventuali errori d’inserimento dati; le validazioni in caso di esito negativo sollevano delle eccezioni di tipo ABiDException, le quali sono opportunamente gestite dal codice e facilmente rintracciabili dall’utente.

Per quanto concerne l’oggetto di tipo Chromosome si nota come grazie alla caratteristica label e al metodo GetChromosomeLabel() si perviene alla definizione di un’etichetta descrivente univocamente la configurazione, ossia il fenotipo il quale viene serializzato e codificato in una stringa.

Attraverso un controllo sull’etichetta ad inizio ciclo di progettazione può dunque esser valutata l’ipotesi di avviare la progettazione al fine di calcolare vincoli di progetto e obiettivi, oppure se copiarne direttamente i valori di una configurazione uguale precedentemente computata, con notevole risparmio in termini computazionali.

Figura. 4.13: Visualizzazione grafica del contenuto delle classi: a sinistra

EvolutionaryAlgorithm e a destra Chromosome

Per quanto concerne la gestione degli operatori genetici, delle operazioni evolutive e di tutti i moduli aperti di ABiDEvoCOM.dll è stato fatto uso di dichiarazione di metodo esplicita mediante impiego di delegati e classi astratte.

Di seguito sono presentati gli algoritmi implementati e la struttura generale per ogni operazione e di ogni operatore, dando una breve descrizione e per i casi più interessanti descrivendo il flusso logico che li supporta.

La selezione:

La classe astratta (Fig. 5.13) rappresentante la selezione richiede come argomenti in ingresso, validandone il contenuto, il numero delle configurazioni genitori che devono essere selezionate, il generatore di numeri casuali e la strategia evolutiva intrapresa.

Figura 4.14: Visualizzazione grafica della gerarchia delle classi, in alto la classe astratta dalla quale ereditano ed estendono le proprietà le classi derivate (in basso)

Gli algoritmi di selezione sino ad ora implementati sono: 1. La selezione a roulette;

2. La selezione a torneo;

3. La selezione a campionamento stoccastico globale (o generale). La scalatura della funzione di fitness:

Nel processo di selezione visto nel paragrafo precedente si perviene alla selezione delle configurazioni mediante determinazione di liste o vettori ordinati o meno, contenenti i valori della funzione di fitness. Tali valori in ABiDEvoCOM.dll non sono dati direttamente dalla funzione di fitness, bensì sono scalati secondo diversi metodi facenti capo alla medesima classe astratta ScalingAlgorithm.

Figura 4.15: Visualizzazione grafica della gerarchia delle classi, in alto la classe astratta dalla quale ereditano ed estendono le proprietà le classi derivate (in basso)

La scalatura della funzione di fitness è utile per prevenire la formazione di super cromosomi come visto per il ranking ed inoltre è utile per i casi riguardanti popolazioni con convergenze piuttosto ampie, dove la competizione tra i cromosomi è meno forte ed il comportamento che emerge nella ricerca è casuale.

La scalatura della funzione di fitness ha dunque due principali obiettivi:

1. Mantenere una ragionevole differenza tra i valori relativi di fitness dei cromosomi; 2. Prevenire un rapido predominio da parte di super cromosomi inizialmente limitando

la competizione, per poi stimolarla.

In generale la funzione di fitness scalata , definita a partire dalla funzione di fitness per il -esimo cromosoma è espressa come(3):

Dove la funzione trasforma la funzione di fitness nella funzione di fitness scalata. Le equazioni impiegate nell’algoritmo sono:

1. La funzione LinearRankScaling:

2. La funzione ExponentialRankScaling si basa su un fattore c, il quale rappresenta la pressione di selezione ed è compreso nell’intervallo aperto (0,1):

3. La funzione NormalizingScaling (4) dinamica è caratterizzata dalla seguente formula nel caso l’obiettivo della strategia sia la massimizzazione:

Nel caso l’obiettivo della strategia sia invece la minimizzazione:

Il parametro è definito nell’intervallo aperto (0,1) e serve per prevenire divisioni per zero, e per aggiustare il comportamento della selezione tra proporzionale al fitness (caso limite ) e casuale (caso limite ).

Replacement:

Gli algoritmi di sostituzione rientrano di fatto nelle operazioni evolutive. Essi sono impiegati al termine dell’applicazione degli operatori convenzionali del GA allo scopo di mantenere nelle generazioni gli individui migliori. La classe astratta (ReplacementAlgorithm) di definizione di tutti gli algoritmi di replacement implementati in ABiDEvoCOM definisce la dimensione della nuova popolazione e l’obiettivo della strategia evolutiva.

Figura 4.16: Visualizzazione grafica della gerarchia delle classi, in alto la classe astratta di sostituzione dalla quale ereditano ed estendono le proprietà le classi derivate (in basso)

Gli algoritmi di sostituzione restituiscono all’uscita una popolazione di cromosomi scelti tra i migliori, i quali verranno confrontati con quelli costituenti la popolazione corrente. L’algoritmo più noto e largamente impiegato è l’ElitismReplacement; tale algoritmo si basa sul concetto dell’elitarismo, ossia il miglior individuo di una vecchia popolazione viene trasmesso alla generazione successiva senza che debba superare la fase di selezione. In altri termini egli sopravvive automaticamente alla selezione che avviene al termine di ogni generazione. L'obiettivo di questa tecnica è quello di non perdere informazioni su una zona promettente nello spazio delle soluzioni. A tal fine sono selezionati gli N migliori individui in ogni generazione, dove N è un parametro definito dall’operatore ad inizio progetto (numberParents).

L’algoritmo di children replacement restituisce un set di cromosomi scelti tra i migliori della popolazione corrente; la dimensione della popolazione restituita o dei sopravvissuti (survivors) è data dal parametro definito nella classe astratta.

Ultimo algoritmo di selezione implementato è il competence replacement, il quale restituisce una popolazione avente i migliori individui della popolazione corrente e della popolazione costituente la generazione precedente. La differenza con l’elitarismo è data dal numero d’individui restituiti che in quest’ultimo caso sono in numero inferiore alla