Algoritmi genetici - Argomenti avanzati

In questa sezione vengono presentati alcuni argomenti avanzati in Algoritmi genetici. Un lettore che cerca solo un'introduzione alle GA può scegliere di saltare questa sezione.

Problemi di ottimizzazione vincolata

I problemi di ottimizzazione vincolata sono quei problemi di ottimizzazione in cui dobbiamo massimizzare o minimizzare un dato valore di funzione obiettivo che è soggetto a determinati vincoli. Pertanto, non tutti i risultati nello spazio della soluzione sono fattibili e lo spazio della soluzione contiene regioni ammissibili come mostrato nell'immagine seguente.

In un tale scenario, gli operatori di crossover e di mutazione potrebbero darci soluzioni che sono irrealizzabili. Pertanto, meccanismi aggiuntivi devono essere impiegati nel GA quando si tratta di problemi di ottimizzazione vincolati.

Alcuni dei metodi più comuni sono:

• Utilizzando penalty functions che riduce l'idoneità delle soluzioni non fattibili, preferibilmente in modo che l'idoneità sia ridotta proporzionalmente al numero di vincoli violati o alla distanza dalla regione ammissibile.

• Utilizzando repair functions che prendono una soluzione irrealizzabile e la modificano in modo da soddisfare i vincoli violati.

• Not allowing infeasible solutions entrare nella popolazione.

• Usare un special representation or decoder functions che garantisce la fattibilità delle soluzioni.

Background teorico di base

In questa sezione, discuteremo del teorema Schema e NFL insieme all'ipotesi dei blocchi costitutivi.

Teorema dello schema

I ricercatori hanno cercato di capire la matematica alla base del funzionamento degli algoritmi genetici e lo Schema Theorem di Holland è un passo in quella direzione. Nel corso dell'anno sono stati apportati vari miglioramenti e suggerimenti al Teorema dello schema per renderlo più generale.

In questa sezione, non approfondiamo la matematica del Teorema dello schema, piuttosto cerchiamo di sviluppare una comprensione di base di cosa sia il Teorema dello schema. La terminologia di base da conoscere è la seguente:

• UN Schemaè un "modello". Formalmente, è una stringa sull'alfabeto = {0,1, *},

  dove * è non importa e può assumere qualsiasi valore.

  Pertanto, * 10 * 1 potrebbe significare 01001, 01011, 11001 o 11011

  Dal punto di vista geometrico, uno schema è un iperpiano nello spazio di ricerca della soluzione.

• Order di uno schema è il numero di posizioni fisse specificate in un gene.

• Defining length è la distanza tra i due simboli fissi più lontani nel gene.

Il teorema dello schema afferma che questo schema con fitness superiore alla media, lunghezza di definizione corta e ordine inferiore ha maggiori probabilità di sopravvivere al crossover e alla mutazione.

Ipotesi dei mattoni

I blocchi predefiniti sono schemi di lunghezza ridotta, di bassa definizione con l'idoneità media sopra indicata. L'ipotesi di elementi costitutivi afferma che tali elementi costitutivi servono come base per il successo e l'adattamento delle GAs man mano che progredisce identificando e ricombinando successivamente tali "building blocks".

Teorema di No Free Lunch (NFL)

Wolpert e Mac già nel 1997 hanno pubblicato un articolo intitolato "No Free Lunch Theorems for Optimization". In sostanza afferma che se facciamo una media sullo spazio di tutti i possibili problemi, tutti gli algoritmi della scatola nera non rivisitati mostreranno le stesse prestazioni.

Significa che più comprendiamo un problema, il nostro GA diventa più specifico per il problema e offre prestazioni migliori, ma compensa ciò eseguendo male per altri problemi.

Apprendimento automatico basato su GA

Gli algoritmi genetici trovano applicazione anche nell'apprendimento automatico. Classifier systems sono una forma di genetics-based machine learning(GBML) che vengono frequentemente utilizzati nel campo del machine learning. I metodi GBML sono un approccio di nicchia all'apprendimento automatico.

Esistono due categorie di sistemi GBML:

• The Pittsburg Approach - In questo approccio, un cromosoma codifica una soluzione, quindi l'idoneità viene assegnata alle soluzioni.

• The Michigan Approach - una soluzione è tipicamente rappresentata da molti cromosomi e quindi l'idoneità è assegnata a soluzioni parziali.

Va tenuto presente che i problemi standard come crossover, mutazione, Lamarckian o Darwiniano, ecc. Sono presenti anche nei sistemi GBML.