Quando lo spazio delle soluzioni diventa troppo grande
Molti problemi di ottimizzazione non hanno una soluzione facilmente calcolabile con un algoritmo diretto.
La ricerca può coinvolgere combinazioni enormi, funzioni non differenziabili o spazi pieni di ottimi locali. In questi casi non sempre è possibile calcolare semplicemente la soluzione migliore.
Gli algoritmi genetici affrontano il problema trattando le possibili soluzioni come una popolazione che evolve nel tempo.
L'idea mi interessava non soltanto dal punto di vista teorico, ma soprattutto come esercizio di progettazione software: come trasformare un algoritmo evolutivo in una libreria generica, riutilizzabile e misurabile?
Costruire un motore generico invece di un singolo esperimento
L'obiettivo era separare il funzionamento dell'algoritmo dalla rappresentazione del problema.
Il motore non dovrebbe sapere se sta ottimizzando una sequenza di byte, un vettore numerico, un insieme di elementi o una permutazione.
Dovrebbe occuparsi dell'evoluzione mentre il problema specifico definisce soltanto ciò che serve per rappresentare, valutare e modificare una soluzione.
Da qui nasce un'architettura basata su:
- generics Go per mantenere la type safety
- funzioni di fitness configurabili
- strategie intercambiabili per selezione, crossover e mutazione
- valutazione parallela delle popolazioni
- esecuzioni deterministiche tramite seed
- osservatori e hook per monitoraggio e terminazione anticipata
- supporto a un modello a isole per esplorare più popolazioni in parallelo
L'obiettivo era quindi costruire un motore di ricerca evolutiva, non un semplice esempio didattico di genetic algorithm.
Come funziona
Ogni esecuzione parte da una popolazione iniziale di candidati.
A ogni generazione il motore seleziona gli individui da cui partire, applica le operazioni di crossover e mutazione, valuta i nuovi candidati e costruisce la popolazione successiva.
Il ciclo continua fino al raggiungimento del numero di generazioni previsto oppure fino a quando una condizione di arresto non viene soddisfatta.
Selezione
La libreria supporta diverse strategie per decidere quali individui hanno maggiori probabilità di contribuire alla generazione successiva, tra cui tournament selection, roulette wheel e rank selection.
È inoltre possibile mantenere direttamente i migliori individui attraverso l'elitismo.
Crossover
La ricombinazione può utilizzare strategie diverse a seconda della rappresentazione del genoma.
Sono disponibili crossover a singolo punto, a due punti, uniforme e OX1 per le rappresentazioni basate su permutazioni.
Mutazione
Anche la mutazione viene trattata come una strategia intercambiabile.
La libreria include mutazioni adatte a rappresentazioni binarie, vettori numerici e permutazioni, tra cui bit flip, Gaussian, swap e inversion.
Valutazione parallela
La funzione di fitness viene valutata attraverso un worker pool bounded.
In questo modo le valutazioni indipendenti possono essere distribuite su più goroutine senza creare una nuova goroutine per ogni individuo a ogni generazione.
Un motore costruito attorno a strategie intercambiabili
L'architettura del progetto separa il ciclo evolutivo dalle singole operazioni che lo compongono.
Il flusso principale è:
Config → Population Generator → Selection → Crossover → Mutation → Fitness Evaluation → Observers → Control → Result
Ogni fase può essere sostituita senza modificare il cuore del motore.
La rappresentazione del genoma viene definita attraverso i generics di Go, mentre selezione, crossover, mutazione e valutazione vengono fornite attraverso componenti configurabili.
Questo permette di utilizzare la stessa infrastruttura per problemi molto diversi.
Il repository include infatti implementazioni per il problema dello zaino, il Traveling Salesman Problem, l'ottimizzazione di funzioni matematiche e il Job Shop Scheduling.
Le parti più difficili
1. Rendere l'algoritmo realmente generico
Un'implementazione legata a un solo tipo di genoma sarebbe relativamente semplice.
Il problema diventa più interessante quando la stessa libreria deve supportare rappresentazioni completamente diverse senza perdere la sicurezza dei tipi.
I generics permettono al motore di lavorare con tipi diversi mantenendo i controlli a compile time, senza ricorrere alla reflection o a conversioni manuali basate su interface{}.
2. Parallelizzare la fitness senza creare troppo overhead
La valutazione della fitness è un punto naturale per il parallelismo, ma creare goroutine continuamente può introdurre costi di scheduling e garbage collection.
Per questo ho utilizzato un worker pool persistente e bounded che può essere riutilizzato tra le generazioni.
I benchmark del repository mostrano anche il limite di questo approccio: aumentare il numero di worker non produce una crescita lineare delle prestazioni perché altre parti del ciclo evolutivo rimangono seriali.
3. Mantenere la riproducibilità
La casualità è una parte essenziale di un genetic algorithm, ma rende molto difficile confrontare due esecuzioni se il comportamento non è controllabile.
Il progetto utilizza seed espliciti per rendere riproducibili le traiettorie evolutive e i risultati nelle stesse condizioni sperimentali.
4. Evitare la convergenza prematura
Un'unica popolazione può convergere troppo rapidamente verso una soluzione locale.
Per affrontare questo problema ho aggiunto un modello a isole, nel quale diverse sottopopolazioni evolvono in parallelo e scambiano periodicamente individui secondo una topologia configurabile.
L'obiettivo è preservare maggiore diversità durante la ricerca.
Perché l'ho costruito in questo modo
1. Generics invece di interface{}
La libreria deve poter rappresentare genomi diversi senza sacrificare la sicurezza dei tipi.
I generics permettono di mantenere questa flessibilità a compile time e rendono l'API più prevedibile.
2. Strategie separate dal motore
Selezione, crossover e mutazione non sono integrate direttamente nel ciclo principale.
Sono componenti sostituibili che permettono di sperimentare rapidamente configurazioni diverse senza riscrivere il motore.
3. Worker pool persistente
La valutazione della fitness è una parte fortemente parallelizzabile, ma il parallelismo deve essere controllato.
Un pool bounded permette di sfruttare più core mantenendo sotto controllo il numero di goroutine attive.
4. Seed espliciti
Un esperimento di ottimizzazione è molto più utile quando può essere ripetuto.
Per questo la casualità è controllata attraverso un seed configurabile e l'esecuzione rimane deterministica nelle stesse condizioni.
5. Benchmark riproducibili
Non volevo limitarmi a dire che un approccio è più veloce o più efficace.
Il repository include benchmark sul dimensionamento della popolazione, sulla scalabilità del worker pool e confronti sperimentali con Simulated Annealing e Random Search. Le prove sono documentate con configurazioni e budget di valutazione espliciti.
Da algoritmo a libreria sperimentale
Il risultato è una libreria di algoritmi genetici che può essere utilizzata con rappresentazioni e problemi diversi senza modificare il motore centrale.
Il progetto supporta valutazione parallela, strategie configurabili, esecuzioni deterministiche, osservatori, terminazione anticipata e un modello a isole con migrazione tra popolazioni.
Gli esperimenti inclusi nel repository mostrano anche come il comportamento cambi al variare dell'architettura.
Ad esempio, nei test su Rastrigin a 5 dimensioni, l'implementazione a 8 isole ha raggiunto una soglia di successo nell'11 di 30 prove, contro 5 di 30 per la singola popolazione nelle condizioni specifiche del benchmark. Questi risultati servono a caratterizzare questa implementazione e questa configurazione sperimentale, non a dimostrare una superiorità generale degli algoritmi genetici rispetto ad altri metodi.
Oltre l'algoritmo genetico
Questo progetto mi ha portato a lavorare su un problema che va oltre l'implementazione dell'algoritmo in sé.
Ho dovuto affrontare progettazione di API generiche, concorrenza in Go, riproducibilità degli esperimenti, astrazione delle strategie, benchmark e valutazione empirica.
La parte più interessante è stata trasformare un algoritmo conosciuto dalla teoria in un componente software che possa essere riutilizzato, misurato e modificato senza dover riprogettare ogni volta l'intero sistema.