Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero

La (1+1)-ES e la regola di un quinto, popolazione e autoadattamento sulla funzione di Rastrigin, CMA-ES, programmi come alberi, regressione simbolica che trova la terza legge di Keplero nei dati sui pianeti, e il rigonfiamento dei programmi.

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

Serie Basi di IA Parte 28 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

Negli anni Sessanta due studenti dell’Università tecnica di Berlino, Ingo Rechenberg e Hans-Paul Schwefel, stavano in una galleria del vento davanti a una piastra snodata. Volevano trovare la forma con la minima resistenza, ma per calcolarla mancavano sia le equazioni sia i computer. Così tiravano a sorte: ruotavano gli snodi a caso, misuravano la resistenza e, se era minore, tenevano la nuova forma. Da quell’esperimento è nata la strategia evolutiva: un’evoluzione che invece di uni e zeri regola numeri. Un quarto di secolo dopo John Koza ha mostrato che con l’evoluzione si possono far crescere anche interi programmi.

Questa parte prosegue l’articolo Algoritmi genetici. Lì un individuo era una stringa di bit; qui sarà un vettore di numeri reali e un albero di programma.

1. Evoluzione di numeri: la (1+1)-ES

Algoritmo — (1+1)-ES

Minimizziamo f : ℝⁿ → ℝ. Un individuo è un punto x ∈ ℝⁿ, σ > 0 è l’ampiezza del passo. A ogni generazione:

1. crea un figlio y = x + σ · z, dove z ~ N(0, I) è un vettore di numeri indipendenti con distribuzione normale;
2. se f(y) ≤ f(x), sostituisci x ← y.

y = x + σ · z,   z ~ N(0, I)

y

figlio — il nuovo candidato che valuteremo

x

genitore — il miglior punto trovato finora; il figlio nasce nel suo intorno, perché vicino a un buon punto di solito ci sono altri buoni punti

σ

ampiezza del passo — un solo numero che stabilisce quanto lontano dal genitore si cerca; il rumore z ha varianza 1, solo σ gli dà la scala del problema

z ~ N(0, I)

direzione e lunghezza del tentativo — la media 0 significa che nessuna direzione è favorita in partenza; la matrice identità I, che tutte le coordinate cambiano in modo indipendente e con la stessa forza

Definizione — distribuzione normale N(0, 1) e N(0, I)

Una variabile aleatoria Z ha distribuzione normale standard N(0, 1) se ha densità φ(z) = e^−z²/2 / √(2π); il suo valore atteso è 0 e la varianza 1. Circa il 68 % dei valori cade nell’intervallo [−1, 1] e il 95 % in [−1,96; 1,96].

Un vettore z ~ N(0, I) in ℝⁿ ha n componenti indipendenti con distribuzione N(0, 1). La sua lunghezza è tipicamente intorno a √n (per n = 10 circa 3,2), perché E‖z‖² = n.

Il nostro programma genera numeri normali con il metodo di Box-Muller a partire da due numeri uniformi u₁, u₂ ∈ (0, 1): z = √(−2 ln u₁) · cos(2πu₂).

Proviamo sulla funzione più semplice possibile, la sfera f(x) = x₁² + … + x₁₀² in dieci dimensioni. Il minimo è ovviamente in zero; partiamo dal punto (3, …, 3), dove f = 90. Come scegliere σ? Un valore grande scende in fretta, ma vicino al minimo continua a oltrepassarlo. Uno piccolo è preciso, ma ci mette un’eternità ad arrivare in fondo.

2. La regola di un quinto

Definizione — regola di un quinto (Rechenberg, 1973)

Se la quota di mutazioni riuscite (figlio migliore del genitore) è maggiore di 1/5, aumenta σ; se è minore, riducilo. Una delle forme possibili: dopo un successo σ ← σ · e^1/3, dopo un insuccesso σ ← σ · e^−1/12. L’ampiezza del passo resta in media invariata esattamente quando riesce un quinto delle mutazioni: (1/5) · (1/3) = (4/5) · (1/12).

I due rami della regola si possono scrivere con un’unica formula; s = 1 dopo un successo e 0 dopo un insuccesso:

σ ← σ · exp( 5/12 · ( s − 1/5 ) )

σ

ampiezza del passo — cambia per moltiplicazione, non per somma: resta positiva e il passo può ridursi di molti ordini di grandezza (da 1 fino ai millesimi), come richiede la vicinanza del minimo

5/12

velocità di adattamento — dopo un successo exp(5/12 · 4/5) = e^1/3 ≈ 1,40, dopo un insuccesso exp(−5/12 · 1/5) = e^−1/12 ≈ 0,92; un numero più grande reagirebbe più in fretta, ma σ oscillerebbe di più

s

esito dell’ultimo tentativo (1 = il figlio non era peggiore) — l’unica informazione di cui la regola ha bisogno

1/5

tasso di successo obiettivo — quando riesce esattamente un quinto dei tentativi, la media di s − 1/5 è zero e σ in media non cambia

La regola di un quinto scende sotto 10⁻⁶ in 587 valutazioni, e la linea del grafico cala in modo uniforme, perché il passo si riduce con la stessa rapidità con cui si avvicina il minimo. Con σ = 1 fisso l’algoritmo urta presto contro un «pavimento» intorno a uno, sotto il quale con salti così grandi non si scende. Con σ = 0,01 scende, ma lentamente: neppure dopo 5 000 valutazioni è sotto 10⁻⁴.

import math, random

def es_1_plus_1(f, x, sigma=1.0, kroku=1000):
    fx = f(x)
    for _ in range(kroku):
        y = [xi + sigma * random.gauss(0, 1) for xi in x]
        fy = f(y)
        if fy <= fx:
            x, fx = y, fy
            sigma *= math.exp(1 / 3)     # successo: aumenta
        else:
            sigma *= math.exp(-1 / 12)   # insuccesso: riduci
    return x, fx

Esempio — i primi dodici passi dell’esecuzione del grafico

Partenza x = (3, …, 3), f(x) = 90, σ = 1. La colonna σ è l’ampiezza del passo dopo l’aggiornamento:

passo	f(y)	successo?	f(x)	σ
1	115,31	no	90,00	0,920
2	95,78	no	90,00	0,846
3	123,94	no	90,00	0,779
4	107,86	no	90,00	0,717
5	101,54	no	90,00	0,659
6	113,11	no	90,00	0,607
7	94,03	no	90,00	0,558
8	95,09	no	90,00	0,513
9	86,27	sì	86,27	0,717
10	114,52	no	86,27	0,659
11	97,72	no	86,27	0,607
12	102,44	no	86,27	0,558

dopo 8 insuccessi: σ = e^−8/12 ≈ 0,513

il passo 9 riesce (86,27 < 90): σ = 0,513 · e^1/3 ≈ 0,513 · 1,396 ≈ 0,717

Con σ = 1 un passo in dieci dimensioni è lungo circa √10 ≈ 3,2 e i primi otto figli sono peggiori della partenza, quindi la regola restringe il passo. Poi i successi arrivano più spesso e σ si assesta dove riesce circa un tentativo su cinque: in tutta l’esecuzione sono riusciti 99 tentativi su 587, cioè il 17 %. Man mano che il punto si avvicina al minimo, con lui cala anche il passo: alla fine dell’esecuzione, dopo 580 valutazioni, σ ≈ 0,00055.

3. Popolazione e autoadattamento

La sfera ha un unico minimo. I problemi reali ne hanno spesso moltissimi, e lì un solo individuo non basta. Una tipica funzione di prova è la funzione di Rastrigin: f(x) = 10n + ∑ (x_i² − 10 cos 2πx_i). È una sfera in cui qualcuno ha scavato una griglia regolare di buche; il minimo globale 0 è nell’origine e intorno ce ne sono centinaia di locali.

f(x) = 10n + ∑_i=1ⁿ ( x_i² − 10 cos 2πx_i )

10n

spostamento verso l’alto — nell’origine il coseno sottrae al massimo 10 per coordinata, la costante lo restituisce perché il minimo globale valga esattamente 0

x_i²

sfera — la pendenza complessiva verso l’origine; senza di essa tutte le buche sarebbero ugualmente profonde e nessun minimo sarebbe globale

10 cos 2πx_i

onde di periodo 1 e ampiezza 10 — scavano una buca a ogni numero intero; l’ampiezza è molto maggiore della pendenza della sfera tra buche vicine, quindi una ricerca locale resta bloccata nella buca più vicina

Esempio — la partenza e le buche vicine (n = 2)

partenza (4,2; −3,8): x₁² = 17,64,   10 cos(2π · 4,2) = 10 cos(0,4π) ≈ 3,09

x₂² = 14,44,   10 cos(2π · (−3,8)) = 10 cos(0,4π) ≈ 3,09

f = 20 + (17,64 − 3,09) + (14,44 − 3,09) ≈ 45,90

fondo delle buche accanto all’origine, in (±1; 0) e (0; ±1): f ≈ 0,99 (nel punto 0,995, non esattamente 1: la sfera lo tira verso l’origine)

fondo delle buche diagonali in (±1; ±1): f ≈ 1,99

Il valore 1,49 alla generazione 8 (vedi sotto) indica quindi una popolazione in una buca vicina, non ancora sul fondo.

Definizione — (μ, λ)-ES e (μ + λ)-ES con autoadattamento

La popolazione ha μ genitori; ogni generazione crea λ > μ figli. Nella (μ, λ) sopravvivono i μ migliori figli e i genitori muoiono; nella (μ + λ) si sceglie tra genitori e figli insieme.

Autoadattamento: ogni individuo porta con sé la propria ampiezza del passo σ. Il figlio prima la muta, σ′ = σ · e^{τ · N(0, 1)} con τ ≈ 1/√(2n), e solo dopo sposta con essa la posizione: y = x + σ′ · N(0, I).

σ′ = σ · e^{τ · N(0, 1)},   τ = 1/√(2n)

σ′

passo del figlio — con esso si sposta subito la posizione, così la fitness del figlio rivela se il passo era buono

σ

passo del genitore — si eredita; il figlio parte da ciò che ha funzionato per il genitore

τ

tasso di apprendimento del passo — quanto può cambiare il passo tra una generazione e l’altra; diminuisce al crescere del numero di dimensioni n, perché una sola fitness porta allora meno informazione sulla bontà del passo

N(0, 1)

variazione casuale — simmetrica attorno a zero, quindi ingrandire e ridurre sono ugualmente probabili; sulla direzione decide solo la selezione

Esempio — mutazione del passo per n = 2

τ = 1/√(2 · 2) = 1/2

N(0, 1) = +1:   σ′ = σ · e^0,5 ≈ 1,65 σ;   N(0, 1) = −1:   σ′ = σ · e^−0,5 ≈ 0,61 σ

Un figlio tipico prova quindi un passo da circa il 40 % più piccolo a circa il 65 % più grande di quello del genitore. Nella nostra esecuzione il passo del miglior individuo è sceso in 15 generazioni da 2 a 0,011: quasi duecento volte.

import math, random

def es_mi_lambda(f, start, mi=15, lam=100, sigma=2.0, generaci=80):
    n = len(start)
    tau = 1 / math.sqrt(2 * n)
    rodice = [(start, sigma)] * mi
    for _ in range(generaci):
        deti = []
        for _ in range(lam):
            x, s = random.choice(rodice)                    # genitore casuale
            s = s * math.exp(tau * random.gauss(0, 1))      # prima muta il passo
            y = [xi + s * random.gauss(0, 1) for xi in x]   # poi con esso la posizione
            deti.append((y, s))
        deti.sort(key=lambda d: f(d[0]))
        rodice = deti[:mi]          # (μ, λ): sopravvivono solo i figli migliori
    return rodice[0]

La popolazione parte intorno al punto (4,2; −3,8), dove f ≈ 45,9. All’inizio è sparsa su più buche contemporaneamente e si raccoglie verso quelle più profonde. Alla generazione 8 il miglior individuo è ancora in una buca vicina (f ≈ 1,49), ma l’ampiezza del passo è già scesa da 2 a 0,27. Alla generazione 15 la popolazione è nel minimo globale e il passo si è ridotto a un centesimo, per poterlo rifinire.

Su cento esecuzioni con semi diversi, la (15, 100)-ES ha trovato il minimo globale in 32 casi. Per confronto, la (1+1)-ES con la regola di un quinto e lo stesso budget di 8 000 valutazioni: in uno solo. Sulle sfere un singolo individuo è il più rapido, su un terreno accidentato vince la popolazione, e anche lei finisce spesso in una delle buche vicine.

4. CMA-ES

L’autoadattamento regola solo la lunghezza del passo. E se il minimo sta in una valle stretta e obliqua, dove conviene fare passi lunghi in una direzione e corti in un’altra? CMA-ES (Hansen e Ostermeier, 2001) impara dai passi riusciti l’intera matrice di covarianza della mutazione: la forma della nuvola da cui estrae i figli. Durante la ricerca la nuvola ruota e si allunga lungo la valle. Per ottimizzare funzioni continue di cui non conosciamo il gradiente, CMA-ES è oggi uno dei metodi più affidabili.

Definizione — mutazione con matrice di covarianza

Per una matrice simmetrica definita positiva C ∈ ℝ^n×n, z ~ N(0, C) è un vettore con valore atteso 0 e covarianze E[z_iz_j] = C_ij. Si ottiene da un rumore ordinario: z = Au, dove u ~ N(0, I) e AA^T = C. Il figlio è y = m + σ · z, dove m è il centro della popolazione.

I punti con la stessa densità stanno su un ellissoide; i suoi assi sono gli autovettori di C e le lunghezze degli assi sono proporzionali alle radici degli autovalori. Per C = I è una sfera e otteniamo una normale strategia evolutiva.

In forma semplificata (la vera CMA-ES aggiunge anche i cosiddetti cammini evolutivi e un proprio controllo di σ, vedi N. Hansen, The CMA Evolution Strategy: A Tutorial, 2016) la matrice dopo ogni generazione si sposta verso i passi riusciti:

C ← (1 − c) C + c ∑_i=1^μ w_i z_iz_i^T

C

matrice di covarianza della mutazione — la forma della nuvola da cui si estraggono i figli

1 − c

memoria — la vecchia matrice si avvicina solo un po’ alla nuova informazione, perché una generazione è un campione piccolo e casuale

c

tasso di apprendimento della matrice, un numero tra 0 e 1 — quanto peso ricevono i passi dell’ultima generazione

∑ w_i

media pesata sui μ figli migliori; i pesi sono positivi, sommano a 1 e un figlio migliore ne ha uno maggiore: impariamo solo dai passi che hanno pagato

z_iz_i^T

il passo riuscito z_i = (y_i − m)/σ come matrice — allunga la nuvola proprio nella sua direzione

Esempio — un passo riuscito lungo la diagonale

C = I (nuvola circolare), un unico passo riuscito z = (1, 1), c = 0,2:

zz^T = [[1, 1], [1, 1]]

C ← 0,8 · [[1, 0], [0, 1]] + 0,2 · [[1, 1], [1, 1]] = [[1; 0,2], [0,2; 1]]

autovalori: 1 + 0,2 = 1,2 nella direzione (1, 1) e 1 − 0,2 = 0,8 nella direzione (1, −1)

La nuvola si è allungata lungo la direzione riuscita e ristretta di traverso: dopo qualche generazione così, si distende lungo la valle.

5. Programmazione genetica

Definizione — un programma come albero

Sono dati un insieme di funzioni F (con le loro arietà) e un insieme di terminali T (variabili e costanti). Un programma è un albero radicato i cui nodi interni sono funzioni di F con tanti figli quanta è la loro arietà, e le cui foglie sono terminali di T. Il valore del programma si calcola dalle foglie alla radice.

Chiusura: ogni funzione deve accettare l’uscita di qualunque altra. Per questo si usano la divisione protetta (la divisione per zero restituisce 1) e la radice del valore assoluto.

John Koza dell’Università di Stanford ha descritto il metodo nel 1992 nel libro Genetic Programming e l’ha mostrato su decine di problemi, dal controllo di un robot alla ricerca di formule.

Esempio — valutazione dell’albero (a ÷ 5) × √a per la Terra

Dalle foglie alla radice, a = 149,6 (milioni di km):

ramo sinistro: a ÷ 5 = 149,6 / 5 = 29,92

ramo destro: √a = √149,6 ≈ 12,231

radice: 29,92 × 12,231 ≈ 365,95 giorni   (valore reale 365,26, scarto +0,19 %)

def gp(populace, generaci, p_krizeni=0.9, max_hloubka=7):
    for _ in range(generaci):
        dalsi = [nejlepsi(populace)]                  # elitismo: il migliore
        while len(dalsi) < len(populace):
            if random.random() < p_krizeni:           # incrocio per scambio di sottoalberi
                a, b = turnaj(populace), turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), podstrom(b, nahodny_uzel(b)))
            else:                                     # mutazione: ramo → nuovo casuale
                a = turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), nahodny_strom(hloubka=2))
            if hloubka(dite) <= max_hloubka:         # scartiamo i figli troppo profondi
                dalsi.append(dite)
        populace = dalsi
    return nejlepsi(populace)        # errore minimo; a parità, l'albero più piccolo

6. Regressione simbolica: la legge di Keplero

Giovanni Keplero cercò per dieci anni la relazione tra la distanza di un pianeta dal Sole e il suo periodo orbitale; pubblicò la terza legge nel 1619. Diamo alla programmazione genetica lo stesso compito. Ha a disposizione otto pianeti (il semiasse maggiore a in milioni di chilometri e il periodo orbitale T in giorni), le operazioni +, −, ×, ÷ e √, la variabile a e le cifre da 1 a 9. L’errore di un programma è lo scarto relativo medio dai periodi orbitali reali. La popolazione ha 300 programmi e 40 generazioni.

Definizione — regressione simbolica

Per dati (x_i, y_i) la regressione simbolica cerca un’espressione g di una grammatica data (funzioni e terminali) che minimizzi l’errore ∑ ℓ(g(x_i), y_i). A differenza della regressione ordinaria, la forma del modello non è data in anticipo, solo i mattoni.

Con precisione, l’errore di un programma g è la media delle differenze assolute dei logaritmi:

E(g) = (1/8) ∑_i=1⁸ | ln g(a_i) − ln T_i |

(1/8) ∑

media sugli otto pianeti — l’errore non dipende da quanti dati abbiamo e si può leggere come «scarto tipico per pianeta»

| … |

valore assoluto — una previsione più grande dell’1 % è cattiva quanto una più piccola dell’1 %, e gli errori di segno diverso non si annullano

ln g(a_i) − ln T_i

la differenza dei logaritmi è ln(g/T), cioè lo scarto relativo: per scarti piccoli ln(1 + r) ≈ r. I periodi orbitali differiscono di quasi mille volte (88 giorni Mercurio, 60 190 Nettuno); con una differenza ordinaria sull’errore deciderebbe solo Nettuno

Il miglior programma della popolazione iniziale, casuale, si scosta dai periodi orbitali reali in media del 32 %. Alla terza generazione ha già uno scarto dell’8 % e la forma giusta a^1,5, solo con la costante 0,22. Alla quindicesima generazione arriva questo:

T = a · √a / 5, cioè T proporzionale ad a^3/2, ovvero T² proporzionale ad a³. È la terza legge di Keplero. Lo scarto medio è dello 0,30 % e la costante 1/5 è molto vicina al valore vero 0,1996 per queste unità. Su venti esecuzioni con semi diversi, diciotto hanno trovato l’esponente 1,5.

Da dove viene 0,1996? Dalla legge di gravitazione di Newton segue, per un’orbita circolare (e per un’ellisse di semiasse maggiore a, quando la massa del pianeta è trascurabile rispetto al Sole), la forma della legge insieme alla costante:

T = 2π / √(GM_☉) · a^3/2

T

periodo orbitale — il tempo di un giro

2π

un giro è un angolo di 2π; la formula nasce dalla velocità angolare ω come T = 2π/ω

√(GM_☉)

la forza di gravità del Sole (G la costante di gravitazione, M_☉ la massa del Sole) — un’attrazione più forte significa un giro più veloce, perciò sta al denominatore

a^3/2

distanza — la gravità si indebolisce con a² e il percorso è più lungo in proporzione ad a; dall’uguaglianza tra forza centripeta e gravitazionale, ω²a = GM_☉/a², risulta ω ∝ a^−3/2

Esempio — la costante in milioni di km e giorni

Il parametro gravitazionale del Sole è GM_☉ = 1,327 124 · 10²⁰ m³/s² (valore nominale dell’Unione Astronomica Internazionale, risoluzione B3 del 2015). L’unità di lunghezza è 10⁹ m, quindi a^3/2 in metri è (10⁹)^3/2 = √(10²⁷) volte più grande:

√(10²⁷ / 1,327 124 · 10²⁰) = √(7,535 · 10⁶) ≈ 2 745,0 s

2π · 2 745,0 s ≈ 17 247 s

17 247 s / 86 400 s/giorno ≈ 0,1996 giorni

Il programma con la costante 1/5 = 0,2 si scosta quindi dello 0,19 %: esattamente lo scarto risultato sopra per la Terra.

7. Il rigonfiamento

Ma l’evoluzione non si è fermata alla bella formula. Entro la generazione 40 ha «migliorato» lo scarto allo 0,23 % con questo:

L’albero ha sedici nodi invece di sei, e i rami aggiunti non fanno altro che ritoccare la costante e aggirare gli arrotondamenti nei dati. Fisicamente è una formula peggiore, sovradattata a otto pianeti. Intanto la dimensione media dei programmi nella popolazione è cresciuta da 9,8 nodi all’inizio a 23,8 alla ventesima generazione.

Definizione — rigonfiamento e pressione di parsimonia

Il rigonfiamento (bloat) è la crescita della dimensione dei programmi nella popolazione che non corrisponde a un miglioramento della loro fitness. La pressione di parsimonia (parsimony pressure) penalizza la dimensione: o la somma all’errore, F′(g) = F(g) + c · |g|, o la usa come secondo criterio a parità di errore.

F′(g) = F(g) + c · |g|

F′(g)

errore corretto in base al quale si seleziona — più piccolo è meglio

F(g)

errore del programma sui dati — resta la cosa principale che vogliamo ridurre

c

prezzo di un nodo — dice di quanto deve migliorare l’errore perché un nodo in più convenga; lo si sceglie in modo che decida solo per miglioramenti trascurabili

|g|

dimensione del programma, il numero di nodi dell’albero — una misura di complessità che si può calcolare senza capire il programma

Esempio — quale c avrebbe salvato la legge di Keplero

Albero della generazione 15: errore 0,2986 %, 6 nodi. Albero della generazione 40: errore 0,2312 %, 16 nodi. L’albero più piccolo vince quando

0,002 986 + 6c < 0,002 312 + 16c

10c > 0,000 674  ⇒  c > 6,7 · 10⁻⁵

Dieci nodi in più hanno migliorato l’errore di meno di un centesimo di punto percentuale. Con un prezzo superiore allo 0,007 % per nodo, l’albero della generazione 40 avrebbe perso nella selezione contro la legge leggibile della generazione 15.

8. Strategie evolutive e programmi oggi

• Strategie evolutive al posto dell’apprendimento per rinforzo. Nel 2017 OpenAI ha mostrato che una semplice strategia evolutiva sa addestrare reti neurali a controllare robot simulati e a giocare ai videogiochi Atari quasi altrettanto bene dell’apprendimento per rinforzo, e che si può distribuire su migliaia di processori che si scambiano solo pochi numeri.
• Scoprire leggi dai dati. Nel 2009 Schmidt e Lipson hanno fatto ricavare alla regressione simbolica leggi del moto e leggi di conservazione da misure su pendoli. Librerie odierne come PySR si usano in fisica e astronomia, dove una formula leggibile vale più di una scatola nera.
• Evoluzione di algoritmi di apprendimento automatico. Il progetto AutoML-Zero (Google, 2020) ha lasciato che l’evoluzione componesse algoritmi di apprendimento a partire da operazioni matematiche elementari e così ha riscoperto, per esempio, la retropropagazione dell’errore.
• Programmi con modelli linguistici. I sistemi FunSearch e AlphaEvolve della parte precedente sono programmazione genetica in cui la mutazione, invece di un ramo casuale, la fa un modello linguistico.

9. Riepilogo

• Le strategie evolutive mutano numeri reali con un rumore normale di ampiezza del passo σ.
• La regola di un quinto e l’autoadattamento regolano σ automaticamente; CMA-ES impara anche la forma delle mutazioni.
• Sulle sfere basta un individuo, su un terreno accidentato aiuta una popolazione: sulla funzione di Rastrigin 32 successi su 100 contro uno.
• La programmazione genetica fa crescere programmi come alberi; la regressione simbolica ha trovato nei dati sui pianeti la terza legge di Keplero.
• I programmi tendono a gonfiarsi e a sovradattarsi: contro questo aiuta la pressione di parsimonia.

Vuoi metterci le mani? Fai scrivere a un agente IA una regressione simbolica e dagli i tuoi dati, magari il periodo di un pendolo in funzione della lunghezza del filo, e guarda se trova √L.

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