Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione

Genoma e fitness, selezione a torneo, incrocio a un punto, mutazione ed elitismo, teorema degli schemi e convergenza prematura — sul problema dello zaino con ottimo noto, dalla tenda a FunSearch e AlphaEvolve.

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

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

La natura non ha un ingegnere, eppure ha prodotto l’occhio, l’ala e il cervello. Le sono bastate tre cose: gli individui differiscono l’uno dall’altro, trasmettono le loro caratteristiche ai discendenti e quelli più adatti hanno più discendenti. Negli anni Settanta John Holland dell’Università del Michigan mostrò che le stesse tre cose funzionano anche in un computer — come metodo generale per cercare buone soluzioni a problemi che non sappiamo risolvere in modo furbo. Un algoritmo genetico non ha bisogno di un gradiente né di una formula; gli basta saper dire quale di due soluzioni è migliore.

Segue la parte Ricerca locale e ricottura simulata. La ricottura migliorava una sola soluzione; un algoritmo genetico ne migliora un’intera popolazione alla volta.

1. Il problema: uno zaino per l’escursione

Ti stai preparando per un’escursione di più giorni. A casa hai 24 cose — tenda, sacco a pelo, fornelletto, macchina fotografica, libro… — e ognuna pesa qualcosa e serve a qualcosa. Lo zaino può pesare al massimo 10 kg. Che cosa portare perché l’utilità sia la più grande possibile?

Definizione — il problema dello zaino (0/1)

Sono dati n oggetti con pesi w_i > 0 e utilità u_i > 0 e una capacità W. Cerchiamo x ∈ {0, 1}ⁿ che massimizzi ∑_i u_ix_i con il vincolo ∑_i w_ix_i ≤ W.

Per pesi interi l’ottimo si può calcolare esattamente con la programmazione dinamica — con tutti i 24 oggetti e una capacità di 1 000 decagrammi (1 dag = 10 g) sono 24 000 passi. Lo zaino migliore ha 727 punti di utilità e pesa 9,9 kg; a casa restano il cibo in più, la macchina fotografica, il libro, i sandali e la crema solare. Grazie a questo vedremo esattamente quanto si avvicina l’evoluzione. Un algoritmo genetico serve però soprattutto dove un metodo esatto del genere non esiste.

La programmazione dinamica riempie una tabella T[i][c] — la migliore utilità raggiungibile usando solo i primi i oggetti, quando possono pesare al massimo c. Ogni casella si calcola dalla riga sopra:

T[i][c] = max( T[i − 1][c] , T[i − 1][c − w_i] + u_i )

T[i][c]

la migliore utilità dei primi i oggetti con capacità c; la casella T[n][W] è la risposta all’intero problema

T[i − 1][c]

l’opzione «l’i-esimo oggetto non lo prendo» — allora il meglio è ciò che si poteva comporre con gli oggetti precedenti con la stessa capacità

T[i − 1][c − w_i]

l’opzione «lo prendo» — l’oggetto occupa w_i, quindi per il resto rimane solo c − w_i; il miglior uso del resto è già nella tabella (vale solo per c ≥ w_i)

u_i

l’utilità dell’oggetto che abbiamo aggiunto nella seconda opzione

Esempio — la tabella per quattro oggetti e una capacità di 50 dag

Frontale (10 dag, 25 punti), coltello (10 dag, 18), fornelletto (40 dag, 30) e materassino (50 dag, 45). Tutti i pesi sono multipli di dieci, quindi bastano colonne di 10 in 10 dag:

oggetti	c = 0	10	20	30	40	50
nessuno	0	0	0	0	0	0
+ frontale	0	25	25	25	25	25
+ coltello	0	25	43	43	43	43
+ fornelletto	0	25	43	43	43	55
+ materassino	0	25	43	43	43	55

Coltello, c = 20: max(T[1][20], T[1][10] + 18) = max(25, 25 + 18) = 43

Fornelletto, c = 40: max(T[2][40], T[2][0] + 30) = max(43, 0 + 30) = 43 — il fornelletto non conviene

Fornelletto, c = 50: max(T[2][50], T[2][10] + 30) = max(43, 25 + 30) = 55 — il fornelletto e la frontale

Materassino, c = 50: max(55, T[3][0] + 45) = max(55, 45) = 55

La strategia golosa prenderebbe gli oggetti per utilità per decagrammo: la frontale (2,5 punti/dag), il coltello (1,8), poi né il materassino (0,9) né il fornelletto (0,75) entrerebbero nei 30 dag rimasti — solo 43 punti. Nel problema grande con 24 oggetti la strategia golosa si ferma a 702 punti: riempie lo zaino di cose piccole e per la tenda (220 dag) non resta più posto.

def batoh(w, u, W):                       # w, u: pesi e utilità, W: capacità
    T = [0] * (W + 1)                     # la riga per «nessun oggetto»
    for i in range(len(w)):
        for c in range(W, w[i] - 1, -1):  # all’indietro: T[c − w[i]] è ancora della riga i − 1
            T[c] = max(T[c], T[c - w[i]] + u[i])
    return T[W]                           # n · W passi: 24 · 1000 = 24 000

2. Individuo, genoma e fitness

Definizione — genoma, popolazione, fitness

Un genoma (cromosoma) è una soluzione codificata — qui una stringa x ∈ {0, 1}²⁴, un bit (gene) per oggetto. Una popolazione è un multiinsieme P di genomi di dimensione fissa μ.

La fitness (idoneità) è una funzione F : {0, 1}ⁿ → ℝ che l’algoritmo massimizza. Per lo zaino

F(x) = ∑ u_ix_i se lo zaino rientra nel limite, altrimenti ∑ u_ix_i − 3 · (∑ w_ix_i − W).

F(x) = ∑ u_ix_i − 3 · max(0, ∑ w_ix_i − W)

F(x)

la fitness dello zaino x — l’unico numero con cui la selezione confronta gli individui

∑ u_ix_i

l’utilità degli oggetti imballati (x_i = 1 conta l’oggetto, 0 lo esclude) — ciò che vogliamo davvero massimizzare

3

il prezzo di un decagrammo oltre il limite — è maggiore del miglior rapporto tra utilità e peso (la frontale, 2,5 punti/dag), quindi aggiungere qualunque cosa a uno zaino già sovraccarico abbassa sempre la fitness

max(0, ∑ w_ix_i − W)

il sovraccarico in decagrammi; il max con zero garantisce che uno zaino entro il limite non riceva penalità e che uno zaino più leggero non sia avvantaggiato

Esempio — la fitness di due zaini

Ottimo: utilità 727, peso 990 dag ≤ 1 000  ⇒  F = 727 − 3 · 0 = 727

Ottimo + macchina fotografica (80 dag, 20 punti): utilità 747, peso 1 070 dag  ⇒  F = 747 − 3 · 70 = 537

La macchina fotografica aggiunge 20 punti, ma il sovraccarico di 70 dag costa 210 — la selezione mette da parte uno zaino così in modo affidabile.

3. Selezione

Definizione — selezione a torneo e a roulette

Selezione a torneo di dimensione k: scegli a caso k individui dalla popolazione e restituisci quello con la fitness più alta.

Selezione a roulette: scegli l’individuo x con probabilità F(x) / ∑_{y ∈ P} F(y) (richiede una fitness positiva).

La pressione selettiva misura quanto fortemente la selezione favorisce gli individui più adatti; nel torneo cresce con k.

Quanto è forte un torneo si può calcolare esattamente. Il nostro programma estrae k individui con reinserimento (lo stesso individuo può entrare due volte nel torneo). Ordiniamo la popolazione dal migliore (i = 1) al peggiore (i = μ):

P(vince l’i-esimo) = ( (μ − i + 1)^k − (μ − i)^k ) / μ^k

P(vince l’i-esimo)

la probabilità che diventi genitore proprio l’i-esimo individuo migliore

(μ − i + 1)^k

il numero di tornei in cui nessuno è migliore dell’i-esimo — tutte le k estrazioni cadono su di lui o su quelli peggiori

(μ − i)^k

da questi togliamo i tornei in cui l’i-esimo non c’è affatto — quelli li vincerebbe qualcuno peggiore; la differenza sono i tornei in cui l’i-esimo è il migliore presente

μ^k

il numero di tutti i tornei possibili (k estrazioni, ognuna tra μ individui) — dividendo otteniamo una probabilità

Esempio — un torneo a tre tra 40 zaini

μ^k = 40³ = 64 000. A ogni generazione si scelgono 38 genitori (due posti li occupano gli individui d’élite):

il migliore: (40³ − 39³) / 64 000 = (64 000 − 59 319) / 64 000 ≈ 7,31%,   attese 38 · 0,0731 ≈ 2,78 selezioni

il 20° migliore: (21³ − 20³) / 64 000 = (9 261 − 8 000) / 64 000 ≈ 1,97%,   attese ≈ 0,75 selezioni

il peggiore: (1³ − 0³) / 64 000 ≈ 0,0016%,   attese ≈ 0,0006 selezioni

Un individuo medio riceve 38/40 = 0,95 selezioni, il migliore quasi il triplo. In generale, in una popolazione grande il migliore riceve circa k volte più della media — per questo la pressione selettiva cresce con k.

4. Incrocio e mutazione

Definizione — incrocio a un punto

Per i genitori a, b ∈ {0, 1}ⁿ scegli a caso un punto c ∈ {1, …, n − 1}. I discendenti sono

(a₁, …, a_c, b_c+1, …, b_n) e (b₁, …, b_c, a_c+1, …, a_n).

L’incrocio si esegue con probabilità p_c, altrimenti i discendenti sono copie dei genitori. Altre varianti sono l’incrocio a due punti e quello uniforme (ogni gene da un genitore scelto a caso).

Definizione — mutazione dei bit

Ogni gene del discendente viene invertito (0 ↔ 1) in modo indipendente con probabilità p_m, di solito p_m = 1/n — in media un gene per individuo.

Esempio — quanti geni inverte la mutazione

Il numero di geni invertiti ha una distribuzione binomiale: P(j geni) = C(n, j) · p_m^j · (1 − p_m)^n−j. Per n = 24 e p_m = 1/24:

numero atteso: n · p_m = 24 · 1/24 = 1

nessun cambiamento: (23/24)²⁴ ≈ 0,360   (per n grande si avvicina a 1/e ≈ 0,368)

esattamente un gene: 24 · (1/24) · (23/24)²³ ≈ 0,376

Circa un terzo dei discendenti resta quindi invariato, un terzo differisce per un gene e il resto per due o più.

I genitori sono i due zaini migliori della popolazione iniziale (423 e 398 punti), il taglio è dopo il dodicesimo oggetto. Nessuno dei discendenti è migliore del migliore dei genitori — hanno 403 e 418 punti. L’incrocio non garantisce un miglioramento; offre solo nuove combinazioni, e poi è la selezione a decidere quali sopravvivono. Nel primo discendente la mutazione ha aggiunto un filtro per l’acqua (15 dag, 32 punti), e d’un tratto ha 435 punti — più di entrambi i genitori.

Esempio — il ricalcolo dell’incrocio della figura

L’utilità si somma gene per gene, quindi basta sommare separatamente l’utilità dell’inizio (oggetti 1–12) e della fine (oggetti 13–24):

genitore 1: 310 + 113 = 423,   genitore 2: 305 + 93 = 398

figlio 1 = inizio del genitore 1 + fine del genitore 2: 310 + 93 = 403

figlio 2 = inizio del genitore 2 + fine del genitore 1: 305 + 113 = 418

la mutazione aggiunge il filtro per l’acqua: 403 + 32 = 435

Il genitore 1 è migliore in entrambe le metà (310 > 305 e 113 > 93), quindi con questo taglio nessun discendente può superarlo — l’incrocio non ha di che comporre un insieme migliore. Il miglioramento è arrivato solo con la mutazione.

5. L’algoritmo completo

Algoritmo — algoritmo genetico

1. Crea una popolazione iniziale casuale di μ individui e valutali.
2. Copia senza modifiche nella nuova generazione gli e individui migliori (elitismo).
3. Finché la nuova generazione non ha μ individui: scegli due genitori, incrociali con probabilità p_c, muta i discendenti e aggiungili.
4. Valuta la nuova generazione e riprendi dal passo 2 finché non si esaurisce il numero di generazioni.

import random

def evoluce(zdatnost, n, velikost=40, generaci=60, p_krizeni=0.9, elita=2):
    pop = [[int(random.random() < 0.3) for _ in range(n)] for _ in range(velikost)]
    for _ in range(generaci):
        pop.sort(key=zdatnost, reverse=True)
        dalsi = [g[:] for g in pop[:elita]]            # elitismo
        while len(dalsi) < velikost:
            a, b = turnaj(pop, zdatnost), turnaj(pop, zdatnost)
            if random.random() < p_krizeni:
                bod = random.randrange(1, n)
                a, b = a[:bod] + b[bod:], b[:bod] + a[bod:]
            dalsi += [mutuj(a), mutuj(b)]
        pop = dalsi[:velikost]
    return max(pop, key=zdatnost)

def turnaj(pop, zdatnost, k=3):
    return max(random.choices(pop, k=k), key=zdatnost)   # k estrazioni con reinserimento

def mutuj(g):
    return [1 - x if random.random() < 1 / len(g) else x for x in g]

Il costo dell’algoritmo lo misuriamo con il numero di valutazioni della fitness — nei problemi reali (simulazioni, misurazioni) è il passo più costoso. Si valuta la popolazione iniziale e poi ogni generazione: μ + G · μ = 40 + 60 · 40 = 2 440 valutazioni per μ = 40 individui e G = 60 generazioni. Gli individui d’élite vengono rivalutati anche se non sono cambiati; un programma più furbo ricorderebbe la loro fitness.

6. L’evoluzione dello zaino

Facciamo partire l’algoritmo: 40 zaini, 60 generazioni, torneo a tre, incrocio con probabilità 0,9, mutazione 1/24 e due individui d’élite. La figura mostra la popolazione nelle generazioni 0, 5, 15, 30 e 60 — ogni riga è uno zaino, ogni colonna un oggetto, in alto per confronto l’ottimo:

All’inizio la popolazione è varia e gli zaini sono piuttosto mezzi vuoti: ogni oggetto ci è finito con probabilità 0,3, quindi pesano intorno ai quattro chili (il peso atteso è 0,3 · ∑ w_i = 0,3 · 12,75 kg ≈ 3,8 kg). Il migliore ha 423 punti, la media 231. Dopo cinque generazioni 36 zaini su 40 portano la tenda, 35 la borraccia, e lo zaino migliore ha 634 punti. Verso la quindicesima generazione la popolazione urta contro la capacità — 12 zaini sono sovraccarichi — e comincia a imparare che cosa sacrificare: il cibo in più e i sandali sono quasi spariti, ma la macchina fotografica la portano ancora 39 zaini. L’ottimo, 727 punti, l’algoritmo lo trova per la prima volta nella generazione 26; nella generazione 30 la macchina fotografica è rimasta in un solo zaino. La popolazione però non si fonde mai in un’unica soluzione — la mutazione continua a provare piccole deviazioni.

Per arrivarci l’algoritmo ha valutato 2 440 zaini — nemmeno due centesimi di punto percentuale di tutte le 16 777 216 possibilità. Una ricerca casuale con lo stesso numero di tentativi in cento ripetizioni non ha trovato l’ottimo neanche una volta e in media si è fermata a 574 punti.

Esempio — perché la ricerca casuale non trova l’ottimo

Uno zaino casuale prende ogni oggetto in modo indipendente con probabilità 0,3. L’ottimo contiene 19 oggetti e ne esclude 5, quindi

P(zaino casuale = ottimo) = 0,3¹⁹ · 0,7⁵ ≈ 1,16 · 10⁻¹⁰ · 0,168 ≈ 1,95 · 10⁻¹¹

numero atteso di centri in 2 440 tentativi: 2 440 · 1,95 · 10⁻¹¹ ≈ 4,8 · 10⁻⁸

Anche se si estraesse in modo uniforme (ogni oggetto con probabilità 1/2), la probabilità sarebbe di una su 16 777 216 per tentativo. Un algoritmo genetico non estrae l’ottimo tutto in una volta — lo compone pezzo per pezzo a partire da zaini che sono già buoni.

7. A che cosa servono l’incrocio e la mutazione

La linea arancione nel grafico è la stessa esecuzione con la mutazione disattivata. Dopo undici generazioni si blocca a 573 punti e non si muove più. Il perché lo mostra un confronto di cento esecuzioni con semi diversi:

Senza mutazione la popolazione perde diversità: quando un gene non c’è in nessun individuo, l’incrocio non può produrlo, e in più la selezione scaccia rapidamente tutto tranne i migliori. Si chiama convergenza prematura. Senza incrocio l’algoritmo funziona — in fondo è una popolazione di hill climbing con selezione —, ma è più lento. L’incrocio aiuta a mettere insieme buoni pezzi nati in individui diversi.

Teorema — il teorema degli schemi di Holland

Uno schema H è un modello su {0, 1, ∗}, dove ∗ significa «qualsiasi cosa»; il suo ordine o(H) è il numero di posizioni fisse e la sua lunghezza di definizione δ(H) la distanza tra la prima e l’ultima posizione fissa. Per m(H, t) individui che corrispondono a H nella generazione t e la selezione a roulette vale

E[m(H, t + 1)] ≥ m(H, t) · F(H) / F̄ · [1 − p_c · δ(H) / (n − 1) − o(H) · p_m],

dove F(H) è la fitness media degli individui dello schema e F̄ la media della popolazione.

E[m(H, t + 1)] ≥ m(H, t) · F(H) / F̄ · [1 − p_c · δ(H) / (n − 1) − o(H) · p_m]

m(H, t)

quanti individui portano il mattone adesso — la generazione successiva parte da loro, per questo si moltiplica per questo numero

F(H) / F̄

di quanto i portatori dello schema sono più adatti della media — la roulette dà loro proporzionalmente più discendenti; sopra 1 lo schema si moltiplica, sotto 1 si estingue

p_c · δ(H) / (n − 1)

la probabilità che l’incrocio tagli lo schema: l’incrocio avviene con p_c e il punto di taglio cade tra le posizioni fisse con probabilità δ/(n − 1) — per questo nuocciono gli schemi lunghi

o(H) · p_m

la probabilità (stimata dall’alto) che la mutazione inverta una delle o(H) posizioni fisse — per questo nuocciono gli schemi di ordine alto

Esempio — uno schema corto e uno lungo sullo zaino

La parentesi quadra per le impostazioni della nostra esecuzione (p_c = 0,9, n = 24, p_m = 1/24). Entrambi gli schemi hanno ordine 2:

«la tenda e il sacco a pelo» (geni 1 e 2, δ = 1): 1 − 0,9 · 1/23 − 2/24 ≈ 1 − 0,039 − 0,083 = 0,878

«la tenda e calzini di ricambio» (geni 1 e 24, δ = 23): 1 − 0,9 · 23/23 − 2/24 ≈ 1 − 0,9 − 0,083 = 0,017

Allo schema corto basta che i suoi portatori siano il 14% più adatti della media (1/0,878 ≈ 1,14), e secondo il teorema si diffonde già. Lo schema lungo dovrebbe essere sessanta volte più adatto — il teorema non promette praticamente nulla su di esso. Il nostro algoritmo usa il torneo, non la roulette, quindi per lui vale solo la parentesi quadra; i primi due fattori si calcolerebbero diversamente.

8. Gli algoritmi genetici nella pratica

• Progettazione di forme. L’antenna dei satelliti ST5 della NASA (lanciati nel 2006) è stata progettata da un algoritmo evolutivo: un filo stranamente contorto che a nessun ingegnere sarebbe venuto in mente, ma che ha soddisfatto i requisiti almeno quanto un’antenna progettata a mano (e in prove successive anche meglio).
• Orari e logistica. Orari, turni di lavoro o la disposizione di un magazzino — problemi con molti vincoli, in cui la fitness si può calcolare ma un algoritmo esatto girerebbe per secoli.
• Apprendimento automatico. L’evoluzione regola gli iperparametri dei modelli e, nella neuroevoluzione, a cui il programma dedica una parte a sé, persino i pesi e le architetture delle reti neurali.
• Evoluzione con i modelli linguistici. Sistemi come FunSearch (2023) e AlphaEvolve (2025) di Google DeepMind mantengono una popolazione di programmi e usano come mutazione un modello linguistico che modifica un programma. La selezione la garantisce una valutazione automatica. Così si sono trovate nuove costruzioni matematiche e algoritmi più veloci.

9. Riepilogo

• Un algoritmo genetico migliora un’intera popolazione di soluzioni: con la selezione dei più adatti, con l’incrocio e con la mutazione.
• La fitness è l’unica cosa che deve sapere del problema; la violazione dei vincoli si può gestire con una penalità.
• La selezione a torneo mantiene la pressione selettiva, l’elitismo non permette di perdere la soluzione migliore.
• Su uno zaino con 16,7 milioni di possibilità ha trovato l’ottimo in 88 esecuzioni su 100 dopo aver valutato 2 440 zaini; la ricerca casuale con lo stesso budget neanche una volta.
• La mutazione fornisce diversità — senza di essa la popolazione converge prematuramente. L’incrocio mette insieme buoni mattoni e accelera l’evoluzione.

Vuoi metterci le mani? Fai scrivere a un agente IA un algoritmo genetico per il tuo zaino da escursione — e poi prova a disattivare la mutazione, ingrandire il torneo o ridurre la popolazione, e osserva che cosa succede alla diversità.

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