Розділ 9. Еволюційне моделювання

Кераміка Пуебло (фото надано службою національних парків США)

Протягом століть кераміка, створена представниками предків культур Пуебло і Моголлон на південному заході Сполучених Штатів і Північної Мексики, мала велике значення як у церемоніальному, так і в повсякденному контексті. Техніки та елементи дизайну, подібні до тих, що використовувалися для створення цієї чаші Chaco Ancestral Pueblo, передаються з покоління в покоління і кожен гончар вивчає, зберігає та тонко адаптує ці дизайни. Цей безперервний процес породжує гобелен родинного та культурного самовираження, що постійно розвивається.

---

Подумайте хвилинку про простіші часи, коли ви писали свої перші програми на p5.js і життя було вільним та легким. Яку фундаментальну концепцію програмування ви, ймовірно, використовували в тих перших програмах і продовжуєте використовувати знову і знову до цього дня? Змінні. Змінні дозволяють зберігати дані та повторно використовувати їх під час виконання програми.

Звичайно, в цьому немає нічого нового. У цій книзі ви вийшли далеко за межі програм лише з однією чи двома простими змінними, працюючи над програмами, організованими навколо складніших структур даних: власних об’єктів, які включають як дані, так і функції. Ви використовували ці складні структури даних — класи — для створення власних маленьких світів рухомих частинок, рухомих об’єктів, клітин і дерев. Але тут є заковика: у кожному прикладі в цій книзі вам доводилося турбуватися про ініціалізацію властивостей цих об’єктів. Можливо, ви створили цілий набір частинок із випадковими кольорами й розмірами або масив рухомих об’єктів, які починаються з однієї спільної позиції ($x$, $y$).

Що, якби замість того, щоб діяти як розумний розробник, призначаючи властивості об’єктів шляхом випадкового чи вдумливого міркування, ви могли б дозволити природному процесу еволюції визначити значення замість вас? Чи можна представити змінні JavaScript об’єкта як ДНК об’єкта? Чи можуть об’єкти народжувати інші об’єкти та передавати свою ДНК новому поколінню? Чи може програма p5.js еволюціонувати?

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

Генетичні алгоритми: натхненні реальними подіями

Основним підходом розробки програм, що розвиваються, є генетичні алгоритми (скорочено ГА-ми), які базуються на основних принципах еволюційної теорії Дарвіна. У цих алгоритмах популяції потенційних вирішень проблеми розвиваються протягом поколінь через процеси, які імітують природний відбір у біологічній еволюції. Хоча комп’ютерне моделювання еволюційних процесів датується 1950-ми роками, більша частина нашого сучасного розуміння ГА-мів походить від роботи Джона Холланда, професора Мічиганського університету, чия книга 1975 року “Адаптація в природних і штучних системах” (MIT Press) поклала початок дослідженню ГА-мів. Сьогодні ГА-ми є частиною ширшої галузі, яку часто називають еволюційним моделюванням.

Щоб було зрозуміло, ГА-ми натхненні лише генетикою та еволюційною теорією і не призначені для точного впровадження науки, що стоїть за цими сферами. Досліджуючи ГА-ми у цьому розділі, я не буду будувати квадрати Паннетта (вибачте за розчарування) і не буду обговорювати нуклеотиди, синтез білка, РНК чи інші теми, пов’язані з біологічними процесами еволюції. Я не так дбаю про створення науково точного моделювання еволюції, як це відбувається у фізичному світі, радше мене цікавлять методи застосування еволюційних стратегій у програмному забезпеченні.

Це не означає, що проєкт з більшою науковою глибиною не матиме цінності. Насправді ціла галузь із досліджень обчислювальної біології бере на себе завдання більш точного моделювання біологічних еволюційних процесів! Я закликаю читачів, які особливо цікавляться цією темою, досліджувати можливості розширення наданих прикладів додатковими еволюційними функціональностями. Проте, щоб проєкти залишалися керованими, я буду дотримуватися основ. І як це сталося, основи будуть досить складними та захопливими.

Я також маю зауважити, що, строго кажучи, термін генетичний алгоритм стосується конкретного алгоритму, реалізованого певним чином для розв’язання конкретних питань і не всі ці особливості важливі для цієї книги. Хоча формально ГА слугуватиме основою для прикладів у цій главі, я не буду галасувати щодо реалізації алгоритму з ідеальною точністю, враховуючи, що я шукаю саме творчих застосувань еволюційної теорії в коді. Таким чином, цей розділ буде розбито на наступні три частини:

• Традиційний генетичний алгоритм: я почну з традиційного, хрестоматійного ГА. Цей алгоритм було розроблено для розв’язання проблем з інформатики, для яких простір вирішення настільки великий, що алгоритм грубої сили (brute-force) займе надто багато часу. Ось приклад: я загадав число від одного до одного мільярда. Скільки часу знадобиться, щоб вгадати? З підходом грубої сили вам доведеться перевіряти кожне можливе рішення. Це один? Це два? Це три? Чи чотири?... Удача тут відіграє важливу роль (можливо, я випадково вибрав п’ять!), але в середньому ви б витратили роки, відраховуючи від одиниці, перш ніж вибрати правильну відповідь. Але що, якби я міг сказати вам, чи була ваша здогадка хорошою, чи поганою? Тепло чи холодно? Дуже тепло? Гаряче? Крижаний холод? Якби ви могли оцінити, наскільки близькі (або відповідні) ваші припущення, то могли б почати обирати числа відповідним чином і швидше прийти до відповіді. Ваша відповідь буде еволюціонувати.
• Інтерактивний вибір: після ознайомлення з традиційною версією я розгляну інші застосування ГА у візуальному мистецтві. Інтерактивний вибір належить до процесу розвитку чого-небудь (часто до створеного комп’ютером зображення) за допомогою взаємодії користувача. Припустимо, ви заходите в музейну галерею і бачите 10 картин. За допомогою інтерактивного вибору ви можете вибрати свої улюблені та дозволити алгоритмічному процесу створити (або розвинути) нові картини на основі ваших уподобань.
• Моделювання екосистеми: традиційна комп’ютерна наука ГА-мів та інтерактивна техніка вибору — це те, що ви, швидше за все, знайдете, якщо шукатимете в інтернеті чи читатимете підручник про штучний інтелект. Але, як ви скоро побачите, вони насправді не імітують процес еволюції, як це відбувається у фізичному світі. У цьому розділі я також досліджуватиму методи моделювання еволюції в екосистемі штучних створінь. Як об’єкти, що рухаються по полотну, можуть зустрітися один з одним, спаровуватися та передавати свої гени новому поколінню? Це може стосуватися безпосередньо проєкту екосистеми, описаного в кінці кожного розділу. Це також буде особливо актуально, коли я досліджуватиму нейроеволюцію у Розділі 11.

Навіщо використовувати генетичні алгоритми?

Щоб допомогти проілюструвати корисність традиційного ГА, я збираюся почати з котів. Але не просто з повсякденних котів. Я збираюся розпочати з кількох котів-муркотунів, які володіють талантом друкування, з метою створити повне зібрання творів Шекспіра (малюнок 9.1).

Це мій нявкяючий твіст до теореми про нескінченну мавпу, яка сформульована наступним чином: мавпа, яка має нескінченну кількість часу і буде випадково натискати клавіші на друкарській машинці, зрештою надрукує повний текст творів Шекспіра. Це лише теорія, оскільки на практиці кількість можливих комбінацій літер і слів робить ймовірність того, що мавпа справді надрукує Шекспіра, мізерною. Якщо говорити про це в перспективі, то навіть якби мавпа почала друкувати на початку Всесвіту, ймовірність того, що до цього часу вона створила, хоча б Гамлета, не кажучи вже про цілі твори Шекспіра, все одно є абсурдно малоймовірною.

Розглянемо кота, на ім’я Клавдіус. Клавдіус друкує на зменшеній друкарській машинці, яка містить лише 27 символів: 26 англійських літер плюс пробіл. Імовірність того, що Клавдіус натисне будь-яку клавішу, становить 1 до 27.

Далі розглянемо класичну фразу “to be or not to be that is the question” (для простоти я ігнорую великі літери й пунктуацію). Фраза містить 39 символів, включаючи пробіли. Якщо Клавдіус почне друкувати, шанс, що він правильно введе перший символ, становить 1 до 27. Оскільки ймовірність того, що він правильно введе другий символ, також дорівнює одній двадцять сьомій, то його шанс надрукувати перші дві літери поспіль у правильному порядку складає 1 до 729 ($27 \times 27$). (Це безпосередньо випливає з нашого обговорення ймовірності у Розділі 0.) Тому ймовірність того, що Клавдіус набере повну фразу, дорівнює $1 / 27$ помноженій на саму себе 39 разів, або $(1/27)^{39}$. Це дорівнює ймовірності...

Зайве говорити, що навіть влучити лише в одну фразу, не кажучи вже про цілу п’єсу, не кажучи вже про всі 38 п’єс Шекспіра малоймовірно. Навіть якби Клавдіус був комп’ютерною симуляцією і міг вводити мільйон випадкових фраз за секунду, щоб Клавдіус мав 99-відсоткову ймовірність врешті-решт правильно вказати лише одну фразу, йому довелося б друкувати 9 719 096 182 010 563 073 125 591 133 903 305 625 605 017 років. Для порівняння, вік Всесвіту становить лише 13 750 000 000 років.

Мета всіх цих незбагненно великих чисел полягає не в тому, щоб викликати у вас головний біль, а в тому, щоб продемонструвати, що алгоритм грубої сили (введення всіх можливих випадкових фраз) не є розумною стратегією для випадкового досягнення фрази “to be or not to be that is the question”. Вихід у генетичних алгоритмах, які починаються з випадкових фраз і швидко знаходять рішення через еволюційні симуляції, залишаючи Клавдіусу багато часу, щоб насолодитися затишним дріманням.

Чесно кажучи, ця конкретна проблема (прийти до фрази “to be or not to be that is the question”) є сміховинною. Оскільки ви вже знаєте відповідь, все що вам потрібно зробити, це ввести її. Ось програма p5.js, яка вирішує проблему:

let s = "to be or not to be that is the question";

console.log(s);

Проте, це приголомшлива проблема для початку, оскільки відома відповідь дозволить вам легко перевірити код і оцінити успішність ГА. Після того, як ви успішно розв’яжете проблему, ви можете почуватися більш впевнено, використовуючи ГА, щоб робити щось справді корисне: розв’язувати проблеми з невідомими відповідями. Цей перший приклад не має ніякої реальної мети, окрім демонстрації того, як працюють ГА-ми. Якщо ви порівнюєте результати ГА з відомою відповіддю та отримуєте “to be or not to be”, значить ви досягли успіху в написанні ГА.

Як працюють генетичні алгоритми

Перш ніж перейти до будь-якого коду, я хотів би пройти через етапи класичного ГА в більш загальному вигляді. Я проілюструю, як популяція створінь (загальний термін для елементів симуляції) може розвиватися протягом ряду поколінь. Щоб зрозуміти, як це працює, важливо окреслити три основні принципи дарвінівської еволюції. Якщо природний відбір має відбуватися у коді, як це відбувається в природі, всі ці три елементи повинні бути присутніми:

• Спадковість: повинен існувати механізм, який дозволяє батьківським створінням в одному поколінні передавати свої риси до дочірніх створінь (нащадків) у наступне покоління.
• Мінливість: для того, щоб відбулася еволюція, у популяції істот має бути присутня різноманітність рис або спосіб для введення варіацій. Уявіть популяцію абсолютно однакових жуків, спільного кольору, розміру, розмаху крил і всього іншого. Без будь-якої різноманітності у популяції діти завжди були б ідентичними батькам і один одному. Нові комбінації ознак не змогли б ніколи виникнути й ніщо не еволюціонувало.
• Відбір: повинен існувати механізм, за допомогою якого деякі створіння мають можливість бути батьками та передавати свою генетичну інформацію, а інші ні. Це зазвичай називають виживанням найпристосованіших. Візьмемо, наприклад, популяцію газелей, яких переслідують леви. Швидші газелі мають більше шансів на втечу від левів, збільшуючи тим самим свої шанси на довше життя, можливість розмножуватися та передавати свою генетичну інформацію нащадкам. Однак термін найпристосованіший може ввести в оману. Часто вважають, що воно означає найбільший, найшвидший або найсильніший і хоча іноді це дійсно охоплює такі фізичні атрибути, як розмір, швидкість або сила, це не є обов’язковим. Суть природного відбору полягає в тих рисах, які найкраще відповідають навколишньому середовищу організму і збільшують його ймовірність виживання та, зрештою, розмноження. Замість того, щоб визначати переваги найпристосованіших простіше сприймати їх як “здатних до відтворення”. Візьмемо, наприклад, Dolania americana (також відому як американська поденкова муха), яка, як вважають, має найкоротший термін життя з усіх комах. Доросла самка живе всього п'ять хвилин, але якщо вона встигне відкласти яйця у воду, то передасть свою генетичну інформацію наступному поколінню. Для котів, які друкують, більш пристосованим котом, якого я вважатиму ймовірнішим для відтворення, буде той, який надрукує більше символів, присутніх у потрібній фразі Шекспіра.

Я хочу підкреслити контекст у якому я застосовую ці дарвінівські концепції: змодельоване, штучне середовище, де конкретні цілі можна визначити кількісно і все це заради творчих цілей.

З’ясувавши ці концепції, я розпочну розповідь про ГА. Я зроблю це в контексті котів, що друкують. Алгоритм буде розділений на кілька кроків, які складаються з двох частин: набору умов для ініціалізації й кроків, які повторюються знову й знову, доки не буде знайдено правильну фразу.

Крок 1: Створення популяції

Для котів, що друкують, першим кроком ГА є створення популяції фраз. Я використовую термін фраза досить вільно для позначення будь-якого рядка символів. Ці фрази є створіннями цього прикладу, хоча, звичайно, вони не дуже схожі на істоти.

У створенні популяції фраз застосовується дарвінівський принцип мінливості (різноманітності). Вважатимемо, для простоти, що я намагаюся розвинути фразу “cat” і маю популяцію з трьох фраз:

Звісно, ці фрази різноманітні, але спробуйте змішувати й поєднувати їх символи у будь-який спосіб, але ви ніколи не отримаєте фразу “cat”. Тут недостатньо різноманітності, щоб розвинути потрібний результат. Однак, якщо у мене буде популяція з тисячі фраз, згенерованих випадковим чином, існуватиме ймовірність, що принаймні одна фраза матиме першим символом літеру “c”, якась інша матиме другим символом літеру “a” і ще якась матиме літеру “t” третім символом. Велика популяція, швидше за все, забезпечить достатню різноманітність для створення бажаної фрази. (У 3-му кроці алгоритму я також продемонструю інший механізм для введення більшої кількості варіацій у випадку, якщо спочатку їх недостатньо.) Отже, крок 1 можна описати таким чином:

Створіть популяцію випадково згенерованих елементів.

Елемент, мабуть, кращий, більш загальний термін, ніж створіння. Але що таке елемент? Під час перегляду прикладів у цьому розділі ви побачите кілька сценаріїв: у вас може бути популяція зображень або популяція рухомих об’єктів, як у Розділі 5. Новим у цьому розділі є те, що кожен елемент, кожен член популяції має віртуальну ДНК, набір властивостей (ви також можете назвати їх генами), які описують, як виглядає або поводиться певний елемент. Для котів, які друкують, наприклад, ДНК може бути рядком символів. Маючи це на увазі, я можу бути ще більш конкретним і описати перший крок ГА таким чином:

Створіть популяцію з N елементів, кожен із випадково згенерованою ДНК.

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

Розрізнення генотипу і фенотипу є ключовим для творчого використання ГА. Які предмети є у вашому світі? Як ви розробите генотип для цих об’єктів — структуру даних для зберігання властивостей кожного об’єкта та значення, які набувають ці властивості? І як ви будете використовувати цю інформацію для розробки фенотипу? Тобто, що ви хочете, щоб ці змінні насправді виражали?

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

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

Хороший аспект прикладу з котячим друкуванням полягає в тому, що немає різниці між генотипом і фенотипом. Дані ДНК — це рядок символів і вираження цих даних — це той самий рядок.

Крок 2: Відбір

Другим кроком ГА є застосування дарвінівського принципу відбору. Він включає у себе оцінку популяції та визначення членів, придатних для вибору в якості батьків для наступного покоління. Процес відбору можна розділити на два етапи:

1. Оцінка пристосованості
2. Створення шлюбного пулу

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

Розглянемо поточний сценарій з котами-друкарями. Знову ж таки, для простоти, я скажу, що цільова фраза це “cat”. Припустімо, що популяція складається з трьох елементів: “hut”, “car” і “box”. Слово “car”, очевидно, найпідхожіше, враховуючи, що воно має два правильні символи у правильних позиціях, слово “hut” — лише один, а “box” — нуль. І ось вона, оцінювальна функція:

Згодом я розгляну приклади зі складнішими оцінковими функціями, але це хороший початок.

Після того, як оцінка пристосованості буде розрахована для всіх членів популяції, наступною частиною процесу відбору є вибір членів, які підходять для батьківства, і поміщення їх у шлюбний пул. Цей крок має кілька варіантів. Наприклад, я міг би використати елітарний підхід і сказати: “Які два члени популяції отримали найвищий бал? От вони двоє і створять всіх дітей для наступного покоління”. Ймовірно, це один із найпростіших способів для програмування, але він суперечить принципу варіації. Якщо два члени популяції (із, можливо, кількатисячної) є єдиними, хто може розмножуватися, наступне покоління матиме малу варіативність і це може загальмувати еволюційний процес.

Натомість я міг би створити шлюбну групу з більшої кількості елементів, наприклад, 50 відсотків кращої частини популяції. Це ще один простий спосіб для кодування, але він також не дасть оптимальних результатів. У цьому випадку елементи з найвищою оцінкою матимуть такий самий шанс бути вибраними, як і ті, що розташовані ближче до середини. Чому фраза у популяції з 1000 фраз, яка займає 500 місце, повинна мати такий самий шанс для відтворення, як і фраза, яка займає 1 місце? Якщо на те пішло, чому фраза під номером 500 повинна мати гарантовану можливість відтворення, тоді як фраза 501 не матиме жодної?

Кращим рішенням для парного пулу є використання ймовірнісного методу, який я назву колесом фортуни (також його називають колесом рулетки). Щоб проілюструвати цей метод, припустімо, що популяція складається з п’яти елементів, кожен з яких має певний показник пристосованості:

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

Далі розділіть кожну оцінку на загальну пристосованість і у результаті отримаєте значення нормалізованої пристосованості:

Тепер настав час для колеса фортуни, зображеного на малюнку 9.2.

Покрутіть колесо і ви помітите, що найвищий шанс бути обраним має елемент $B$, за ним йде $A$, потім $E$, потім $D$ і нарешті $C$. Цей вибір на основі ймовірності відповідно до пристосованості є чудовим підходом. Це гарантує, що елементи з найвищими оцінками матимуть найімовірнішу можливість відтворення, а також це не усуває повністю будь-які інші варіації популяції. На відміну від елітарного підходу, навіть елемент з найнижчими балами (у цьому випадку $C$) має принаймні якийсь шанс передати свою інформацію наступному поколінню. Це важливо, тому що цілком можливо (і часто так буває), що деякі елементи з низькими балами мають крихітні частинки генетичного коду, які є справді корисними і їх не слід вилучати з популяції. Наприклад, у випадку розвитку фрази “to be or not to be”, ми можемо мати наступні елементи:

Як бачите, елементи $A$ і $B$ явно найкраще підходять й матимуть найвищу оцінку. Але жодна з них не містить правильних символів для закінчення фрази. Елемент $C$, навіть якщо він отримав би дуже низький бал, випадково має генетичні дані для кінця фрази. Хоча я міг би хотіти, щоб $A$ і $B$ були обрані для створення більшості наступного покоління, я також хочу, щоб $C$ теж мав невеликий шанс для участі у процесі відтворення.

Крок 3: Відтворення

Тепер, коли я продемонстрував стратегію відбору батьківських елементів, останнім кроком є застосування відтворення для створення наступного покоління популяції, з урахуванням дарвінівського принципу спадковості, де діти успадковують властивості своїх батьків. Знову ж таки, тут можна застосувати численні підходи. Наприклад, однією розумною (і легкою для програмування) стратегією є клонування, коли береться лише один батьківський елемент і створюється точна його копія для формування дочірнього елементу. Однак, як і у випадку з елітарним підходом до відбору, це суперечить меті варіації. Натомість стандартний підхід до ГА полягає у виборі двох батьків і створенні дочірнього елемента відповідно до двох кроків таких як:

1. Схрещування
2. Мутація

Перший крок схрещування створює дитину з генетичного коду двох батьків. Для прикладу з котами-друкарями, після кроку відбору, я вибрав наступні дві батьківські фрази з пулу для спаровування (тут я використовую інші й трохи коротші рядки довжиною у 6 символів, замість необхідних рядків для фрази “to be or not to be”):

Зараз постає завдання створити дочірню фразу з двох обраних. Можливо, найочевиднішим способом (назвемо його методом 50/50) було б взяти перші три символи з елементу $A$, а інші три з елементу $B$, як показано на малюнку 9.3.

Різновидом цього підходу є вибір випадкової середньої точки. Іншими словами, мені не завжди потрібно вибирати рівно половину символів від кожного із батьків. Я міг би використати комбінацію 1 і 5 або 2 і 4. Це краще, ніж підхід 50/50, оскільки він збільшує різноманітність можливостей для наступного покоління (див. малюнок 9.4).

Інша можливість полягає у випадковому виборі батьківського символу для кожного символу в дочірньому рядку, як показано на малюнку 9.5. Ви можете подумати про це як про підкидання монети шість разів: коли випадає решка ми беремо літеру з батьківського елементу $A$, орел — беремо літеру з елементу $B$. Це дає ще більше можливих результатів: “codurg”, “natine”, “notune”, “cadune” і так далі.

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

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

Мутація описується в термінах частоти. Даний ГА може мати частоту мутації, наприклад, 5 відсотків, або 1 відсоток, або 0.1 відсотка. Скажімо, через схрещування я дійшов до дочірньої фрази “catire”. Якщо рівень мутації становить 1 відсоток, це означає, що кожен символ у фразі має шанс на мутацію у 1 відсоток, перш ніж він “народиться” у наступному поколінні. Що означає мутація символу? У цьому випадку мутацію можна визначити як вибір нового випадкового символу. Імовірність у 1 відсоток є досить низькою, тому здебільшого мутація взагалі не відбуватиметься в рядку з шести символів (насправді приблизно в 94 відсотках випадків). Однак, коли це відбувається, мутований символ замінюється на випадково згенерований (див. малюнок 9.6).

Як ви побачите в наступних прикладах, частота мутації може сильно вплинути на поведінку системи. Дуже високий рівень мутацій (наприклад, 80 відсотків) зведе нанівець весь еволюційний процес і залишить вас із чимось більш схожим на алгоритм грубої сили. Якщо більшість генів дитини генеруються випадковим чином, ви не можете гарантувати, що з кожним наступним поколінням більш придатні гени з’являютимуться частіше.

Загалом процес відбору (вибір двох батьків) і розмноження (схрещування та мутація) повторюється N разів, доки ви не отримаєте нову популяцію з N елементів.

Крок 4: Повторення!

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

Кодування генетичного алгоритму

Тепер, коли я описав усі кроки ГА, настав час перевести їх у код. Перш ніж заглибитися у деталі реалізації, подумаємо, як ці кроки вписуються у загальну стандартну структуру програми p5.js. Що входитиме у функцію setup(), а що у функцію draw()?

setup()

Крок 1, Ініціалізація: створення початкової популяції з N елементів, кожен із випадково згенерованою ДНК.

draw()

Крок 2, Відбір: оцінка пристосованості кожного елемента популяції й формування шлюбного пулу.

Крок 3, Відтворення: повторення попередніх кроків N разів:

• Вибір двох батьківських елементів з імовірністю відповідно до відносної пристосованості.
• Схрещування: створення дочірнього елемента, поєднуючи ДНК батьківських елементів.
• Мутація: зміна ДНК дочірнього елемента на основі заданої ймовірності.
• Додавання новоствореного елемента до нової популяції.

Крок 4: Заміна старої популяції новою і повернення до кроку 2.

Маючи цей план, я можу почати писати код.

Крок 1: Ініціалізація

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

let population = [];

Вибір масиву для представлення списку простий, але залишається питання: масив чого? Об’єкт є чудовим вибором для зберігання генетичної інформації, оскільки він може містити кілька властивостей і методів. Ці генетичні об’єкти будуть структуровані відповідно до класу, який я назву DNA:

class DNA {

}

Що має бути у класі DNA? Для кота, який друкує, ДНК буде випадковою фразою, яку він друкує, тобто рядком символів. Однак використання масиву символів (а не об’єкта рядка) забезпечує більш загальний шаблон, який можна легко поширити на інші типи даних. Наприклад, ДНК істоти у фізичній системі може бути масивом векторів або масивом чисел для зображення (піксельні значення RGB). У масиві можна перерахувати будь-який набір властивостей і навіть якщо рядок зручний для конкретного цього сценарію, масив буде кращою основою для майбутніх еволюційних прикладів.

ГА вказує, що я створюю популяцію з N елементів, кожен із випадково згенерованими генами. Таким чином, конструктор ДНК містить цикл для заповнення кожного елемента масиву genes:

class DNA {

  constructor(length) {

    this.genes = [];

    for (let i = 0; i < length; i++) {

      this.genes[i] = randomCharacter();

    }

  }

}

Щоб випадково згенерувати символ, я напишу допоміжну функцію під назвою randomCharacter(), що викликатиметься для кожного окремого гена:

function randomCharacter() {
  let c = floor(random(32, 127));
  return String.fromCharCode(c);
}

Вибрані випадкові числа відповідають певному символу відповідно до стандарту, відомого як ASCII (американський стандартний код для обміну інформацією), а String.fromCharCode() є рідним методом JavaScript, який перетворює число у відповідний символ на основі цього стандарту. Вказаний мною діапазон охоплює великі та малі літери, цифри, знаки пунктуації та спеціальні символи. Альтернативний підхід може використовувати стандарт Unicode, який включає емодзі та символи з різних мов світу, забезпечуючи більший діапазон символів для іншого цільового рядка.

Тепер, коли у мене є конструктор, я можу повернутися до функції setup() та ініціалізувати кожен об’єкт DNA для масиву population:

let population = [];

function setup() {

  for (let i = 0; i < population.length; i++) {

    population[i] = new DNA(18);

  }

}

Клас DNA ще не завершено. Мені потрібно надати йому методи, які виконуватимуть усі інші завдання ГА. Я зроблю це під час імплементації кроків 2 і 3.

Крок 2: Відбір

Крок 2 говорить: “Оцініть пристосованість кожного елемента популяції та побудуйте шлюбний пул”. Я почну з першої частини, оцінюючи пристосованість кожного елемента. Раніше я зазначав, що одним із варіантів оцінювання пристосованості для введених фраз є загальна кількість правильних символів. Тепер я трохи перегляну цю оцінювальну функцію і визначу її як відсоток правильних символів, тобто кількість правильних символів поділених на загальну кількість символів:

Де потрібно розраховувати пристосованість? Оскільки клас DNA містить генетичну інформацію (фразу, яку я буду перевіряти на цільову фразу), я можу написати метод усередині класу DNA, щоб він сам оцінював свою власну пристосованість. Підготуємо цільову фразу:

let target = "to be or not to be";

Тепер я можу порівнювати кожен ген із відповідним символом у цільовій фразі, збільшуючи лічильник щоразу, коли знаходжу правильний символ у правильній позиції. Наприклад, символ t зустрічається у кількох місцях фрази target, але це підвищує пристосованість, лише якщо він знаходиться у масиві genes у правильній позиції відповідного індексу:

class DNA {

  constructor(length) {

    this.genes = [];

    this.fitness = 0;

    for (let i = 0; i < length; i++) {

      this.genes[i] = randomCharacter();

    }

  }

  calculateFitness(target) {
    let score = 0;
    for (let i = 0; i < this.genes.length; i++) {
      if (this.genes[i] === target.charAt(i)) {
        score++;
      }
    }
    this.fitness = score / target.length;
  }

}

Оскільки пристосованість обчислюється для кожного наступного покоління, найпершим кроком, який я зроблю всередині циклу у функції draw(), буде виклик функції оцінки пристосованості для кожного елементу популяції:

function draw() {

  for (let phrase of population) {

    phrase.calculateFitness(target);

  }

}

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

У Розділі 0 я розглянув основи ймовірності й генерування спеціального розподілу випадкових чисел. Я збираюся використати тут ті самі методи, щоб призначити ймовірність кожному члену популяції, вибираючи батьків шляхом обертання колеса фортуни. Переглянувши малюнок 9.2, ваш розум може негайно повернутися до Розділу 3 і подумати про кодування симуляції справжнього обертового колеса. Як би це не було весело (і ви якось можете зробити таке колесо!), це зовсім непотрібно.

Одне з рішень, яке може тут спрацювати, полягає в тому, щоб вибрати з п’яти варіантів, зображених на малюнку 9.2 (A, B, C, D, E) відповідно до їхніх імовірностей, заповнивши масив кількома екземплярами кожного батьківського елемента. Іншими словами, уявіть, що у вас є відро з дерев’яними літерами, як на малюнку 9.7. Виходячи з попередніх імовірностей, воно повинно містити 30 літер A, 40 літер B, 5 літер C, 10 літер D і 15 літер E. Якби ви вибрали випадкову букву з цього відра, то мали б 30-відсотковий шанс отримати букву A, 5-відсотковий шанс отримати літеру C і так далі.

Для коду ГА це відро може бути масивом, а кожна дерев’яна літера — потенційним батьківським об’єктом DNA. Таким чином, шблюбний пул створюється шляхом додавання до масиву кожного з батьківських елементів певну кількість разів, відповідно до оцінки їх пристосованості:

  let matingPool = [];

  for (let phrase of population) {

    let n = floor(phrase.fitness * 100);

    for (let j = 0; j < n; j++) {

      matingPool.push(phrase);

    }

  }

Коли шлюбний пул готовий, настав час вибрати двох батьків! Вибір двох батьків для кожної дитини є дещо довільним рішенням. Це, безумовно, віддзеркалює людське відтворення і є стандартним способом у підручнику ГА-мів, але з точки зору творчих застосувань тут справді немає обмежень. Ви можете вибрати лише одного батька для клонування або розробити методологію відтворення для вибору трьох-чотирьох батьків для генерації дитячої ДНК. Для цієї демонстрації я виберу два батьківські елементи та назву їх parentA і parentB.

  let parentA = random(matingPool);

  let parentB = random(matingPool);

Цей метод створення шлюбного пулу та вибору з нього батьків працює, але це не єдиний спосіб відбору. Інші, більш ефективні методи не вимагають додаткового масиву з кількома посиланнями на кожен елемент. Наприклад, згадайте обговорення нерівномірного розподілу випадкових чисел у Розділі 0. Там я реалізував метод прийняття-відхилення. Якщо його застосувати тут, підхід полягатиме у випадковому виборі елемента з вихідного масиву population, а потім у виборі другого випадкового числа-кваліфікатора для перевірки відповідності значення елемента. Якщо пристосованість менша за кваліфікаційне число, почніть заново і виберіть новий елемент. Продовжуйте доки двоє батьків не будуть визнані достатньо пристосованими для спільної пари.

Варто розглянути ще одну чудову альтернативу, яка подібним чином використовує принцип відбору — пропорційну пристосованість. Щоб зрозуміти, як це працює, уявіть собі естафету, в якій кожен член популяції пробігає задану дистанцію, прив’язану до його рівня пристосованості. Чим вище пристосованість, тим далі вони бігають. Давайте також припустимо, що оцінки пристосованості були нормалізовані, щоб усі суми дорівнювали 1 (так само як у випадку з колесом фортуни). Першим кроком є вибір стартової лінії — випадкової відстані від фінішу. Ця відстань є випадковим числом від 0 до 1. (За мить ви побачите, що фінішна лінія вважається нульовою).

let start = random(1);

Потім естафета починається на стартовій лінії з першим представником популяції:

let index = 0;

Бігун проходить відстань, визначену його нормалізованим показником пристосованості, а потім передає естафету наступному бігуну:

while (start > 0) {

  start = start - population[index].fitness;

  index++;

}

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

Нижче усі кроки функції, яка повертає вибраний елемент, об’єднані разом:

function weightedSelection() {

  let index = 0;

  let start = random(1);

  while (start > 0) {

    start = start - population[index].fitness;

    index++;

  }

  index--;
  return population[index];

}

Це добре підходить для відбору, оскільки кожен учасник має можливість перетнути фінішну лінію (усі оцінки пристосованості складаються до 1), але ті, хто біжить на більші дистанції (тобто ті, хто має вищий бал оцінки), мають більше шансів. Однак, попри те, що цей метод є більш ефективним для пам’яті, він може бути більш вимогливим до обчислень, особливо для великих популяцій, оскільки вимагає ітерації по популяції для кожного відбору. Напротивагу, оригінальний метод з масивом matingPool потребує лише однієї дії з випадковим пошуком в масиві для кожного батьківського елементу.

Залежно від конкретних вимог і обмежень вашого проєкту ГА, один підхід може виявитися більш прийнятним, ніж інший. Я буду чергувати їх у прикладах, наведених у цьому розділі.

У будь-якому з цих алгоритмів той самий батьківський елемент може бути обраний двічі для даної дитини. Якби я хотів, то міг би вдосконалити алгоритм, щоб переконатися, що це неможливо. Ймовірно, це мало б невеликий вплив на кінцевий результат, але можливо це варто дослідити в рамках окремої вправи.

Крок 3: Відтворення (схрещування і мутація)

Коли я вже отримав двох батьків, наступним кроком буде виконання операції схрещування для генерації дочірньої ДНК з подальшою мутацією:

let child = parentA.crossover(parentB);

child.mutate();

Звісно, методи crossover() і mutate() не з’явилися у класі DNA магічним чином й мені потрібно їх написати. Спосіб виклику мого методу crossover() вказує на те, що він повинен отримати екземпляр DNA як аргумент (тут це parentB) і повернути новий екземпляр DNA, тобто child:

crossover(partner) {

  let child = new DNA(this.genes.length);

  let midpoint = floor(random(this.genes.length));

  for (let i = 0; i < this.genes.length; i++) {

    if (i < midpoint) {
      child.genes[i] = this.genes[i];

    } else {

      child.genes[i] = partner.genes[i];

    }

  }

  return child;

}

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

Написати метод mutate() навіть простіше ніж crossover(). Все, що мені потрібно зробити, це пройтись масивом генів і випадковим чином вибрати новий символ відповідно до визначеної частоти мутації. Наприклад, при частоті мутації в 1 відсоток, новий символ буде створено лише 1 раз на 100 разів:

let mutationRate = 0.01;

if (random(1) < mutationRate) {

  /* Будь-який код тут виконуватиметься в 1% випадків. */

}

mutate(mutationRate) {

  for (let i = 0; i < this.genes.length; i++) {

    if (random(1) < mutationRate) {

      this.genes[i] = randomCharacter();

    }

  }

}

Щоб спростити процес мутації, я знову можу використати допоміжну функцію randomCharacter().

Збираємо все разом

На цей час я двічі пройшов кроками ГА: перший раз описав алгоритм у формі розповіді, а другий раз із фрагментами коду, що імплементують кожен із кроків. Тепер я готовий зібрати все до купи й показати вам повний код разом з основними кроками алгоритму.

let mutationRate = 0.01;

let populationSize = 150;

let population = [];

let target = "to be or not to be";

function setup() {

  createCanvas(640, 360);

  for (let i = 0; i < populationSize; i++) {
    population[i] = new DNA(target.length);
  }

}

function draw() {

  for (let phrase of population) {
    phrase.calculateFitness(target);
  }

  let matingPool = [];

  for (let phrase of population) {

    let n = floor(phrase.fitness * 100);
    for (let j = 0; j < n; j++) {
      matingPool.push(phrase);
    }

  }

  for (let i = 0; i < population.length; i++) {
    let parentA = random(matingPool);
    let parentB = random(matingPool);

    let child = parentA.crossover(parentB);

    child.mutate(mutationRate);

    population[i] = child;

  }

}

Файл sketch.js точно відображає кроки ГА. Однак більшість функціональних можливостей інкапсульовано у класі DNA:

class DNA {

  constructor(length) {
    this.genes = [];
    for (let i = 0; i < length; i++) {
      this.genes[i] = randomCharacter();
    }
    this.fitness = 0;
  }

  getPhrase() {
    return this.genes.join("");
  }

  calculateFitness(target) {
    let score = 0;
    for (let i = 0; i < this.genes.length; i++) {
      if (this.genes[i] === target.charAt(i)) {
        score++;
      }
    }
    this.fitness = score / target.length;
  }

  crossover(partner) {
    let child = new DNA(this.genes.length);
    let midpoint = floor(random(this.genes.length));
    for (let i = 0; i < this.genes.length; i++) {
      if (i < midpoint) {
        child.genes[i] = this.genes[i];
      } else {
        child.genes[i] = partner.genes[i];
      }
    }
    return child;
  }

  mutate(mutationRate) {
    for (let i = 0; i < this.genes.length; i++) {
      if (random(1) < mutationRate) {
        this.genes[i] = randomCharacter();
      }
    }
  }

}

function randomCharacter() {
  let c = floor(random(32, 127));
  return String.fromCharCode(c);
}

У прикладі 9.1 ви можете помітити, що нові дочірні елементи безпосередньо додаються до масиву population. Такий підхід можливий, оскільки у мене є окремий масив шлюбного пулу, який містить посилання на оригінальні батьківські елементи. Однак, якби замість цього я використовував функцію з підходом естафети weightedSelection(), мені потрібно було б створити тимчасовий масив для нової популяції. Цей тимчасовий масив міститиме дочірні елементи й замінюватиме вихідний масив лише після завершення кроку відтворення. Ви побачите, як це реалізовано у прикладі 9.2.

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

Хороша річ у використанні ГА у проєктах в тому, що приклад коду можна легко переносити із програми у програму. Основні механізми відбору і відтворення не потребують змін. Однак вам, творцю, доведеться налаштувати три ключові компоненти ГА для кожного використання. Це надзвичайно важливо для переходу від тривіальних демонстрацій еволюційного моделювання (як у прикладі з Шекспіром) до творчого використання в проєктах, які ви робите в p5.js та інших середовищах програмування.

Ключовий аспект 1: Глобальні змінні

ГА не має багато змінних. Якщо ви подивитеся на код у прикладі 9.1, то побачите лише дві глобальні змінні (не враховуючи масиви для зберігання популяції й шлюбного пулу):

let mutationRate = 0.01;

let populationSize = 150;

Ці дві змінні можуть значно вплинути на поведінку системи, і використовування довільних значень тут не краща ідея (хоча їх налаштування методом проб і помилок є цілком розумним способом отримати оптимальні значення).

Я вибрав спеціальні значення для демонстрації прикладу з Шекспіром, щоб практично гарантувати, що ГА розв’яже фразу, але не надто швидко (у середньому приблизно за 1000 поколінь), щоб продемонструвати процес протягом певного періоду часу. Однак набагато більша популяція дасть швидші результати (для мети з більшою ефективністю алгоритму, а не демонстрацією). Ось таблиця з деякими результатами:

Зауважте, що збільшення чисельності популяції різко зменшує кількість поколінь, необхідних для розв’язання фрази. Однак це не обов’язково зменшує кількість часу. Коли популяція зростає до 50 000 елементів, програма починає виконуватися повільно, враховуючи кількість часу, необхідного для обробки оцінки пристосованості та створення шлюбного пулу з такої кількості елементів. (Звісно, якщо вам потрібна така велика популяція, можна зробити певну оптимізацію.)

Окрім розміру популяції, на продуктивність може сильно вплинути частота мутацій:

Без жодної мутації (0 відсотків) вам може просто пощастити. Якщо всі правильні символи присутні десь в елементах початкової популяції, ви дуже швидко розвинете потрібну фразу. Якщо ні, то програма не зможе досягти точної фрази. Запустіть її кілька разів і побачите обидва варіанти. Крім того, як тільки рівень мутації стає достатньо високим (наприклад, 10 відсотків), виникає стільки випадковості (одна з кожних 10 букв є випадковою у кожному новому дочірньому елементі), що симуляція майже повертається до випадкової версії котів-друкарів. Теоретично це зрештою призведе до потрібної фрази, але ви можете чекати набагато, набагато довше, ніж це буде розумним.

Ключовий аспект 2: Функія оцінки пристосованості

Пограти з частотою мутації або чисельністю популяції досить легко і потребує лише введення потрібних чисел у вашу програму. Справжня важка робота розробки ГА полягає в написанні функції, що оцінює пристосованість. Якщо ви не можете визначити цілі вашої проблеми й чисельно оцінити наскільки вони були досягнуті, то не матимете успішної еволюції у вашій симуляції.

Перш ніж я перейду до інших сценаріїв дослідження складніших оцінювальних функцій, я хочу поглянути на недоліки у моїй шекспірівській функції. Подумайте про розв’язання фрази, яка містить не 18 символів, а 1000. І візьміть два елементи популяції, один із 800 правильними символами, а інший із 801. Ось їхні оцінки пристосованості:

Цей сценарій має кілька проблем. По-перше, я додаю елементи до шлюбного пулу N разів, де N дорівнює значенню пристосованості, помноженому на 100. Але об’єкти можна додавати до масиву лише цілу кількість разів, тому A і B буде додано 80 разів, даючи їм рівну ймовірність для відбору. Навіть із покращеним рішенням, яке враховує ймовірності з рухомою крапкою, 80.1 відсотка лише трохи перевищують 80 відсотків. Але отримати в еволюційному сценарії 801 правильний символ набагато краще, ніж 800. Я справді хочу, щоб цей додатковий символ враховувався. Я хочу, щоб оцінка пристосованості для 801 символу була суттєво кращою, ніж оцінка для 800 символів.

Іншими словами, малюнок 9.8 показує графіки двох можливих функцій оцінки пристосованості.

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

Я можу досягти результату другого типу різними способами. Наприклад, я міг би сказати так:

Тут показники пристосованості зростають квадратично, тобто пропорційно до квадрата кількості правильних символів. Скажімо, у мене є два члени популяції, один із п’ятьма правильними символами, а інший із шістьма. Число 6 на 20 відсотків більше, ніж число 5. Однак, при піднесенні кількості правильних символів у квадрат, оцінка пристосованості збільшиться з 25 до 36, тобто на 44 відсотки:

Ось інша можлива формула:

А ось як ця формула працює зі збільшенням кількості правильних символів:

Тут показники оцінки пристосованості зростають експоненціально, подвоюючись з кожним додатковим правильним символом.

Хоча це конкретне обговорення експоненціальних і лінійних рівнянь є важливою деталлю у розробці хорошої оцінювальної функції, я не хочу, щоб ви випустили тут більш важливий момент: ви можете створювати власні оцінювальні функції! Я дуже сумніваюся, що будь-який проєкт, який ви робитимете на p5.js із ГА, передбачатиме підрахунок правильної кількості символів у рядку. У контексті цієї книги ви, швидше за все, захочете еволюціонувати створіння, яке є частиною фізичної системи. Можливо, ви прагнете оптимізувати ваги поведінкових шаблонів, щоб створіння могло найкраще втікати від хижака, уникати перешкоди чи проходити через лабіринт. Ви повинні запитати себе, що ви збираєтеся оцінювати.

Розглянемо симуляцію перегонів, у якій перегонове авто розвиває оптимізацію свого дизайну для кращої швидкості:

Як щодо миші, яка еволюціонує оптимальним шляхом, щоб знайти шматок сиру?

Розробка керованих комп’ютером гравців у грі також є поширеним сценарієм. Скажімо, ви програмуєте футбольну гру, у якій користувач є воротарем. Решта гравців керуються вашою програмою і мають набір параметрів, які визначають, як вони б’ють м’яч у напрямку воріт. Якою буде оцінка пристосованості для будь-якого гравця?

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

Зрештою, якщо у вас немає оцінювальної функції, яка б ефективно оцінювала продуктивність окремих елементів вашої популяції, у вас не буде еволюції. А ще оцінювальна функція з одного прикладу, швидше за все, не підійде до зовсім іншого проєкту. Інколи вам доведеться розробляти таку функцію з нуля, щоб вона підходила саме для вашого конкретного проєкту. А де це імплементувати? Все, що вам потрібно відредагувати, це кілька рядків коду всередині методу, який обчислює змінну fitness:

calculateFitness() {

  ????????????

  ????????????

  this.fitness = ??????????

}

Заповнення цих знаків запитання — це та частина, де ви зможете проявити себе!

Ключовий аспект 3: Генотип і фенотип

Останній аспект розробки власного ГА стосується способу кодування властивостей вашої системи. Що ви намагаєтеся виразити і як перевести це у купу чисел? Що таке генотип і фенотип?

Я почав із прикладу з Шекспіром через легкість проєктування як його генотипу (набору символів), так і його вираження — фенотипу (рядку, зображеному на полотні). Однак це не завжди так легко. Наприклад, говорячи про оцінювальну функцію для футбольного матчу, я з радістю припустив існування керованих комп’ютером гравців, кожен з яких має “набір параметрів, які визначають, як вони б’ють м’яч у напрямку воріт”, але насправді визначення того, що це за параметри та спосіб їх кодування, потребує певних роздумів і творчості. І, звісно, тут немає однозначної правильної відповіді: ви самі вирішуєте, як розробляти систему.

Хороша новина, і я натякнув про це раніше в цьому розділі, полягає в тому, що ви весь час переводили генотипи (дані) у фенотипи (вираження). Щоразу, коли ви пишете клас у p5.js, ви створюєте цілу купу змінних:

class Vehicle {

  constructor() {

    this.maxspeed = ????;

    this.maxforce = ????;

    this.size = ????;

    this.separationWeight = ????;

    /* та інші змінні... */

  }

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

class DNA {

  constructor(length) {

    this.genes = [];
    for (let i = 0; i < length; i++) {

      this.genes[i] = random(1);

    }

  }

}

Зверніть увагу, що зараз я помістив необроблені генетичні дані (генотип) і їх вираження (фенотип) у два окремі класи. Клас DNA — це генотип — це просто набір чисел. Клас Vehicle — це фенотип — вираження того, як перетворити ці цифри в анімовану візуальну поведінку. Обидва класи можна зв’язати, включивши у клас Vehicle екземпляр DNA:

class Vehicle {

  constructor() {

    this.dna = new DNA(4);

    this.maxspeed = dna.genes[0];
    this.maxforce = dna.genes[1];
    this.size = dna.genes[2];
    this.separationWeight = dna.genes[3];

    /* та інші змінні... */

  }

Звісно, ви, ймовірно, не хочете, щоб усі ваші змінні мали діапазон від 0 до 1. Але замість того, щоб намагатися запам’ятати, як налаштувати ці діапазони в класі DNA , простіше витягнути вихідну генетичну інформацію з об’єкта DNA, а потім використати функцію map() із p5.js, щоб змінити діапазон відповідно до вашого фенотипу. Наприклад, якщо вам потрібна змінна size зі значенням від 10 до 72, ви б написали наступне:

    this.size = map(this.dna.genes[2], 0, 1, 10, 72);

В інших випадках ви можете створити генотип, який є масивом об’єктів. Розглянемо конструкцію ракети з низкою двигунів. Ви можете розглядати кожен двигун як вектор, який описує його направлення і відносну силу:

class DNA {

  constructor(length) {

    this.genes = [];
    for (let i = 0; i < length; i++) {

      this.genes[i] = p5.Vector.random2D();

      this.genes[i].mult(random(10));

    }

  }

}

Фенотип — це клас Rocket, який бере участь у фізичній системі:

class Rocket {

  constructor() {

    this.dna = ????;

    /* та інші змінні... */

  }

}  

Що чудово в розділенні генотипу та фенотипу на окремі класи (наприклад, DNA і Rocket), так це те, що коли прийде час створювати весь код, ви помітите, що клас DNA, який я розробив раніше, залишається незмінним. Єдине, що змінюється це тип даних, які зберігаються у масиві (числа, вектори тощо), і вираження цих даних у класі фенотипу.

У наступному розділі я розвину цю ідею трохи далі й пройду необхідні кроки для реалізації прикладу, який включає рухомі тіла та ДНК у вигляді масиву векторів.

Еволюція сил: Розумні ракети

Я згадав про ракети з певної причини: у 2009 році Джер Торп опублікував приклад ГА у своєму блозі під назвою “Розумні ракети”. Торп зазначив, що національне управління з аеронавтики та дослідження космічного простору (NASA) використовує еволюційні обчислювальні методи для розв'язання різноманітних проблем, від конструкції супутникової антени до моделей запуску ракет. Це надихнуло його створити flash-програму з демонстрацією еволюції ракет.

Ось сценарій: група ракет запускається знизу екрана з метою вразити ціль у верхній частині екрана. Наявні перешкоди блокують прямолінійний шлях до цілі (див. малюнок 9.9).

Кожна ракета оснащена п’ятьма двигунами різної сили й напрямку дії (малюнок 9.10). Двигуни не запускаються усі разом і не працюють безперервно, скоріше, вони спрацьовують по одному у певній послідовності.

У цій частині розділу я збираюся розробити власні спрощені розумні ракети, натхненні Торпом. Коли я дійду до кінця розділу, то залишу реалізацію деяких додаткових просунутих функцій Торпа як вправу.

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

Розробка ракет

Щоб імплементувати мою еволюцію розумних ракети, я почну з того, що візьму клас Mover з Розділу 2 і перейменую його на Rocket:

class Rocket {

  constructor(x, y) {

    this.position = createVector(x, y);
    this.velocity = createVector();
    this.acceleration = createVector();

  }

  applyForce(force) {
    this.acceleration.add(force);
  }

  update() {

    this.velocity.add(this.acceleration);

    this.position.add(this.velocity);

    this.acceleration.mult(0);

  }

}

За допомогою цього класу я можу рухати ракету, викликаючи метод applyForce() з новою силою для кожного кадру анімації. Двигун прикладає до ракети єдину силу на кожен кадр анімації у функції draw(). Але на цьому етапі я ще далекий від завершення. Щоб зробити мої ракети “розумними” і розвинутими, мені потрібно подумати про три ключові аспекти програмування власного ГА, як описано в попередній частині розділу.

Ключовий аспект 1 полягає у визначенні правильних глобальних змінних для розміру популяції та частоти мутації. Наразі я не буду надто турбуватися про ці змінні й довільно виберу значення, що виглядають розумно — можливо, чисельність популяції у 50 ракет і рівень мутації у 1 відсоток. Щойно я побудую систему і запущу свою програму, я зможу експериментувати з цими цифрами.

Ключовий аспект 2 полягає у розробці відповідної функції, що оцінюватиме пристосованість. У цьому випадку метою ракети є досягнення цілі. Чим ближче ракета наближається до цілі, тим вище її пристосованість. Отже, рівень пристосованості обернено пропорційний відстані: чим менша відстань, тим більша пристосованість, а чим більша відстань, тим менша пристосованість.

Щоб застосувати це на практиці, мені спочатку потрібно додати до класу Rocket властивість fitness для збереження значення пристосованості:

class Rocket {

  constructor(x, y) {

    this.fitness = 0;

    this.position = createVector(x, y);

    this.velocity = createVector();

    this.acceleration = createVector();

  }

Далі, мені потрібно додати до класу Rocket метод розрахунку пристосованості. Зрештою, тільки об’єкт Rocket знає, як обчислити свою відстань до цілі, тому функція пристосованості має жити у цьому класі. Припускаючи, що у мене є вектор target, я можу написати наступне:

  calculateFitness() {

    let distance = p5.Vector.dist(this.position, target);

    this.fitness = 1 / distance;

  }

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

  calculateFitness() {

    let distance = p5.Vector.dist(position, target);

    this.fitness = 1 / (distance * distance);

  }

Я хотів би зробити кілька додаткових покращень у функції оцінки пристосування, але це хороший початок.

Нарешті, ключовий аспект 3 полягає в тому, щоб подумати про зв’язок між генотипом і фенотипом. Я заявляв, що кожна ракета має двигун, який діє у змінному напрямку зі змінною величиною — іншими словами є вектором! Таким чином, генотип — дані, необхідні для кодування поведінки ракети — є масивом векторів, по одному для кожного кадру анімації:

class DNA {

  constructor(length) {

    this.genes = [];

    for (let i = 0; i < length; i++) {

      this.genes[i] = createVector();

    }

  }

}

Радісна новина — у класі DNA мені нічого не потрібно дороблювати. Уся функціональність яка потрібна була для кота-друкаря (схрещення і мутація) тут також підходить. Єдина відмінність, яку я повинен враховувати, це те, як ініціалізувати масив генів. З друкарським котом я мав масив символів і вибирав випадковий символ для кожного елемента масиву. Тепер я зроблю те саме й ініціалізую послідовність ДНК як масив випадкових векторів.

Вашим інстинктивним бажанням, при створенні випадкового вектора, може бути наступний код:

let v = createVector(random(-1, 1), random(-1, 1));

Цей код ідеально підходить і, ймовірно, зробить свою справу. Однак, якщо я намалюю кожен можливий вектор такого підходу, то результат заповнить квадратний простір (див. малюнок 9.11, ліворуч). У цьому випадку це, мабуть, не має особливого впливу, але серед значень існує невелике упередження до діагональних напрямків, оскільки вектор від центру квадрата до кута довший за чисто вертикальний або горизонтальний напрямок.

Як ви пам’ятаєте з Розділу 3, кращим варіантом буде вибрати випадковий кут і створити з нього одиничний вектор з довжиною 1. Це продукує результати, які утворюють кругле поле векторних значень (див. праву частину малюнку 9.11) і їх можна досягти за допомогою полярного підходу створення координат за допомогою методу p5.Vector.random2D():

for (let i = 0; i < length; i++) {

  this.genes[i] = p5.Vector.random2D();

}

Вектор з довжиною 1 насправді створить досить велику силу. Пам’ятайте, що сили застосовуються до прискорення, яке акумулюється у швидкості від 30 разів на секунду (або залежно від налаштованої частоти кадрів). Тому для цього прикладу я додам до класу DNA ще одну змінну, максимальну силу, і випадковим чином масштабую всі вектори, щоб значення були десь між 0 і максимумом. Це контролюватиме потужність двигуна:

class DNA {

  constructor() {

    this.genes = [];

    this.maxForce = 0.1;

    for (let i = 0; i < lifeSpan; i++) {
      this.genes[i] = p5.Vector.random2D();

      this.genes[i].mult(random(0, maxforce));

    }

  }

Зверніть увагу, що я використовую змінну lifeSpan для встановлення довжини масиву векторів genes. Ця глобальна змінна зберігає загальну кількість кадрів у життєвому циклі кожного покоління, що дозволяє мені створити вектор для кожного кадру ракетного буття.

Вираження цього масиву векторів, його фенотипом, є мій клас Rocket. Щоб закріпити зв’язок, мені потрібно додати до класу екземпляр об’єкта DNA:

class Rocket {

  constructor(x, y, dna) {

    this.dna = dna;

    this.fitness = 0;

    this.position = createVector(x, y);

    this.velocity = createVector();

    this.acceleration = createVector();

  }

Для чого я використовую this.dna? Коли ракета запускається, вона проходить крізь ряд векторів і застосовує їх один за одним як силу. Для досягнення цього, мені потрібно включити до класу змінну this.geneCounter, яка допоможе проходити через масив:

class Rocket {

  constructor(x, y, dna) {

    this.dna = dna;

    this.fitness = 0;

    this.geneCounter = 0;

    this.position = createVector(x, y);

    this.velocity = createVector();

    this.acceleration = createVector();

  }

  run() {

    this.applyForce(this.dna.genes[this.geneCounter]);

    this.geneCounter++;

    this.update();

  }

}

Тепер у мене є клас DNA (генотип) і клас Rocket (фенотип). Останній шматочок головоломки — це механізм управління популяцією ракет і здійснення селекції та відтворення.

Управління популяцією

Щоб файл sketch.js був більш охайним, я додам у класі Population код для керування масивом об’єктів Rocket. Як і у випадку з класом DNA, хорошою новиною є те, що мені майже нічого не потрібно змінювати з прикладу котів-друкарів. Я просто організую код у більш об’єктно-орієнтований спосіб з методами selection() і reproduction(). Щоб продемонструвати інший підхід, я також нормалізую значення пристосованості у методі selection() і використаю алгоритм зваженого відбору (естафету) у методі reproduction(). Це усуває потребу в окремому масиві шлюбних пулів. Код методу weightedSelection() такий самий, як і написаний раніше у цьому розділі:

class Population {

  constructor(mutation, length) {

    this.mutationRate = mutation;

    this.population = [];

    this.generations = 0;

    for (let i = 0; i < length; i++) {

      this.population[i] = new Rocket(320, 220, new DNA());

    }

  }

  fitness() {
    for (let rocket of this.population) {
      rocket.calculateFitness();
    }
  }

  selection() {

    let totalFitness = 0;
    for (let rocket of this.population) {
      totalFitness += rocket.fitness;
    }

    for (let rocket of this.population) {
      rocket.fitness /= totalFitness;
    }

  }

  reproduction() {

    let newPopulation = [];

    for (let i = 0; i < this.population.length; i++) {

      let parentA = this.weightedSelection();
      let parentB = this.weightedSelection();

      let child = parentA.crossover(parentB);

      child.mutate(this.mutationRate);

      newPopulation[i] = new Rocket(320, 240, child);

    }

    this.population = newPopulation;

  }

Однак мені потрібно внести ще одну досить важливу зміну. З котами, що друкують, випадкова фраза оцінювалася, як тільки вона була створена. Рядок символів не мав тривалості життя, він існував виключно з метою обчислення його пристосованості. Однак ракетам потрібно проіснувати певний період часу, перш ніж їх можна буде оцінити, тобто їм потрібно дати шанс зробити спробу досягти ціль. Тому мені потрібно додати ще один метод до класу Population, який запускає симуляцію фізики. Це ідентично тому, що я робив у методі run() системи частинок — оновлення позиції всіх частинок і їх малювання:

  live() {

    for (let rocket of this.population) {

      rocket.run();

    }

  }

}

Нарешті я готовий до функцій setup() і draw(). Тут моя основна відповідальність полягає в тому, щоб реалізувати кроки ГА у відповідному порядку, викликаючи методи з класу Population:

    population.fitness();

    population.selection();

    population.reproduction();

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

1. Створення популяції ракет.
2. Нехай ракети живуть N кадрів.
3. Розвиток наступного покоління:
   • Відбір
   • Відтворення
4. Повернення до кроку 2.

Щоб знати, коли переходити від кроку 2 до кроку 3, мені потрібна змінна lifeCounter, яка відстежуватиме прогрес поточного покоління разом зі змінно lifeSpan. У функцій draw(), поки значення lifeCounter менше ніж lifeSpan, для запуску моделювання популяції викликається метод live(). Коли значення lifeCounter досягне значення lifeSpan, настане час виконання методів для розвитку нового покоління fitness(), selection() і reproduction().

let lifeSpan = 500;

let lifeCounter = 0;

let population;

function setup() {

  createCanvas(640, 240);

  population = new Population(0.01, 50);

}

function draw() {

  background(255);

  if (lifeCounter < lifeSpan) {

    population.live();
    lifeCounter++;

  } else {

    lifeCounter = 0;
    population.fitness();
    population.selection();
    population.reproduction();

  }

}

function mousePressed() {
  target.x = mouseX;
  target.y = mouseY;
}

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

Внесення покращень

Мої розумні ракети працюють, але поки що не дуже захопливо. Зрештою, ракети просто еволюціонують до отримання ДНК із купою векторів, які вказують прямо на ціль. Щоб зробити приклад цікавішим, я збираюся запропонувати два вдосконалення. Для початку, коли я вперше описав сценарій розумної ракети, я сказав, що ракети повинні розвинути здатність уникнення перешкод. Додавання цієї функціональності зробить систему складнішою й ефективніше продемонструє потужність еволюційного алгоритму.

Щоб розвинути уникнення перешкод, мені потрібна для цього наявність якихось перешкод. Я можу легко створити прямокутні нерухомі перешкоди, реалізувавши клас об’єктів типу Obstacle, які зберігатимуть своє положення і розміри:

class Obstacle {

  constructor(x, y, w, h) {

    this.position = createVector(x, y);

    this.w = w;

    this.h = h;

  }

Я додам до класу Obstacle метод contains(), який повертатиме true, якщо ракета влучила у перешкоду, або false — у протилежному випадку:

  contains(spot) {

    return (

      spot.x > this.position.x &&

      spot.x < this.position.x + this.w &&

      spot.y > this.position.y &&

      spot.y < this.position.y + this.h

    );

  }

Якщо я створю масив об’єктів Obstacle, то зможу перевірити кожну ракету, чи не зіткнулася вона з якоюсь із перешкод. Якщо відбудеться зіткнення, то ракета змінить свою булеву змінну hitObstacle на true. Щоб досягти цього, мені потрібно додати відповідний метод до класу Rocket:

  checkObstacles(obstacles) {
    for (let obstacle of obstacles) {
      if (obstacle.contains(this.position)) {
        this.hitObstacle = true;
      }
    }
  }

Якщо ракета вдариться у перешкоду, я зупиню ракету від оновлення свого положення. Оновлений метод run() тепер отримує як аргумент масив obstacles:

  run(obstacles) {

    if (!this.hitObstacle) {
      this.applyForce(this.dna.genes[this.geneCounter]);
      this.geneCounter = (this.geneCounter + 1);
      this.update();

      this.checkObstacles(obstacles);

    }

    this.show();

  }

Також у мене є можливість налаштувати пристосованість ракети. Якщо ракета вдаряється у перешкоду, оцінка пристосованості повинна скорегуватися і стати значно зменшеною:

  calculateFitness() {

    let distance = p5.Vector.dist(this.position, target);

    this.fitness = 1 / (distance * distance);

    if (this.hitObstacle) {
      this.fitness *= 0.1;
    }

  }

При цьому ракети мають можливість розвиватися для уникнення перешкод. Але я не зупинюся на цьому. Я хочу зробити ще одне покращення.

Якщо ви уважно подивитеся на приклад 9.2, то помітите, що ракети не отримують винагороди за те, що вони швидше досягають цілі. Єдиною змінною у розрахунку пристосованості є відстань до цілі в кінці життя покоління. Насправді якщо ракета наближається до цілі дуже близько, але перестрибує її та пролітає повз, вона може бути покарана за те, що досягла ціль швидше. У цьому випадку перегони виграє повільність і стабільність.

Я міг би покращити алгоритм кількома способами, щоб оптимізувати швидкість досягнення мети. По-перше, я міг би розрахувати пристосованість ракети на основі того, як вона наближається до цілі у будь-який момент свого життя, замість того, щоб використовувати її відстань до цілі у кінці покоління. Я створю для цього нову змінну recordDistance і буду оновлювати її у методі checkTarget() класу Rocket:

  checkTarget() {

    let distance = p5.Vector.dist(this.position, target);

    if (distance < this.recordDistance) {
      this.recordDistance = distance;
    }

Крім того, ракета заслуговує винагороди залежно від швидкості, з якою вона досягає ціль. Для цього мені потрібен спосіб дізнатися, коли ракета влучила у ціль. Фактично, у мене вже є один: у класі Obstacle є метод contains(), оскільки ціль також може буде реалізована як своєрідна перешкода. Це просто перешкода, яку ракета хоче вразити! Я можу використовувати метод contains(), щоб встановити нову змінну hitTarget у кожному об’єкті Rocket. Якщо ракета потрапить у ціль, то зупиниться так само як вона зупиняється, коли потрапляє у перешкоду:

    if (target.contains(this.position)) {
      this.hitTarget = true;
    }

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

    if (!this.hitTarget) {
      this.finishCounter++;
    }
  }

Я хочу, щоб пристосованість також була обернено пропорційною до значення finishCounter. Щоб досягти цього, я можу покращити оцінювальну функцію за допомогою наступних змін:

  calculateFitness() {

    this.fitness = 1 / (this.finishTime * this.recordDistance);

    this.fitness = pow(this.fitness, 4);

    if (this.hitObstacle) {
      this.fitness *= 0.1;
    }

    if (this.hitTarget) {
      this.fitness *= 2;
    }

  }

Обидва вдосконалення включено в код прикладу 9.3.

Цей приклад можна покращити й розширити багатьма способами. Наступні вправи пропонують ідеї та завдання для глибшого дослідження ГА. Подумайте що ще ви можете спробувати?

Інтерактивний відбір

Карл Сімс — дослідник комп’ютерної графіки й візуальний художник, який багато працював із ГА-мами. Він також добре відомий своєю роботою з системами частинок! Одним із його інноваційних еволюційних проєктів є музейна інсталяція “Galapagos”. Початково ця інсталяція була встановлена в NTT InterCommunication Center в Токіо у 1997 році. Вона складається з 12 моніторів на яких відображаються комп’ютерні зображення. Ці зображення розвиваються з часом, дотримуючись кроків ГА відбору і відтворення.

Інновація тут полягає не у використанні ГА, а скоріше у стратегії функції оцінювання пристосованості. Перед кожним монітором на підлозі розташований датчик, який може визначити присутність відвідувача, який дивиться на екран. Придатність зображення пов’язана з тривалістю часу, протягом якого глядачі дивляться на зображення. Цей підхід відомий як інтерактивний відбір — ГА зі значеннями пристосованості, які призначають люди.

Інтерактивний відбір не обмежується мистецькими інсталяціями, а досить поширений у цифрову епоху оцінок і оглядів, створених користувачами. Чи можете ви уявити собі створення ідеальної пісні на основі ваших рейтингів у Spotify? Чи ідеальної книги за відгуками з Goodreads? Проте, дотримуючись природної теми книги, я проілюструю, як працює інтерактивний відбір, використовуючи популяцію цифрових квітів, як на малюнку 9.12.

Кожна квітка матиме набір властивостей: колір пелюстки, розмір пелюстки, кількість пелюсток, колір серцевинки, розмір серцевинки, довжину стебла і колір стебла. ДНК квітки (генотип) — це масив десяткових чисел від 0 до 1, з окремим значенням для кожної властивості:

class DNA {

  constructor() {

    this.genes = [];
    for (let i = 0; i < 14; i++) {

      this.genes[i] = random(0, 1);

    }

  }

Фенотип — це клас Flower, який включає екземпляр об’єкта DNA:

class Flower {

  constructor(dna) {

    this.dna = dna;

    this.fitness = 1;

  }

Коли прийде час малювати квітку, я скористаюся функцією map() із p5.js, щоб перетворити будь-яке значення гена у відповідний діапазон розмірів у пікселях або значення кольору. (Я також використовую функцію colorMode(RGB, 1), щоб встановити діапазон RGB значень від 0 до 1.)

  show() {

    let genes = this.dna.genes;

    let petalColor  = color(genes[0], genes[1], genes[2], genes[3]);
    let petalSize   = map(genes[4], 0, 1, 4, 24);
    let petalCount  = floor(map(genes[5], 0, 1, 2, 16));
    let centerColor = color(genes[6], genes[7], genes[8]);
    let centerSize  = map(genes[9], 0, 1, 24, 48);
    let stemColor   = color(genes[10], genes[11], genes[12]);
    let stemLength  = map(genes[13], 0, 1, 50, 100); 

До цього моменту я не зробив нічого нового. Це той самий процес, який я використовував у кожному прикладі ГА. Різниця полягає в тому, що я не збираюся писати функцію fitness() для обчислення оцінки придатності на основі математичної формули. Натомість я попрошу призначити придатність у користувача.

Спосіб, як саме попросити користувача призначити придатність, найкраще розглядати як дизайн-проблему взаємодії, і це насправді не входить до сфери цієї книги. Я не збираюся розпочинати докладну дискусію про те, як запрограмувати повзунки чи створити власні апаратні циферблати або вебпрограму, яка дозволить людям виставляти результати онлайн. Спосіб отримання показників для оцінки придатності залежить від вас і конкретної програми, яку ви розробляєте. Для цієї демонстрації я буду надихатися інсталяцією Galapagos і просто збільшуватиму значення придатності квітки щоразу, коли на неї буде наведено курсор. А після натискання на кнопку Evolve Next Generation буде створюватися наступне покоління квітів.

Подивіться, як етапи ГА — відбір і відтворення — застосовуються у функції nextGeneration(), яка запускається подією mousePressed(), яку під’єднано до елементу button. Придатність підвищується у методі rollover() з класу Population. Метод виявляє присутність курсора над будь-якою квіткою. Ви можете знайти докладнішу інформацію про програму у супровідному прикладі коду на вебсайті книги.

let population;

function setup() {

  createCanvas(640, 240);

  colorMode(RGB, 1);

  let populationSize = 8;

  let mutationRate = 0.05;

  population = new Population(mutationRate, populationSize);

  button = createButton("evolve new generation");
  button.mousePressed(nextGeneration);
  button.position(10, 210);

}

function draw() {

  background(1);

  population.show();

  population.rollover(mouseX, mouseY);
  textAlign(LEFT);
  text("Generation " + population.generations, 12, height - 40);

}

function nextGeneration() {
  population.selection();
  population.reproduction();
}

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

Однак більш важливою проблемою тут є проблема часу. У природному світі еволюція відбувається протягом мільйонів років. У світі комп’ютерного моделювання перших прикладів цього розділу популяції здатні розвивати свою поведінку відносно швидко, оскільки нові покоління продукуються алгоритмічно. У прикладі з котами, що друкують, нове покоління народжується у кожному запуску функції draw() (приблизно 60 разів на секунду). Кожне покоління інтелектуальних ракет має термін життя 250 кадрів — це все лише мить ока у порівнянні з еволюційним часом. Однак у випадку інтерактивного відбору вам доведеться сидіти й чекати, поки хтось оцінить кожен елемент популяції, перш ніж ви зможете перейти до наступного покоління. Оцінка великої популяції була б невиправдано виснажливою для користувача — не кажучи вже про те, скільки поколінь ви могли б витримати?

Ви, звичайно, можете обійти цю проблему розумними способами. Виставка Сімса “Galapagos” приховала процес оцінювання від глядачів, оскільки це відбувалося через звичайну поведінку перегляду творів мистецтва у галереї. Створення вебдодатку, який дозволить багатьом людям розподілено оцінювати сукупність, також є хорошою стратегією для швидкого досягнення потрібних оцінок великих популяцій.

Зрештою, ключ до успішної інтерактивної системи відбору зводиться до тих самих аспектів, які були встановлені раніше. Що таке генотип і фенотип? І як ви обчислюєте оцінку пристосованості або, у цьому випадку, яка ваша стратегія визначення придатності відповідно до взаємодії з користувачем?

Вправа 9.14

Ще одною з основоположних робіт Карла Сімса в галузі ГА-мів є “Evolved Virtual Creatures”. У цьому проєкті популяція цифрових істот у змодельованому фізичному середовищі оцінюється на предмет їх здатності виконувати такі завдання, як плавання, біг, стрибки, слідування і змагання з кубика рубіка. У проєкті використовується генотип на основі вузлів: ДНК істоти — це не лінійний список векторів чи чисел, а карта вузлів (дуже подібно до симуляції м’якого тіла з Розділу 6). Фенотип — це саме тіло істоти, мережа кінцівок, з’єднаних м’язами.

Чи можете ви створити ДНК квітки, рослини чи істоти як мережу частин? Однією з ідей є використання інтерактивного відбору для вдосконалення дизайну. Крім того, щоб створити спрощену 2D-версію істот Сімса, ви можете включити пружинні сили, можливо, за допомогою Toxiclibs.js або Matter.js. Що, якби істоти розвивалися відповідно до оцінювальної функції, пов’язаної з конкретною метою? Щоб дізнатися більше про підходи Сімса ви можете прочитати його статтю 1994 року і переглянути на YouTube відео “Evolved Virtual Creatures”.

Моделювання екосистеми

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

У нашому реальному світі, як я розказував на початку розділу, ми насправді не маємо виживання саме найпристосованіших, а маємо виживання тих хто розмножується. Істоти, які живуть довше, у багатьох випадках мають більше шансів на розмноження. Діти народжуються, живуть деякий час, можливо, самі народжують дітей, а може і ні, а потім помирають. Чи міг би я написати програму, яка б відобразила цей більш реалістичний погляд на еволюційну біологію?

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

Я почну з уявлення простого сценарію. Я створю створіння під назвою bloop (блуп), кульки, яка рухається по полотну відповідно до шуму Перліна. Створіння матиме радіус і максимальну швидкість. Чим меншого воно розміру, тим швидше буде рухатися, чим більшого — тим повільніше:

class Bloop {

  constructor(x, y) {

    this.position = createVector(x, y);

    this.xoff = random(1000);
    this.yoff = random(1000);

    this.maxSpeed = 5;

    this.r = 8;

  }

  update() {
    let vx = map(noise(this.xoff), 0, 1, -this.maxspeed, this.maxspeed);
    let vy = map(noise(this.yoff), 0, 1, -this.maxspeed, this.maxspeed);
    this.xoff += 0.01;
    this.yoff += 0.01;
    let velocity = createVector(vx, vy);
    this.position.add(velocity);
  }

  show() {
    stroke(0);
    fill(127);

    circle(this.position.x, this.position.y, this.r * 2);

  }

}

Як зазвичай, популяція блупів може зберігатися у масиві, яким своєю чергою може керувати клас під назвою World:

class World {

  constructor(populationSize) {

    this.bloops = [];
    for (let i = 0; i < populationSize; i++) {

      this.bloops.push(new Bloop(random(width), random(height)));

    }

  }

Поки що я просто повторюю системи частинок як у Розділі 4. У мене є сутність під назвою Bloop, яка рухається по полотну, і клас під назвою World, який керує змінною кількістю цих сутностей. Щоб перетворити це на систему, яка розвивається, мені потрібно додати до свого світу дві додаткові функціональності:

• Вмирання блупів.
• Народження блупів.

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

class Bloop {

  constructor(position, dna) {

    this.health = 100;

    /* Інша частина конструктора */

Кожного разу при роботі методу update() блуп-сутність втрачатиме частину здоров’я:

  update() {

    this.health -= 0.2;
    /* Інша частина методу update() */

Якщо значення health падає нижче 0, блуп гине:

  dead() {
    return (this.health < 0.0);
  }

Це хороший початок, але насправді я реально нічого не досяг. Зрештою, якщо всі блуп-створіння починають своє існування маючи 100 очок здоров’я і втрачають його з однаковою швидкістю, то всі вони житимуть однаково довго і помруть разом. Якщо кожний окремий блуп живе однаковий проміжок часу, то кожний з них має однакові шанси на розмноження і тому еволюційних змін не відбудеться.

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

Припустімо, що у мене є масив векторних позицій під назвою food. Я міг би перевірити близькість кожного блупа до кожної позиції їжі. Якщо блуп достатньо близько, тоді він їсть їжу (яка потім видаляється зі світу) і збільшує своє здоров’я:

  eat(food) {

    for (let i = food.length - 1; i >= 0; i--) {

      let distance = p5.Vector.dist(this.position, food[i]);

      if (distance < this.r) {

        this.health += 100;
        food.splice(i, 1);

      }

    }

  }

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

Тепер, коли світ побудовано, настав час додати компоненти, необхідні для еволюції. Насамперед необхідно встановити генотип і фенотип.

Генотип і фенотип

Здатність блупа знаходити їжу пов’язана з двома змінними: розміром і швидкістю (див. малюнок 9.13). Більшим блупам буде легше знаходити їжу просто тому, що їх розмір дозволить їм частіше перетинатися з їжею. А швидші блупи можуть знайти більше їжі, оскільки вони можуть покрити більше простору за коротший період часу.

Оскільки розмір і швидкість обернено пропорційні (великі блупи повільні, маленькі — швидкі), мені потрібен генотип лише з одним числом.

class DNA {

  constructor() {

    this.genes = [];
    for (let i = 0; i < 1; i++) {
      this.genes[i] = random(0, 1);
    }

  }

class Bloop {

  constructor(x, y, dna) {

    this.dna = dna;

    this.maxSpeed = map(this.dna.genes[0], 0, 1, 15, 0);
    this.r = map(this.dna.genes[0], 0, 1, 0, 25);
    /* Вся інша частина ініціалізації об’єкта */

Зауважте, що властивість maxSpeed зіставляється з діапазоном значень від 15 до 0. Блуп зі значенням гена 0 рухатиметься зі швидкістю 15, тоді як блуп зі значенням гена рівним 1 не рухатиметься взагалі (матиме швидкість 0).

Відбір і розмноження

Тепер, коли я маю генотип і фенотип, мені потрібно перейти до розробки методу відбору блупів для батьківства. Раніше я казав, що чим довше живе блуп, тим більше у нього шансів розмножитися. Тривалість життя блупа — це його пристосованість.

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

Простішим варіантом було б, щоб блупи клонували самі себе, не потребуючи партнера і миттєво створюючи новий блуп з таким же генетичним набором. Наприклад, що якщо в будь-який момент блуп матиме 1 відсоток імовірності до самовідтворення? За допомогою цього алгоритму відбору, чим довше живе блуп, тим більша ймовірність, що він клонує себе. Це еквівалентно тому, що чим більше разів ви граєте в лотерею, тим більша ймовірність того, що ви виграєте (хоча, на жаль, ваші реальні шанси виграти в лотерею все ще дорівнюватимуть нулю).

Щоб реалізувати цей алгоритм відбору, я можу написати метод у класі Bloop, який кожного кадру вибиратиме випадкове число. Якщо число менше від 0.01 (1 відсоток), то народжуватиметься новий блуп:

  reproduce() {

    if (random(1) < 0.01) {
      /* Створення дочірнього блупу! */
    }

  }

  reproduce() {

    if (random(1) < 0.005) {

      let childDNA = this.dna.copy();

      childDNA.mutate(0.01);

      return new Bloop(this.position.copy(), childDNA);

    }

  }

Зверніть увагу, що я знизив імовірність відтворення з 1 відсотка до 0.05. Ця зміна має істотне значення, оскільки з високою ймовірністю відтворення система швидко переповниться, але при занадто низькій імовірності популяція, скоріш за все швидко вимре.

Реалізувати метод copy() у класі DNA доволі легко за допомогою стандартного методу масиву slice(), який створює новий масив, копіюючи елементи з поточного масиву:

class DNA {

  copy() {

    let newDNA = new DNA();

    newDNA.genes = this.genes.slice();

    return newDNA;

  }

}

За допомогою фрагментів коду для відбору і відтворення я можу завершити клас World, щоб керувати списком об’єктів Bloop, а також об’єктом Food, який містить список позицій для їжі (які я намалюю у вигляді маленьких квадратів).

Перш ніж запускати приклад, приділіть хвилинку, щоб поміркувати й здогадатися, до якого розміру та швидкості блупів буде розвиватися система. Я обговорю ці деталі після коду.

let world;

function setup() {

  createCanvas(640, 240);

  world = new World(20);

}

function draw() {

  background(255);

  world.run();

}

class World {

  constructor(populationSize) {

    this.bloops = [];
    for (let i = 0; i < populationSize; i++) {
      let position = createVector(random(width), random(height));
      let dna = new DNA();
      this.bloops.push(new Bloop(position, dna));
    }

    this.food = new Food(populationSize);

  }

  run() {

    this.food.run();

    for (let i = this.bloops.length - 1; i >= 0; i--) {

      let bloop = this.bloops[i];
      bloop.run();
      bloop.eat(this.food);

      if (bloop.dead()) {
        this.bloops.splice(i, 1);
        this.food.add(bloop.position);
      } else {

        let child = this.bloops[i].reproduce();
        if (child) {
          this.bloops.push(child);
        }

      }

    }

  }

}

Якщо ви вирішили, що блупи будуть середнього розміру з середньою швидкістю, то маєте рацію. Просто через спроєктованість цієї системи великі блупи занадто повільно знаходять їжу. А швидкі блупи занадто малі, щоб знайти їжу. Ті, які здатні прожити найдовше, як правило, знаходяться посередині, вони достатньо великі та швидкі, щоб знайти їжу (але не надто великі чи надто швидкі). Також існують деякі аномалії. Наприклад, якщо купа великих блупів опиниться в одному місці (і ледь рухатиметься, оскільки вони такі великі), усі вони можуть раптово вимерти, залишивши багато їжі для одного великого блупа, який випадково опиниться там, щоб поїсти й це дозволить таким чином мініпопуляції великих блупів підтримувати себе певний період часу в одному положенні.

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

Проєкт “Екосистема”

Додайте здатність вашої екосистеми до еволюційних змін, спираючись на приклади цього розділу:

• Додайте у свою екосистему популяцію хижаків. Біологічну еволюцію між хижаками та здобиччю (або паразитами й господарями) часто називають перегонами озброєнь під час якої створіння постійно пристосовуються та протидіють одне одному. Чи можете ви досягти такої поведінки у системі з кількох створінь?
• Як би ви здійснили схрещування і мутацію між двома батьківськими об’єктами в екосистемі, змодельованій по прикладу блупів? Спробуйте застосувати алгоритм, щоб дві істоти спаровувалися, перебуваючи на певній відстані.
• Спробуйте використати ваги для кількох керувальних сил у якості ДНК створіння. Чи можете ви створити сценарій за яким створіння еволюціонують, щоб співпрацювати одне з одним?
• Однією з найбільших проблем у моделюванні екосистеми є досягнення балансу. Ймовірно, ви побачите, що більшість ваших спроб призводять або до масового перенаселення (з наступним масовим вимиранням), або до масового вимирання. Які способи можна застосувати, щоб досягти балансу? Розгляньте можливість використання ГА для розробки оптимальних параметрів для екосистеми.