Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę

Genom i przystosowanie, selekcja turniejowa, krzyżowanie jednopunktowe, mutacja i elitaryzm, twierdzenie o schematach i przedwczesna zbieżność — na problemie plecakowym ze znanym optimum, od namiotu po FunSearch i AlphaEvolve.

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

Seria Podstawy AI Część 27 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

Przyroda nie ma inżyniera, a mimo to wytworzyła oko, skrzydło i mózg. Wystarczyły jej trzy rzeczy: osobniki różnią się od siebie, przekazują swoje cechy potomkom, a lepiej przystosowane mają więcej potomków. W latach siedemdziesiątych John Holland z Uniwersytetu Michigan pokazał, że te same trzy rzeczy działają również w komputerze — jako ogólna metoda szukania dobrych rozwiązań zadań, o których nie wiemy, jak je sprytnie rozwiązać. Algorytm genetyczny nie potrzebuje gradientu ani wzoru; wystarczy mu umiejętność powiedzenia, które z dwóch rozwiązań jest lepsze.

Nawiązuje do części Przeszukiwanie lokalne i symulowane wyżarzanie. Wyżarzanie ulepszało jedno rozwiązanie; algorytm genetyczny ulepsza całą ich populację naraz.

1. Zadanie: plecak na wycieczkę

Szykujesz się na kilkudniową wycieczkę. W domu masz 24 rzeczy — namiot, śpiwór, kuchenkę, aparat, książkę… — i każda coś waży i do czegoś się przydaje. Plecak może ważyć najwyżej 10 kg. Co zabrać, żeby pożytek był jak największy?

Definicja — problem plecakowy (0/1)

Dane jest n przedmiotów o masach w_i > 0 i wartościach u_i > 0 oraz ładowność W. Szukamy x ∈ {0, 1}ⁿ, które maksymalizuje ∑_i u_ix_i przy warunku ∑_i w_ix_i ≤ W.

Dla całkowitych mas optimum da się obliczyć dokładnie programowaniem dynamicznym — dla wszystkich 24 rzeczy i ładowności 1 000 dekagramów to 24 000 kroków. Najlepszy plecak ma 727 punktów wartości i waży 9,9 kg; w domu zostaje dodatkowe jedzenie, aparat, książka, sandały i krem do opalania. Dzięki temu zobaczymy dokładnie, jak blisko dojdzie ewolucja. Algorytm genetyczny przydaje się jednak głównie tam, gdzie takiej dokładnej metody nie ma.

Programowanie dynamiczne wypełnia tabelę T[i][c] — najlepszą wartość, jaką można osiągnąć tylko z pierwszych i rzeczy, gdy mogą ważyć najwyżej c. Każde pole oblicza się z wiersza nad nim:

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

T[i][c]

najlepsza wartość z pierwszych i rzeczy przy ładowności c; pole T[n][W] jest odpowiedzią na całe zadanie

T[i − 1][c]

możliwość „i-tej rzeczy nie biorę” — wtedy najlepsze jest to, co dało się złożyć z poprzednich rzeczy przy tej samej ładowności

T[i − 1][c − w_i]

możliwość „biorę” — rzecz zajmuje w_i, więc na pozostałe zostaje tylko c − w_i; najlepsze wykorzystanie reszty mamy już w tabeli (wolno tylko dla c ≥ w_i)

u_i

wartość rzeczy, którą w tej drugiej możliwości dopakowaliśmy

Przykład — tabela dla czterech rzeczy i ładowności 50 dag

Czołówka (10 dag, 25 punktów), nóż (10 dag, 18), kuchenka (40 dag, 30) i karimata (50 dag, 45). Wszystkie masy są wielokrotnościami dziesięciu, więc wystarczą kolumny co 10 dag:

rzeczy	c = 0	10	20	30	40	50
żadna	0	0	0	0	0	0
+ czołówka	0	25	25	25	25	25
+ nóż	0	25	43	43	43	43
+ kuchenka	0	25	43	43	43	55
+ karimata	0	25	43	43	43	55

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

Kuchenka, c = 40: max(T[2][40], T[2][0] + 30) = max(43, 0 + 30) = 43 — kuchenka się nie opłaca

Kuchenka, c = 50: max(T[2][50], T[2][10] + 30) = max(43, 25 + 30) = 55 — kuchenka i czołówka

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

Strategia zachłanna brałaby rzeczy według wartości na dekagram: czołówkę (2,5 punktu/dag), nóż (1,8), potem ani karimata (0,9), ani kuchenka (0,75) nie zmieściłyby się w pozostałych 30 dag — tylko 43 punkty. W dużym zadaniu z 24 rzeczami strategia zachłanna kończy na 702 punktach: zapełnia plecak drobiazgami i na namiot (220 dag) nie zostaje już miejsca.

def batoh(w, u, W):                       # w, u: masy i wartości, W: ładowność
    T = [0] * (W + 1)                     # wiersz dla „żadnej rzeczy”
    for i in range(len(w)):
        for c in range(W, w[i] - 1, -1):  # od tyłu: T[c − w[i]] jest jeszcze z wiersza i − 1
            T[c] = max(T[c], T[c - w[i]] + u[i])
    return T[W]                           # n · W kroków: 24 · 1000 = 24 000

2. Osobnik, genom i przystosowanie

Definicja — genom, populacja, przystosowanie

Genom (chromosom) to zakodowane rozwiązanie — tutaj ciąg x ∈ {0, 1}²⁴, jeden bit (gen) na rzecz. Populacja to multizbiór P genomów o stałej liczności μ.

Przystosowanie (fitness) to funkcja F : {0, 1}ⁿ → ℝ, którą algorytm maksymalizuje. Dla plecaka

F(x) = ∑ u_ix_i, gdy plecak się mieści, w przeciwnym razie ∑ u_ix_i − 3 · (∑ w_ix_i − W).

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

F(x)

przystosowanie plecaka x — jedyna liczba, według której selekcja porównuje osobniki

∑ u_ix_i

wartość spakowanych rzeczy (x_i = 1 rzecz wlicza, 0 pomija) — to, co naprawdę chcemy maksymalizować

3

cena jednego dekagrama ponad limit — jest większa niż najlepszy stosunek wartości do masy (czołówka, 2,5 punktu/dag), więc dopakowanie czegokolwiek do już przeładowanego plecaka zawsze obniży przystosowanie

max(0, ∑ w_ix_i − W)

przeładowanie w dekagramach; max z zerem zapewnia, że plecak, który się mieści, nie dostaje kary, a lżejszy plecak nie jest faworyzowany

Przykład — przystosowanie dwóch plecaków

Optimum: wartość 727, masa 990 dag ≤ 1 000  ⇒  F = 727 − 3 · 0 = 727

Optimum + aparat (80 dag, 20 punktów): wartość 747, masa 1 070 dag  ⇒  F = 747 − 3 · 70 = 537

Aparat dodaje 20 punktów, ale przeładowanie o 70 dag kosztuje 210 — selekcja niezawodnie odsunie taki plecak na bok.

3. Selekcja

Definicja — selekcja turniejowa i ruletkowa

Selekcja turniejowa rozmiaru k: wybierz z populacji losowo k osobników i zwróć tego o najwyższym przystosowaniu.

Selekcja ruletkowa: wybierz osobnika x z prawdopodobieństwem F(x) / ∑_{y ∈ P} F(y) (wymaga dodatniego przystosowania).

Presja selekcyjna to miara tego, jak silnie selekcja faworyzuje lepiej przystosowane osobniki; w turnieju rośnie wraz z k.

Jak silny jest turniej, da się obliczyć dokładnie. Nasz program losuje k osobników ze zwracaniem (ten sam osobnik może trafić do turnieju dwa razy). Uporządkujmy populację od najlepszego (i = 1) do najgorszego (i = μ):

P(wygrywa i-ty) = ( (μ − i + 1)^k − (μ − i)^k ) / μ^k

P(wygrywa i-ty)

szansa, że rodzicem zostanie właśnie i-ty najlepszy osobnik

(μ − i + 1)^k

liczba turniejów, w których nikt nie jest lepszy od i-tego — wszystkie k losowań pada na niego lub gorszych

(μ − i)^k

od nich odejmujemy turnieje, w których i-tego w ogóle nie ma — te wygrałby ktoś gorszy; różnica to turnieje, w których i-ty jest najlepszym obecnym

μ^k

liczba wszystkich możliwych turniejów (k losowań, każde z μ osobników) — dzieląc, dostajemy prawdopodobieństwo

Przykład — turniej z trzech wśród 40 plecaków

μ^k = 40³ = 64 000. W każdym pokoleniu wybiera się 38 rodziców (dwa miejsca zajmują osobniki elitarne):

najlepszy: (40³ − 39³) / 64 000 = (64 000 − 59 319) / 64 000 ≈ 7,31%,   oczekiwanie 38 · 0,0731 ≈ 2,78 wyboru

20. najlepszy: (21³ − 20³) / 64 000 = (9 261 − 8 000) / 64 000 ≈ 1,97%,   oczekiwanie ≈ 0,75 wyboru

najgorszy: (1³ − 0³) / 64 000 ≈ 0,0016%,   oczekiwanie ≈ 0,0006 wyboru

Przeciętny osobnik dostaje 38/40 = 0,95 wyboru, najlepszy prawie trzy razy tyle. Ogólnie dla dużej populacji najlepszy dostaje mniej więcej k razy więcej niż przeciętny — dlatego presja selekcyjna rośnie wraz z k.

4. Krzyżowanie i mutacja

Definicja — krzyżowanie jednopunktowe

Dla rodziców a, b ∈ {0, 1}ⁿ wybierz losowo punkt c ∈ {1, …, n − 1}. Potomkami są

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

Krzyżowanie przeprowadza się z prawdopodobieństwem p_c, w przeciwnym razie potomkowie są kopiami rodziców. Inne warianty to krzyżowanie dwupunktowe i jednorodne (każdy gen od losowego rodzica).

Definicja — mutacja bitowa

Każdy gen potomka jest niezależnie odwracany (0 ↔ 1) z prawdopodobieństwem p_m, zwykle p_m = 1/n — średnio jeden gen na osobnika.

Przykład — ile genów odwraca mutacja

Liczba odwróconych genów ma rozkład dwumianowy: P(j genów) = (n po j) · p_m^j · (1 − p_m)^n−j. Dla n = 24 i p_m = 1/24:

oczekiwana liczba: n · p_m = 24 · 1/24 = 1

bez zmiany: (23/24)²⁴ ≈ 0,360   (dla dużego n zbliża się do 1/e ≈ 0,368)

dokładnie jeden gen: 24 · (1/24) · (23/24)²³ ≈ 0,376

Mniej więcej jedna trzecia potomków zostaje więc bez zmian, jedna trzecia różni się jednym genem, a reszta dwoma lub więcej.

Rodzicami są dwa najlepsze plecaki z populacji początkowej (423 i 398 punktów), cięcie jest za dwunastą rzeczą. Żaden z potomków nie jest lepszy od lepszego z rodziców — mają 403 i 418 punktów. Krzyżowanie nie gwarantuje poprawy; oferuje tylko nowe kombinacje, a selekcja zdecyduje potem, które przetrwają. Mutacja u pierwszego potomka dopakowała filtr do wody (15 dag, 32 punkty) i ten ma nagle 435 punktów — więcej niż oboje rodzice.

Przykład — przeliczenie krzyżowania z rysunku

Wartość sumuje się po genach, więc wystarczy osobno zsumować wartość początku (rzeczy 1–12) i końca (rzeczy 13–24):

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

potomek 1 = początek rodzica 1 + koniec rodzica 2: 310 + 93 = 403

potomek 2 = początek rodzica 2 + koniec rodzica 1: 305 + 113 = 418

mutacja dopakowuje filtr do wody: 403 + 32 = 435

Rodzic 1 jest lepszy w obu połowach (310 > 305 i 113 > 93), więc przy tym cięciu żaden potomek nie może go prześcignąć — krzyżowanie nie ma z czego złożyć lepszej całości. Poprawę przyniosła dopiero mutacja.

5. Cały algorytm

Algorytm — algorytm genetyczny

1. Utwórz losową populację początkową μ osobników i oceń je.
2. Do nowego pokolenia skopiuj e najlepszych osobników bez zmian (elitaryzm).
3. Dopóki nowe pokolenie nie ma μ osobników: wybierz dwoje rodziców, z prawdopodobieństwem p_c skrzyżuj ich, potomków zmutuj i dodaj.
4. Oceń nowe pokolenie i przejdź do kroku 2, dopóki nie wyczerpie się liczba pokoleń.

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]]            # elitaryzm
        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 losowań ze zwracaniem

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

Koszt algorytmu mierzymy liczbą ocen przystosowania — w prawdziwych zadaniach (symulacje, pomiary) to najdroższy krok. Ocenia się populację początkową, a potem każde pokolenie: μ + G · μ = 40 + 60 · 40 = 2 440 ocen dla μ = 40 osobników i G = 60 pokoleń. Osobniki elitarne są oceniane ponownie, choć się nie zmieniły; sprytniejszy program zapamiętałby ich przystosowanie.

6. Ewolucja plecaka

Uruchommy algorytm: 40 plecaków, 60 pokoleń, turniej z trzech, krzyżowanie z prawdopodobieństwem 0,9, mutacja 1/24 i dwa osobniki elitarne. Rysunek pokazuje populację w pokoleniach 0, 5, 15, 30 i 60 — każdy wiersz to jeden plecak, każda kolumna jedna rzecz, na górze dla porównania optimum:

Na początku populacja jest różnorodna, a plecaki są raczej w połowie puste: każda rzecz trafiła do nich z prawdopodobieństwem 0,3, więc ważą około czterech kilogramów (oczekiwana masa to 0,3 · ∑ w_i = 0,3 · 12,75 kg ≈ 3,8 kg). Najlepszy ma 423 punkty, średnia 231. Po pięciu pokoleniach namiot niesie 36 z 40 plecaków, butelkę z wodą 35, a najlepszy plecak ma 634 punkty. Około piętnastego pokolenia populacja dochodzi do granicy ładowności — 12 plecaków jest przeładowanych — i zaczyna się uczyć, co poświęcić: dodatkowe jedzenie i sandały prawie zniknęły, ale aparat niesie na razie 39 plecaków. Optimum, 727 punktów, algorytm znajduje po raz pierwszy w pokoleniu 26; w pokoleniu 30 aparat został już tylko w jednym plecaku. Populacja nigdy jednak nie zlewa się w jedno rozwiązanie — mutacja wciąż próbuje drobnych odchyleń.

Algorytm ocenił w tym celu 2 440 plecaków — niecałe dwie setne procenta ze wszystkich 16 777 216 możliwości. Przeszukiwanie losowe z tą samą liczbą prób w stu powtórzeniach nie znalazło optimum ani razu i średnio skończyło na 574 punktach.

Przykład — dlaczego przeszukiwanie losowe nie znajdzie optimum

Losowy plecak bierze każdą rzecz niezależnie z prawdopodobieństwem 0,3. Optimum zawiera 19 rzeczy i pomija 5, więc

P(losowy plecak = optimum) = 0,3¹⁹ · 0,7⁵ ≈ 1,16 · 10⁻¹⁰ · 0,168 ≈ 1,95 · 10⁻¹¹

oczekiwana liczba trafień w 2 440 próbach: 2 440 · 1,95 · 10⁻¹¹ ≈ 4,8 · 10⁻⁸

Nawet gdyby losować równomiernie (każda rzecz z prawdopodobieństwem 1/2), szansa wynosi jeden do 16 777 216 na próbę. Algorytm genetyczny nie wylosowuje optimum od razu — składa je po kawałku z plecaków, które już są dobre.

7. Do czego służy krzyżowanie, a do czego mutacja

Pomarańczowa linia na wykresie to ten sam przebieg z wyłączoną mutacją. Po jedenastu pokoleniach utyka na 573 punktach i już się nie rusza. Dlaczego, pokaże porównanie stu przebiegów z różnymi ziarnami:

Bez mutacji populacja traci różnorodność: gdy genu nie ma w żadnym osobniku, krzyżowanie go nie wytworzy, a selekcja dodatkowo szybko wypiera wszystko poza najlepszymi. Nazywa się to przedwczesną zbieżnością. Bez krzyżowania algorytm działa — to właściwie populacja wspinaczy z selekcją — ale jest wolniejszy. Krzyżowanie pomaga składać razem dobre kawałki, które powstały w różnych osobnikach.

Twierdzenie — twierdzenie Hollanda o schematach

Schemat H to wzorzec nad {0, 1, ∗}, gdzie ∗ oznacza „cokolwiek”; jego rząd o(H) to liczba ustalonych pozycji, a rozpiętość δ(H) odległość pierwszej i ostatniej ustalonej pozycji. Dla m(H, t) osobników pasujących do H w pokoleniu t i selekcji ruletkowej zachodzi

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

gdzie F(H) to średnie przystosowanie osobników ze schematu, a F̄ średnia populacji.

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

m(H, t)

ile osobników niesie cegiełkę teraz — następne pokolenie z nich wychodzi, dlatego się przez to mnoży

F(H) / F̄

o ile nosiciele schematu są lepiej przystosowani od średniej — ruletka daje im proporcjonalnie więcej potomków; powyżej 1 schemat się mnoży, poniżej 1 wymiera

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

szansa, że krzyżowanie rozetnie schemat: krzyżowanie zachodzi z p_c, a punkt cięcia pada z prawdopodobieństwem δ/(n − 1) między ustalone pozycje — dlatego szkodzą długie schematy

o(H) · p_m

szansa (z góry), że mutacja odwróci którąś z o(H) ustalonych pozycji — dlatego szkodzą schematy wysokiego rzędu

Przykład — krótki i długi schemat na plecaku

Nawias kwadratowy dla ustawień naszego przebiegu (p_c = 0,9, n = 24, p_m = 1/24). Oba schematy mają rząd 2:

„namiot i śpiwór” (geny 1 i 2, δ = 1): 1 − 0,9 · 1/23 − 2/24 ≈ 1 − 0,039 − 0,083 = 0,878

„namiot i zapasowe skarpety” (geny 1 i 24, δ = 23): 1 − 0,9 · 23/23 − 2/24 ≈ 1 − 0,9 − 0,083 = 0,017

Krótkiemu schematowi wystarczy, by jego nosiciele byli o 14% lepiej przystosowani od średniej (1/0,878 ≈ 1,14), i według twierdzenia już się rozprzestrzenia. Długi schemat musiałby być sześćdziesiąt razy lepiej przystosowany — twierdzenie w zasadzie nic o nim nie obiecuje. Nasz algorytm używa turnieju, nie ruletki, więc dotyczy go tylko nawias kwadratowy; pierwsze dwa czynniki liczyłoby się inaczej.

8. Algorytmy genetyczne w praktyce

• Projektowanie kształtów. Antenę satelitów NASA ST5 (wystrzelonych w 2006 roku) zaprojektował algorytm ewolucyjny: dziwnie powyginany drucik, który nie przyszedłby inżynierowi do głowy, ale spełnił wymagania co najmniej tak dobrze jak antena zaprojektowana ręcznie (w późniejszych próbach nawet lepiej).
• Harmonogramy i logistyka. Plany zajęć, grafiki zmian czy układ magazynu — zadania z wieloma warunkami, w których przystosowanie da się obliczyć, ale dokładny algorytm działałby wieki.
• Uczenie maszynowe. Ewolucja dostraja hiperparametry modeli, a w neuroewolucji, której program kursu poświęca osobną część, także wagi i architektury sieci neuronowych.
• Ewolucja z modelami językowymi. Systemy takie jak FunSearch (2023) i AlphaEvolve (2025) od Google DeepMind utrzymują populację programów i jako mutacji używają modelu językowego, który program modyfikuje. Selekcję zapewnia automatyczna ocena. W ten sposób udało się znaleźć nowe konstrukcje matematyczne i szybsze algorytmy.

9. Podsumowanie

• Algorytm genetyczny ulepsza całą populację rozwiązań: selekcją dobrze przystosowanych, krzyżowaniem i mutacją.
• Przystosowanie to jedyne, co musi wiedzieć o zadaniu; naruszenie warunków można rozwiązać karą.
• Selekcja turniejowa utrzymuje presję selekcyjną, elitaryzm nie pozwala stracić najlepszego rozwiązania.
• Na plecaku z 16,7 miliona możliwości znalazł optimum w 88 na 100 przebiegów po ocenie 2 440 plecaków; przeszukiwanie losowe z tym samym budżetem ani razu.
• Mutacja dostarcza różnorodności — bez niej populacja przedwcześnie się zbiega. Krzyżowanie składa dobre cegiełki i przyspiesza ewolucję.

Chcesz to wypróbować na własnej skórze? Niech agent AI napisze algorytm genetyczny dla twojego własnego plecaka na wycieczkę — a potem spróbuj wyłączyć mutację, powiększyć turniej albo zmniejszyć populację i obserwuj, co stanie się z różnorodnością.

Masz inne zdanie? Napisz na support@coden-app.com.