Nell’articolo sulle reti neurali abbiamo addestrato una rete usando la retropropagazione: si calcola un gradiente, si fa un passo nella direzione che riduce la perdita, si ripete. Il metodo funziona a meraviglia quando il panorama della funzione di perdita è liscio e differenziabile. Tuttavia, non tutti i problemi di ottimizzazione offrono questo vantaggio.

In alcuni problemi non c’è alcun gradiente da calcolare. In altri il gradiente esiste, ma il panorama è talmente disseminato di minimi locali che la discesa del gradiente vi rimane inesorabilmente intrappolata. Altri ancora implicano scelte discrete, permutazioni o strutture combinatorie per le quali le derivate non sono nemmeno definite. Per queste casistiche esiste una classe di algoritmi diversa. Gli algoritmi genetici sono tra i più naturali da comprendere, poiché mutuano la loro logica direttamente dall’evoluzione biologica.

L’analogia biologica

L’evoluzione mantiene una popolazione di individui. Ciascuno di essi è portatore di un genoma, ovvero una sequenza di geni che ne codifica le caratteristiche. Tali individui sono sottoposti alla pressione selettiva: quelli che meglio si adattano all’ambiente hanno maggiori probabilità di sopravvivere e riprodursi. La riproduzione, tuttavia, non è una semplice copia. Due genitori trasmettono i propri geni alla prole tramite il crossover (o incrocio), mescolando i rispettivi genomi. Di tanto in tanto, un gene subisce un’alterazione casuale a causa di una mutazione, la quale introduce una variazione che nessuno dei genitori possedeva.

Nel corso di molte generazioni, la popolazione si sposta verso una maggiore fitness (l’idoneità), che rappresenta la misura di quanto un individuo sia in grado di risolvere il problema in questione. Nessun individuo ha pianificato il miglioramento e non è stato consultato alcun gradiente. L’algoritmo è cieco, parallelo e sorprendentemente efficace.

Questo vocabolario viene impiegato in senso letterale. Una soluzione candidata è un cromosoma; i valori che la codificano sono i geni; la bontà della soluzione è la sua fitness. Tutto il resto ne consegue.

Perché non usare semplicemente la discesa del gradiente?

La discesa del gradiente è lo strumento ideale quando la funzione obiettivo è differenziabile e il panorama presenta una struttura gestibile. L’implementazione della rete neurale presente su questo sito ne è un ottimo esempio: la perdita è liscia, tendenzialmente convessa in prossimità delle soluzioni, e la retropropagazione fornisce gradienti esatti a basso costo computazionale.

Esistono però tre situazioni in cui questo presupposto viene meno.

Non differenziabilità. Se la funzione obiettivo comporta scelte discrete, ordinamenti, pianificazioni o vincoli logici, non c’è alcun gradiente da calcolare. Non è possibile derivare un’espressione come “questo percorso visita tutte le città esattamente una volta”.

Multimodalità. Alcune funzioni lisce presentano un numero tale di ottimi locali che la discesa del gradiente, pur partendo da un’inizializzazione ragionevole, finisce sistematicamente per bloccarsi in un punto lontano dall’ottimo globale. L’algoritmo converge, ma nel punto sbagliato.

Funzioni black-box. A volte è possibile valutare una soluzione candidata senza però poterne ispezionare i meccanismi interni. In questi casi il gradiente non è disponibile, lo sono soltanto i valori di fitness.

Gli algoritmi genetici (GA) risolvono tutte e tre le problematiche. Il compromesso è chiaro: su problemi lisci e unimodali, la discesa del gradiente converge più rapidamente e con maggiore precisione. Su problemi accidentati, discreti o di tipo black-box, i GA esplorano lo spazio in modo ampio attraverso un’intera popolazione, anziché vincolarsi a una singola traiettoria.

Il problema di riferimento

L’obiettivo sarà ottimizzare la seguente funzione per x nell’intervallo [0, 20]:

f(x) = sin(x) * cos(x/3) + 0.5 * sin(2x)

Questa funzione presenta sette massimi locali. Tre di essi condividono il valore massimo globale di circa 1.2498, situato in prossimità di x = 1.00, x = 10.43 e x = 19.85. Tra di essi e nei loro dintorni si trovano quattro massimi locali inferiori, con valori di f pari a circa 0.32 e 0.12, vicino a x = 3.96, 6.70, 13.39 e 16.13.

L’ascesa del gradiente a partire da x = 7.0 converge verso x = 6.70, f = 0.12, ovvero il massimo locale più basso del dominio. L’algoritmo non ha modo di sapere che nelle vicinanze esistono picchi molto più alti. Partendo da x = 4.0, l’ascesa del gradiente si assesta su x = 3.96, f = 0.32. La posizione di partenza determina completamente il risultato.

I GA, al contrario, troveranno f = 1.2498 in modo affidabile, indipendentemente dal punto del dominio in cui ricade la popolazione iniziale.

L’algoritmo

Vi sono cinque operazioni, applicate all’interno di un ciclo:

1. Inizializzazione

Si crea una popolazione di N soluzioni candidate, distribuendole in modo casuale nello spazio di ricerca. Per i problemi a valori reali, ogni gene viene estratto in modo uniforme dall’intervallo consentito. La popolazione rappresenta il budget di diversità dell’algoritmo: una popolazione più numerosa esplora in modo più approfondito, ma comporta un costo maggiore in termini di valutazioni per generazione.

2. Valutazione della fitness

Si applica la funzione obiettivo a ogni individuo e si memorizza il risultato come fitness dell’individuo stesso. Questo passaggio è solitamente il più oneroso dal punto di vista computazionale: nei problemi del mondo reale, una singola valutazione della fitness potrebbe richiedere l’esecuzione di una simulazione o l’interrogazione di un sistema fisico.

3. Selezione

Si scelgono i genitori per la generazione successiva. In questo caso utilizziamo la selezione a torneo: si estraggono a caso k individui dalla popolazione attuale e si seleziona il più adatto tra di essi. Il procedimento viene ripetuto per scegliere ogni singolo genitore.

Per i problemi continui, la selezione a torneo è preferibile rispetto a quella a roulette (proporzionale alla fitness) per due ragioni. In primo luogo, è invariante di scala: conta solo la posizione in classifica tra i concorrenti, non la grandezza assoluta dei valori di fitness. La pressione selettiva di una roulette collassa quando la fitness di un individuo domina sulle altre, trasformando la selezione in una lotteria. In secondo luogo, la dimensione del torneo k controlla direttamente la pressione selettiva: k=2 è un approccio morbido, k=10 è aggressivo. È possibile regolarla senza dover riscalare la funzione di fitness.

4. Crossover

Si combinano due genitori per generare una prole. Per i geni a valori reali, l’approccio standard è il crossover BLX-alpha (crossover per fusione). Dati due genitori a e b con valori genici in un certo intervallo, il gene del figlio viene campionato uniformemente da:

[min(a, b) - alpha * |b - a|,  max(a, b) + alpha * |b - a|]

Il parametro alpha controlla quanto il figlio possa cadere al di fuori dell’intervallo compreso tra i genitori. Con alpha = 0, la prole si trova sempre tra i genitori (sfruttamento). Con alpha = 0.5, la prole può spingersi oltre ciascun genitore per una distanza pari al 50% del divario tra di essi (approccio bilanciato). Valori più alti incoraggiano una maggiore esplorazione. La scelta standard è alpha = 0.5.

Il BLX-alpha è appropriato per i problemi a valori reali perché produce una prole in un intorno continuo dei genitori, proporzionato alla loro distanza reciproca. Un crossover binario che operasse su una rappresentazione in bit a virgola mobile risulterebbe arbitrario e instabile.

5. Mutazione

Dopo il crossover, si applica una mutazione alla prole con probabilità p_mutation. Per i geni a valori reali, si aggiunge del rumore gaussiano: gene += N(0, sigma). Il parametro sigma controlla l’ampiezza del passo di mutazione.

La mutazione svolge un ruolo specifico: reintroduce la variazione che la selezione tende a erodere. Man mano che una popolazione converge, i suoi membri diventano sempre più simili. Senza mutazione, il crossover tra individui quasi identici produrrebbe una prole altrettanto identica, portando la popolazione al ristagno. La mutazione perturba gli individui spingendoli in regioni inesplorate dello spazio di ricerca, prevenendo così una convergenza prematura.

L’implementazione in Go

Codifica a valori reali. Nessuna libreria esterna. Le uniche importazioni sono math, math/rand e fmt.

package main

import (
	"fmt"
	"math"
	"math/rand"
)

// Individual holds a single candidate solution and its fitness.
type Individual struct {
	gene    float64
	fitness float64
}

// Population is a slice of individuals.
type Population []Individual

// initPopulation creates a random population within the given bounds.
func initPopulation(size int, bounds [2]float64) Population {
	pop := make(Population, size)
	for i := range pop {
		pop[i].gene = bounds[0] + rand.Float64()*(bounds[1]-bounds[0])
	}
	return pop
}

// evaluate applies f to every individual and stores the result as fitness.
func evaluate(pop Population, f func(float64) float64) Population {
	for i := range pop {
		pop[i].fitness = f(pop[i].gene)
	}
	return pop
}

// tournamentSelect picks k random individuals and returns the fittest.
func tournamentSelect(pop Population, k int) Individual {
	best := pop[rand.Intn(len(pop))]
	for i := 1; i < k; i++ {
		candidate := pop[rand.Intn(len(pop))]
		if candidate.fitness > best.fitness {
			best = candidate
		}
	}
	return best
}

// blxCrossover produces an offspring using BLX-alpha blend crossover.
// The offspring gene is sampled uniformly from the interval
// [min(a,b) - alpha*d, max(a,b) + alpha*d] where d = |b.gene - a.gene|.
func blxCrossover(a, b Individual, alpha float64, bounds [2]float64) Individual {
	d := math.Abs(b.gene - a.gene)
	lo := math.Min(a.gene, b.gene) - alpha*d
	hi := math.Max(a.gene, b.gene) + alpha*d
	gene := lo + rand.Float64()*(hi-lo)
	// Clamp to search space boundaries.
	if gene < bounds[0] {
		gene = bounds[0]
	}
	if gene > bounds[1] {
		gene = bounds[1]
	}
	return Individual{gene: gene}
}

// mutate adds Gaussian noise to the gene with probability rate.
func mutate(ind Individual, rate, sigma float64, bounds [2]float64) Individual {
	if rand.Float64() < rate {
		ind.gene += rand.NormFloat64() * sigma
		if ind.gene < bounds[0] {
			ind.gene = bounds[0]
		}
		if ind.gene > bounds[1] {
			ind.gene = bounds[1]
		}
	}
	return ind
}

// bestOf returns the individual with the highest fitness in the population.
func bestOf(pop Population) Individual {
	best := pop[0]
	for _, ind := range pop[1:] {
		if ind.fitness > best.fitness {
			best = ind
		}
	}
	return best
}

// evolve runs one generation: select, cross, mutate, evaluate.
// Elitism: the best individual from the current generation is carried forward unchanged.
func evolve(
	pop Population,
	f func(float64) float64,
	bounds [2]float64,
	crossoverRate float64,
	mutationRate float64,
	sigma float64,
	tournamentK int,
	alpha float64,
) Population {
	next := make(Population, len(pop))

	// Elitism: preserve the best individual.
	next[0] = bestOf(pop)

	for i := 1; i < len(pop); i++ {
		parent1 := tournamentSelect(pop, tournamentK)
		var child Individual
		if rand.Float64() < crossoverRate {
			parent2 := tournamentSelect(pop, tournamentK)
			child = blxCrossover(parent1, parent2, alpha, bounds)
		} else {
			child = parent1
		}
		child = mutate(child, mutationRate, sigma, bounds)
		child.fitness = f(child.gene)
		next[i] = child
	}

	return next
}

func main() {
	rand.Seed(42)

	// Target function: multimodal, several local maxima over [0, 20].
	f := func(x float64) float64 {
		return math.Sin(x)*math.Cos(x/3) + 0.5*math.Sin(2*x)
	}

	bounds := [2]float64{0, 20}
	popSize := 50
	generations := 100
	crossoverRate := 0.8
	mutationRate := 0.1
	sigma := 0.5
	tournamentK := 3
	alpha := 0.5

	pop := initPopulation(popSize, bounds)
	pop = evaluate(pop, f)

	for gen := 0; gen <= generations; gen++ {
		if gen%10 == 0 {
			best := bestOf(pop)
			fmt.Printf("Gen %3d: best x = %.4f, f(x) = %.4f\n", gen, best.gene, best.fitness)
		}
		pop = evolve(pop, f, bounds, crossoverRate, mutationRate, sigma, tournamentK, alpha)
	}

	best := bestOf(pop)
	fmt.Printf("\nResult: x = %.6f, f(x) = %.6f\n", best.gene, best.fitness)
}

Salvando il codice come main.go e avviandolo con go run main.go, si ottiene questo output:

Gen   0: best x = 19.9464, f(x) = 1.2370
Gen  10: best x = 19.8505, f(x) = 1.2498
Gen  20: best x = 19.8505, f(x) = 1.2498
Gen  30: best x = 19.8505, f(x) = 1.2498
Gen  40: best x = 19.8505, f(x) = 1.2498
Gen  50: best x = 19.8505, f(x) = 1.2498
Gen  60: best x = 19.8505, f(x) = 1.2498
Gen  70: best x = 19.8505, f(x) = 1.2498
Gen  80: best x = 19.8505, f(x) = 1.2498
Gen  90: best x = 19.8505, f(x) = 1.2498
Gen 100: best x = 19.8505, f(x) = 1.2498

Result: x = 19.850493, f(x) = 1.249804

La popolazione individua un valore di x vicino a 19.85 (uno dei tre massimi globali a f = 1.2498) entro la decima generazione e lo mantiene per le restanti novanta.

Analisi dell’implementazione

Vale la pena menzionare alcune scelte progettuali.

Elitismo. La funzione evolve conserva il singolo miglior individuo di ogni generazione all’indice zero. Senza l’elitismo, la pressione selettiva e la mutazione potrebbero scartare accidentalmente la migliore soluzione trovata fino a quel momento. L’elitismo garantisce un miglioramento monotono: la migliore fitness osservata può solo rimanere invariata o migliorare.

Clamping nel crossover e nella mutazione. Il BLX-alpha può produrre valori genici al di fuori dei limiti di ricerca, specialmente quando si incrociano due genitori vicini a un margine. Il blocco esplicito (clamping) in blxCrossover e mutate mantiene legale ogni individuo. Questa tecnica introduce una lieve distorsione in prossimità dei confini: molti campioni fuori limite diventano valori limite, aumentandone leggermente la frequenza. Per la maggior parte dei problemi, ciò è accettabile. Le alternative includono il campionamento con rigetto (scartare e ricampionare finché non si rientra nei limiti) o l’avvolgimento (wrapping).

Fitness alla nascita. La funzione evolve chiama f(child.gene) subito dopo aver creato il figlio, anziché eseguire un passaggio di valutazione separato. Questo mantiene il codice semplice per i problemi scalari a singolo obiettivo. Nel caso di funzioni di fitness onerose, raggruppare le valutazioni in lotti permette di sfruttare il parallelismo: un’estensione naturale in Go consisterebbe nell’avviare ogni valutazione in una goroutine e raccogliere i risultati tramite un canale.

Nessuno stato globale. Ogni funzione accetta ciò di cui ha bisogno sotto forma di parametri. tournamentSelect, blxCrossover e mutate sono pure, nel senso che leggono unicamente i propri argomenti e la sorgente condivisa rand. Sostituire una diversa strategia di selezione o operatore di crossover richiede la modifica della sola chiamata pertinente all’interno di evolve.

Qui la discesa del gradiente fallisce

Per rendere concreto il compromesso, ecco l’ascesa del gradiente sulla stessa funzione, partendo da x = 7.0:

package main

import (
	"fmt"
	"math"
)

func f(x float64) float64 {
	return math.Sin(x)*math.Cos(x/3) + 0.5*math.Sin(2*x)
}

func main() {
	x := 7.0
	lr := 0.05

	for i := 0; i < 2000; i++ {
		// Numerical gradient via central differences.
		grad := (f(x+1e-6) - f(x-1e-6)) / (2e-6)
		x += lr * grad
		if x < 0 {
			x = 0
		}
		if x > 20 {
			x = 20
		}
	}

	fmt.Printf("Gradient ascent result: x = %.4f, f(x) = %.4f\n", x, f(x))
	// Output: Gradient ascent result: x = 6.7020, f(x) = 0.1212
}

Output: Gradient ascent result: x = 6.7020, f(x) = 0.1212

L’algoritmo si è arrampicato fino al massimo locale più vicino e si è fermato. Non aveva alcun meccanismo per accorgersi che un picco dieci volte più alto si trovava a 3 unità di distanza sulla sinistra, e un altro a 13 unità sulla destra. Partendo da x = 4.0, l’ascesa del gradiente si assesta a x = 3.96, f = 0.32: un altro risultato locale, un altro errore. Il punto di partenza determina completamente la risposta.

I GA trovano f = 1.2498 a partire da qualsiasi inizializzazione ragionevole, poiché esplorano l’intero dominio simultaneamente. Alla generazione zero, la popolazione è distribuita su tutto l’intervallo [0, 20]. La selezione non elimina immediatamente ogni individuo vicino a un picco inferiore: individui dislocati ovunque sopravvivono abbastanza a lungo da contribuire con il proprio materiale genetico. L’operatore di crossover produce regolarmente una prole che atterra lontano da entrambi i genitori quando questi sono distanti tra loro, un’evenienza comune nelle prime generazioni, quando la popolazione copre l’intero spettro.

La popolazione non è “più intelligente” della discesa del gradiente. È semplicemente parallela: cinquanta esplorazioni simultanee anziché una sola. La diversità delle posizioni di partenza è il vero motore del meccanismo, non una presunta comprensione speciale del panorama.

A cosa servono davvero gli algoritmi genetici

La funzione analizzata finora è un giocattolo: il dominio è unidimensionale, continuo e l’ottimo reale è noto. I GA lo hanno trovato in un millisecondo. Gli impieghi nel mondo reale sono meno ordinati.

Ricerca dell’architettura neurale. La struttura di una rete neurale (numero di livelli, ampiezza, connessioni saltate, funzioni di attivazione) è un oggetto combinatorio discreto. La discesa del gradiente ottimizza i pesi data un’architettura fissa, ma i GA sono stati utilizzati per esplorare lo spazio stesso delle architetture, trattando le strutture di rete come cromosomi.

Pianificazione e instradamento. Il problema del commesso viaggiatore e i suoi cugini industriali (pianificazione delle commesse, instradamento dei veicoli) sono di natura combinatoria. Un cromosoma può codificare una permutazione di città o di lavori. Gli operatori di crossover progettati per le permutazioni (come l’order crossover) preservano gli ordinamenti validi. In questi casi, la discesa del gradiente non è applicabile.

Ottimizzazione dei parametri per sistemi black-box. Quando il sistema da ottimizzare è una simulazione, un dispositivo fisico o una base di codice preesistente che non può essere differenziata, i GA lo trattano come una scatola nera: lo richiamano, ottengono uno scalare ed effettuano la selezione su tale scalare. Non è richiesto alcun accesso interno.

Ottimizzazione degli iperparametri. Tasso di apprendimento, dimensione del batch, forza di regolarizzazione, profondità dell’architettura: i GA trattano questi elementi come geni ed esplorano lo spazio degli iperparametri tramite una ricerca basata sulla popolazione.

Il vero limite, a onor del vero, è l’efficienza campionaria. I GA valutano la funzione obiettivo moltissime volte, una per ogni individuo a ogni generazione. Per funzioni economiche (come il nostro esempio) non ci sono problemi. Per quelle costose (giorni di simulazione per singola valutazione), i GA richiedono un’attenta gestione del budget computazionale, spesso combinata con modelli surrogati che approssimano il panorama della fitness a basso costo tra una valutazione dispendiosa e l’altra.

Cosa tralascia l’implementazione

L’implementazione presentata funziona per il problema di riferimento, ma nella pratica assumono rilevanza diverse estensioni.

Problemi multidimensionali. L’estensione a più geni per individuo implica trasformare Individual.genes in una slice, adattare blxCrossover affinché operi gene per gene e definire la fitness su un input a valori vettoriali. La struttura di evolve rimane invece invariata.

Gestione dei vincoli. Molti problemi reali presentano vincoli che vanno oltre i semplici limiti spaziali. Gli approcci comuni includono funzioni di penalità (ridurre la fitness in caso di violazione dei vincoli), operatori di riparazione (riproiettare la prole non ammissibile nell’insieme delle soluzioni ammissibili) o la pena di morte (scartare gli individui non ammissibili e sostituirli). Ciascuno di questi metodi presenta dei compromessi, a seconda di quanto sia estesa la regione non ammissibile rispetto allo spazio delle soluzioni valide.

Conservazione della diversità. Nei problemi multimodali, a volte si desidera trovare più soluzioni valide, non solo la migliore in assoluto. Le tecniche di niching (condivisione della fitness, crowding) applicano una penalità agli individui troppo simili agli altri membri della popolazione, mantenendo la diversità su più picchi. L’implementazione attuale trova un solo massimo globale; il niching manterrebbe dei rappresentanti vicino a tutti e tre i picchi a f = 1.2498.

Parametri adattivi. Un tasso di mutazione e un sigma fissi funzionano bene per problemi semplici. Le varianti auto-adattive dei GA codificano i parametri di mutazione nel genoma stesso, consentendo all’algoritmo di regolare il proprio comportamento di ricerca man mano che la popolazione evolve. Ciò si rivela particolarmente utile quando l’ampiezza del passo di mutazione appropriata varia a seconda delle diverse regioni dello spazio di ricerca.

Il punto fondamentale

La discesa del gradiente è locale: segue il panorama in un singolo punto. Gli algoritmi genetici sono globali: la popolazione copre il panorama in molti punti simultaneamente. Questo vantaggio, tuttavia, non è gratuito. L’esplorazione basata sulla popolazione costa un numero maggiore di valutazioni della funzione per unità di progresso rispetto a quanto faccia la discesa del gradiente sui problemi lisci. La scommessa che i GA fanno è che valga la pena pagare il costo di tali valutazioni pur di evitare di rimanere in trappola.

Quando questa scommessa si rivela corretta, la ricompensa consiste nel trovare soluzioni che un metodo puramente locale non raggiungerebbe mai. Il meccanismo è mutuato da un processo che ha avuto tre miliardi di anni per perfezionarsi. Noi abbiamo il privilegio di poterlo utilizzare in un centinaio di righe di codice Go.