Nell’articolo sulle reti neurali abbiamo addestrato una rete con la backpropagation: calcolare un gradiente, muoversi nella direzione che riduce la loss, ripetere. Il metodo funziona perfettamente quando il paesaggio della loss è liscio e differenziabile. Non tutti i problemi di ottimizzazione offrono questa comodità.

Alcuni problemi non hanno gradiente da calcolare. Altri ce l’hanno, ma il paesaggio è così disseminato di minimi locali che il gradient descent finisce quasi sempre intrappolato in uno lontano dall’ottimo globale. Altri ancora coinvolgono scelte discrete, permutazioni o strutture combinatorie per cui le derivate non sono nemmeno definite. Per questi esiste una classe di algoritmi diversa. I genetic algorithm sono tra i più naturali da comprendere: la loro logica è presa in prestito direttamente dall’evoluzione biologica.

L’analogia biologica

L’evoluzione mantiene una popolazione di individui. Ogni individuo porta un genoma, una sequenza di gene che codificano le sue caratteristiche. Gli individui sono sottoposti a pressione selettiva: quelli più adatti all’ambiente hanno più probabilità di sopravvivere e riprodursi. La riproduzione non è una copia. Due genitori contribuiscono al genoma del figlio attraverso il crossover, mescolando i loro patrimoni genetici. Occasionalmente un gene cambia per caso tramite mutation, introducendo variazione che nessun genitore possedeva.

Nel corso di molte generazioni, la popolazione si sposta verso un fitness più alto, cioè verso soluzioni migliori al problema che si vuole risolvere. Nessun individuo ha pianificato il miglioramento. Nessun gradiente è stato consultato. L’algoritmo è cieco, parallelo e sorprendentemente efficace.

Useremo questo vocabolario esattamente così. Una soluzione candidata è un chromosome. I valori che la codificano sono gene. La qualità della soluzione è il suo fitness. Il resto segue.

Perché non usare semplicemente il gradient descent?

Il gradient descent è lo strumento giusto quando la funzione obiettivo è differenziabile e il paesaggio ha una struttura gestibile. L’implementazione della rete neurale su questo sito ne è un buon esempio: la loss è liscia, approssimativamente convessa vicino alle soluzioni, e la backpropagation fornisce gradienti esatti a basso costo.

Tre situazioni rompono questa ipotesi.

Non differenziabilità. Se la funzione obiettivo coinvolge scelte discrete, ordinamenti, scheduling o vincoli logici, non c’è gradiente da calcolare. Non si può derivare «questo percorso visita tutte le città esattamente una volta».

Multimodalità. Alcune funzioni lisce hanno così tanti ottimi locali che il gradient descent, partendo da qualsiasi inizializzazione ragionevole, finisce regolarmente bloccato in uno lontano dall’ottimo globale. L’algoritmo converge, ma nel posto sbagliato.

Funzioni a scatola nera. A volte si riesce a valutare una soluzione candidata ma non si può ispezionare l’interno della funzione. Il gradiente non è disponibile: si hanno solo i valori di fitness.

I genetic algorithm affrontano tutti e tre i casi. Il compromesso è chiaro: su problemi lisci e unimodali, il gradient descent converge più velocemente e con maggiore precisione. Su problemi accidentati, discreti o a scatola nera, il GA esplora lo spazio in modo ampio attraverso un’intera popolazione, invece di impegnarsi in un’unica traiettoria.

Il problema obiettivo

Ottimizziamo questa funzione su x in [0, 20]:

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

Questa funzione ha sette massimi locali. Tre di essi condividono il valore massimo globale di circa 1.2498, situati vicino a x = 1.00, x = 10.43 e x = 19.85. Tra e attorno a loro si trovano quattro massimi locali più bassi, con valori di f attorno a 0.32 e 0.12, vicino a x = 3.96, 6.70, 13.39 e 16.13.

Il gradient ascent da x = 7.0 converge a x = 6.70, f = 0.12: il massimo locale più basso del dominio. Non può sapere che picchi molto più alti esistono nelle vicinanze. Il gradient ascent da x = 4.0 si ferma a x = 3.96, f = 0.32. Il punto di partenza determina completamente il risultato.

Il GA troverà f = 1.2498 in modo affidabile, indipendentemente da dove si trovano gli individui della popolazione iniziale nel dominio.

L’algoritmo

Cinque operazioni, applicate in un ciclo:

1. Inizializzazione

Si crea una population di N soluzioni candidate, distribuite casualmente nello spazio di ricerca. Per problemi a valori reali, ogni gene viene estratto uniformemente dall’intervallo consentito. La population è il budget di diversità dell’algoritmo: una population più grande esplora in modo più approfondito ma richiede più valutazioni per generazione.

2. Valutazione del fitness

Si applica la funzione obiettivo a ogni individuo e si salva il risultato come fitness. Questo passo è solitamente il più costoso: per problemi reali, una singola valutazione del fitness può richiedere l’esecuzione di una simulazione o la consultazione di un sistema fisico.

3. Selezione

Si scelgono i genitori per la generazione successiva. Usiamo il tournament selection: si estraggono k individui a caso dalla population corrente e si seleziona il più fit tra loro. Si ripete per scegliere ogni genitore.

Il tournament selection è preferito alla selezione a roulette wheel (proporzionale al fitness) per i problemi continui per due ragioni. Prima: è invariante rispetto alla scala, conta solo il rango tra i concorrenti, non il valore assoluto del fitness. La pressione selettiva di una roulette wheel collassa quando il fitness di un individuo domina sugli altri, trasformando la selezione in una lotteria. Seconda: la dimensione del torneo k controlla direttamente la pressione selettiva, k=2 è gentile, k=10 è aggressivo, senza bisogno di riscalare la funzione di fitness.

4. Crossover

Si combinano due genitori per produrre un figlio. Per gene a valori reali, l’approccio standard è il BLX-alpha crossover (blend crossover). Dati i genitori a e b con valori del gene 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 lontano dall’intervallo tra i genitori può cadere il figlio. Con alpha = 0, i figli sono sempre compresi tra i genitori (sfruttamento). Con alpha = 0.5, i figli possono raggiungere il 50% del divario tra i genitori oltre l’uno o l’altro (equilibrio). Valori più alti favoriscono una maggiore esplorazione. La scelta standard è alpha = 0.5.

BLX-alpha è appropriato per i problemi a valori reali perché produce figli in un intorno continuo dei genitori, scalato dalla loro distanza. Un crossover binario che opera sulla rappresentazione bit di un numero in virgola mobile sarebbe arbitrario e instabile.

5. Mutation

Dopo il crossover, si applica la mutation al figlio con probabilità p_mutation. Per gene a valori reali, si aggiunge rumore gaussiano: gene += N(0, sigma). Il parametro sigma controlla la dimensione del passo di mutation.

La mutation svolge un ruolo specifico: reintroduce la variazione che la selezione erode. Man mano che una population converge, i suoi membri diventano simili tra loro. Senza mutation, il crossover tra individui quasi identici produce figli quasi identici. La population ristagna. La mutation perturba gli individui verso regioni inesplorate dello spazio di ricerca, impedendo la 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)
}

Salva il file come main.go ed eseguilo con go run main.go. 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 population trova x vicino a 19.85 (uno dei tre massimi globali a f = 1.2498) già alla generazione 10 e lo mantiene per le restanti 90 generazioni.

Leggere l’implementazione

Alcune scelte progettuali vale la pena nominare.

Elitismo. La funzione evolve preserva il singolo miglior individuo di ogni generazione all’indice zero. Senza elitismo, la pressione selettiva e la mutation possono eliminare accidentalmente la migliore soluzione trovata fino a quel momento. L’elitismo garantisce un miglioramento monotono: il miglior fitness osservato finora può solo restare uguale o migliorare.

Clamping in crossover e mutation. BLX-alpha può produrre valori del gene al di fuori dei limiti dello spazio di ricerca, specialmente quando due genitori vicini a un confine vengono incrociati. Il clamping esplicito in blxCrossover e mutate mantiene ogni individuo valido. Il clamping introduce una piccola distorsione vicino ai confini: molti campioni fuori range diventano valori limite, aumentandone leggermente la frequenza. Per la maggior parte dei problemi questo è accettabile. Le alternative includono il campionamento per rigetto (scartare e ricampionare finché non si è in-bounds) o il 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 problemi scalari a singolo obiettivo. Per funzioni di fitness costose, l’elaborazione in batch delle valutazioni consente il parallelismo: un’estensione naturale in Go consisterebbe nel lanciare ogni valutazione in una goroutine e raccogliere i risultati tramite un canale.

Nessuno stato globale. Ogni funzione riceve ciò di cui ha bisogno come parametro. tournamentSelect, blxCrossover e mutate sono pure nel senso che leggono solo i loro argomenti e la sorgente condivisa rand. Sostituire una strategia di selezione o un operatore di crossover diverso richiede di modificare solo la chiamata corrispondente in evolve.

Il gradient descent fallisce qui

Per rendere concreto il compromesso, ecco il gradient ascent 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 è salito fino al massimo locale più vicino e si è fermato. Non aveva modo di accorgersi che un picco dieci volte più alto esiste a 3 unità a sinistra e un altro a 13 unità a destra. Da x = 4.0, il gradient ascent si ferma a x = 3.96, f = 0.32: anche questo è locale, anche questo è sbagliato. Il punto di partenza determina completamente la risposta.

Il GA trova f = 1.2498 da qualsiasi inizializzazione ragionevole perché esplora l’intero dominio simultaneamente. La population è distribuita su [0, 20] alla generazione zero. La selezione non elimina subito ogni individuo vicino a un picco più basso: gli individui ovunque sopravvivono abbastanza a lungo da contribuire con il loro materiale genetico. L’operatore di crossover produce regolarmente figli che cadono lontano da entrambi i genitori quando questi sono distanti tra loro, cosa comune nelle prime generazioni quando la population copre l’intero intervallo.

La population non è «più intelligente» del gradient descent. È semplicemente parallela: cinquanta esplorazioni simultanee invece di una. La diversità dei punti di partenza è il meccanismo, non una conoscenza speciale del paesaggio.

Per cosa sono davvero adatti i genetic algorithm

La funzione precedente è un esempio didattico: il dominio è unidimensionale, continuo e l’ottimo vero è noto. Il GA lo ha trovato in un millisecondo. Gli usi reali sono meno ordinati.

Neural architecture search. La struttura di una rete neurale (numero di strati, larghezza, skip connection, funzioni di attivazione) è un oggetto combinatorio discreto. Il gradient descent ottimizza i pesi data un’architettura fissa. Il GA è stato usato per esplorare lo spazio delle architetture stesso, trattando le strutture di rete come chromosome.

Scheduling e routing. Il problema del commesso viaggiatore e i suoi cugini industriali (job shop scheduling, vehicle routing) sono combinatori. Un chromosome può codificare una permutazione di città o lavori. Gli operatori di crossover progettati per le permutazioni (come l’order crossover) preservano gli ordinamenti validi. Il gradient descent non è applicabile.

Tuning di parametri per sistemi a scatola nera. Quando il sistema da ottimizzare è una simulazione, un dispositivo fisico o una codebase legacy che non può essere differenziata, il GA lo tratta come una scatola nera: lo si invoca, si ottiene uno scalare, si seleziona su quello scalare. Non è richiesto alcun accesso interno.

Ottimizzazione degli iperparametri. Learning rate, batch size, forza di regolarizzazione, profondità dell’architettura: il GA li tratta come gene ed esplora lo spazio degli iperparametri tramite esplorazione basata sulla population.

Il limite onesto è l’efficienza del campionamento. Il GA valuta la funzione obiettivo molte volte, una per individuo per generazione. Per funzioni economiche (come il nostro esempio) va bene. Per funzioni costose (giorni di simulazione per valutazione), il GA richiede una gestione attenta del budget, spesso combinata con modelli surrogati che approssimano il paesaggio del fitness a basso costo tra una valutazione costosa e l’altra.

Cosa manca all’implementazione

Questa implementazione funziona per il problema obiettivo. Alcune estensioni sono rilevanti in pratica.

Problemi multidimensionali. Estendere a più gene per individuo significa rendere Individual.genes uno slice, adattare blxCrossover per operare gene per gene, e definire il fitness su un input vettoriale. La struttura di evolve non cambia.

Gestione dei vincoli. Molti problemi reali hanno vincoli che vanno oltre i semplici limiti del dominio. Gli approcci comuni includono le funzioni di penalità (ridurre il fitness per le violazioni dei vincoli), gli operatori di riparazione (proiettare i figli non ammissibili sull’insieme ammissibile) o la death penalty (scartare gli individui non ammissibili e sostituirli). Ciascuno ha compromessi che dipendono da quanto grande è la regione non ammissibile rispetto a quella ammissibile.

Preservazione della diversità. Su problemi multimodali si vuole a volte trovare più soluzioni buone, non solo la migliore in assoluto. Le tecniche di niching (fitness sharing, crowding) applicano una penalità agli individui troppo simili agli altri nella population, mantenendo la diversità su più picchi. L’implementazione corrente trova un massimo globale; il niching manterrebbe rappresentanti vicino a tutti e tre i picchi a f = 1.2498.

Parametri adattativi. Un mutation rate e un sigma fissi funzionano per problemi semplici. Le varianti di GA auto-adattativi codificano i parametri di mutation nel genoma stesso, permettendo all’algoritmo di regolare il proprio comportamento di ricerca man mano che la population evolve. Questo è particolarmente utile quando la dimensione appropriata del passo di mutation varia tra diverse regioni dello spazio di ricerca.

Il punto più profondo

Il gradient descent è locale: segue il paesaggio in un singolo punto. I genetic algorithm sono globali: la population copre il paesaggio in molti punti simultaneamente. Non è un pasto gratis. L’esplorazione basata sulla population costa più valutazioni della funzione per unità di progresso rispetto a quanto fa il gradient descent su problemi lisci. La scommessa che il GA sta facendo è che il costo delle valutazioni vale la pena di essere pagato per evitare di restare intrappolati.

Quando quella scommessa è giusta, il guadagno è trovare soluzioni che un metodo puramente locale non raggiungerebbe mai. Il meccanismo è preso in prestito da un processo che ha avuto tre miliardi di anni per perfezionarsi. Noi lo usiamo in un centinaio di righe di Go.