Finalità


In questo articolo, vedremo alcune delle basi degli algoritmi genetici, ovvero cosa siano, a cosa servano, perchè vengano chiamati "genetici", e così via. Non si tratterà di un articolo solamente teorico, in quando vedremo come sia possibile implementare un altgoritmo genetico usando Visual Basic .NET. L'articolo è corredato da codice sorgente per permettere all'utente ulteriori sperimentazioni.

Introduzione


Un algoritmo genetico può essere visto come una componente del campo dell'intelligenza artificiale. Si tratta, in sostanza, di una metodologia di ricerca, facente uso di metaeuristica per raggiungere un obiettivo particolare, o per ricercare la soluzione ad un problema. Viene utilizzato il termine "genetico" in quanto, per risolvere un problema, utilizzeremo procedure ispirate al processo di selezione naturale. Non vogliamo semplicemente trovare una soluzione: desideriamo creare un programma che possa "crescere", o "evolvere" verso il nostro obiettivo, e che sia in grado di trovare per proprio conto la strada per giungere a destinazione (o quasi).

Il nostro mondo naturale


Nel suo «Principi di Biologia», Herbert Spencer coniò l'espressione "sopravvivenza del più adatto", quale sinonimo di "più capace nella gestione del contesto corrente". Darwin, nel suo "L'Origine delle Specie", citò Spencer ampliando il concetto esposto con quello di "selezione naturale", espressione che potremmo intendere come "strutturato in modo migliore per un ambito locale immediato". In un ambiente qualsiasi, è l'ambiente stesso a porre gli standard per la determinazione di chi sia "adatto".

Per esempio, in un luogo che ospita forti predatori, un requisito fondamentale alla sopravvivenza potrebbe essere quello di essere molto veloci nella fuga, oppure di saper lottare con efficacia. In un mondo del genere, un veloce corridore o un forte lottatore saranno candidati migliori ad una sopravvivenza migliore o più duratura, rispetto a coloro che sono sprovvisti di tali abilità. Possiamo affermare che il mondo ponga una domanda del tipo: "come puoi trattare con i predatori?" - e che coloro che sanno trovare una buona risposta a tale quesito saranno capaci di sopravvivere (è ovviamente una semplificazione, ma non ci interessa in questa sede rimanere eccessivamente fedeli alle sfaccettature biologiche del problema).

Possiamo identificare alcuni parametri: un mondo in cui vivere (o "un problema da risolvere"), una popolazione che dovrà affrontare le sfide del mondo (o, individui che cercheranno di risolvere i problemi posti dalle condizioni naturali in cui si muovono), una storia riguardante individui che passeranno alle generazioni future la propria esperienza, i propri punti di forza (e quelli di debolezza), il loro DNA, nella speranza che i successori saranno in grado di essere migliori.

Nel settore informatico, è possibile prendere ispirazione dall'approccio biologico riguardo la risoluzione di problemi. La natura non utilizza approcci di tipo brute-force, ma crea una moltitudine di possibili soluzioni dalla ricombinazione di risposte precedenti. Di nuovo, si tratta di un'iper-semplificazione, in quanto in un contesto reale anche il mondo muta i propri requisiti in funzione della mutazione degli abitanti, ma le basi dell'approccio restano comunque valide anche nel mondo digitale. Gli AG (algoritmi genetici) ereditano alcune terminologie proprie della biologia. Possiamo identificare il concetto di cromosoma/individuo, ovvero la singola soluzione ad un dato problema; la popolazione, ovvero l'insieme delle possibili soluzioni; il gene, o la parte (byte) di un individuo; l'adeguatezza, intesa come la percentuale di validità di una soluzione/individuo; il crossing-over, ovvero la ricombinazione delle soluzioni in nuovi modelli; la mutazione, intesa come i cambiamenti casuali (o pseudo tali) che possono prodursi all'interno di una soluzione qualsiasi.

Panoramica di un algoritmo genetico


Consideriamo un semplice problema: abbiamo un obiettivo numerico, per esempio il numero 5. Possiamo pensare a questo numero come alla sfida che il mondo ci sta ponendo (il dominio delle soluzioni). In tale mondo avremo degli abitanti, costituiti da un certo ammontare di operazioni matematiche. Possiamo prendere ad esempio 100 operazioni casuali per iniziare. Ciascuna operazione dovrà confrontarsi con la sfida, cercando di risolverla. Tale confronto è definito "fitness", e questo termine rappresenta, come visto in precedenza, il tasso di adeguatezza in un dato dominio delle soluzioni.

Ad esempio, l'operazione "0+0" avrà un fitness basso, in quanto impossibilitata a produrre un valore vicino al nostro obiettivo, ma "0+5" costituirà una soluzione perfettamente valida. Dovremo pertanto procedere a valutare ciascun membro della popolazione, calcolandone il fitness. Attraverso questo procedimento, troveremo le risposte migliori, o più vicine, al nostro problema. A questo punto, potremo estrarre alcune delle coppie di soluzioni migliori, "accoppiandole" per produrre nuovi elementi che condividano le caratteristiche di entrambi i genitori, e ripetendo il processo per l'interezza della nostra popolazione. Se desideriamo mantenere costante il numero di elementi, dovremo a questo punto scartare un egual numero di individui tra i peggiori.

È quindi nata una nuova generazione di soluzioni - speriamo più vicina al nostro obiettivo - che attende di essere testata contro il nostro problema. Il processo va ripetuto fino al raggiungimento di soluzioni completamente valide, o ritenute soddisfacenti. Gli esseri viventi comunicano il proprio DNA alla prole: in informatica, ogni cosa è composta da bytes, e possiamo considerare tali sequenze come una sorta di DNA digitale, una rappresentazione di ciò che è un individuo. Nell'esempio di cui sopra, potremmo rappresentare un'operazione usando ad esempio 6 bytes: i primi e gli ultimi due come numeri tra 0 e 255 (da 00 a FF), mentre i due bytes mediani potrebbero raffigurare l'operatore (ad esempio, 00 = +, 01 = -, e così via).

Attraverso la fase di accoppiamento, estraiamo una parte di questi bytes da un genitore, ed una parte diversa dall'altro. Combinando tali parti, avremo un nuovo individuo. Come in un ambiente reale, potremo voler introdurre una sorta di "mutazione", che possa alterare in modo arbitrario i geni/bytes che vengono trasmessi. In altre parole, gli AG riguardano la scoperta del percorso migliore per risolvere un problema, creando soluzioni sempre migliori. Perulteriori approfondimenti, si veda la sezione Bibliografia al termine dell'articolo.

Un'implementazione pratica


Dopo questo fiume di parole, vediamo come poter realizzare un meccanismo di questo tipo attraverso la stesura di codice, cercando di beneficiare delle capacità di un AG in modo pratico. Nel codice che segue, discuteremo un problema di tipo grafico: data un'icona-obiettivo, e disponendo di una popolazione di immagini costituita da bytes casuali, cercare di "evolvere" detta popolazione verso l'obiettivo, nella speranza di raggiungerlo completamente (ovvero, almeno una soluzione sarà identica all'immagine rappresentante il nostro modello).

Come detto in apertura, utilizzeremo Visual Basic. L'utente finale sarà in condizione di poter scegliere un file ICO delle dimensioni di 16 x 16 pixels, ed il programma genererà una popolazione costante di 100 elementi. Per ciascuno di questi elementi, valuteremo il tasso di fitness, e sarà semplice farlo: dal momento che un'icona è un insieme di bytes, confronteremo ciascuno di essi con ciascun byte del nostro obiettivo. Maggiori saranno le similitudini, più alto sarà il fitness, e migliore l'immagine. Per ciascuna generazione di soluzioni, estrarremo 4 elementi da accoppiare, dai quali generare 4 nuove selezioni in cui riprodurre i bytes dei genitori, scartando poi i 4 elementi peggiori per mantenere costante la popolazione.

La classe GAImage, immagine "genetica"


La classe che rappresenta la nostra immagine "genetica" può essere scritta come segue:

Public Class GAImage
  
    Const _FIXED_BYTES As Integer = 42
  
    Dim _targetBytes() As Byte
  
    Dim _personalBytes() As Byte
    Dim _isMutable() As Boolean
  
    Public ReadOnly Property FixedBytes As Integer
        Get
            Return _FIXED_BYTES
        End Get
    End Property
  
    Public Property PersonalBytes As Byte()
        Get
            Return _personalBytes
        End Get
        Set(value As Byte())
            _personalBytes = value
        End Set
    End Property
  
    Public ReadOnly Property Fitness As Single
        Get
            Dim _fitness As Single = 0
            For ii As Integer = 0 To _targetBytes.Length - 1
                If _targetBytes(ii) = _personalBytes(ii) Then
                    _fitness += 1
                    _isMutable(ii) = False
                End If
  
            Next
            Return _fitness
        End Get
    End Property
  
    Public ReadOnly Property FitnessPercent As Single
        Get
            Return (Me.Fitness * 100 / _targetBytes.Length).ToString("000.00")
        End Get
    End Property
  
    Public Function isByteMutable(numByte As Integer) As Boolean
        Return _isMutable(numByte)
    End Function
  
    Public Sub New(_target() As Byte, _code() As Byte, Optional randomInit As Boolean = True)
        ReDim _personalBytes(_target.Length - 1)
        ReDim _targetBytes(_target.Length - 1)
        _targetBytes = _target
  
        ReDim _isMutable(_target.Length - 1)
        For ii As Integer = 0 To _isMutable.Length - 1
            _isMutable(ii) = True
        Next
  
        For ii As Integer = 0 To _FIXED_BYTES
            _personalBytes(ii) = _targetBytes(ii)
        Next
  
        If Not randomInit Then Exit Sub
  
        Randomize()
        For ii As Integer = _FIXED_BYTES + 1 To _targetBytes.Length - 1
            _personalBytes(ii) = _code(Int(Rnd() * (_code.Length - 1)))
        Next
    End Sub
  
End Class


Il suo costruttore richiede una copia dei bytes dell'obiettivo, un set di bytes da cui estrarre i bytes che costituiranno il codice del nuovo individuo, ed un flag che determina se è necessario eseguire un'inizializzazione casuale (a seguire ulteriori spiegazioni). La classe espone alcune proprietà: PersonalBytes permette l'accesso al "codice genetico" dell'individuo, in termini di array dei bytes che lo costituiscono; Fitness calcola quanto l'immagine corrente e quella bersaglio siano simili.

Tramite l'array _isMutable, imposteremo un'eventuale resistenza aggiunta alla mutazione per uno specifico byte, cercando di "mimare" quelli che, per una specie, rappresentano i tratti genetici solidamente acquisiti); FitnessPercent espone semplicemente il valore di Fitness in forma percentuale; FixedBytes ha invece un'utilità di tipo "tecnico": dal momento che i primi 42 bytes rappresentano l'intestazione binaria di un file ICO, essi devono essere condivisi tra bersaglio e possibili soluzioni, per poter produrre immagini valide e visualizzabile. In questa classe, abbiamo tutto ciò che occorre alla creazione di icone che seguano un pattern genetico.

Abbiamo necessità di un contesto in cui lo sviluppo delle soluzioni possa aver luogo. Un semplice Form in cui osservare le modifiche alle nostre generazioni andrà bene.

Il campo giochi


Vediamo quale sarà l'aspetto finale del nostro Form:



Il tasto "Choose target" permette all'utente la selezione di un'icona, ovvero dell'immagine che vorremo raggiungere evolvendo le nostre soluzioni. Cento PictureBox, dinamicamente create, conterranno l'output relativo a ciascuna GAImage. Vengono generate delle GAImage casuali, e possiamo vedere come nessuna di queste abbia la benchè minima correlazione con il nostro obiettivo, esponendo situazioni piuttosto caotiche. Ad ogni modo, valutando ciascuna di essere potremo senz'altro identificare le migliori, ed iniziare i cicli di accoppiamento.

Vediamo un'esecuzione tipica, per discuterne poi le diverse parti



Salterò interamente le parti relative alla creazione dei controlli, che il lettore potrà vedere nel codice sorgente. Ciò che verrà discusso qui è strettamente inerente agli aspetti legati agli AG. Di conseguenza, il codice che segue sarà volutamente incompleto rispetto aquello scaricabile, in modo da essere maggiormente chiaro rispetto alla tematica principale. Suggerisco lo scaricamenteo del progetto per una panoramica più vasta.

Creazione di un set di soluzioni iniziale


Aprendo la nostra immagine-obiettivo, potremo accedere ai bytes che la costituiscono. I bytes dell'immagine bersaglio saranno il nostro codice genetico ideal, ed ogni byte distinto rappresenterà un elemento del set a cui accedere per attingere le informazioni necessarie alla creazione del codice delle possibili soluzioni. 

Private Sub LoadImage(path As String)
    Dim b As New Icon(path)
    pbOriginal.Image = b.ToBitmap
  
    Dim ms As New MemoryStream
    b.Save(ms)
    ReDim _targetBytes(ms.ToArray.Length - 1)
    _targetBytes = ms.ToArray
  
    _GACode = New List(Of Byte)
    Dim _tmpCode As New List(Of Byte)
    _tmpCode.AddRange(_targetBytes)
    _GACode.AddRange(From bt As Byte In _tmpCode Distinct Select bt)
End Sub


L'icona selezionata verrà scritta nel PictureBox pbOriginal. I suoi bytes saranno letti attraverso un MemoryStream, e scritti nell'array _targetBytes. Da talearray estrarremo dei valori distinti, per popolare una lista di possibili "geni" da impiegare nella creazione di nuove icone. Si può pensare a tale lista come alle componenti del nostro codice genetico: il DNA è costituito da 4 elementi fondamentali, ovvero adenina, guanina, citosina, timina. Il codice delle nostre icone, quindi, non attinge alla casualità più completa, bensì da un numero di possibilità precostituite. Se, ad esempio, tra i bytes costituenti il codice dell'immagine iniziale, non è presente il byte AF, nessuna delle possibili soluzioni conterrà mai tale byte, in quanto esso non sarà presente nel codice da cui estrarre i possibili "geni".

Private Sub InitializePopulation()
    _GAPopulation = New List(Of GAImage)
  
    For ii As Integer = 0 To _SAMPLE_NUMBER - 1
        Dim _ga As New GAImage(_targetBytes, _GACode.ToArray)
        _GAPopulation.Add(_ga)
  
        Dim pb As PictureBox = CType(GroupBox3.Controls("pbSample" & ii.ToString("00")), PictureBox)
        Try
           pb.Image = Image.FromStream(New MemoryStream(_ga.PersonalBytes))
        Catch
        End Try
    Next
End Sub


Popoliamo una lista di partenza costituita da GAImage, inizializzando ciascuna di essere con l'insieme dei bytes dell'immagine obiettivo (procedimento utile al successivo calcolo del fitness), e passando l'insieme del "pool genetico" a cui poter attingere per l'estrazione dei bytes. Si consiglia di fare riferimento alla classe GAImage riportata sopra per ulteriori dettagli sulla procedura di inizializzazione. L'icona da me utilizzata per i test qui riportati ha lunghezza di 318 bytes: è quindi molto improbabile che uno qualsiasi dei membri della popolazione originale produca il nostro risultato finale. Diventa necessario eseguire i cicli di accoppiamento descritti sopra, in modo da combinare gli elementi migliori di ciascuna generazione.

Una proposta per l'evoluzione


Propongo qui a seguire un possibile approccio al comportamento evolutivo. Nel mio codice, tale procedura inizia alla pressione del tasto Button2. Di nuovo, il codice non strettamente relativo agli AG è stato omesso (fare riferimento al sorgente completo)

Private Sub Button2_Click(sender As Object, e As EventArgs) Handles Button2.Click
    ' omissione
  
    While _runFlag
        ' omissione
  
        Dim bestSamples As IEnumerable(Of GAImage) = From ga As GAImage In _GAPopulation Order By ga.Fitness Descending Take (4)
              
        ' omissione
  
        If bestSamples(0).FitnessPercent > 95 Then Button3_Click(sender, e)
  
        Dim sample01 As GAImage = GenerateImage(bestSamples(0), bestSamples(1))
        Dim sample02 As GAImage = GenerateImage(bestSamples(1), bestSamples(0))
        Dim sample03 As GAImage = GenerateImage(bestSamples(2), bestSamples(3))
        Dim sample04 As GAImage = GenerateImage(bestSamples(3), bestSamples(2))
  
        _GAPopulation.Insert(0, sample01)
        _GAPopulation.Insert(1, sample02)
        _GAPopulation.Insert(2, sample03)
        _GAPopulation.Insert(3, sample04)
  
        Dim worstSamples As IEnumerable(Of GAImage) = From ga As GAImage In _GAPopulation Order By ga.Fitness Ascending Take (4)
        _GAPopulation.Remove(worstSamples(0))
        _GAPopulation.Remove(worstSamples(1))
        _GAPopulation.Remove(worstSamples(2))
        _GAPopulation.Remove(worstSamples(3))
  
        ' omissione
    End While
End Sub


Semplicemente, si esegue un loop indefinito nella lista di GAImages (o almeno fino al raggiungimento del 95% dell'obiettivo), prelevando ogni volta 4 esemplari tra i migliori, e combinando i loro bytes. Inseriamo i 4 individui creati in cima alla lista (supponiamo siano i migliori), e rimuoviamo un egual numero di elementi tra quelli aventi il peggior fitness. È possibile, nel caso qualcosa "vada storto" durante la fase di accoppiamento/mutazione, che una tra le soluzioni di nuova generazione risulti peggiore di una pre-esistente: se rientra tra le 4 peggiori, viene scartata.

Private Function GenerateImage(firstGA As GAImage, secondGA As GAImage) As GAImage
    Dim _ga As New GAImage(_targetBytes, _GACode.ToArray, False)
    For ii As Integer = _ga.FixedBytes To firstGA.PersonalBytes.Length - 1 Step 1
        _ga.PersonalBytes(ii) = IIf(secondGA.isByteMutable(ii), Mutation(secondGA.PersonalBytes(ii), 2), Mutation(secondGA.PersonalBytes(ii), 20))
    Next
    Return _ga
End Function


L'accoppiamento è piuttosto semplice: ogni byte accessibile del primo esemplare viene ciclato, ed il byte risultante è calcolato come segue: se lo stesso byte del secondo elemento è resistente alla mutazione, allora tenteremo di variarlo con un tasso di successo pari a 1/20. In caso contrario, useremo un tasso di 1/2.

Private Function Mutation(bt As Byte, rate As Byte) As Byte
    Randomize()
    Dim prob As Integer = Int(Rnd() * rate)
  
    If prob Mod rate = 0 Then
        Return _GACode(Int(Rnd() * (_GACode.Count - 1)))
    Else
        Return bt
    End If
End Function


La chiamate a Mutation() avviene in modo probabilistico: se tale probabilità è riscontrata, il byte in questione viene estratto casualmente dal pool di byte possibili. In caso contrario, il byte del secondo elemento, avente lo stesso indice del primo, viene propagato nel nuovo elemento. Il ciclo, attraverso ciascuna generazione/popolazione, ci condurrà con una certa approssimazione verso il risultato finale. Questo è solo uno dei metodi che può essere impiegato per l'implementazione di un AG: lo sviluppatore è - in sostanza - il giudice che determina quali siano i parametri che entrano in gioco, e quali siano la regole generali da applicare per la risoluzione di un particolare problema.

Nel nostro caso, purchè producano risultati validi ed "evolutivi", altri approcci sono possibili.
 

Video esempio


Un video di esempio relativo ad una sessione di esempio piò essere visto a questo indirizzo: g6JebAjtWQ

Download codice sorgente


Bibliografia