Genetické algoritmy: populace, křížení, mutace a výběr na batohu na výlet

Genom a zdatnost, turnajový výběr, jednobodové křížení, mutace a elitismus, věta o schématech a předčasná konvergence — na úloze batohu se známým optimem, od stanu po FunSearch a AlphaEvolve.

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

Série Základy AI Díl 27 z 83

Celá osnova série 83 z 83 témat hotovo

Co si odnesete

Jak zakódovat řešení jako genom a jak výběr, křížení a mutace vylepšují celou populaci.
Proč bez mutace evoluce předčasně zkonverguje a k čemu je křížení.
Kde se genetické algoritmy používají dnes — i s jazykovým modelem v roli mutace.

Co se hodí znát předem: Lokální hledání a simulované žíhání: obchodní cestující přes krajská města

Příroda nemá inženýra, a přesto vyrobila oko, křídlo i mozek. Stačily jí tři věci: jedinci se od sebe liší, své vlastnosti předávají potomkům a ti zdatnější mají potomků víc. V sedmdesátých letech John Holland z Michiganské univerzity ukázal, že tytéž tři věci fungují i v počítači — jako obecná metoda, jak hledat dobrá řešení úloh, u kterých nevíme, jak je řešit chytře. Genetický algoritmus nepotřebuje gradient, nepotřebuje vzorec, potřebuje jen umět říct, které ze dvou řešení je lepší.

Navazuje na díl Lokální hledání a simulované žíhání. Žíhání vylepšovalo jedno řešení; genetický algoritmus jich vylepšuje celou populaci najednou.

1. Úloha: batoh na výlet

Chystáte se na několikadenní výlet. Doma máte 24 věcí — stan, spacák, vařič, foťák, knihu… — a každá něco váží a k něčemu je. Batoh smí vážit nejvýš 10 kg. Co vzít, aby byl užitek co největší?

Definice — úloha batohu (0/1)

Nechť n ∈ ℕ, n ≥ 1, je počet věcí, w₁, …, w_n > 0 jejich hmotnosti, u₁, …, u_n > 0 jejich užitky a W > 0 nosnost batohu. Výběr věcí zapíšeme vektorem x = (x₁, …, x_n) ∈ {0, 1}ⁿ, kde x_i = 1, právě když i-tou věc bereme. Výběr x je přípustný, právě když ∑_i=1ⁿ w_ix_i ≤ W. Úloha batohu (0/1) je úloha najít

x* ∈ argmax { ∑_i=1ⁿ u_ix_i : x ∈ {0, 1}ⁿ, ∑_i=1ⁿ w_ix_i ≤ W }.

Hledáme tedy přípustný výběr s největším součtem užitků; „0/1“ v názvu znamená, že každou věc lze vzít jen celou a nejvýš jednou.

Laicky řečeno

Každá věc je otázka „beru, neberu“ — jednička, nebo nula. Možností je 2²⁴, tedy 16 777 216 batohů. Hladová strategie „nejdřív to nejužitečnější na kilo“ často funguje, ale optimum nezaručí: jedna těžká věc může vytlačit tři lehké, které byly dohromady cennější.

Pro celočíselné hmotnosti se dá optimum spočítat přesně dynamickým programováním — ze všech 24 věcí a nosnosti 1 000 dekagramů je to 24 000 kroků. Nejlepší batoh má 727 bodů užitku a váží 9,9 kg; doma zůstane jídlo navíc, foťák, kniha, sandály a opalovací krém. Díky tomu zase přesně uvidíme, jak blízko se evoluce dostane. Genetický algoritmus se ale hodí hlavně tam, kde takový přesný postup neexistuje.

Dynamické programování vyplňuje tabulku T[i][c] — nejlepší užitek, kterého lze dosáhnout jen z prvních i věcí, když smějí vážit nejvýš c. Každé políčko se spočítá z řádku nad ním:

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

T[i][c]: nejlepší užitek z prvních i věcí při nosnosti c; políčko T[n][W] je odpověď na celou úlohu
T[i − 1][c]: možnost „i-tou věc neberu“ — pak je nejlepší to, co šlo složit z předchozích věcí se stejnou nosností
T[i − 1][c − w_i]: možnost „beru“ — věc zabere w_i, takže na ostatní zbude jen c − w_i; nejlepší využití zbytku už v tabulce máme (smí se jen pro c ≥ w_i)
u_i: užitek věci, kterou jsme v té druhé možnosti přibalili

Optimální batoh buď i-tou věc obsahuje, nebo ne — a v obou případech je zbytek optimálním batohem menší úlohy. Začíná se řádkem T[0][c] = 0.

Příklad — tabulka pro čtyři věci a nosnost 50 dkg

Čelovka (10 dkg, 25 bodů), nůž (10 dkg, 18), vařič (40 dkg, 30) a karimatka (50 dkg, 45). Všechny hmotnosti jsou násobky deseti, takže stačí sloupce po 10 dkg:

věci	10	20	30	40	50
žádná	0	0	0	0	0
+ čelovka	25	25	25	25	25
+ nůž	25	43	43	43	43
+ vařič	25	43	43	43	55
+ karimatka	25	43	43	43	55

Nůž, c = 20: T[2][20] = max(T[1][20], T[1][10] + 18) = max(25, 25 + 18) = 43

Vařič, c = 40: T[3][40] = max(T[2][40], T[2][0] + 30) = max(43, 0 + 30) = 43 — vařič se nevyplatí

Vařič, c = 50: T[3][50] = max(T[2][50], T[2][10] + 30) = max(43, 25 + 30) = 55 — vařič a čelovka

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

(Barvy podle vzorce výše.)

Hladová strategie by vzala věci podle užitku na dekagram: čelovku (2,5 bodu/dkg), nůž (1,8), pak by se karimatka (0,9) ani vařič (0,75) do zbylých 30 dkg nevešly — jen 43 bodů. Ve velké úloze s 24 věcmi skončí hladová strategie na 702 bodech: naplní batoh drobnostmi a na stan (220 dkg) už nezbude místo.

def batoh(w, u, W):                       # w, u: hmotnosti a užitky, W: nosnost
    T = [0] * (W + 1)                     # řádek pro „žádná věc“
    for i in range(len(w)):
        for c in range(W, w[i] - 1, -1):  # odzadu: T[c − w[i]] je ještě z řádku i − 1
            T[c] = max(T[c], T[c - w[i]] + u[i])
    return T[W]                           # n · W kroků: 24 · 1000 = 24 000

2. Jedinec, genom a zdatnost

Definice — genom, populace, zdatnost

Nechť je dána úloha batohu s n věcmi, hmotnostmi w_i a nosností W v dekagramech a užitky u_i (i = 1, …, n; u nás n = 24).

Genom (chromozom) je zakódované řešení; pro batoh je to řetězec x = (x₁, …, x_n) ∈ {0, 1}ⁿ. Jeho složky x_i — jeden bit na věc — nazýváme geny.
Populace velikosti μ ∈ ℕ je μ-tice genomů P = (x⁽¹⁾, …, x^(μ)), x^(j) ∈ {0, 1}ⁿ; tentýž genom v ní může být víckrát (na pořadí nezáleží, jde tedy o multimnožinu s μ prvky). Prvkům populace říkáme jedinci.
Zdatnost (fitness) je funkce F : {0, 1}ⁿ → ℝ, kterou algoritmus maximalizuje. Pro batoh ji definujeme s trestem za přetížení: F(x) = ∑_i=1ⁿ u_ix_i, je-li ∑_i=1ⁿ w_ix_i ≤ W, F(x) = ∑_i=1ⁿ u_ix_i − 3 · (∑_i=1ⁿ w_ix_i − W), jinak.

Pro přípustný batoh je tedy zdatnost rovna jeho užitku a za každý dekagram přes nosnost se odečtou 3 body.

Laicky řečeno

Jedinec je jeden konkrétní batoh zapsaný jako řada jedniček a nul. Zdatnost říká, jak je dobrý. Přetížený batoh nezakážeme, jen ho potrestáme — za každý dekagram navíc tři body dolů. Algoritmus se tak o hranici nosnosti dozví postupně, a i přetížený batoh může mít geny, které se později hodí.

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

F(x): zdatnost batohu x — jediné číslo, podle kterého výběr porovnává jedince
∑ u_ix_i: užitek zabalených věcí (x_i = 1 věc započítá, 0 vynechá) — to, co doopravdy chceme maximalizovat
3: cena jednoho dekagramu přes limit — je větší než nejlepší poměr užitku a hmotnosti (čelovka, 2,5 bodu/dkg), takže přibalit cokoli do už přetíženého batohu zdatnost vždy sníží
max(0, ∑ w_ix_i − W): přetížení v dekagramech; max s nulou zajistí, že batoh, který se vejde, trest nedostane a lehčí batoh není zvýhodněn

Oba případy z definice v jednom vzorci: trest je nulový, dokud se batoh vejde, a pak roste s každým dekagramem navíc.

Příklad — zdatnost dvou batohů

Optimum: užitek 727, hmotnost 990 dkg ≤ 1 000 ⇒ F = 727 − 3 · 0 = 727

Optimum + foťák (80 dkg, 20 bodů): užitek 747, hmotnost 1 070 dkg ⇒ F = 747 − 3 · 70 = 537

(Barvy podle vzorce výše.)

Foťák přidá 20 bodů, ale přetížení 70 dkg stojí 210 — výběr takový batoh spolehlivě odsune.

3. Výběr

Definice — turnajový a ruletový výběr

Nechť P = (x⁽¹⁾, …, x^(μ)) je populace velikosti μ a F : {0, 1}ⁿ → ℝ zdatnost. Výběr je náhodný postup, který z P vrátí jednoho jedince (rodiče):

Turnajový výběr velikosti k ∈ ℕ, k ≥ 1: vylosuj nezávisle a rovnoměrně indexy i₁, …, i_k ∈ {1, …, μ} (s vracením, tentýž index může padnout víckrát) a vrať jedince x^(i*), kde i* ∈ argmax_{j ∈ {i₁, …, i_k}} F(x^(j)) (při shodě zdatností kteréhokoli z nejlepších).
Ruletový výběr (předpokládá F(x^(j)) > 0 pro všechna j): vrať jedince x⁽ⁱ⁾, i ∈ {1, …, μ}, s pravděpodobností P(vybrán x⁽ⁱ⁾) = F(x⁽ⁱ⁾)/∑_j=1^μ F(x^(j)).

Selekční tlak je kvalitativní pojem: jak silně výběr upřednostňuje zdatnější jedince. Měřit ho lze například poměrem očekávaného počtu výběrů nejlepšího a průměrného jedince (viz příklad níže); u turnaje roste s k.

Laicky řečeno

Turnaj: vytáhnete tři náhodné batohy a rodičem se stane ten nejlepší z nich. Lepší batohy tak mají víc dětí, ale i průměrný má šanci, když se potká se slabšími. Kdyby se množili jen ti úplně nejlepší, populace by rychle zdegenerovala na kopie jednoho jedince — a s ní by zmizela rozmanitost, ze které evoluce žije.

Jak silný je turnaj, se dá spočítat přesně. Náš program losuje k jedinců s vracením (tentýž jedinec se může do turnaje dostat dvakrát). Seřaďme populaci od nejlepšího (i = 1) po nejhoršího (i = μ):

P(vyhraje i-tý) = (μ − i + 1)^k − (μ − i)^k/μ^k

P(vyhraje i-tý): šance, že se rodičem stane právě i-tý nejlepší jedinec
(μ − i + 1)^k: počet turnajů, ve kterých nikdo není lepší než i-tý — všech k losů padne mezi něj a horší
(μ − i)^k: z nich odečteme turnaje, ve kterých i-tý vůbec není — ty by vyhrál někdo horší; rozdíl jsou turnaje, kde je i-tý nejlepší přítomný
μ^k: počet všech možných turnajů (k losů, každý z μ jedinců) — dělením dostaneme pravděpodobnost

Pravděpodobnost závisí jen na pořadí, ne na tom, o kolik je kdo lepší — turnaj proto funguje i se zápornou zdatností, ruleta ne.

Příklad — turnaj ze tří ve 40 batozích

μ^k = 40³ = 64 000. Za generaci se vybírá 38 rodičů (dvě místa zaberou elitní jedinci); barvy podle vzorce výše:

nejlepší: 40³ − 39³/64 000 = 64 000 − 59 319/64 000 ≈ 7,31 %, očekávaně 38 · 0,0731 ≈ 2,78 výběru

20. nejlepší: 21³ − 20³/64 000 = 9 261 − 8 000/64 000 ≈ 1,97 %, očekávaně ≈ 0,75 výběru

nejhorší: 1³ − 0³/64 000 ≈ 0,0016 %, očekávaně ≈ 0,0006 výběru

Průměrný jedinec dostane 38/40 = 0,95 výběru, nejlepší skoro třikrát tolik. Obecně pro velkou populaci vychází nejlepšímu zhruba k-krát víc než průměru — proto selekční tlak roste s k.

4. Křížení a mutace

Definice — jednobodové křížení

Nechť n ≥ 2, a = (a₁, …, a_n) a b = (b₁, …, b_n) ∈ {0, 1}ⁿ jsou genomy rodičů a p_c ∈ [0, 1] pravděpodobnost křížení. Jednobodové křížení vytvoří dva potomky takto:

S pravděpodobností 1 − p_c křížení neproběhne a potomci jsou kopie rodičů a a b.
Jinak vylosuj rovnoměrně bod křížení c ∈ {1, …, n − 1} a potomci jsou a′ = (a₁, …, a_c, b_c+1, …, b_n), b′ = (b₁, …, b_c, a_c+1, …, a_n).

Potomci tedy převezmou prvních c genů od jednoho rodiče a zbylých n − c od druhého. Další varianty jsou dvoubodové křížení (dva body, prohodí se úsek mezi nimi) a uniformní křížení, kde pro každé i = 1, …, n nezávisle s pravděpodobností 1/2 platí a′_i = a_i, b′_i = b_i, jinak a′_i = b_i, b′_i = a_i.

Laicky řečeno

Dva batohy si rozstřihnete na stejném místě a prohodíte konce. Dítě dostane začátek seznamu od jednoho rodiče a konec od druhého. Pokud jeden rodič dobře vyřešil spaní a druhý jídlo, má dítě šanci zdědit obojí.

Definice — bitová mutace

Nechť x = (x₁, …, x_n) ∈ {0, 1}ⁿ je genom a p_m ∈ [0, 1] pravděpodobnost mutace. Bitová mutace vytvoří genom x′ ∈ {0, 1}ⁿ tak, že pro každé i = 1, …, n nezávisle na ostatních genech

x′_i = 1 − x_i s pravděpodobností p_m, x′_i = x_i s pravděpodobností 1 − p_m.

Každý gen se tedy s pravděpodobností p_m překlopí (0 ↔ 1). Obvykle se volí p_m = 1/n, takže se v průměru překlopí n · p_m = 1 gen na jedince.

Laicky řečeno

Občas se dítě od rodičů v jedné drobnosti liší: přibalí věc, kterou nikdo z rodičů neměl, nebo nějakou vyndá. Mutace je jediný zdroj úplně nových genů — křížení umí jen přeskládat to, co už v populaci je.

Příklad — kolik genů mutace překlopí

Počet překlopených genů má binomické rozdělení: P(j genů) = (n nad j) · p_m^j · (1 − p_m)^n−j. Pro n = 24 a p_m = 1/24:

očekávaný počet: n · p_m = 24 · 1/24 = 1

žádná změna: (23/24)²⁴ ≈ 0,360 (pro velké n se blíží 1/e ≈ 0,368)

právě jeden gen: 24 · 1/24 · (23/24)²³ ≈ 0,376

Zhruba třetina potomků tedy zůstane beze změny, třetina se liší v jednom genu a zbytek ve dvou a více.

Dva nejlepší batohy počáteční populace, jejich potomci a mutace

Rodiče jsou dva nejlepší batohy z počáteční populace (423 a 398 bodů), střih je za dvanáctou věcí. Žádný z potomků není lepší než lepší z rodičů — mají 403 a 418 bodů. Křížení zlepšení nezaručuje; jen nabízí nové kombinace a výběr pak rozhodne, které přežijí. Mutace u prvního potomka přibalila filtr na vodu (15 dkg, 32 bodů) a ten má rázem 435 bodů — víc než oba rodiče.

Příklad — přepočet křížení z obrázku

Užitek se sčítá po genech, takže stačí sečíst užitek začátku (věci 1–12) a konce (věci 13–24) zvlášť:

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

potomek 1 = začátek rodiče 1 + konec rodiče 2: 310 + 93 = 403

potomek 2 = začátek rodiče 2 + konec rodiče 1: 305 + 113 = 418

mutace přibalí filtr na vodu: 403 + 32 = 435

Rodič 1 je lepší v obou polovinách (310 > 305 a 113 > 93), takže s tímhle střihem ho žádný potomek překonat nemůže — křížení nemá z čeho složit lepší celek. Zlepšení přinesla až mutace.

5. Celý algoritmus

Algoritmus — genetický algoritmus

Vstup: délka genomu n ≥ 2, zdatnost F : {0, 1}ⁿ → ℝ, velikost populace μ ∈ ℕ, počet elitních jedinců e ∈ {0, …, μ − 1}, velikost turnaje k ≥ 1, pravděpodobnost křížení p_c ∈ [0, 1], pravděpodobnost mutace p_m ∈ [0, 1] a počet generací G ∈ ℕ. Výstup: nejzdatnější jedinec poslední generace; při e ≥ 1 je to zároveň nejzdatnější jedinec, kterého algoritmus kdy ohodnotil.

Vytvoř náhodnou počáteční populaci P₀ s μ jedinci (u nás má každý gen hodnotu 1 s pravděpodobností 0,3), ohodnoť je funkcí F a polož t ← 0.
Je-li t = G, skonči a vrať jedince z P_t s největší zdatností.
Do nové generace P_t+1 zkopíruj e nejzdatnějších jedinců z P_t beze změny (elitismus).
Dokud má P_t+1 méně než μ jedinců: vyber z P_t turnajem velikosti k dva rodiče, proveď jejich jednobodové křížení s pravděpodobností p_c, oba potomky zmutuj bitovou mutací s p_m a přidej je do P_t+1; přebývá-li nakonec jedinec nad μ, zahoď ho.
Ohodnoť jedince P_t+1, polož t ← t + 1 a pokračuj krokem 2.

Algoritmus se zastaví v kroku 2 po přesně G generacích.

Laicky řečeno

Generace za generací: nejlepší dva přežijí rovnou, ostatní místa obsadí děti zdatných rodičů, trochu přeskládané a trochu pozměněné. Elitismus zaručí, že nejlepší nalezený batoh se nikdy neztratí.

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]]            # elitismus
        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 losů s vracením

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

Cenu algoritmu měříme počtem ohodnocení zdatnosti — u skutečných úloh (simulace, měření) je to nejdražší krok. Ohodnotí se počáteční populace a pak každá generace: μ + G · μ = 40 + 60 · 40 = 2 440 ohodnocení pro μ = 40 jedinců a G = 60 generací. Elitní jedinci se ohodnocují znovu, i když se nezměnili; chytřejší program by si jejich zdatnost pamatoval.

6. Evoluce batohu

Pusťme algoritmus: 40 batohů, 60 generací, turnaj ze tří, křížení s pravděpodobností 0,9, mutace 1/24 a dva elitní jedinci. Obrázek ukazuje populaci v generacích 0, 5, 15, 30 a 60 — každý řádek je jeden batoh, každý sloupec jedna věc, nahoře pro srovnání optimum:

Populace batohů v průběhu evoluce; oranžově přetížené

Na začátku je populace pestrá a batohy jsou spíš poloprázdné: každá věc se do nich dostala s pravděpodobností 0,3, takže váží kolem čtyř kilo (očekávaná hmotnost je 0,3 · ∑ w_i = 0,3 · 12,75 kg ≈ 3,8 kg). Nejlepší má 423 bodů, průměr 231. Po pěti generacích nese stan 36 ze 40 batohů, láhev s vodou 35 a nejlepší batoh má 634 bodů. Kolem patnácté generace populace narazí na nosnost — 12 batohů je přetížených — a začne se učit, co obětovat: jídlo navíc a sandály skoro zmizely, foťák ale zatím nese 39 batohů. Optimum, 727 bodů, najde algoritmus poprvé v generaci 26; v generaci 30 už foťák zbyl jen v jednom batohu. Populace se ale nikdy neslije do jediného řešení — mutace pořád zkouší drobné odchylky.

Zdatnost po generacích nejlepší průměr populace nejlepší bez mutace

Algoritmus k tomu ohodnotil 2 440 batohů — necelé dvě setiny procenta ze všech 16 777 216 možností. Náhodné hledání se stejným počtem pokusů ve sto opakováních optimum nenašlo ani jednou a v průměru skončilo na 574 bodech.

Příklad — proč náhodné hledání optimum nenajde

Náhodný batoh bere každou věc nezávisle s pravděpodobností 0,3. Optimum obsahuje 19 věcí a 5 jich vynechává, takže

P(náhodný batoh = optimum) = 0,3¹⁹ · 0,7⁵ ≈ 1,16 · 10⁻¹⁰ · 0,168 ≈ 1,95 · 10⁻¹¹

očekávaný počet zásahů ve 2 440 pokusech: 2 440 · 1,95 · 10⁻¹¹ ≈ 4,8 · 10⁻⁸

I kdyby se losovalo rovnoměrně (každá věc s pravděpodobností 1/2), je šance jedna ku 16 777 216 na pokus. Genetický algoritmus nevylosuje optimum najednou — skládá ho po kouscích z batohů, které už jsou dobré.

7. K čemu je křížení a k čemu mutace

Oranžová čára v grafu je týž běh s vypnutou mutací. Po jedenácti generacích uvízne na 573 bodech a už se nehne. Proč, ukáže srovnání ze sta běhů s různými semínky:

Varianta	Našla optimum	Průměrný užitek
Výběr + křížení + mutace	88 ze 100	726,6
Výběr + mutace (bez křížení)	70 ze 100	725,0
Výběr + křížení (bez mutace)	0 ze 100	596,8
Náhodné hledání, stejně pokusů	0 ze 100	573,5

Bez mutace ztratí populace rozmanitost: když gen v žádném jedinci není, křížení ho nevyrobí, a výběr navíc rychle vytlačí všechno kromě nejlepších. Tomu se říká předčasná konvergence. Bez křížení algoritmus funguje — je to vlastně populace horolezců s výběrem —, ale je pomalejší. Křížení pomáhá skládat dohromady dobré kusy, které vznikly v různých jedincích.

Věta — Hollandova věta o schématech

Nechť n ≥ 2. Schéma je řetězec H = (H₁, …, H_n) ∈ {0, 1, ∗}ⁿ, kde ∗ znamená „cokoli“. Genom x ∈ {0, 1}ⁿ odpovídá schématu H, právě když x_i = H_i pro všechna i s H_i ≠ ∗. Pozice i s H_i ≠ ∗ jsou pevné; předpokládejme, že aspoň jedna existuje. Definujme

řád o(H) = |{i : H_i ≠ ∗}| — počet pevných pozic,
délku δ(H) = max{i : H_i ≠ ∗} − min{i : H_i ≠ ∗} — vzdálenost první a poslední pevné pozice.

Nechť genetický algoritmus s populací velikosti μ a kladnou zdatností F > 0 tvoří celou novou generaci ruletovým výběrem, jednobodovým křížením s pravděpodobností p_c a bitovou mutací s pravděpodobností p_m (bez elitismu). Nechť m(H, t) je počet jedinců generace t, kteří odpovídají H, a je-li m(H, t) > 0, nechť F(H) je jejich průměrná zdatnost a F̄ průměrná zdatnost celé generace t. Pak pro očekávaný počet v další generaci (při dané generaci t) platí

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

Slovy: výběr počet nositelů schématu násobí poměrem jejich zdatnosti k průměru a křížení s mutací z něj nejvýš odečtou uvedené ztráty.

Laicky řečeno

Schéma je „stavební kámen“, například „beru stan i spacák, na ostatním nezáleží“. Věta říká, že krátké stavební kameny s nadprůměrnou zdatností se v populaci šíří — a to exponenciálně rychle, protože každou generaci se jejich počet zhruba násobí poměrem F(H)/F̄. Krátké proto, že je křížení méně často rozstřihne. Věta je jen dolní odhad a o tom, jak dobře algoritmus funguje, se dodnes vedou diskuse.

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

m(H, t): kolik jedinců nese stavební kámen teď — další generace z nich vychází, proto se s ním násobí
F(H)/F̄: o kolik jsou nositelé schématu zdatnější než průměr — ruleta jim dá úměrně víc potomků; nad 1 se schéma množí, pod 1 vymírá
p_c · δ(H)/n − 1: šance (shora), že křížení schéma rozstřihne: křížení proběhne s p_c a bod střihu padne s pravděpodobností δ(H)/n − 1 mezi pevné pozice — proto vadí dlouhá schémata
o(H) · p_m: šance (shora), že mutace překlopí některou z o(H) pevných pozic — proto vadí schémata vysokého řádu

Výběr schéma množí, křížení a mutace ho mohou zničit; odečtení obou ztrát je odhad zdola, protože rozstřižené schéma může i znovu vzniknout.

Příklad — krátké a dlouhé schéma na batohu

Hranatá závorka pro nastavení našeho běhu (p_c = 0,9, n = 24, p_m = 1/24). Obě schémata mají řád 2; barvy podle vzorce výše:

„stan i spacák“ (geny 1 a 2, δ = 1): 1 − 0,9 · 1/23 − 2 · 1/24 ≈ 1 − 0,039 − 0,083 = 0,878

„stan i ponožky navíc“ (geny 1 a 24, δ = 23): 1 − 0,9 · 23/23 − 2 · 1/24 ≈ 1 − 0,9 − 0,083 = 0,017

Krátkému schématu stačí, aby jeho nositelé byli o 14 % zdatnější než průměr (1/0,878 ≈ 1,14), a podle věty se už šíří. Dlouhé schéma by muselo být šedesátkrát zdatnější — věta o něm v podstatě nic neslibuje. Náš algoritmus používá turnaj, ne ruletu, takže pro něj platí jen hranatá závorka; první dva činitele by se počítaly jinak.

8. Genetické algoritmy v praxi

Návrh tvarů. Anténa družic NASA ST5 (vypuštěných v roce 2006) byla navržena evolučním algoritmem: zvláštně pokroucený drátek, který by inženýra nenapadl, ale splnil zadání aspoň stejně dobře jako ručně navržená anténa (v pozdějších pokusech i lépe).
Rozvrhy a logistika. Rozvrhy, plány směn nebo uspořádání skladu — úlohy s mnoha podmínkami, kde se zdatnost dá spočítat, ale přesný algoritmus by běžel věky.
Strojové učení. Evoluce ladí hyperparametry modelů a v neuroevoluci, které má osnova vlastní díl, i váhy a architektury neuronových sítí.
Evoluce s jazykovými modely. Systémy jako FunSearch (2023) a AlphaEvolve (2025) od Google DeepMind udržují populaci programů a jako mutaci používají jazykový model, který program upraví. Výběr zajistí automatické hodnocení. Takhle se podařilo najít nové matematické konstrukce i rychlejší algoritmy.

9. Shrnutí

Genetický algoritmus vylepšuje celou populaci řešení: výběrem zdatných, křížením a mutací.
Zdatnost je jediné, co o úloze potřebuje vědět; porušení podmínek se dá řešit trestem.
Turnajový výběr drží selekční tlak, elitismus nedovolí ztratit nejlepší řešení.
Na batohu s 16,7 miliony možností našel optimum v 88 ze 100 běhů po ohodnocení 2 440 batohů; náhodné hledání se stejným rozpočtem ani jednou.
Mutace dodává rozmanitost — bez ní populace předčasně zkonverguje. Křížení skládá dobré stavební kameny a evoluci zrychluje.

Chcete si to osahat? Nechte AI agenta napsat genetický algoritmus pro váš vlastní batoh na výlet — a pak zkuste vypnout mutaci, zvětšit turnaj nebo zmenšit populaci a sledujte, co se stane s rozmanitostí.

Máte na to jiný názor? Napište na support@coden-app.com.

Genetické algoritmy: populace, křížení, mutace a výběr na batohu na výlet

1. Úloha: batoh na výlet

2. Jedinec, genom a zdatnost

3. Výběr

4. Křížení a mutace

5. Celý algoritmus

6. Evoluce batohu

7. K čemu je křížení a k čemu mutace

8. Genetické algoritmy v praxi

9. Shrnutí

Agent na vašem počítači, ovládaný z telefonu