Gli algoritmi genetici sono algoritmi che emulano l'evoluzione di una popolazione in cui viga la legge di sopravvivenza del più adatto. In questo articolo presenterò brevemente come si implementa in linea teorica (e pratica) un algoritmo genetico.

Gli algoritmi genetici vengono usati sostanzialmente per risolvere problemi di massimizzazione. Vengono adottati a favore di altri metodi, ad esempio, perchè il problema è difficilmente formalizzabile, o perchè non esistono basi teoriche forti che supportino la scrittura di un codice adeguato. Una volta posto il problema, si vuole far evolvere una popolazione di soluzioni possibili fino a che non se ne trovi una ottima, che non necessariamente è la soluzione esatta (ma piuttosto quella meno sbagliata). Per esemplificare i passaggi che andrò ad illustrare, cercheremo di risolvere questo problema: Si hanno 10 variabili, a₁, a₂, ... a₁₀. Tutte devono contenere valori distinti e compresi tra 1 e 20. Si vuole trovare la combinazione ottima di numeri tale sia massima l'espressione: In questo caso siamo favoriti dalla formulazione del problema perchè, come spiegherò tra breve, disponiamo già della funzione di fitness. Tuttavia attaccare questo problema con i metodi tradizionali non sarebbe possibile: andando di brute force si sprecherebbe più tempo (sebbene gli algoritmi gentici siano una specie di brute force migliorato); usando strumenti matematici quali derivate parziali, si potrebbe formalizzare il problema, ma se la richiesta cambiasse anche solo di poco si dovrebbero rifare tutti i calcoli e riscrivere di conseguenza il codice.

Per iniziare, dobbiamo disporre di un insieme di soluzioni possibili, ossia dei vettori casuali di 10 numeri compresi tra 1 e 20. Non è detto che queste soluzioni siano le migliori per il problema, anzi, è altamente improbabile che lo siano poiché sono per ipotesi casuali. Esse costituiscono il cosiddetto genetic pool, o, più semplicemente, la popolazione della cui evoluzione ci occuperemo. Il numero di soluzioni possibili presenti nel pool iniziale è arbitrario e definisce uno dei 4/5 parametri importanti dell'algoritmo: più individui favoriscono una maggiore varietà, ma al contempo incrementano il tempo necessario per passare alla generazione successiva (poiché ci sono più informazioni da processare). Cominciamo con lo scrivere un codice che produca le nostre sequenze di numeri:

Module Module1

    'In questa classe scriveremo tutto il codice dell'algoritmo genetico
    Public Class GeneticEngine
        Private _Population As List(Of Int32())

        'La popolazione delle soluzioni. Ogni soluzione è, come avevamo detto,
        'una serie di 10 numeri, ossia un vettore di interi
        Public ReadOnly Property Population() As List(Of Int32())
            Get
                Return _Population
            End Get
        End Property

        Public Sub New()
            _Population = New List(Of Int32())
        End Sub

        'Crea la popolazione iniziale con numeri casuali
        Public Sub CreatePopulation(ByVal Size As Int32)
            Me.Population.Clear()

            'Il parametro del costruttore di Random è un numero intero detto
            'Seed (seme) che influenza la generazione di numeri pseudocasuali.
            'Usando il numero di millisecondi dell'ora corrente, aggiungiamo un
            'ulteriore fattore di variabilità all'algoritmo.
            Dim Rnd As New Random(Date.Now.Millisecond)
            Dim Numbers As New List(Of Int32)

            For I As Int32 = 1 To Size
                'Nuovo vettore, possibile soluzione
                Dim Vector(9) As Int32

                'Aggiunge i numeri da 1 a 20 a una lista
                Numbers.Clear()
                For J As Int32 = 1 To 20
                    Numbers.Add(J)
                Next
                'Quindi ne estrae 10. Dopo ogni estrazione, cancella il numero
                'estratto dalla lista, in modo che non si ripeta. Il problema
                'specificava infatti che i valori dovessero essere distinti
                For J As Int32 = 0 To 9
                    Vector(J) = Numbers(Rnd.Next(0, Numbers.Count))
                    Numbers.Remove(Vector(J))
                Next
                'Aggiunge il vettore alla popolazione
                Me.Population.Add(Vector)
            Next
        End Sub
    End Class

    Sub Main()
        Dim Engine As New GeneticEngine
        Engine.CreatePopulation(20)

        'Crea una popolazione di 20 individui e scrive a schermo i
        'vettori casuali generati
        For Each Vector As Int32() In Engine.Population
            For I As Int32 = 0 To Vector.Length - 1
                Console.Write(Vector(I) & " ")
            Next
            Console.WriteLine()
        Next

        Console.ReadKey()
    End Sub

End Module

Una volta generato il pool genetico iniziale, occore dare una spinta all'algoritmo verso l'evoluzione. Con questo termine intendiamo il miglioramento della popolazione attraverso il passaggio in molte generazioni successive. Ogni generazione ha una determinata popolazione, che si è sviluppata dalla precedente mediante selezione. Come la scienza insegna, in una popolazione ci sono individui più o meno adatti alla riproduzione. Quelli più adatti in genere vantano caratteristiche migliori e perciò hanno più probabilità di accoppiarsi. Nella scrittura dell'algoritmo occorre quindi definire una funzione che ci dica quanto buona è una soluzione. In base a questo potremmo eseguire altri calcoli sulle probabilità di sopravvivenza. Come avevo accennato precedentemente, nell'affrontare questo problema siamo particolarmente fortunati, poiché abbiamo già la funzione da massimizzare e non ci resta altro che tradurla in codice. Dato che si tratta di semplici somme e prodotti, non è nulla di complicato. Questa funzione si chiama generalmente fitness:

Module Module1

    Public Class GeneticEngine
        Private _Population As List(Of Int32())

        Public ReadOnly Property Population() As List(Of Int32())
            Get
                Return _Population
            End Get
        End Property

        Public Sub New()
            _Population = New List(Of Int32())
        End Sub

        'La somma è fatta con gli operatori di aggregazione di LINQ, mentre il
        'prodotto è una banale trascrizione a mano degli unici elementi di
        'posto primo (ricordate che l'elemento di indice 1 ha posto 2, eccetera...).
        'Tuttavia, se ci sono elementi ripetuti, il vettore è da scartare, e la
        'sua fitness sarà nulla. Nonostante la nostra accortezza nel controllare
        'questa condizione al momento dell'inizializzazione, vedremo che ci sono 
        'fenomeni quali la mutazione e il crossover che possono scombinare l'array
        Public Function EvaluateFitness(ByVal Vector As Int32()) As Double
            Dim Result As Double = Vector.Sum(Function(I As Int32) ((I Mod 2) * 2 - 1) * I) + Vector(1) * Vector(2) * Vector(4) * Vector(6) / (2 * 3 * 5 * 7)
            If Vector.Distinct().Count < 10 Then
                Result = 0
            End If
            Return Result
        End Function

        Public Sub CreatePopulation(ByVal Size As Int32)
            Me.Population.Clear()

            Dim Rnd As New Random(Date.Now.Millisecond)
            Dim Numbers As New List(Of Int32)

            For I As Int32 = 1 To Size
                Dim Vector(9) As Int32

                Numbers.Clear()
                For J As Int32 = 1 To 20
                    Numbers.Add(J)
                Next
                For J As Int32 = 0 To 9
                    Vector(J) = Numbers(Rnd.Next(0, Numbers.Count))
                    Numbers.Remove(Vector(J))
                Next
                Me.Population.Add(Vector)
            Next
        End Sub
    End Class

    Sub Main()
        Dim Engine As New GeneticEngine
        Engine.CreatePopulation(20)

        For Each Vector As Int32() In Engine.Population
            For I As Int32 = 0 To Vector.Length - 1
                Console.Write("{0:00} ", Vector(I))
            Next
            Console.WriteLine("  >  Fitness = {0}", Engine.EvaluateFitness(Vector))
        Next

        Console.ReadKey()
    End Sub
    
End Module

Per capire meglio la funzione Sum() vi consiglio di leggere questo articolo. L'espressione ((I Mod 2) * 2 - 1) è un modo computazionalmente medo dispendioso di scrivere (-1)^(i+1): potete verificarlo facilmente facendo due calcoli. Per il resto, ora abbiamo tutto il nostro pool genetico, completo di fitness per ogni individuo. Noi vogliamo che solo le soluzioni con fitness più alta possano accoppiarsi. Tuttavia, esistono molte tecniche diverse per scegliere quale soluzione si possa accoppiare, tutte basate sulla probabilità/casualità e sulla fitness.

In questo tipo di selezione, l'individuo con fitness maggiore ha maggiori probabilità di accoppiarsi, ma non è certo che questo succeda. Per calcolare questa probabilità si prende la sua fitness e la si divide per la fitness totale di tutta la popolazione (ossia la somma di tutte le fitness calcolate). Il nome deriva dal fatto che, se immaginassimo di avere una lunga striscia che rappresenta la superficie della corona circolare di una roulette e di suddividere questa striscia in porzioni proporzionali alla fitness di ogni individuo, allora lanciando la pallina e facendo girare la roulette, l'individuo con la fetta più grande avrebbe maggiori possibilità che la pallina si fermi sulla sua parte di striscia: La relazione tra f e p, tuttavia, non è proprio proporzionale, ma piuttosto asintotica. Infatti, qualora f tendesse a infinito, p tenderebbe a 1, rendendo certo l'evento "accoppiamento" per la soluzione data. Ecco una semplice implementazione:

'Amount è il numero di candidati da selezionare. Anche questo
'è un parametro che caratterizza l'algoritmo.
Public Function SelectBoidsRoulette(ByVal Amount As Int32) As List(Of Int32())
    'Calcola la fitness per ogni soluzione. Fitness è un IEnumerable(Of Double)
    'che contiene tanti elementi quante sono le soluzioni. L'i-esimo elemento
    'indica la fitness dell'i-esima soluzione
    Dim Fitnesses = From Vector As Int32() In Me.Population _
        Select EvaluateFitness(Vector)
    'Calcola la fitness totale sommando tutti i valori contenuti nella
    'collezione Fitnesses appena creata
    Dim TotalFitness As Double = Fitnesses.Sum()
    Dim Result As New List(Of Int32())
    Dim Rnd As New Random(Date.Now.Millisecond)
    Dim Temp As Double = 0
    Dim Value As Double

    Do
        'Estrae un valore a caso tra 0 e 1
        Value = Rnd.NextDouble()

        Temp = 0
        'Ora, per ogni soluzione, calcola la sua probabilità di essere
        'scelta. Questa è un numero tra 0 e 1, e la somma di tutte le
        'probabilità di ogni evento possibile è ovviamente 1.
        'Costruiamo quindi tanti piccoli intervallini che corrispondono alle
        'parti in cui era divisa l'ipotetica roulette. Ogni intervallino ha
        'ampiezza pari alla probabilità del corrispondente individuo di
        'essere scelto, ed è posto subito dopo il suo precedente.
        'In questo modo, se avessimo 5 individui con fitness rispettivamente 1, 2, 3,
        '4 e 5, avremo che (posto che 1+2+3+4+5=15):
        ' - il primo intervallino è [0, 1/15);
        ' - il secondo è [1/15, 1/15 + 2/15) = [1/15, 3/15);
        ' - il terzo è [3/15, 3/15 + 3/15) = [3/15, 6/15);
        ' - il quarto è [6/15, 10/15);
        ' - il quinto è [10/15, 1).
        'Scegliendo un numero casuale tra 0 e 1 possiamo vedere in quale di questi
        'intervallini esso ricada. Sceglieremo come candidato l'individuo nel
        'cui intervallo è stato pescato il numero casuale.
        'Come si nota, l'ultimo possiede la fascia più ampia, ma non per questo
        'gli è garantito di essere estratto.
        For I As Int32 = 0 To Fitnesses.Count() - 1
            If (Value >= Temp) And (Value < Temp + Fitnesses(I) / TotalFitness) Then
                'Non aggiunge la soluzione se è già stata scelta. In questo caso
                'sarà eseguita un'altra iterazione grazie al Do Loop
                If Not Result.Contains(Me.Population(I)) Then
                    Result.Add(Me.Population(I))
                End If
            End If
            Temp += Fitnesses(I) / TotalFitness
        Next
        
    Loop Until Result.Count = Amount

    Fitnesses = Nothing
    Rnd = Nothing

    Return Result
End Function