Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу

Геном і пристосованість, турнірний добір, одноточкове схрещування, мутація та елітизм, теорема про схеми й передчасна збіжність — на задачі про рюкзак із відомим оптимумом, від намету до FunSearch і AlphaEvolve.

14 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 27 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

Природа не має інженера, а все ж створила око, крило й мозок. Їй вистачило трьох речей: особини відрізняються одна від одної, передають свої властивості нащадкам, а пристосованіші мають більше нащадків. У сімдесятих роках Джон Голланд із Мічиганського університету показав, що ті самі три речі працюють і в комп’ютері — як загальний метод пошуку добрих розв’язків задач, про які ми не знаємо, як розв’язати їх спритно. Генетичному алгоритму не потрібен градієнт, не потрібна формула; потрібно лише вміти сказати, який із двох розв’язків кращий.

Ця частина продовжує частину Локальний пошук та імітація відпалу. Відпал покращував один розв’язок; генетичний алгоритм покращує цілу їх популяцію одночасно.

1. Задача: рюкзак для походу

Ви збираєтеся в кількаденний похід. Удома маєте 24 речі — намет, спальник, пальник, фотоапарат, книжку… — і кожна щось важить і для чогось потрібна. Рюкзак може важити щонайбільше 10 кг. Що взяти, щоб користь була якомога більшою?

Означення — задача про рюкзак (0/1)

Дано n предметів із масами w_i > 0 і цінностями u_i > 0 та вантажність W. Шукаємо x ∈ {0, 1}ⁿ, яке максимізує ∑_i u_ix_i за умови ∑_i w_ix_i ≤ W.

Для цілих мас оптимум можна обчислити точно динамічним програмуванням — для всіх 24 речей і вантажності 1 000 декаграмів це 24 000 кроків. Найкращий рюкзак має 727 балів користі і важить 9,9 кг; удома лишаються зайва їжа, фотоапарат, книжка, сандалі й сонцезахисний крем. Завдяки цьому ми точно побачимо, наскільки близько дійде еволюція. Генетичний алгоритм, утім, корисний переважно там, де такого точного методу немає.

Динамічне програмування заповнює таблицю T[i][c] — найкращу користь, якої можна досягти лише з перших i речей, коли вони можуть важити щонайбільше c. Кожну клітинку обчислюють із рядка над нею:

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

T[i][c]

найкраща користь із перших i речей за вантажності c; клітинка T[n][W] — відповідь на всю задачу

T[i − 1][c]

варіант «i-ту річ не беру» — тоді найкраще те, що можна було скласти з попередніх речей за тієї самої вантажності

T[i − 1][c − w_i]

варіант «беру» — річ займає w_i, тож на решту лишається тільки c − w_i; найкраще використання залишку вже є в таблиці (дозволено лише для c ≥ w_i)

u_i

користь речі, яку ми в другому варіанті доклали

Приклад — таблиця для чотирьох речей і вантажності 50 даг

Налобний ліхтарик (10 даг, 25 балів), ніж (10 даг, 18), пальник (40 даг, 30) і каремат (50 даг, 45). Усі маси кратні десяти, тож вистачить стовпців із кроком 10 даг:

речі	c = 0	10	20	30	40	50
жодної	0	0	0	0	0	0
+ ліхтарик	0	25	25	25	25	25
+ ніж	0	25	43	43	43	43
+ пальник	0	25	43	43	43	55
+ каремат	0	25	43	43	43	55

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

Пальник, c = 40: max(T[2][40], T[2][0] + 30) = max(43, 0 + 30) = 43 — пальник не вигідний

Пальник, c = 50: max(T[2][50], T[2][10] + 30) = max(43, 25 + 30) = 55 — пальник і ліхтарик

Каремат, c = 50: max(55, T[3][0] + 45) = max(55, 45) = 55

Жадібна стратегія брала б речі за користю на декаграм: ліхтарик (2,5 бала/даг), ніж (1,8), а тоді ні каремат (0,9), ні пальник (0,75) у решту 30 даг уже не влізли б — лише 43 бали. У великій задачі з 24 речами жадібна стратегія зупиняється на 702 балах: заповнює рюкзак дрібницями, і на намет (220 даг) місця вже не лишається.

def batoh(w, u, W):                       # w, u: маси й цінності, W: вантажність
    T = [0] * (W + 1)                     # рядок для «жодної речі»
    for i in range(len(w)):
        for c in range(W, w[i] - 1, -1):  # з кінця: T[c − w[i]] ще з рядка i − 1
            T[c] = max(T[c], T[c - w[i]] + u[i])
    return T[W]                           # n · W кроків: 24 · 1000 = 24 000

2. Особина, геном і пристосованість

Означення — геном, популяція, пристосованість

Геном (хромосома) — це закодований розв’язок; тут рядок x ∈ {0, 1}²⁴, один біт (ген) на річ. Популяція — мультимножина P геномів сталого розміру μ.

Пристосованість (fitness) — функція F : {0, 1}ⁿ → ℝ, яку алгоритм максимізує. Для рюкзака

F(x) = ∑ u_ix_i, коли рюкзак уміщується, інакше ∑ u_ix_i − 3 · (∑ w_ix_i − W).

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

F(x)

пристосованість рюкзака x — єдине число, за яким добір порівнює особин

∑ u_ix_i

користь запакованих речей (x_i = 1 річ зараховує, 0 пропускає) — те, що ми справді хочемо максимізувати

3

ціна одного декаграма понад ліміт — вона більша за найкраще співвідношення користі й маси (ліхтарик, 2,5 бала/даг), тож докласти будь-що до вже перевантаженого рюкзака завжди знизить пристосованість

max(0, ∑ w_ix_i − W)

перевантаження в декаграмах; max із нулем гарантує, що рюкзак, який уміщується, штрафу не отримає, а легший рюкзак не матиме переваги

Приклад — пристосованість двох рюкзаків

Оптимум: користь 727, маса 990 даг ≤ 1 000  ⇒  F = 727 − 3 · 0 = 727

Оптимум + фотоапарат (80 даг, 20 балів): користь 747, маса 1 070 даг  ⇒  F = 747 − 3 · 70 = 537

Фотоапарат додає 20 балів, але перевантаження на 70 даг коштує 210 — добір такий рюкзак надійно відсуне.

3. Добір

Означення — турнірний і рулетковий добір

Турнірний добір розміру k: вибери з популяції навмання k особин і поверни ту, що має найвищу пристосованість.

Рулетковий добір: вибери особину x з імовірністю F(x) / ∑_{y ∈ P} F(y) (потребує додатної пристосованості).

Тиск добору — міра того, наскільки сильно добір надає перевагу пристосованішим особинам; у турніру він росте з k.

Наскільки сильний турнір, можна обчислити точно. Наша програма витягає k особин із поверненням (та сама особина може потрапити в турнір двічі). Упорядкуймо популяцію від найкращої (i = 1) до найгіршої (i = μ):

P(виграє i-та) = ( (μ − i + 1)^k − (μ − i)^k ) / μ^k

P(виграє i-та)

шанс, що батьком стане саме i-та найкраща особина

(μ − i + 1)^k

кількість турнірів, у яких ніхто не кращий за i-ту — усі k витягувань падають на неї або гірших

(μ − i)^k

від них віднімаємо турніри, у яких i-тої взагалі немає, — їх виграв би хтось гірший; різниця — це турніри, де i-та найкраща з присутніх

μ^k

кількість усіх можливих турнірів (k витягувань, кожне з μ особин) — поділивши, отримаємо ймовірність

Приклад — турнір із трьох серед 40 рюкзаків

μ^k = 40³ = 64 000. За покоління вибирають 38 батьків (два місця займають елітні особини):

найкраща: (40³ − 39³) / 64 000 = (64 000 − 59 319) / 64 000 ≈ 7,31 %,   очікувано 38 · 0,0731 ≈ 2,78 вибору

20-та найкраща: (21³ − 20³) / 64 000 = (9 261 − 8 000) / 64 000 ≈ 1,97 %,   очікувано ≈ 0,75 вибору

найгірша: (1³ − 0³) / 64 000 ≈ 0,0016 %,   очікувано ≈ 0,0006 вибору

Пересічна особина отримує 38/40 = 0,95 вибору, найкраща — майже втричі більше. Загалом для великої популяції найкращій випадає приблизно в k разів більше, ніж пересічній, — тому тиск добору росте з k.

4. Схрещування і мутація

Означення — одноточкове схрещування

Для батьків a, b ∈ {0, 1}ⁿ вибери навмання точку c ∈ {1, …, n − 1}. Нащадки —

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

Схрещування виконують з імовірністю p_c, інакше нащадки — копії батьків. Інші варіанти — двоточкове та рівномірне схрещування (кожен ген від випадкового з батьків).

Означення — бітова мутація

Кожен ген нащадка незалежно перевертається (0 ↔ 1) з імовірністю p_m, зазвичай p_m = 1/n — у середньому один ген на особину.

Приклад — скільки генів перевертає мутація

Кількість перевернутих генів має біноміальний розподіл: P(j генів) = C(n, j) · p_m^j · (1 − p_m)^n−j. Для n = 24 і p_m = 1/24:

очікувана кількість: n · p_m = 24 · 1/24 = 1

жодної зміни: (23/24)²⁴ ≈ 0,360   (для великих n наближається до 1/e ≈ 0,368)

рівно один ген: 24 · (1/24) · (23/24)²³ ≈ 0,376

Отже, приблизно третина нащадків лишається без змін, третина відрізняється одним геном, а решта — двома й більше.

Батьки — два найкращі рюкзаки з початкової популяції (423 і 398 балів), розріз — за дванадцятою річчю. Жоден із нащадків не кращий за кращого з батьків — вони мають 403 і 418 балів. Схрещування покращення не гарантує; воно лише пропонує нові комбінації, а добір потім вирішить, які виживуть. Мутація в першого нащадка доклала фільтр для води (15 даг, 32 бали), і він одразу має 435 балів — більше, ніж обоє батьків.

Приклад — перерахунок схрещування з рисунка

Користь додається по генах, тож досить окремо додати користь початку (речі 1–12) і кінця (речі 13–24):

батько 1: 310 + 113 = 423,   батько 2: 305 + 93 = 398

нащадок 1 = початок батька 1 + кінець батька 2: 310 + 93 = 403

нащадок 2 = початок батька 2 + кінець батька 1: 305 + 113 = 418

мутація докладає фільтр для води: 403 + 32 = 435

Батько 1 кращий в обох половинах (310 > 305 і 113 > 93), тож за такого розрізу його не може перевершити жоден нащадок — схрещуванню нема з чого скласти кращого цілого. Покращення принесла лише мутація.

5. Увесь алгоритм

Алгоритм — генетичний алгоритм

1. Створи випадкову початкову популяцію з μ особин і оціни їх.
2. Скопіюй у нове покоління e найкращих особин без змін (елітизм).
3. Поки нове покоління не має μ особин: вибери двох батьків, з імовірністю p_c схрести їх, нащадків мутуй і додай.
4. Оціни нове покоління й переходь до кроку 2, поки не вичерпається кількість поколінь.

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]]            # елітизм
        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 витягувань із поверненням

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

Вартість алгоритму вимірюємо кількістю оцінок пристосованості — у справжніх задачах (симуляції, вимірювання) це найдорожчий крок. Оцінюють початкову популяцію, а потім кожне покоління: μ + G · μ = 40 + 60 · 40 = 2 440 оцінок для μ = 40 особин і G = 60 поколінь. Елітні особини оцінюються знову, хоч і не змінилися; кмітливіша програма запам’ятовувала б їхню пристосованість.

6. Еволюція рюкзака

Запустімо алгоритм: 40 рюкзаків, 60 поколінь, турнір із трьох, схрещування з імовірністю 0,9, мутація 1/24 і дві елітні особини. Рисунок показує популяцію в поколіннях 0, 5, 15, 30 і 60 — кожен рядок — один рюкзак, кожен стовпець — одна річ, угорі для порівняння оптимум:

Спочатку популяція строката, а рюкзаки радше напівпорожні: кожна річ потрапила до них з імовірністю 0,3, тож вони важать близько чотирьох кілограмів (очікувана маса — 0,3 · ∑ w_i = 0,3 · 12,75 кг ≈ 3,8 кг). Найкращий має 423 бали, середнє — 231. Через п’ять поколінь намет несуть 36 із 40 рюкзаків, пляшку з водою — 35, а найкращий рюкзак має 634 бали. Близько п’ятнадцятого покоління популяція впирається у вантажність — 12 рюкзаків перевантажені — і починає вчитися, чим пожертвувати: зайва їжа й сандалі майже зникли, але фотоапарат поки що несуть 39 рюкзаків. Оптимум, 727 балів, алгоритм уперше знаходить у поколінні 26; у поколінні 30 фотоапарат лишився вже тільки в одному рюкзаку. Проте популяція ніколи не зливається в один розв’язок — мутація постійно пробує дрібні відхилення.

Алгоритм для цього оцінив 2 440 рюкзаків — неповні дві соті відсотка з усіх 16 777 216 можливостей. Випадковий пошук із тією самою кількістю спроб у ста повтореннях не знайшов оптимуму жодного разу й у середньому зупинився на 574 балах.

Приклад — чому випадковий пошук не знайде оптимуму

Випадковий рюкзак бере кожну річ незалежно з імовірністю 0,3. Оптимум містить 19 речей і 5 пропускає, тож

P(випадковий рюкзак = оптимум) = 0,3¹⁹ · 0,7⁵ ≈ 1,16 · 10⁻¹⁰ · 0,168 ≈ 1,95 · 10⁻¹¹

очікувана кількість влучань у 2 440 спробах: 2 440 · 1,95 · 10⁻¹¹ ≈ 4,8 · 10⁻⁸

Навіть якби витягали рівномірно (кожну річ з імовірністю 1/2), шанс був би один до 16 777 216 на спробу. Генетичний алгоритм не витягає оптимум одразу — він складає його шматочок за шматочком із рюкзаків, які вже добрі.

7. Навіщо схрещування і навіщо мутація

Помаранчева лінія на графіку — той самий запуск із вимкненою мутацією. Через одинадцять поколінь вона застрягає на 573 балах і більше не рухається. Чому, покаже порівняння ста запусків із різними зернами:

Без мутації популяція втрачає розмаїття: коли гена немає в жодній особині, схрещування його не створить, а добір до того ж швидко витісняє все, крім найкращих. Це називають передчасною збіжністю. Без схрещування алгоритм працює — по суті це популяція альпіністів із добором, — але повільніше. Схрещування допомагає складати разом добрі шматки, що виникли в різних особинах.

Теорема — теорема Голланда про схеми

Схема H — це шаблон над {0, 1, ∗}, де ∗ означає «будь-що»; її порядок o(H) — кількість фіксованих позицій, а довжина δ(H) — відстань між першою та останньою фіксованою позицією. Для m(H, t) особин, що відповідають H у поколінні t, і рулеткового добору виконується

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

де F(H) — середня пристосованість особин зі схеми, а F̄ — середнє популяції.

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

m(H, t)

скільки особин несе будівельний блок зараз — наступне покоління виходить із них, тому на це множать

F(H) / F̄

наскільки носії схеми пристосованіші за середнє — рулетка дає їм пропорційно більше нащадків; понад 1 схема розмножується, нижче 1 вимирає

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

шанс, що схрещування розріже схему: схрещування відбувається з p_c, а точка розрізу з імовірністю δ/(n − 1) падає між фіксовані позиції — тому шкодять довгі схеми

o(H) · p_m

шанс (оцінка згори), що мутація переверне якусь з o(H) фіксованих позицій — тому шкодять схеми високого порядку

Приклад — коротка й довга схема на рюкзаку

Квадратна дужка для налаштувань нашого запуску (p_c = 0,9, n = 24, p_m = 1/24). Обидві схеми мають порядок 2:

«намет і спальник» (гени 1 і 2, δ = 1): 1 − 0,9 · 1/23 − 2/24 ≈ 1 − 0,039 − 0,083 = 0,878

«намет і запасні шкарпетки» (гени 1 і 24, δ = 23): 1 − 0,9 · 23/23 − 2/24 ≈ 1 − 0,9 − 0,083 = 0,017

Короткій схемі досить, щоб її носії були на 14 % пристосованіші за середнє (1/0,878 ≈ 1,14), і за теоремою вона вже поширюється. Довга схема мала б бути вшістдесятеро пристосованішою — теорема про неї по суті нічого не обіцяє. Наш алгоритм використовує турнір, а не рулетку, тож для нього справджується лише квадратна дужка; перші два множники обчислювалися б інакше.

8. Генетичні алгоритми на практиці

• Проєктування форм. Антену супутників NASA ST5 (запущених 2006 року) спроєктував еволюційний алгоритм: дивно покручений дротик, який інженерові не спав би на думку, але виконав вимоги щонайменше так само добре, як антена, спроєктована вручну (у пізніших дослідах навіть краще).
• Розклади й логістика. Розклади, графіки змін чи планування складу — задачі з багатьма умовами, де пристосованість можна обчислити, але точний алгоритм працював би вічність.
• Машинне навчання. Еволюція налаштовує гіперпараметри моделей, а в нейроеволюції, якій програма курсу присвячує окрему частину, — і ваги та архітектури нейронних мереж.
• Еволюція з мовними моделями. Системи на кшталт FunSearch (2023) і AlphaEvolve (2025) від Google DeepMind підтримують популяцію програм і як мутацію використовують мовну модель, яка програму змінює. Добір забезпечує автоматичне оцінювання. Так вдалося знайти нові математичні конструкції та швидші алгоритми.

9. Підсумок

• Генетичний алгоритм покращує цілу популяцію розв’язків: добором пристосованих, схрещуванням і мутацією.
• Пристосованість — єдине, що йому треба знати про задачу; порушення умов можна розв’язати штрафом.
• Турнірний добір тримає тиск добору, елітизм не дає втратити найкращий розв’язок.
• На рюкзаку з 16,7 мільйона можливостей він знайшов оптимум у 88 зі 100 запусків, оцінивши 2 440 рюкзаків; випадковий пошук із тим самим бюджетом — жодного разу.
• Мутація постачає розмаїття — без неї популяція передчасно збігається. Схрещування складає добрі будівельні блоки й пришвидшує еволюцію.

Хочете спробувати самі? Попросіть ШІ-агента написати генетичний алгоритм для вашого власного рюкзака для походу — а потім спробуйте вимкнути мутацію, збільшити турнір або зменшити популяцію і стежте, що станеться з розмаїттям.

Маєте іншу думку? Напишіть на support@coden-app.com.