Genetické algoritmy: populácia, kríženie, mutácia a výber na batohu na výlet

Genóm a zdatnosť, turnajový výber, jednobodové kríženie, mutácia a elitizmus, veta o schémach a predčasná konvergencia — na úlohe batohu so známym optimom, od stanu po FunSearch a AlphaEvolve.

14 minút Matěj Žalmánek 2026-10-15

Séria Základy AI Diel 27 z 52

Celá osnova série Hotovo: 52 z 83 tém

Čo si odnesiete

Ako zakódovať riešenie ako genóm a ako výber, kríženie a mutácia vylepšujú celú populáciu.
Prečo bez mutácie evolúcia predčasne skonverguje a na čo je kríženie.
Kde sa genetické algoritmy používajú dnes — aj s jazykovým modelom v úlohe mutácie.

Čo sa hodí vedieť vopred: Lokálne hľadanie a simulované žíhanie: obchodný cestujúci cez krajské mestá

Príroda nemá inžiniera, a predsa vyrobila oko, krídlo aj mozog. Stačili jej tri veci: jedince sa od seba líšia, svoje vlastnosti odovzdávajú potomkom a tí zdatnejší majú potomkov viac. V sedemdesiatych rokoch John Holland z Michiganskej univerzity ukázal, že tie isté tri veci fungujú aj v počítači — ako všeobecná metóda, ako hľadať dobré riešenia úloh, pri ktorých nevieme, ako ich riešiť šikovne. Genetický algoritmus nepotrebuje gradient, nepotrebuje vzorec, potrebuje len vedieť povedať, ktoré z dvoch riešení je lepšie.

Nadväzuje na diel Lokálne hľadanie a simulované žíhanie. Žíhanie vylepšovalo jedno riešenie; genetický algoritmus ich vylepšuje celú populáciu naraz.

1. Úloha: batoh na výlet

Chystáte sa na niekoľkodňový výlet. Doma máte 24 vecí — stan, spací vak, varič, fotoaparát, knihu… — a každá niečo váži a na niečo je. Batoh smie vážiť najviac 10 kg. Čo vziať, aby bol úžitok čo najväčší?

Definícia — úloha batohu (0/1)

Nech n ∈ ℕ, n ≥ 1, je počet vecí, w₁, …, w_n > 0 ich hmotnosti, u₁, …, u_n > 0 ich úžitky a W > 0 nosnosť batohu. Výber vecí zapíšeme vektorom x = (x₁, …, x_n) ∈ {0, 1}ⁿ, kde x_i = 1 práve vtedy, keď i-tú vec berieme. Výber x je prípustný práve vtedy, keď ∑_i=1ⁿ w_ix_i ≤ W. Úloha batohu (0/1) je úloha nájsť

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

Hľadáme teda prípustný výber s najväčším súčtom úžitkov; „0/1“ v názve znamená, že každú vec možno vziať len celú a najviac raz.

Laicky povedané

Každá vec je otázka „beriem, neberiem“ — jednotka, alebo nula. Možností je 2²⁴, teda 16 777 216 batohov. Pažravá stratégia „najprv to najužitočnejšie na kilo“ často funguje, ale optimum nezaručí: jedna ťažká vec môže vytlačiť tri ľahké, ktoré boli dohromady cennejšie.

Pre celočíselné hmotnosti sa dá optimum spočítať presne dynamickým programovaním — zo všetkých 24 vecí a nosnosti 1 000 dekagramov je to 24 000 krokov. Najlepší batoh má 727 bodov úžitku a váži 9,9 kg; doma zostane jedlo navyše, fotoaparát, kniha, sandále a opaľovací krém. Vďaka tomu zase presne uvidíme, ako blízko sa evolúcia dostane. Genetický algoritmus sa však hodí hlavne tam, kde taký presný postup neexistuje.

Dynamické programovanie vypĺňa tabuľku T[i][c] — najlepší úžitok, ktorý možno dosiahnuť len z prvých i vecí, keď smú vážiť najviac c. Každé políčko sa spočíta z riadka nad ním:

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

T[i][c]: najlepší úžitok z prvých i vecí pri nosnosti c; políčko T[n][W] je odpoveď na celú úlohu
T[i − 1][c]: možnosť „i-tú vec neberiem“ — potom je najlepšie to, čo sa dalo poskladať z predchádzajúcich vecí s rovnakou nosnosťou
T[i − 1][c − w_i]: možnosť „beriem“ — vec zaberie w_i, takže na ostatné zostane len c − w_i; najlepšie využitie zvyšku už v tabuľke máme (smie sa len pre c ≥ w_i)
u_i: úžitok veci, ktorú sme v tej druhej možnosti pribalili

Optimálny batoh buď i-tú vec obsahuje, alebo nie — a v oboch prípadoch je zvyšok optimálnym batohom menšej úlohy. Začína sa riadkom T[0][c] = 0.

Príklad — tabuľka pre štyri veci a nosnosť 50 dkg

Čelovka (10 dkg, 25 bodov), nôž (10 dkg, 18), varič (40 dkg, 30) a karimatka (50 dkg, 45). Všetky hmotnosti sú násobky desiatich, takže stačia stĺpce po 10 dkg:

veci	10	20	30	40	50
žiadna	0	0	0	0	0
+ čelovka	25	25	25	25	25
+ nôž	25	43	43	43	43
+ varič	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

Varič, c = 40: T[3][40] = max(T[2][40], T[2][0] + 30) = max(43, 0 + 30) = 43 — varič sa neoplatí

Varič, c = 50: T[3][50] = max(T[2][50], T[2][10] + 30) = max(43, 25 + 30) = 55 — varič a čelovka

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

(Farby podľa vzorca vyššie.)

Pažravá stratégia by vzala veci podľa úžitku na dekagram: čelovku (2,5 bodu/dkg), nôž (1,8), potom by sa karimatka (0,9) ani varič (0,75) do zvyšných 30 dkg nezmestili — len 43 bodov. Vo veľkej úlohe s 24 vecami skončí pažravá stratégia na 702 bodoch: naplní batoh drobnosťami a na stan (220 dkg) už nezostane miesto.

def batoh(w, u, W):                       # w, u: hmotnosti a úžitky, W: nosnosť
    T = [0] * (W + 1)                     # riadok pre „žiadna vec“
    for i in range(len(w)):
        for c in range(W, w[i] - 1, -1):  # odzadu: T[c − w[i]] je ešte z riadka i − 1
            T[c] = max(T[c], T[c - w[i]] + u[i])
    return T[W]                           # n · W krokov: 24 · 1000 = 24 000

2. Jedinec, genóm a zdatnosť

Definícia — genóm, populácia, zdatnosť

Nech je daná úloha batohu s n vecami, hmotnosťami w_i a nosnosťou W v dekagramoch a úžitkami u_i (i = 1, …, n; u nás n = 24).

Genóm (chromozóm) je zakódované riešenie; pre batoh je to reťazec x = (x₁, …, x_n) ∈ {0, 1}ⁿ. Jeho zložky x_i — jeden bit na vec — nazývame gény.
Populácia veľkosti μ ∈ ℕ je μ-tica genómov P = (x⁽¹⁾, …, x^(μ)), x^(j) ∈ {0, 1}ⁿ; ten istý genóm v nej môže byť viackrát (na poradí nezáleží, ide teda o multimnožinu s μ prvkami). Prvkom populácie hovoríme jedince.
Zdatnosť (fitness) je funkcia F : {0, 1}ⁿ → ℝ, ktorú algoritmus maximalizuje. Pre batoh ju definujeme s trestom za preťaženie: F(x) = ∑_i=1ⁿ u_ix_i, ak ∑_i=1ⁿ w_ix_i ≤ W, F(x) = ∑_i=1ⁿ u_ix_i − 3 · (∑_i=1ⁿ w_ix_i − W), inak.

Pre prípustný batoh je teda zdatnosť rovná jeho úžitku a za každý dekagram cez nosnosť sa odčítajú 3 body.

Laicky povedané

Jedinec je jeden konkrétny batoh zapísaný ako rad jednotiek a núl. Zdatnosť hovorí, aký je dobrý. Preťažený batoh nezakážeme, len ho potrestáme — za každý dekagram navyše tri body dole. Algoritmus sa tak o hranici nosnosti dozvie postupne, a aj preťažený batoh môže mať gény, ktoré sa neskôr zídu.

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

F(x): zdatnosť batohu x — jediné číslo, podľa ktorého výber porovnáva jedincov
∑ u_ix_i: úžitok zabalených vecí (x_i = 1 vec započíta, 0 vynechá) — to, čo naozaj chceme maximalizovať
3: cena jedného dekagramu cez limit — je väčšia ako najlepší pomer úžitku a hmotnosti (čelovka, 2,5 bodu/dkg), takže pribaliť čokoľvek do už preťaženého batohu zdatnosť vždy zníži
max(0, ∑ w_ix_i − W): preťaženie v dekagramoch; max s nulou zaistí, že batoh, ktorý sa zmestí, trest nedostane a ľahší batoh nie je zvýhodnený

Oba prípady z definície v jednom vzorci: trest je nulový, kým sa batoh zmestí, a potom rastie s každým dekagramom navyše.

Príklad — zdatnosť dvoch batohov

Optimum: úžitok 727, hmotnosť 990 dkg ≤ 1 000 ⇒ F = 727 − 3 · 0 = 727

Optimum + fotoaparát (80 dkg, 20 bodov): úžitok 747, hmotnosť 1 070 dkg ⇒ F = 747 − 3 · 70 = 537

(Farby podľa vzorca vyššie.)

Fotoaparát pridá 20 bodov, ale preťaženie 70 dkg stojí 210 — výber taký batoh spoľahlivo odsunie.

3. Výber

Definícia — turnajový a ruletový výber

Nech P = (x⁽¹⁾, …, x^(μ)) je populácia veľkosti μ a F : {0, 1}ⁿ → ℝ zdatnosť. Výber je náhodný postup, ktorý z P vráti jedného jedinca (rodiča):

Turnajový výber veľkosti k ∈ ℕ, k ≥ 1: vylosuj nezávisle a rovnomerne indexy i₁, …, i_k ∈ {1, …, μ} (s vracaním, ten istý index môže padnúť viackrát) a vráť jedinca x^(i*), kde i* ∈ argmax_{j ∈ {i₁, …, i_k}} F(x^(j)) (pri zhode zdatností ktoréhokoľvek z najlepších).
Ruletový výber (predpokladá F(x^(j)) > 0 pre všetky j): vráť jedinca x⁽ⁱ⁾, i ∈ {1, …, μ}, s pravdepodobnosťou P(vybraný x⁽ⁱ⁾) = F(x⁽ⁱ⁾)/∑_j=1^μ F(x^(j)).

Selekčný tlak je kvalitatívny pojem: ako silno výber uprednostňuje zdatnejších jedincov. Merať ho možno napríklad pomerom očakávaného počtu výberov najlepšieho a priemerného jedinca (pozri príklad nižšie); pri turnaji rastie s k.

Laicky povedané

Turnaj: vytiahnete tri náhodné batohy a rodičom sa stane ten najlepší z nich. Lepšie batohy tak majú viac detí, ale aj priemerný má šancu, keď sa stretne so slabšími. Keby sa množili len tí úplne najlepší, populácia by rýchlo zdegenerovala na kópie jedného jedinca — a s ňou by zmizla rozmanitosť, z ktorej evolúcia žije.

Aký silný je turnaj, sa dá spočítať presne. Náš program losuje k jedincov s vracaním (ten istý jedinec sa môže do turnaja dostať dvakrát). Zoraďme populáciu od najlepšieho (i = 1) po najhoršieho (i = μ):

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

P(vyhrá i-ty): šanca, že sa rodičom stane práve i-ty najlepší jedinec
(μ − i + 1)^k: počet turnajov, v ktorých nikto nie je lepší ako i-ty — všetkých k žrebov padne medzi neho a horších
(μ − i)^k: z nich odčítame turnaje, v ktorých i-ty vôbec nie je — tie by vyhral niekto horší; rozdiel sú turnaje, kde je i-ty najlepší prítomný
μ^k: počet všetkých možných turnajov (k žrebov, každý z μ jedincov) — delením dostaneme pravdepodobnosť

Pravdepodobnosť závisí len od poradia, nie od toho, o koľko je kto lepší — turnaj preto funguje aj so zápornou zdatnosťou, ruleta nie.

Príklad — turnaj z troch v 40 batohoch

μ^k = 40³ = 64 000. Za generáciu sa vyberá 38 rodičov (dve miesta zaberú elitní jedinci); farby podľa vzorca vyššie:

najlepší: 40³ − 39³/64 000 = 64 000 − 59 319/64 000 ≈ 7,31 %, očakávane 38 · 0,0731 ≈ 2,78 výberu

20. najlepší: 21³ − 20³/64 000 = 9 261 − 8 000/64 000 ≈ 1,97 %, očakávane ≈ 0,75 výberu

najhorší: 1³ − 0³/64 000 ≈ 0,0016 %, očakávane ≈ 0,0006 výberu

Priemerný jedinec dostane 38/40 = 0,95 výberu, najlepší skoro trikrát toľko. Všeobecne pre veľkú populáciu vychádza najlepšiemu zhruba k-krát viac ako priemeru — preto selekčný tlak rastie s k.

4. Kríženie a mutácia

Definícia — jednobodové kríženie

Nech n ≥ 2, a = (a₁, …, a_n) a b = (b₁, …, b_n) ∈ {0, 1}ⁿ sú genómy rodičov a p_c ∈ [0, 1] pravdepodobnosť kríženia. Jednobodové kríženie vytvorí dvoch potomkov takto:

S pravdepodobnosťou 1 − p_c kríženie neprebehne a potomkovia sú kópie rodičov a a b.
Inak vylosuj rovnomerne bod kríženia c ∈ {1, …, n − 1} a potomkovia sú a′ = (a₁, …, a_c, b_c+1, …, b_n), b′ = (b₁, …, b_c, a_c+1, …, a_n).

Potomkovia teda prevezmú prvých c génov od jedného rodiča a zvyšných n − c od druhého. Ďalšie varianty sú dvojbodové kríženie (dva body, vymení sa úsek medzi nimi) a uniformné kríženie, kde pre každé i = 1, …, n nezávisle s pravdepodobnosťou 1/2 platí a′_i = a_i, b′_i = b_i, inak a′_i = b_i, b′_i = a_i.

Laicky povedané

Dva batohy si rozstrihnete na rovnakom mieste a vymeníte konce. Dieťa dostane začiatok zoznamu od jedného rodiča a koniec od druhého. Ak jeden rodič dobre vyriešil spanie a druhý jedlo, má dieťa šancu zdediť oboje.

Definícia — bitová mutácia

Nech x = (x₁, …, x_n) ∈ {0, 1}ⁿ je genóm a p_m ∈ [0, 1] pravdepodobnosť mutácie. Bitová mutácia vytvorí genóm x′ ∈ {0, 1}ⁿ tak, že pre každé i = 1, …, n nezávisle od ostatných génov

x′_i = 1 − x_i s pravdepodobnosťou p_m, x′_i = x_i s pravdepodobnosťou 1 − p_m.

Každý gén sa teda s pravdepodobnosťou p_m preklopí (0 ↔ 1). Obvykle sa volí p_m = 1/n, takže sa v priemere preklopí n · p_m = 1 gén na jedinca.

Laicky povedané

Občas sa dieťa od rodičov v jednej drobnosti líši: pribalí vec, ktorú nikto z rodičov nemal, alebo nejakú vyberie. Mutácia je jediný zdroj úplne nových génov — kríženie vie len preskladať to, čo už v populácii je.

Príklad — koľko génov mutácia preklopí

Počet preklopených génov má binomické rozdelenie: P(j génov) = (n nad j) · p_m^j · (1 − p_m)^n−j. Pre n = 24 a p_m = 1/24:

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

žiadna zmena: (23/24)²⁴ ≈ 0,360 (pre veľké n sa blíži 1/e ≈ 0,368)

práve jeden gén: 24 · 1/24 · (23/24)²³ ≈ 0,376

Zhruba tretina potomkov teda zostane bez zmeny, tretina sa líši v jednom géne a zvyšok v dvoch a viacerých.

Dva najlepšie batohy počiatočnej populácie, ich potomkovia a mutácia

Rodičia sú dva najlepšie batohy z počiatočnej populácie (423 a 398 bodov), strih je za dvanástou vecou. Žiadny z potomkov nie je lepší ako lepší z rodičov — majú 403 a 418 bodov. Kríženie zlepšenie nezaručuje; len ponúka nové kombinácie a výber potom rozhodne, ktoré prežijú. Mutácia u prvého potomka pribalila filter na vodu (15 dkg, 32 bodov) a ten má razom 435 bodov — viac ako obaja rodičia.

Príklad — prepočet kríženia z obrázka

Úžitok sa sčítava po génoch, takže stačí sčítať úžitok začiatku (veci 1–12) a konca (veci 13–24) zvlášť:

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

potomok 1 = začiatok rodiča 1 + koniec rodiča 2: 310 + 93 = 403

potomok 2 = začiatok rodiča 2 + koniec rodiča 1: 305 + 113 = 418

mutácia pribalí filter na vodu: 403 + 32 = 435

Rodič 1 je lepší v oboch polovicách (310 > 305 a 113 > 93), takže s týmto strihom ho žiadny potomok prekonať nemôže — kríženie nemá z čoho poskladať lepší celok. Zlepšenie prinesla až mutácia.

5. Celý algoritmus

Algoritmus — genetický algoritmus

Vstup: dĺžka genómu n ≥ 2, zdatnosť F : {0, 1}ⁿ → ℝ, veľkosť populácie μ ∈ ℕ, počet elitných jedincov e ∈ {0, …, μ − 1}, veľkosť turnaja k ≥ 1, pravdepodobnosť kríženia p_c ∈ [0, 1], pravdepodobnosť mutácie p_m ∈ [0, 1] a počet generácií G ∈ ℕ. Výstup: najzdatnejší jedinec poslednej generácie; pri e ≥ 1 je to zároveň najzdatnejší jedinec, ktorého algoritmus kedy ohodnotil.

Vytvor náhodnú počiatočnú populáciu P₀ s μ jedincami (u nás má každý gén hodnotu 1 s pravdepodobnosťou 0,3), ohodnoť ich funkciou F a polož t ← 0.
Ak je t = G, skonči a vráť jedinca z P_t s najväčšou zdatnosťou.
Do novej generácie P_t+1 skopíruj e najzdatnejších jedincov z P_t bez zmeny (elitizmus).
Kým má P_t+1 menej než μ jedincov: vyber z P_t turnajom veľkosti k dvoch rodičov, vykonaj ich jednobodové kríženie s pravdepodobnosťou p_c, oboch potomkov zmutuj bitovou mutáciou s p_m a pridaj ich do P_t+1; ak nakoniec prebýva jedinec nad μ, zahoď ho.
Ohodnoť jedincov P_t+1, polož t ← t + 1 a pokračuj krokom 2.

Algoritmus sa zastaví v kroku 2 po presne G generáciách.

Laicky povedané

Generácia za generáciou: najlepší dvaja prežijú rovno, ostatné miesta obsadia deti zdatných rodičov, trochu preskladané a trochu pozmenené. Elitizmus zaručí, že najlepší nájdený batoh sa nikdy nestratí.

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]]            # elitizmus
        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 žrebov s vracaním

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

Cenu algoritmu meriame počtom ohodnotení zdatnosti — pri skutočných úlohách (simulácie, merania) je to najdrahší krok. Ohodnotí sa počiatočná populácia a potom každá generácia: μ + G · μ = 40 + 60 · 40 = 2 440 ohodnotení pre μ = 40 jedincov a G = 60 generácií. Elitní jedinci sa ohodnocujú znova, aj keď sa nezmenili; šikovnejší program by si ich zdatnosť pamätal.

6. Evolúcia batohu

Pustime algoritmus: 40 batohov, 60 generácií, turnaj z troch, kríženie s pravdepodobnosťou 0,9, mutácia 1/24 a dvaja elitní jedinci. Obrázok ukazuje populáciu v generáciách 0, 5, 15, 30 a 60 — každý riadok je jeden batoh, každý stĺpec jedna vec, hore na porovnanie optimum:

Populácia batohov v priebehu evolúcie; oranžovo preťažené

Na začiatku je populácia pestrá a batohy sú skôr poloprázdne: každá vec sa do nich dostala s pravdepodobnosťou 0,3, takže vážia okolo štyroch kíl (očakávaná hmotnosť je 0,3 · ∑ w_i = 0,3 · 12,75 kg ≈ 3,8 kg). Najlepší má 423 bodov, priemer 231. Po piatich generáciách nesie stan 36 zo 40 batohov, fľašu s vodou 35 a najlepší batoh má 634 bodov. Okolo pätnástej generácie populácia narazí na nosnosť — 12 batohov je preťažených — a začne sa učiť, čo obetovať: jedlo navyše a sandále skoro zmizli, fotoaparát však zatiaľ nesie 39 batohov. Optimum, 727 bodov, nájde algoritmus prvýkrát v generácii 26; v generácii 30 už fotoaparát zostal len v jednom batohu. Populácia sa však nikdy nezleje do jediného riešenia — mutácia stále skúša drobné odchýlky.

Zdatnosť po generáciách najlepší priemer populácie najlepší bez mutácie

Algoritmus na to ohodnotil 2 440 batohov — necelé dve stotiny percenta zo všetkých 16 777 216 možností. Náhodné hľadanie s rovnakým počtom pokusov v sto opakovaniach optimum nenašlo ani raz a v priemere skončilo na 574 bodoch.

Príklad — prečo náhodné hľadanie optimum nenájde

Náhodný batoh berie každú vec nezávisle s pravdepodobnosťou 0,3. Optimum obsahuje 19 vecí a 5 ich vynecháva, takže

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

očakávaný počet zásahov v 2 440 pokusoch: 2 440 · 1,95 · 10⁻¹¹ ≈ 4,8 · 10⁻⁸

Aj keby sa losovalo rovnomerne (každá vec s pravdepodobnosťou 1/2), je šanca jedna ku 16 777 216 na pokus. Genetický algoritmus nevylosuje optimum naraz — skladá ho po kúskoch z batohov, ktoré už sú dobré.

7. Na čo je kríženie a na čo mutácia

Oranžová čiara v grafe je ten istý beh s vypnutou mutáciou. Po jedenástich generáciách uviazne na 573 bodoch a už sa nepohne. Prečo, ukáže porovnanie zo sto behov s rôznymi semienkami:

Variant	Našla optimum	Priemerný úžitok
Výber + kríženie + mutácia	88 zo 100	726,6
Výber + mutácia (bez kríženia)	70 zo 100	725,0
Výber + kríženie (bez mutácie)	0 zo 100	596,8
Náhodné hľadanie, rovnako pokusov	0 zo 100	573,5

Bez mutácie stratí populácia rozmanitosť: keď gén v žiadnom jedincovi nie je, kríženie ho nevyrobí, a výber navyše rýchlo vytlačí všetko okrem najlepších. Tomu sa hovorí predčasná konvergencia. Bez kríženia algoritmus funguje — je to vlastne populácia horolezcov s výberom —, ale je pomalší. Kríženie pomáha skladať dohromady dobré kúsky, ktoré vznikli v rôznych jedincoch.

Veta — Hollandova veta o schémach

Nech n ≥ 2. Schéma je reťazec H = (H₁, …, H_n) ∈ {0, 1, ∗}ⁿ, kde ∗ znamená „čokoľvek“. Genóm x ∈ {0, 1}ⁿ zodpovedá schéme H práve vtedy, keď x_i = H_i pre všetky i s H_i ≠ ∗. Pozície i s H_i ≠ ∗ sú pevné; predpokladajme, že aspoň jedna existuje. Definujme

rád o(H) = |{i : H_i ≠ ∗}| — počet pevných pozícií,
dĺžku δ(H) = max{i : H_i ≠ ∗} − min{i : H_i ≠ ∗} — vzdialenosť prvej a poslednej pevnej pozície.

Nech genetický algoritmus s populáciou veľkosti μ a kladnou zdatnosťou F > 0 tvorí celú novú generáciu ruletovým výberom, jednobodovým krížením s pravdepodobnosťou p_c a bitovou mutáciou s pravdepodobnosťou p_m (bez elitizmu). Nech m(H, t) je počet jedincov generácie t, ktorí zodpovedajú H, a ak je m(H, t) > 0, nech F(H) je ich priemerná zdatnosť a F̄ priemerná zdatnosť celej generácie t. Potom pre očakávaný počet v ďalšej generácii (pri danej generácii t) platí

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

Slovami: výber počet nositeľov schémy násobí pomerom ich zdatnosti k priemeru a kríženie s mutáciou z neho najviac odčítajú uvedené straty.

Laicky povedané

Schéma je „stavebný kameň“, napríklad „beriem stan aj spací vak, na ostatnom nezáleží“. Veta hovorí, že krátke stavebné kamene s nadpriemernou zdatnosťou sa v populácii šíria — a to exponenciálne rýchlo, pretože každú generáciu sa ich počet zhruba násobí pomerom F(H)/F̄. Krátke preto, že ich kríženie menej často rozstrihne. Veta je len dolný odhad a o tom, ako dobre algoritmus funguje, sa dodnes vedú diskusie.

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

m(H, t): koľko jedincov nesie stavebný kameň teraz — ďalšia generácia z nich vychádza, preto sa s ním násobí
F(H)/F̄: o koľko sú nositelia schémy zdatnejší ako priemer — ruleta im dá úmerne viac potomkov; nad 1 sa schéma množí, pod 1 vymiera
p_c · δ(H)/n − 1: šanca (zhora), že kríženie schému rozstrihne: kríženie prebehne s p_c a bod strihu padne s pravdepodobnosťou δ(H)/n − 1 medzi pevné pozície — preto vadia dlhé schémy
o(H) · p_m: šanca (zhora), že mutácia preklopí niektorú z o(H) pevných pozícií — preto vadia schémy vysokého rádu

Výber schému množí, kríženie a mutácia ju môžu zničiť; odčítanie oboch strát je odhad zdola, pretože rozstrihnutá schéma môže aj znova vzniknúť.

Príklad — krátka a dlhá schéma na batohu

Hranatá zátvorka pre nastavenie nášho behu (p_c = 0,9, n = 24, p_m = 1/24). Obe schémy majú rád 2; farby podľa vzorca vyššie:

„stan aj spací vak“ (gény 1 a 2, δ = 1): 1 − 0,9 · 1/23 − 2 · 1/24 ≈ 1 − 0,039 − 0,083 = 0,878

„stan aj ponožky navyše“ (gény 1 a 24, δ = 23): 1 − 0,9 · 23/23 − 2 · 1/24 ≈ 1 − 0,9 − 0,083 = 0,017

Krátkej schéme stačí, aby jej nositelia boli o 14 % zdatnejší ako priemer (1/0,878 ≈ 1,14), a podľa vety sa už šíri. Dlhá schéma by musela byť šesťdesiatkrát zdatnejšia — veta o nej v podstate nič nesľubuje. Náš algoritmus používa turnaj, nie ruletu, takže pre neho platí len hranatá zátvorka; prvé dva činitele by sa počítali inak.

8. Genetické algoritmy v praxi

Návrh tvarov. Anténa družíc NASA ST5 (vypustených v roku 2006) bola navrhnutá evolučným algoritmom: zvláštne pokrútený drôtik, ktorý by inžiniera nenapadol, ale splnil zadanie aspoň rovnako dobre ako ručne navrhnutá anténa (v neskorších pokusoch aj lepšie).
Rozvrhy a logistika. Rozvrhy, plány zmien alebo usporiadanie skladu — úlohy s mnohými podmienkami, kde sa zdatnosť dá spočítať, ale presný algoritmus by bežal veky.
Strojové učenie. Evolúcia ladí hyperparametre modelov a v neuroevolúcii, ktorá má v osnove vlastný diel, aj váhy a architektúry neurónových sietí.
Evolúcia s jazykovými modelmi. Systémy ako FunSearch (2023) a AlphaEvolve (2025) od Google DeepMind udržiavajú populáciu programov a ako mutáciu používajú jazykový model, ktorý program upraví. Výber zaistí automatické hodnotenie. Takto sa podarilo nájsť nové matematické konštrukcie aj rýchlejšie algoritmy.

9. Zhrnutie

Genetický algoritmus vylepšuje celú populáciu riešení: výberom zdatných, krížením a mutáciou.
Zdatnosť je jediné, čo o úlohe potrebuje vedieť; porušenie podmienok sa dá riešiť trestom.
Turnajový výber drží selekčný tlak, elitizmus nedovolí stratiť najlepšie riešenie.
Na batohu so 16,7 milióna možností našiel optimum v 88 zo 100 behov po ohodnotení 2 440 batohov; náhodné hľadanie s rovnakým rozpočtom ani raz.
Mutácia dodáva rozmanitosť — bez nej populácia predčasne skonverguje. Kríženie skladá dobré stavebné kamene a evolúciu zrýchľuje.

Chcete si to vyskúšať? Nechajte AI agenta napísať genetický algoritmus pre váš vlastný batoh na výlet — a potom skúste vypnúť mutáciu, zväčšiť turnaj alebo zmenšiť populáciu a sledujte, čo sa stane s rozmanitosťou.

Máte na to iný názor? Napíšte na support@coden-app.com.

Genetické algoritmy: populácia, kríženie, mutácia a výber na batohu na výlet

1. Úloha: batoh na výlet

2. Jedinec, genóm a zdatnosť

3. Výber

4. Kríženie a mutácia

5. Celý algoritmus

6. Evolúcia batohu

7. Na čo je kríženie a na čo mutácia

8. Genetické algoritmy v praxi

9. Zhrnutie

Agent na vašom počítači, ovládaný z telefónu