Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT

Il neurone e la rete in breve, evoluzione di un controllore per il pendolo inverso su un carrello, perché l’evoluzione invece del gradiente, XOR e neuroni nascosti, NEAT con le marcature storiche e la speciazione, cosa succede senza speciazione e gli eredi da HyperNEAT ad AmoebaNet.

15 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 31 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Oggi le reti neurali si addestrano quasi esclusivamente con la discesa del gradiente: la rete sbaglia, si calcola in quale direzione ruotare leggermente ciascun peso, e lo si ruota. Ma che fare se l’errore non si può derivare — se del successo veniamo a sapere solo alla fine della partita, o se non sappiamo nemmeno come debba essere fatta la rete? Allora tocca all’evoluzione. La neuroevoluzione lascia che gli algoritmi evolutivi coltivino i pesi delle reti e, nella versione più interessante, anche la loro forma. Con questa parte si chiude il modulo sugli algoritmi ispirati alla natura e al tempo stesso si apre la porta alle reti neurali.

Segue le parti Algoritmi genetici e Strategie evolutive e programmazione genetica.

1. La rete neurale in breve

Definizione — neurone artificiale e rete

Un neurone con ingressi x₁, …, x_n, pesi w₁, …, w_n e bias (soglia) b calcola

y = σ(w₁x₁ + … + w_nx_n + b),

dove σ è la funzione di attivazione — per esempio la sigmoide σ(z) = 1 / (1 + e^−z), oppure un semplice gradino «positivo → 1, altrimenti 0».

Una rete neurale è un grafo orientato di neuroni: gli ingressi della rete portano ai neuroni, le uscite dei neuroni ad altri neuroni. In una rete feedforward il grafo non ha cicli. I neuroni che non sono né ingressi né uscite sono nascosti.

y = σ( ∑_i=1ⁿ w_i x_i + b )

x_i

ingressi — ciò che il neurone «vede» (nel pendolo: posizione, velocità, angolo); il neurone non li modifica, li usa solo per calcolare

w_i

pesi — l’unica cosa che si apprende o si evolve; il segno dice se il neurone sostiene l’ingresso o lo smorza, il modulo quanto conta

b

bias — sposta il confine di decisione; senza di esso ingressi nulli darebbero sempre lo stesso σ(0) e il confine dovrebbe passare per l’origine

σ

funzione di attivazione — la non linearità; senza di essa anche una rete di molti strati calcolerebbe solo una funzione lineare, perché la composizione di funzioni lineari è ancora lineare

2. Evoluzione dei pesi: il pendolo inverso su un carrello

Un classico problema di controllo: su un carrello è incernierata un’asta e il carrello deve mantenerla verticale spostandosi avanti e indietro a sinistra e a destra — come quando si tiene in equilibrio una scopa sul palmo della mano.

Definizione — il problema del pendolo inverso su un carrello

Lo stato è la quaterna (x, v, θ, ω): posizione x e velocità v del carrello, angolo θ dell’asta rispetto alla verticale e la sua velocità angolare ω. Ogni 0,02 s il controllore sceglie una forza di +10 N oppure −10 N e lo stato cambia secondo le equazioni del moto (carrello da 1 kg, asta da 0,1 kg lunga 1 m). Il tentativo termina quando |θ| > 12° oppure |x| > 2,4 m. L’obiettivo è resistere 1 000 passi (20 s).

Il controllore sarà un unico neurone con attivazione a gradino: la forza è +10 N quando w₁x + w₂v + w₃θ + w₄ω + b > 0, altrimenti −10 N. La fitness è il numero medio di passi su tre diverse partenze.

Definizione — equazioni del moto del pendolo inverso su un carrello

L’angolo θ si misura dalla verticale, una forza positiva spinge il carrello nella direzione delle x positive. Indichiamo con M = m_v + m_t = 1 + 0,1 = 1,1 kg la massa complessiva di carrello e asta, con l = 0,5 m la metà della lunghezza dell’asta (la distanza del baricentro dalla cerniera) e g = 9,8 m/s². Senza attrito (equazioni nella forma data da Barto, Sutton e Anderson, 1983, e usata ancora oggi dalla maggior parte delle implementazioni) l’accelerazione angolare dell’asta ε e l’accelerazione del carrello a sono:

a_F = (F + m_t l ω² sin θ) / M

ε = (g sin θ − cos θ · a_F) / (l (4/3 − m_t cos² θ / M))

a = a_F − m_t l ε cos θ / M

La simulazione procede con il metodo di Eulero con passo Δt = 0,02 s: la nuova posizione è la vecchia più Δt volte la vecchia velocità, la nuova velocità è la vecchia più Δt volte l’accelerazione — x ← x + Δt v, v ← v + Δt a, θ ← θ + Δt ω, ω ← ω + Δt ε.

ε = ( g sin θ − cos θ · a_F ) / l (4/3 − m_t cos² θ / M)

g sin θ

gravità — il motivo per cui l’asta cade: più è inclinata, più la gravità la ribalta ulteriormente; in posizione verticale è nulla, quindi la verticale è un equilibrio, ma instabile

a_F

accelerazione del carrello dovuta alla forza del controllore (più una piccola forza centrifuga dell’asta) — l’unico modo in cui il controllore agisce sull’asta: il carrello le passa sotto e la cerniera la «spinge» indietro

cos θ

quanta parte della spinta orizzontale fa ruotare l’asta — per un’asta verticale quasi tutta, per un’asta distesa nulla; per questo un’asta inclinata di più di qualche grado si salva a fatica

l (4/3 − …)

inerzia dell’asta — il 4/3 deriva dal momento d’inerzia di un’asta omogenea attorno a un’estremità, ⅓ m(2l)² = ⁴⁄₃ ml²; il termine sottratto corregge il fatto che, quando l’asta ruota, sobbalza anche il carrello sotto di essa

Esempio — un passo della simulazione

Partenza (0, 0, 0,05, 0), cioè asta inclinata di 0,05 rad ≈ 2,9°. Denominatore: 0,5 · (4/3 − 0,1 · 0,9988² / 1,1) ≈ 0,621.

senza forza (F = 0): ε = 9,8 · 0,0500 / 0,621 ≈ +0,79 rad/s² — l’asta comincia a cadere

forza +10 N: a_F = 10 / 1,1 ≈ 9,09 m/s²,   ε = (0,490 − 0,999 · 9,09) / 0,621 ≈ −13,8 rad/s²

dopo il passo: ω = 0 + 0,02 · (−13,8) ≈ −0,28 rad/s,   v ≈ 0 + 0,02 · 9,72 ≈ 0,19 m/s

Una forza di ±10 N è enorme rispetto alla gravità — un solo strattone inverte il verso della caduta. Il problema quindi non sta nella forza, ma nel tempismo: quando smettere di spingere perché l’asta non oscilli dall’altra parte.

Quanto ottiene il caso? Su mille controllori con pesi casuali uno solo ha resistito tutti i 20 secondi; la mediana è 9 passi — l’asta cade in meno di un quinto di secondo. Un controllore ingenuo, che si limita a muoversi verso il lato in cui l’asta pende, resiste 39 passi: l’asta la prende, ma la fa oscillare sempre di più. La strategia evolutiva (5, 20) della parte sulle strategie evolutive ha trovato un controllore che resiste tutti i 20 secondi da tutte e tre le partenze alla 15ª generazione — dopo circa trecento controllori provati:

Il controllore evoluto dà il peso maggiore alla velocità angolare — non riprende l’asta quando sta già cadendo, ma quando comincia appena a cadere. Pesi non trascurabili li hanno anche l’angolo e la velocità del carrello, così il carrello non oscilla e non esce dal binario. Nessuno ha scritto una simile «regola»; è venuta fuori dall’evoluzione.

Definizione — fitness del controllore ed evoluzione dei pesi

Per i pesi w = (w₁, …, w₄, b) sia T_k(w) ∈ {1, …, 1 000} il numero di passi prima che, dalla partenza k, l’asta cada o il carrello esca dal binario (al massimo 1 000). La fitness è

Z(w) = ⅓ (T₁(w) + T₂(w) + T₃(w)),

con le partenze (0, 0, 0,05, 0), (0, 0, −0,08, 0) e (0,5, 0, 0,02, 0,1). Tre partenze invece di una impediscono all’evoluzione di trovare un controllore capace di gestire una sola posizione iniziale. Z è costante a tratti — una piccola variazione dei pesi di solito non cambia affatto il numero di passi, quindi il gradiente è nullo quasi ovunque. Ecco perché l’evoluzione.

Strategia evolutiva (5, 20): cinque genitori con pesi casuali in [−1, 1]; in ogni generazione venti figli, ciascuno ottenuto da un genitore casuale aggiungendo 0,5 · N(0, 1) a ogni peso; i nuovi genitori sono i cinque figli migliori.

import random

def regulator(w, s):                 # s = (x, v, θ, ω)
    u = w[0]*s[0] + w[1]*s[1] + w[2]*s[2] + w[3]*s[3] + w[4]
    return 10 if u > 0 else -10       # attivazione a gradino: forza ±10 N

def zdatnost(w):                     # simuluj(): passi fino alla caduta, al massimo 1000
    return sum(simuluj(regulator, w, start) for start in STARTY) / 3

rodice = [[random.uniform(-1, 1) for _ in range(5)] for _ in range(5)]
for generace in range(30):
    deti = [[wi + 0.5 * random.gauss(0, 1) for wi in random.choice(rodice)]
            for _ in range(20)]
    deti.sort(key=zdatnost, reverse=True)
    rodice = deti[:5]                # (5, 20): sopravvivono solo i figli

Esempio — come decide il controllore evoluto

Pesi trovati dall’evoluzione (arrotondati): w = (0,05; 1,01; 1,37; 4,23), b = 0,09 per (x, v, θ, ω).

asta inclinata, ferma: (0, 0, 0,05, 0) → u = 1,37 · 0,05 + 0,09 ≈ +0,16 → +10 N, il carrello passa sotto l’asta

asta inclinata, ma già in fase di ritorno: (0, 0, 0,05, −0,1) → u = 0,07 − 0,42 + 0,09 ≈ −0,26 → −10 N, il carrello frena

Nel secondo caso l’asta è inclinata allo stesso modo, ma il controllore spinge nel verso opposto: la velocità angolare −0,1 rad/s con peso 4,23 conta più dell’angolo 0,05 rad con peso 1,37. L’asta sta tornando da sola, e se il carrello continuasse a spingere, oscillerebbe dall’altra parte. Il controllore ingenuo «solo in base all’angolo» spingerebbe allo stesso modo in entrambi gli stati — per questo fa oscillare l’asta.

3. Perché l’evoluzione e non il gradiente

• Ricompensa sparsa. Con il pendolo, un gioco o un robot la qualità si vede solo dopo un intero episodio. All’evoluzione basta un solo numero alla fine.
• Parti non derivabili. Attivazione a gradino, simulatore fisico, regole del gioco — l’evoluzione non ha bisogno di derivarli.
• Parallelismo. Ogni individuo si può valutare in modo indipendente su un computer diverso.
• Struttura. Il gradiente sa regolare i pesi, ma non aggiungere un neurone. L’evoluzione può cambiare anche la forma della rete.

Lo svantaggio è la voracità: invece di un unico gradiente che indica la direzione per tutti i pesi contemporaneamente, l’evoluzione prova modifiche casuali. Per reti con milioni di pesi il gradiente è di solito molto più efficiente, ammesso che lo si possa calcolare.

4. Quando i pesi non bastano: XOR

La funzione XOR restituisce 1 quando esattamente uno dei due ingressi vale 1. Come ha mostrato la parte Logica e dimostrazioni, un singolo neurone non la sa calcolare: la sua uscita divide il piano degli ingressi con una retta, e nessuna retta separa i punti (0, 1), (1, 0) da (0, 0), (1, 1). Per lo XOR serve almeno un neurone nascosto. E qui si apre una domanda che la sola evoluzione dei pesi non risolve: quanti neuroni, e come collegarli?

Teorema — lo XOR non è linearmente separabile

Non esistono numeri w₁, w₂, b tali che w₁x₁ + w₂x₂ + b > 0 valga esattamente per i punti in cui lo XOR è uguale a 1.

Dimostrazione. Se tali numeri esistessero, varrebbe

(0, 0): b ≤ 0    (1, 1): w₁ + w₂ + b ≤ 0

(1, 0): w₁ + b > 0    (0, 1): w₂ + b > 0

Sommando la prima riga si ottiene w₁ + w₂ + 2b ≤ 0, sommando la seconda w₁ + w₂ + 2b > 0. Contraddizione. ∎

La dimostrazione non usa la forma della funzione di attivazione — vale per ogni singolo neurone la cui uscita dipende solo dal segno della somma pesata (il gradino come la sigmoide con soglia 0,5).

Si può rispondere a mano — progettare l’architettura e lasciare all’evoluzione solo la regolazione dei pesi. Ma nei problemi più complessi non abbiamo idea di quale architettura sia quella giusta. Perché non lasciar evolvere anche quella?

5. NEAT: evoluzione di reti che crescono

I tentativi di far evolvere la struttura delle reti si scontravano con tre problemi. Come incrociare due reti di forma diversa? Come dare una possibilità a una nuova struttura che all’inizio è peggiore, perché i suoi nuovi pesi non sono ancora regolati? E come evitare che le reti si gonfino inutilmente? Kenneth Stanley e Risto Miikkulainen nel 2002 hanno risposto con l’algoritmo NEAT (NeuroEvolution of Augmenting Topologies), basato su tre idee.

Definizione — genoma NEAT e marcature storiche

Il genoma è una lista di geni di connessione; ogni gene ha un neurone di origine e uno di destinazione, un peso, un indicatore attivo/disattivo e un numero di innovazione. Ogni volta che una mutazione crea per la prima volta nella popolazione una nuova connessione, questa riceve il successivo numero di innovazione libero; la stessa modifica strutturale in un altro individuo riceve lo stesso numero.

Mutazioni: modifica dei pesi; aggiunta di una connessione tra due neuroni finora non collegati; aggiunta di un neurone — una connessione esistente a → b con peso w viene disattivata e sostituita dalla coppia a → h con peso 1 e h → b con peso w.

L’incrocio allinea i geni dei genitori secondo i numeri di innovazione: i geni corrispondenti si ereditano a caso da uno dei due genitori, gli altri dal genitore con fitness maggiore.

Esempio — aggiunta di un neurone su una connessione con peso 2

Il nostro NEAT usa, come l’articolo originale, una sigmoide più ripida σ(z) = 1 / (1 + e^−4,9z). La connessione x₁ → y con peso 2 contribuiva all’uscita con 2x₁. Dopo la suddivisione ci sono x₁ → h con peso 1 e h → y con peso 2:

x₁ = 1:   2 · σ(1) = 2 · 0,993 ≈ 1,985   (prima 2)

x₁ = 0:   2 · σ(0) = 2 · 0,5 = 1   (prima 0)

«In modo simile» qui significa quindi solo in parte: per l’ingresso 1 la variazione è trascurabile, per l’ingresso 0 alla somma si aggiunge un uno, perché la sigmoide in zero restituisce un mezzo. La rete così peggiora un po’ — ed è proprio per questo che la nuova struttura ha bisogno della protezione di cui si parla più avanti.

Definizione — speciazione e condivisione della fitness

La distanza di compatibilità tra due genomi è

δ = c₁ E / N + c₂ D / N + c₃ W̄,

dove E è il numero di geni in eccesso (con numeri oltre la fine del genoma più corto), D il numero di geni disgiunti (mancanti nel mezzo), W̄ la differenza media dei pesi dei geni corrispondenti e N la dimensione del genoma più grande (per genomi piccoli 1). I genomi con δ sotto una soglia appartengono alla stessa specie. La fitness di un individuo si divide per la dimensione della sua specie e i figli si ripartiscono tra le specie in base alla loro fitness media.

δ = c₁ E / N + c₂ D / N + c₃ W̄

c₁ E

geni in eccesso — struttura che un genoma ha acquisito solo dopo l’ultima «invenzione» comune; indica un ramo evolutivo più giovane e diverso

c₂ D

geni disgiunti — invenzioni risalenti a quando entrambi esistevano già, che ha solo uno dei due; un’ulteriore misura della differenza di struttura

N

dimensione del genoma più grande — perché due genomi grandi che differiscono per pochi geni su molti non risultino distanti quanto due genomi piccoli che differiscono quasi in tutto; per genomi con meno di 20 geni si prende N = 1

c₃ W̄

differenza media dei pesi dei geni corrispondenti — reti collegate allo stesso modo ma con pesi molto diversi calcolano funzioni diverse; il peso c₃ è minore, perché la struttura cambia più di rado e conta di più

Esempio — la distanza dopo l’aggiunta di un neurone

Il genoma A ha i geni 1–5. Il genoma B deriva da un antenato simile: ha anch’esso i geni 1–5 (il gene 3 disattivato, perché lo ha suddiviso un nuovo neurone) e in più i geni 6 e 7 dovuti all’aggiunta del neurone. I pesi dei geni corrispondenti differiscono di 0,2; 0,6; 0; 0,9 e 0,8.

corrispondenti: 1–5 → W̄ = (0,2 + 0,6 + 0 + 0,9 + 0,8) / 5 = 0,5

in eccesso: 6, 7 (oltre la fine del genoma più corto, che termina con il gene 5) → E = 2;   disgiunti: nessuno → D = 0

δ = 1 · 2 / 1 + 1 · 0 / 1 + 0,4 · 0,5 = 2,2 < 3 → stessa specie

Se B acquisisse un’altra connessione (gene 8), risulterebbe E = 3 e δ = 3,2 ≥ 3 — B fonderebbe una nuova specie. Un singolo nuovo neurone quindi non esclude la rete dalla specie, ma un nuovo neurone più una nuova connessione sì.

n_k = P · F̄_k / ∑_j F̄_j,   F̄_k = ∑_{i ∈ Sk} f_i / |S_k|

n_k

numero di figli della specie k nella generazione successiva — è così che NEAT premia il successo, non selezionando singoli individui dall’intera popolazione

P

dimensione della popolazione (150) — i figli si spartiscono come una torta, la popolazione non cresce né diminuisce

|S_k|

numero di membri della specie — condivisione della fitness: la fitness di ogni membro si divide per la dimensione della sua specie, f′_i = f_i / |S_k|; così una specie grande non può ottenere di più solo perché è grande

F̄_k

somma delle fitness condivise della specie, cioè la sua fitness media — sulla fetta di torta decide la qualità, non il numero

∑_j F̄_j

somma su tutte le specie — la divisione produce quote che sommano a 1, così si ripartiscono esattamente P figli (dopo l’arrotondamento per difetto il resto va alla specie migliore)

Esempio — perché la condivisione protegge una nuova specie

Popolazione di 150: la specie affermata A ha 120 reti con fitness media 9,0, la nuova specie B con un neurone nascosto 30 reti con fitness media 7,5.

con condivisione: n_A = 150 · 9,0 / 16,5 ≈ 81,8 → 81 (+1 di resto) = 82,   n_B = 150 · 7,5 / 16,5 ≈ 68,2 → 68

senza condivisione (in base alla somma delle fitness 1 080 e 225): A ≈ 150 · 1 080 / 1 305 ≈ 124,   B ≈ 26

Senza condivisione la nuova specie si estinguerebbe in poche generazioni, perché è peggiore e più piccola. Con la condivisione riceve più figli di quanti membri abbia, e ha il tempo di regolare i pesi.

La terza idea è la più semplice: partire dal minimo. All’inizio nessuna rete ha neuroni nascosti — gli ingressi portano direttamente all’uscita. La struttura cresce solo quando conviene. Le reti risultanti tendono quindi a essere piccole.

Tutto insieme — una generazione del nostro NEAT semplificato (le probabilità sono quelle con cui gira il programma per lo XOR):

popolazione ← 150 reti minime (x₁, x₂ e bias direttamente in y, pesi casuali in [−2, 2])
per la generazione g = 0, 1, …, 100:
    valuta ogni rete con la fitness f
    se una rete risolve il problema: fine
    dividi le reti in specie: la rete va nella prima specie con il cui rappresentante
                              ha δ < 3,
                              altrimenti ne fonda una nuova
    elimina le specie che non sono migliorate per 15 generazioni (tranne quella con la
        rete migliore)
    alla specie k assegna n_k = 150 · F̄_k / ∑ F̄_j figli
    in ogni specie:
        genitori ← il miglior 20 % dei membri
        se la specie ha più di 5 membri, la sua rete migliore passa invariata
        ogni ulteriore figlio:
            con probabilità 0,75 incrocio di due genitori, altrimenti copia di uno
            con probabilità 0,8 modifica i pesi
                (90 %: w ← w + N(0, 1), 10 %: nuovo casuale)
            con probabilità 0,1 aggiungi una connessione
            con probabilità 0,03 aggiungi un neurone (suddividi una connessione attiva
                casuale)

6. NEAT su XOR

Il nostro NEAT semplificato ha una popolazione di 150 reti e al massimo 100 generazioni. Nell’esecuzione della figura ha risolto lo XOR alla generazione 27 con una rete con un solo neurone nascosto e sette connessioni — la soluzione più piccola possibile:

f = ( 4 − ∑ |y − t| )²

∑ |y − t|

errore — somma degli scarti dell’uscita y dal valore corretto t su tutti e quattro gli ingressi; in valore assoluto, perché gli errori per eccesso e per difetto non si annullino a vicenda

4

errore massimo possibile (quattro ingressi, ogni scarto al più 1) — sottraendo, l’errore che vogliamo ridurre diventa una fitness che l’evoluzione aumenta, ed è sempre non negativa

²

elevamento al quadrato — accentua le differenze vicino alla soluzione: una rete con errore 0,5 ha fitness 12,25, una con errore 1 solo 9, così la selezione premia di più gli ultimi punti percentuali

La rete si può leggere. Il neurone nascosto h si accende solo quando entrambi gli ingressi sono 0 (entrambi hanno un grande peso negativo, il bias è positivo). Le connessioni dirette all’uscita da sole calcolerebbero «non entrambi insieme» — uscita 1 per tutto tranne (1, 1) —, ma il peso fortemente negativo da h la spegne per (0, 0). Le uscite 0,000; 0,855; 1,000 e 0,005 arrotondate sono esattamente lo XOR. Nel frattempo il numero di specie è salito da una a circa venti.

Esempio — calcolo della rete per tutti e quattro gli ingressi

Pesi (arrotondati): verso h da x₁, x₂ e dal bias −3,37; −3,67; 0,95; verso y da x₁, x₂, dal bias e da h −1,42; −2,96; 3,32; −5,69. L’attivazione è σ(z) = 1 / (1 + e^−4,9z). Prima si calcola h, poi y (la tabella usa i pesi non arrotondati, quindi un ricalcolo a mano può differire nell’ultima cifra):

(x1, x2)	zh	h	zy	y	|y − t|
(0, 0)	0,95	0,990	3,32 − 5,69 · 0,990 = −2,32	0,000	0,000
(0, 1)	−2,72	0,000	−2,96 + 3,32 = 0,36	0,855	0,145
(1, 0)	−2,43	0,000	−1,42 + 3,32 = 1,89	1,000	0,000
(1, 1)	−6,09	0,000	−1,42 − 2,96 + 3,32 = −1,06	0,005	0,005

L’errore è 0,150 e la fitness (4 − 0,150)² ≈ 14,82 su 16. La rete risponde peggio per (0, 1): l’uscita 0,855 sta correttamente sopra la metà, ma non vicino a uno — per la soluzione basta, un’ulteriore regolazione dei pesi alzerebbe ancora la fitness.

Su cinquanta esecuzioni con semi diversi NEAT ha risolto lo XOR in 47, in media in 31 generazioni, con 2,6 neuroni nascosti che fanno davvero qualcosa. L’articolo originale riporta 32 generazioni e 2,35 neuroni nascosti — il nostro NEAT semplificato ci va quindi vicino.

7. Su cosa si regge NEAT

Le stesse 50 esecuzioni con una parte dell’algoritmo disattivata:

Senza speciazione NEAT quasi non funziona. Una rete con un neurone nascosto, appena nata, è peggiore delle reti affermate che non lo hanno, perché i suoi nuovi pesi sono casuali — e in un’unica competizione comune la selezione la elimina subito. La speciazione la protegge finché non matura. Senza incrocio lo XOR si risolve comunque, solo più lentamente e con reti più grandi (3,1 neuroni nascosti attivi): l’incrocio aiuta a mettere insieme le scoperte parziali di individui diversi.

8. Gli eredi di NEAT

• HyperNEAT (Stanley e coll., 2009) fa evolvere una piccola rete che a sua volta genera i pesi di una rete grande in base alla geometria del problema — come un genoma che non descrive ogni cellula, ma le regole di crescita.
• La ricerca della novità (Lehman e Stanley, 2011) non premia la fitness, ma il comportamento nuovo. In un labirinto con ingannevoli vicoli ciechi ha trovato l’obiettivo più spesso della ricerca guidata dalla fitness.
• Neuroevoluzione profonda. Nel 2017 il team di Uber AI ha mostrato che un semplice algoritmo genetico è in grado di addestrare reti con milioni di pesi sui giochi Atari in modo paragonabile all’apprendimento per rinforzo.
• Ricerca evolutiva di architetture neurali. La rete AmoebaNet (Google, 2019) è nata dall’evoluzione di blocchi costitutivi e nel riconoscimento di immagini su ImageNet era all’epoca tra le migliori. Oggi le architetture le progettano più spesso le persone o altri metodi, ma l’evoluzione resta una delle possibilità.

9. Riepilogo

• La neuroevoluzione coltiva reti neurali con algoritmi evolutivi — è utile dove il gradiente non si può calcolare o dove la ricompensa arriva solo alla fine.
• L’evoluzione dei pesi di un singolo neurone tiene in equilibrio il pendolo inverso su un carrello per 20 secondi dopo circa trecento tentativi; pesi casuali danno in mediana 9 passi.
• Per lo XOR un solo neurone non basta — bisogna cambiare la struttura della rete.
• NEAT fa evolvere pesi e struttura: le marcature storiche rendono possibile l’incrocio, la speciazione protegge le nuove strutture e le reti crescono a partire dal minimo.
• Senza speciazione NEAT ha risolto lo XOR in 1 esecuzione su 50, con la speciazione in 47 — e la soluzione migliore aveva un solo neurone nascosto.

Vuoi metterci le mani? Chiedi a un agente IA di scrivere il pendolo inverso su un carrello con l’evoluzione del controllore, e poi prova due aste di lunghezza diversa sullo stesso carrello — la celebre versione più difficile in cui NEAT a suo tempo eccelleva.

La vedi diversamente? Scrivi a support@coden-app.com.