Калькулятор генетичних алгоритмів

Генетичні алгоритми (ГА) — це метаевристичні алгоритми оптимізації, натхненні механізмами природної еволюції: відбором, схрещуванням та мутацією. Вони працюють з популяцією потенційних рішень, які еволюціонують з покоління в покоління, поступово наближаючись до оптимуму. Концепція була запропонована Джоном Холландом у 1960-х роках та популяризована Девідом Голдбергом. Генетичні алгоритми ефективні для задач, де простір пошуку великий, складний або погано вивчений, і де класичні методи оптимізації неефективні.

Інтерактивний симулятор генетичного алгоритму

Параметри оптимізації функції

Параметри генетичного алгоритму

Результати еволюції:

Покоління: 0

Найкращий фітнес: -

Середній фітнес: -

Найкраще рішення: -

Теорія генетичних алгоритмів

Біологічна аналогія

Біологія → Генетичний алгоритм ───────────────────────────────────────────── Популяція організмів → Набір потенційних рішень Хромосома → Кодування рішення (рядок) Ген → Елемент кодування Алель → Значення гена Генотип → Закодоване рішення Фенотип → Декодоване рішення Пристосованість → Значення цільової функції (фітнес) Природний відбір → Селекція кращих особин Схрещування → Кросовер (обмін генами) Мутація → Випадкова зміна генів Покоління → Ітерація алгоритму

Загальна схема ГА

ГЕНЕТИЧНИЙ АЛГОРИТМ: 1. ІНІЦІАЛІЗАЦІЯ Створити початкову популяцію P(0) з N випадкових особин 2. ОЦІНКА Обчислити фітнес f(x) для кожної особини x ∈ P(t) 3. ЦИКЛ (поки не виконано критерій зупинки): 3.1. СЕЛЕКЦІЯ Вибрати батьківські пари на основі фітнесу 3.2. КРОСОВЕР Схрестити батьків з ймовірністю p_c Створити нащадків 3.3. МУТАЦІЯ Мутувати нащадків з ймовірністю p_m 3.4. ОЦІНКА Обчислити фітнес нащадків 3.5. ЗАМІНА Сформувати нову популяцію P(t+1) 4. РЕЗУЛЬТАТ Повернути найкращу знайдену особину

Кодування рішень

  • Двійкове: Класичне кодування рядками {0,1}. Підходить для дискретних задач.
  • Цілочисельне: Гени — цілі числа. Зручне для перестановок та індексів.
  • Дійсне (речове): Гени — дійсні числа. Природне для неперервної оптимізації.
  • Перестановочне: Хромосома — перестановка чисел. Для задач упорядкування (TSP).
  • Деревоподібне: Гени — вузли дерева. Для генетичного програмування.

Генетичні оператори

Кросовер (схрещування)

Одноточковий кросовер

Батько 1: [A B C | D E F] Точка розрізу Батько 2: [1 2 3 | 4 5 6] ───────────────── Нащадок 1: [A B C | 4 5 6] Нащадок 2: [1 2 3 | D E F]

Двоточковий кросовер

Батько 1: [A B | C D E | F G] Батько 2: [1 2 | 3 4 5 | 6 7] ───────────────────── Нащадок 1: [A B | 3 4 5 | F G] Нащадок 2: [1 2 | C D E | 6 7]

Рівномірний кросовер

Маска: [1 0 1 0 1 1 0] Батько 1: [A B C D E F G] Батько 2: [1 2 3 4 5 6 7] ───────────────── Нащадок: [A 2 C 4 E F 7] (1→від батька 1, 0→від батька 2)

Кросовер для перестановок (OX — Order Crossover)

Батько 1: [1 2 3 | 4 5 6 | 7 8 9] Батько 2: [9 3 7 | 8 2 6 | 5 1 4] ↓ 1. Копіюємо середню частину від Батька 1: [_ _ _ | 4 5 6 | _ _ _] 2. Заповнюємо решту з Батька 2 (по порядку, без повторів): Послідовність з P2: 5,1,4,9,3,7,8,2,6 → без 4,5,6: 1,9,3,7,8,2 Нащадок: [3 7 8 | 4 5 6 | 2 1 9]

Мутація

Для двійкового/цілочисельного кодування

Бітова мутація (Bit Flip): До: [0 1 0 1 1 0 1] ↓ (мутація) Після: [0 1 1 1 1 0 1]

Для дійсного кодування

Гаусівська мутація: x' = x + N(0, σ) де σ — стандартне відхилення (контролює силу мутації) Рівномірна мутація: x' = x + U(-δ, δ) Креп-мутація: x' = x ± ε (малий зсув)

Для перестановок

Обмін (Swap): До: [1 2 3 4 5 6] ↕ Після: [1 5 3 4 2 6] Вставка (Insert): До: [1 2 3 4 5 6] → виймаємо 3 Після: [1 2 4 5 3 6] → вставляємо після 5 Інверсія (Inversion): До: [1 2 3 4 5 6] ←─────→ Після: [1 5 4 3 2 6] → реверс підпослідовності Скремблювання (Scramble): До: [1 2 3 4 5 6] [─────] Після: [1 4 2 5 3 6] → випадкова перестановка підпослідовності

Методи селекції

Рулетка (Roulette Wheel Selection)

Ймовірність вибору особини i: p_i = f_i / Σf_j де f_i — фітнес особини i Приклад: Особини: A B C D Фітнес: 10 20 30 40 (сума = 100) Ймов.: 10% 20% 30% 40% Проблеми: • Чутлива до масштабу фітнесу • Домінування супер-особин на початку • Слабкий тиск відбору в кінці

Турнірна селекція (Tournament Selection)

Алгоритм: 1. Випадково вибрати k особин (розмір турніру) 2. Повернути найкращу з них Переваги: • Простота реалізації • Легко контролювати тиск відбору через k • Не потребує масштабування фітнесу • Добре паралелізується Типові значення k: 2-7 k=2: слабкий тиск (більше різноманітності) k=N: сильний тиск (швидша збіжність, ризик передчасної)

Рангова селекція (Rank Selection)

Алгоритм: 1. Відсортувати популяцію за фітнесом 2. Присвоїти ранги: 1 (найгірший) ... N (найкращий) 3. Ймовірність вибору пропорційна рангу Лінійне ранжування: p_i = (2 - s)/N + 2*r_i*(s - 1)/(N*(N - 1)) де s ∈ [1, 2] — тиск відбору, r_i — ранг особини i Переваги: • Постійний тиск відбору • Не залежить від масштабу фітнесу

Елітизм

Ідея: зберігати найкращі особини без змін Алгоритм: 1. Скопіювати k найкращих особин в нове покоління 2. Решту місць заповнити нащадками Типове k: 1-2 особини (1-4% популяції) Переваги: • Гарантує монотонне покращення найкращого рішення • Зберігає цінний генетичний матеріал Недоліки: • Може сприяти передчасній збіжності

Теорема про схеми

Схема (Schema)

Схема — шаблон рядка з символом "не важливо" (*) Приклад для двійкового алфавіту: H = 1**01* Відповідають: 100010, 100011, 110010, 110011, ... Характеристики схеми H: • Порядок o(H) — кількість фіксованих позицій o(1**01*) = 3 • Визначальна довжина δ(H) — відстань між крайніми фікс. позиціями δ(1**01*) = 5 - 1 = 4 • Фітнес f(H) — середній фітнес особин, що відповідають H

Теорема (Holland, 1975)

Нехай m(H, t) — кількість особин зі схемою H у поколінні t. Очікувана кількість у наступному поколінні: E[m(H, t+1)] ≥ m(H, t) × [f(H)/f̄] × [1 - p_c × δ(H)/(L-1)] × [1 - o(H) × p_m] де: • f̄ — середній фітнес популяції • p_c — ймовірність кросоверу • p_m — ймовірність мутації • L — довжина хромосоми Висновок: схеми з високим фітнесом, малим порядком та малою визначальною довжиною ("building blocks") експоненційно зростають у популяції. Це пояснює, чому ГА працюють: вони неявно паралельно досліджують величезну кількість схем.

Застосування генетичних алгоритмів

1. Оптимізація

  • Комбінаторна оптимізація: TSP, планування, розміщення
  • Неперервна оптимізація: налаштування параметрів, конструювання
  • Багатоцільова оптимізація: NSGA-II, SPEA2 для Парето-оптимізації
  • Обмежена оптимізація: штрафні функції, спеціальні оператори

2. Машинне навчання

  • Вибір ознак: оптимальний набір атрибутів для моделі
  • Налаштування гіперпараметрів: оптимізація архітектури мережі
  • Нейроеволюція: еволюція ваг та топології нейромереж (NEAT)
  • Правила класифікації: еволюція if-then правил

3. Інженерія та дизайн

  • Оптимізація форми конструкцій
  • Дизайн антен та електронних схем
  • Аеродинамічна оптимізація
  • Проектування ліків та молекул

4. Планування та розклад

Задачі планування: • Job-shop scheduling — розклад робіт на верстатах • Project scheduling — управління проектами • Timetabling — розклад занять, іспитів • Vehicle routing — маршрутизація транспорту Кодування: • Перестановочне (порядок операцій) • Пріоритетне (пріоритети задач) • Часове (моменти початку)

5. Ігри та штучний інтелект

  • Еволюція стратегій гри
  • Процедурна генерація контенту (рівні, персонажі)
  • Налаштування балансу гри
  • Еволюція поведінки агентів

Варіанти та розширення

Еволюційні стратегії (ES)

(μ, λ)-ES та (μ + λ)-ES Особливості: • Дійсне кодування • Самоадаптація параметрів мутації • Мутація важливіша за кросовер • Детерміністична селекція (μ найкращих) (μ, λ): батьки не переходять у наступне покоління (μ + λ): батьки конкурують з нащадками CMA-ES (Covariance Matrix Adaptation ES): Адаптація коваріаційної матриці — один з найпотужніших методів для неперервної оптимізації

Диференціальна еволюція (DE)

Мутація на основі різниць: v_i = x_r1 + F × (x_r2 - x_r3) де r1, r2, r3 — випадкові різні індекси F ∈ [0, 2] — коефіцієнт масштабування Біноміальний кросовер з цільовим вектором x_i Переваги: • Простота (мало параметрів) • Ефективність для неперервної оптимізації • Самоадаптивні варіанти (jDE, SHADE)

Генетичне програмування (GP)

Еволюція програм (дерев виразів) Хромосома — синтаксичне дерево: + / \ * sin / \ \ x y x Кросовер: обмін піддеревами Мутація: заміна піддерева новим випадковим Застосування: • Символьна регресія • Автоматичний синтез програм • Еволюція правил та стратегій

Острівна модель (Island Model)

Паралельний ГА з міграцією: ┌─────────┐ міграція ┌─────────┐ │ Острів 1│ ←─────────→ │ Острів 2│ └─────────┘ └─────────┘ ↕ ↕ ┌─────────┐ ┌─────────┐ │ Острів 3│ ←─────────→ │ Острів 4│ └─────────┘ └─────────┘ Переваги: • Збереження різноманітності • Природний паралелізм • Різні параметри на різних островах

Реальні застосування ГА

1. Інженерне проектування

Оптимізація крила літака: • Геном: параметри профілю (товщина, кривизна, кут атаки) • Фітнес: піднімальна сила / опір (CFD симуляція) • Результат: 10-15% покращення аеродинаміки Конструкції антен: • NASA ST5 satellite (2006) • Еволюційно знайдені антени перевершили ручний дизайн • Унікальні форми, які б людина не придумала Оптимізація турбін: • General Electric — профілі лопатей • Rolls-Royce — охолодження турбін

2. Машинне навчання

Нейроеволюція (Neuroevolution): • NEAT (NeuroEvolution of Augmenting Topologies) - Еволюція структури + ваг нейромережі - Speciation для захисту інновацій • HyperNEAT - Непряме кодування через CPPN - Масштабування на великі мережі • OpenAI Evolution Strategies (2017) - Альтернатива backpropagation - Паралелізується на тисячі CPU Підбір гіперпараметрів: • Random Forest: кількість дерев, глибина, features • SVM: C, gamma, kernel • Neural networks: learning rate, architecture

3. Біоінформатика

Вирівнювання послідовностей: • Множинне вирівнювання (MSA) • NP-складна задача • ГА знаходять якісні наближення Фолдинг білків: • Rosetta@home використовує еволюційні підходи • Передбачення третинної структури • AlphaFold обігнав традиційні методи (2020) Дизайн ліків: • Оптимізація молекулярних структур • Фітнес: зв'язування з мішенню, токсичність • De novo drug design

4. Планування та розклади

Job Shop Scheduling: • n робіт × m машин • Мінімізація makespan • ГА з PMX кросовером Розклад занять: • Університетський розклад • Обмеження: час, аудиторії, викладачі • Constraint handling через штрафи Логістика: • Vehicle Routing Problem (VRP) • Маршрутизація доставки Amazon, UPS • Економія 10-20% на пальному

5. Фінанси

Торгові стратегії: • Геном: параметри індикаторів, правила входу/виходу • Фітнес: Sharpe ratio, прибутковість, просадка • Важливо: out-of-sample тестування! Оптимізація портфеля: • Маркович + обмеження • Multi-objective: прибуток vs ризик • Pareto-фронт ефективних портфелів Ризик-менеджмент: • Stress testing • Scenario generation

Багатоцільова оптимізація (MOO)

Pareto-оптимальність

Задача: min f₁(x), min f₂(x), ..., min fₖ(x) Домінування: x ≻ y якщо • ∀i: fᵢ(x) ≤ fᵢ(y) • ∃j: fⱼ(x) < fⱼ(y) Pareto-фронт: множина недомінованих рішень Немає єдиного "найкращого" — компроміси Приклад (автомобіль): f₁ = витрата пального f₂ = -прискорення f₃ = ціна Pareto-фронт: спортивні ↔ економічні ↔ бюджетні

NSGA-II алгоритм

Non-dominated Sorting Genetic Algorithm II (Deb, 2002) 1. Швидке недоміноване сортування O(MN²) - Розбиття популяції на фронти F₁, F₂, ... 2. Crowding distance - Оцінка "самотності" в просторі цілей - Збереження різноманітності на фронті 3. Турнірна селекція - Спочатку за рангом фронту - При рівності — за crowding distance 4. Елітизм - Об'єднання батьків та нащадків - Вибір кращих N особин

Інші MOO алгоритми

  • NSGA-III — reference points для many-objective
  • MOEA/D — декомпозиція на скалярні підзадачі
  • SPEA2 — strength Pareto evolutionary algorithm
  • SMS-EMOA — hypervolume-based selection

Налаштування параметрів

Типові діапазони

Розмір популяції: • Прості задачі: 30-50 • Середні: 100-200 • Складні / великий геном: 500-1000 Ймовірність кросовера: 0.6-0.9 • Вища → більше exploration • Нижча → exploitation Ймовірність мутації: 1/L до 1/√L (L = довжина генома) • Занадто низька → передчасна збіжність • Занадто висока → випадковий пошук Кількість поколінь: • Залежить від складності • Критерій зупинки: стагнація фітнесу

Адаптивні параметри

Self-adaptive mutation: Геном включає σ (крок мутації) σ' = σ × exp(τ × N(0,1)) x' = x + σ' × N(0,1) Parameter control strategies: 1. Deterministic — за розкладом 2. Adaptive — на основі feedback (успішність) 3. Self-adaptive — еволюціонують разом з рішенням Приклад adaptive: • 1/5 правило: якщо <20% мутацій успішні → зменшити σ • Якщо >20% успішних → збільшити σ

Уникнення передчасної збіжності

Проблема: популяція сходиться до локального оптимуму Рішення: 1. Fitness sharing — штраф за схожість f'(i) = f(i) / Σⱼ sh(d(i,j)) 2. Crowding — заміна схожого, а не найгіршого 3. Островна модель — ізольовані субпопуляції 4. Random immigrants — випадкові особини кожне покоління 5. Hypermutation — періодичне збільшення мутації 6. Restart — перезапуск зі збереженням найкращого

Benchmark функції

Одномодальні

Sphere: f(x) = Σ xᵢ² • Глобальний мінімум: f(0) = 0 • Найпростіша тестова функція Rosenbrock (banana): f(x,y) = (1-x)² + 100(y-x²)² • Глобальний мінімум: f(1,1) = 0 • Довга вузька долина — складно для ГА

Багатомодальні

Rastrigin: f(x) = 10n + Σ[xᵢ² - 10cos(2πxᵢ)] • Багато локальних мінімумів • Глобальний мінімум: f(0) = 0 Ackley: f(x) = -20exp(-0.2√(Σxᵢ²/n)) - exp(Σcos(2πxᵢ)/n) + 20 + e • Майже плоска зовнішня область • Глобальний мінімум: f(0) = 0 Schwefel: f(x) = 418.9829n - Σ xᵢsin(√|xᵢ|) • Глобальний мінімум далеко від локальних • f(420.97) = 0 Griewank: f(x) = Σxᵢ²/4000 - Πcos(xᵢ/√i) + 1 • Багато регулярних локальних мінімумів

Інструменти та бібліотеки

Python

  • DEAP — Distributed Evolutionary Algorithms in Python
  • PyGAD — простий ГА з підтримкою Keras
  • pymoo — multi-objective optimization
  • inspyred — EC framework
  • LEAP — lightweight EC library

Інші мови

  • ECJ (Java) — потужний EC framework
  • JMetal (Java) — multi-objective
  • ParadisEO (C++) — паралельні метаевристики
  • Jenetics (Java) — сучасний ГА

Книги

  • "Introduction to Evolutionary Computing" — Eiben & Smith
  • "Genetic Algorithms in Search, Optimization & Machine Learning" — Goldberg
  • "How to Solve It: Modern Heuristics" — Michalewicz & Fogel
  • "Multi-Objective Optimization using Evolutionary Algorithms" — Deb

Практичне значення та контекст

Коротка довідка

Методи математичного аналізу були незалежно розроблені Ньютоном (1665–1666) та Лейбніцем (1684). У XIX ст. Коші та Вейєрштрасс заклали суворі основи теорії границь.

Де застосовується

Математичний аналіз застосовується у кожній точній науці. У фізиці похідні описують швидкість і прискорення та рівняння руху. В інженерії інтеграли використовуються для розрахунку напружень і теплових потоків. В економіці диференціальне числення дозволяє знаходити граничні витрати та прибутки. У комп'ютерних науках градієнтний спуск (похідні) є основою навчання нейронних мереж.

Часті запитання (FAQ)

Навіщо вивчати цю тему?
Ця тема є основою математичної освіти і широко застосовується в природничих науках, інженерії, економіці та комп'ютерних науках. Розуміння базових понять допомагає краще орієнтуватися у складніших розділах математики та ефективно вирішувати реальні задачі.
З чого почати вивчення теми?
Починайте з основних визначень і теорем, наведених на цій сторінці. Опрацюйте приклади розв'язання задач покроково, потім спробуйте самостійно вирішити кілька вправ. Наш калькулятор допоможе перевірити правильність відповідей.
Що таке алгоритмічна складність?
Алгоритмічна складність описує, як зростає час виконання або обсяг пам'яті алгоритму залежно від розміру вхідних даних. Позначається нотацією O(n): O(1) — константний час, O(n) — лінійний, O(n²) — квадратичний, O(log n) — логарифмічний. Для великих даних різниця критична: O(n²) при n=10⁶ потребує 10¹² операцій проти O(n log n) ≈ 2×10⁷.
Де застосовуються методи теорії графів?
Теорія графів застосовується у маршрутизації мережі (алгоритм Дейкстри), соціальних мережах (аналіз зв'язків), плануванні (задача комівояжера), компіляторах (аналіз залежностей), базах даних (реляційні моделі), а також у біоінформатиці для аналізу молекулярних структур.
Як користуватися цим калькулятором?
Введіть необхідні значення у відповідні поля та натисніть кнопку обчислення. Результат відобразиться одразу. Калькулятор підтримує десяткові числа та від'ємні значення — для введення від'ємного числа використовуйте знак мінус. Усі розрахунки виконуються онлайн без встановлення додаткового програмного забезпечення.

📁 Категорія: IT