„виживає не найсильніший і не найрозумніший, а той, хто краще за всіх пристосовується до змін.”чарльз дарвін

” навіть якщо у одного з тисячі з’явиться інтерес до цих алгоритмів, і він вирішить заглибитися — це вже відмінно.”

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

# що це?

Генетичний алгоритм (га) – це алгоритм пошуку та оптимізації, прообразом якого став біологічний принцип природного відбору.

# як він працює?

перший етап-створення популяції. в даному випадку популяція – це не сукупність біологічних особин, а безліч можливих рішень наявної проблеми, які утворюють простір пошуку (space search).

другий етап-підрахунок функції придатності (пристосованості, fitness function). ця функція приймає на введенні потенційне рішення проблеми (candidate solution), а видає значення, що оцінює його придатність. У випадку з класичним генетичним алгоритмом цільова функція і функція придатності-це одне і те ж. Далі перевіримо, чи виконано умова зупинки алгоритму. Алгоритм припинить виконуватися, якщо досягнуто очікуване оптимальне значення, якщо отримане значення більше не покращується або після закінчення заданого часу / кількості ітерацій. Після зупинки відбувається вибір самої пристосованої хромосоми (за найбільшим значенням функції). Якщо ж умова зупинки не виконана, то за результатами природного відбору буде проводитися селекція хромосом для виробництва нащадків.

третій етап — схрещування ( в російських джерелах – «кросинговер», рідше «кросовер») і мутація.

Блок-схема генетичного алгоритму

схрещування, мутація та селекція – це генетичні оператори. Як і в природі, ймовірність схрещування на кілька порядків вище ймовірності мутації. Схрещування підтримує нескінченну різноманітність в популяції, це перерозподіл генетичного матеріалу батьків, завдяки якому у нащадків з’являються нові поєднання генів. Але про які “генах” і “хромосомах” може йти мова поза контекстом живої природи? у генетичному алгоритмі “хромосома « — набір параметрів, що визначають пропоноване можливе рішення, а» ген « – це одна з» букв «рядка» хромосоми”, як правило, має двійкове значення. Як ми пам’ятаємо, в результаті селекції відбираються самі пристосовані хромосоми-до них і застосовуються ці генетичні оператори. Напевно, ви зараз думаєте, яким же чином може відбуватися схрещування у таких «хромосом». Можливо кілька сценаріїв, згадаємо лише деякі з них.

Одноточковий кросинговер (single-point crossover): є пара батьківських хромосом з набором генів l, для них випадковим чином вибирається так звана точка схрещування px – це якась позиція гена в хромосомі. До [1; px] однієї батьківської хромосоми приєднується [px+1; l] інший, і виходить перший нащадок. Другий нащадок виходить також схрещуванням, але «у зворотний бік».

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

Двоточковий кросинговер (two-point crossover): обмін генетичним матеріалом, (тобто, бітами) відбувається в двох точках схрещування.

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

Однорідний кросинговер( uniform crossover): значення кожного біта в хромосомі нащадка визначається згідно випадково згенерованої масці кросинговера. Якщо в масці стоїть 0-береться ген від першого з батьків, якщо 1-від другого.

Однорідний кросинговер

Для більш глибокого занурення в тему еволюційних алгоритмів реокмендуем вивчити статтю f. Herrera, m. Losano, a. M. Sanches hybrid crossover operators for real-coded genetic algorithms: an experimental study.

мутація – генетичний оператор, який з якоюсь ймовірністю змінює один або кілька «генів» у випадкових позиціях «хромосоми». Для чого він потрібен? навіщо мутації (зміни в генетичному коді) існують в природі, чи можуть вони сприяти кращому виживанню виду? ця стаття не про генетику, але не будемо забувати, що саме вона послужила джерелом натхнення для холланда, творця генетичного алгоритму (1975). Нащадки, які зазнали впливу генетичних операторів, утворюють нову популяцію – і в ній починається чергова ітерація га. Знову йде підрахунок функції придатності, відбувається природний відбір, а далі алгоритм або зупиниться, якщо задана умова виконана, або знову перейде до селекції. Якщо хочеться подивитися цікаве застосування, можна почитати розбір завдання комівояжера (travelling salesman problem) і завдання про укладання рюкзака (knapsack problem) із застосуванням га. Обидві ці завдання є завданнями комбінаторної оптимізації, тобто в кінцевому безлічі об’єктів ми шукаємо оптимальний. Самі того не підозрюючи, ми вирішуємо подібні завдання кожен день. Тепер подивимося на переваги і недоліки цього методу.

плюси га

Цей алгоритм має унікальні сильні сторони:

  • пропонує на виборнесколько рішень, а не одне;
  • досліджує відразу кілька точок, а не одну за одною, завдяки чому цільова функція не упреться в локальний екстремум;
  • оптимізація відбувається безупинно мінливих умовах середовища, а популяції доводиться пристосовуватися;
  • може запропонувати задовільне рішення для np-hard проблеми;
  • допускає паралельні обчислення;
  • підходить для вирішення завдань з різними параметрами (головне — задати відповідну функцію придатності).

мінуси га

  • «просто хороше рішення ” – це теж іноді недолік;
  • багато точок в просторі пошуку-це теж іноді недолік;
  • не завжди зручно уявити завдання в термінах генів і хромосом.

⇡# для яких завдань використовується га?

За допомогою га вирішується цілий спектр завдань: від розробки антен nasa до програм розпізнавання структури білків.

У фінансах га успішно використовується для моделювання економічних агентів з обмежено раціональною поведінкою: фінансового прогнозування, інвестування, і т. Д. Одне з цікавих завдань-оптимізація фінансового портфеля (portfolio optimization). У теорії ігор га застосовується, наприклад, для вирішення дилеми в’язня. Його можна застосовувати в іграх з двома учасниками для оптимізації стратегій.

В робототехніці га прекрасно застосовується для управління людиноподібним роботом, оптимізації планування маршруту (routing). В авіації – для системи контролю польотів. До речі про авіацію: вчені general electric і ренсселерівського політехнічного інституту застосували га для конструювання турбіни реактивного двигуна, який застосовується в сучасних авіалайнерах.

Можна використовувати га і в ближчих для нас ситуаціях, наприклад, для планування розкладу на виробництві або у великому навчальному закладі. У першому випадку фітнес-функція може задавати кількість деталей, виготовлених за певну кількість часу, а в другому – «штрафувати» конфліктуючі гілки розкладу. Можливості для творчості просто безмежні.

що далі?

Https://loginom.ru/blog/ga-math

Ще по застосуваннях га англійською мовою:

Нещодавно вийшла привертає увагу книга: buontempo, frances. Genetic algorithms and machine learning for programmers: create ai models and evolve solutions. Pragmatic bookshelf, 2019.

матеріали, які використовувалися для написання цієї статті:

  • джон х. Холланд. Генетичні алгоритми. “у світі науки”, 1992
  • hornby, gregory, et al. “automated antenna design with evolutionary algorithms.” space 2006. 2006. 7242.
  • darrel whitley “a genetic algorithm tutorial”, 1993.
  • f.herrera, m.losano, a.m.sanches. “hybrid crossover operators for real-coded genetic algorithms: an experimental study”.
  • guennoun, z., and f. Hamza. “stocks portfolio optimization using classification and genetic algorithms.” applied mathematical sciences 6.94 (2012):4673-4684.
  • блок-схема: intuit.ru