Генетичне програмування («Yet Another Велосипед» Edition)


Давайте на деякий час відвернемося від чергового "мови-вбивці C++", приголомшливих синтетичних тестів продуктивності який-небудь NoSQL-ой СУБД, хайпи навколо нового JS-фреймворку, і зануримося в світ "програмування заради програмування".

Передмова
Березень починався для мене з читання статей про те, що Хабр вже торт. Судячи по відгуку, тема була розкрита наболіла. З іншого боку, мені вдалося дещо для себе винести з цього: "ви і є Опір", якщо ви це читаєте — ви і є Хабр. І зробити його цікавішим (або хоча б різноманітніше, відійти від існуючої тенденції на агрегацію рекламних постів, околоализарщины і корпоративних блогів) можна тільки силами рядових користувачів. У мене як раз був на той момент невеликий проект, хоч і вимагає серйозного доопрацювання, про який мені захотілося розповісти. І я вирішив — за місяць (наївний!) напишу статтю. Як ми бачимо, зараз вже середина кінець квітня початок травня травень у розпалі, звинувачувати в цьому можна як мою лінь, так і нерегулярність вільного часу. Але все ж, стаття побачила світ! Що цікаво, поки я працював над статтею, вже встигли вийти дві схожі: Що таке граматична еволюція + легка реалізація, Символьна регресія і ще один підхід. Не будь я таким слоупоком, можна було вписатися і оголосити місяць генетичних алгоритмів :)
Так, я усвідомлюю повною мірою, що на дворі 2016 рік, а я пишу такий длиннопост. Ще й малюнки виконані в стилі "курка лапою" пером на планшеті, з шрифтами Comics Sans для гиків xkcd.

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


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

Тепер WE NEED TO GO DEEPER. Перше наближення:

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

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

Тепер давайте розглянемо основний цикл докладніше:

Що стало помітно в другому наближенні? По-перше, ми оперуємо не одним, а групою рішень, яку назвемо покоління. По-друге, з'явилися нові сутності:
  • Генетичні операції (так-так, одвічна плутанина з перекладом, англійське "operator" суть наше "операція") потрібні щоб отримати нове рішення на базі попередніх. Зазвичай це схрещування (випадкове поєднання двох розрізняються рішень) і мутація (випадкове зміна одного рішення).
  • Функція пристосованості (мені більше сподобалося фітнес-функція) потрібна для оцінки ступеня нашої задоволеності результатом рішення.Кому на розум прийшло TDD?справді, , коли якщо ми навчимося легко писати тести які відповідають не тільки на питання, завалив наш код тест чи ні, і дають вимірну оцінку, наскільки близько він підійшов до успіху, ми станемо на крок ближче до самопишущимся програмами. Не здивуюся, якщо такі спроби вже були.
  • Селекція описує принципи відбору рішень в наступне покоління.
Недоліки
Як би багатообіцяюче все звучало, у обговорюваного підходу до вирішення завдань повно фатальних фундаментальних недоліків. Практикуючись, я спіткнувся, напевно, про всі відомі підводні камені. Самий головний, на мій погляд, з них: погана масштабованість. Швидкість зростання витрат на обчислення в середньому перевищує швидкість зростання вхідних даних (як у наївних алгоритми сортування). Про решту недоліки я розповім попутно далі.



Практика

Вибір мови
вибрано Ruby. Ця мова відносно недавно заповнив у моїх справах нішу, яку традиційно займав Пітон, і він настільки мене зачарував, що я неодмінно вирішив познайомитися з ним ближче і отримати більше досвіду. А тут така можливість! Люблю вбивати N (N > 1) зайцев. Не виключаю, що мій код може місцями викликати посмішки, якщо не фейспалмы у олдових кубістів (ні, вибачте, але саме кубістів, інші варіанти — тролінг).


Генотип
Першою думкою було те, що саме в мові є eval, то генотип рішення може без будь-яких хитрощів будуватися з довільних символів (виступають у ролі генів), і на виході ми матимемо скрипт інтерпретується в microsoft самим Ruby. Другою думкою було те, що на еволюцію рішень з такими високими ступенями свободи може піти реально багато років. Так що я навіть не ворухнув пальцем в цьому напрямку, і думаю, не помилився. Можна спробувати даний підхід років так через 30, якщо збережеться закон Мура.
Еволюція у результаті була укладена в досить жорсткі рамки. Генами рішення є високоорганізовані токени з можливістю вкладеності (побудови деревоподібної структури).
У першому експерименті, де ми будемо говорити про рішення як математичних виразах, токени це константи, змінні, і бінарні операції (не знаю, наскільки легітимний термін, в контексті проекту "бінарна операція" означає дію над двома операндами (наприклад, додавання).
До речі, я вирішив частково залишити сумісність з eval, тому якщо запитати рядковий подання сертифіката (через стандартний to_s), то можна отримати цілком пристойну рядок для інтерпретації. Наприклад:
f = Formula::AdditionOperator.new(Formula::Variable.new (x), Formula::IntConstant.new(5))
f.to_s # "(x+5)"

Так і наочніше так.


Генетичні операції
В якості основного і єдиного способу зміни генотипу рішень я вибрав мутацію. Головним чином тому, що вона простіше формалізується. Не виключаю, що розмноження схрещуванням могло б бути ефективнішою (а якщо судити на прикладі живої природи, то, схоже, так і є), проте в її формалізації криється багато підводних каменів, і, скоріше всього, накладаються певні обмеження на саму структуру генотипу. Загалом, я пішов найпростішим шляхом.
У розділах статті, присвячених опису кінцевих експериментів, детально розписані правила мутації рішень. Але є і загальні риси, про які хочеться розповісти:
  • Іноді (насправді часто буває, що лише за один крок мутації неможливо домогтися поліпшення результатів, хоча мутація йде, в цілому, у вірному напрямку. Тому у фазі застосування генетичних операцій рішень дозволено мутувати необмежену кількість разів за хід. Ймовірність виглядає так:
    — 50% — одна мутація
    — 25% — дві мутації
    — 12.5% — три мутації
    — і т. д.
  • Буває, за кілька кроків мутант може стати ідентичним з батьків, або різні батьки отримують однакових мутантів; такі випадки присікаються. Більше того, я взагалі вирішив підтримувати сувору унікальність рішень в рамках одного покоління.
  • Іноді мутації породжують абсолютно непрацездатні рішення. З цим боротися аналітично вкрай складно, зазвичай, проблема розкривається тільки в момент їх оцінки фітнес-функцією. Я дозволяю таким рішенням бути. Все одно велика частина з часом зникне в результаті селекцій.


Фітнес-функція
З її реалізацією ніяких проблем немає, але є один нюанс: складність фітнес-функції зростає практично нарівні з зростанням складності розв'язуваної задачі. Щоб вона була здатна виконувати свою роботу в розумні терміни, я спробував реалізувати її настільки просто, наскільки можливо.
Нагадаю, що генеруються рішення повертають певний результат на основі певного набору вхідних даних. Так от, мається на увазі, що ми знаємо, який ідеальний(еталонний) результат потрібно отримати певний набір вхідних даних. Результати є исчислимыми, а значить, ми здатні видати кількісну оцінку якості певного рішення, провівши порівняння повернутого результату з еталонним.
Крім цього, кожне рішення має непрямими характеристиками, з яких я виділив, на мою думку, основну — ресурсомісткість. У деяких завданнях ресурсомісткість рішення буває залежна від набору вхідних даних, а в інших — ні.
Разом, фітнес-функція:
  • обчислює наскільки результати рішення відрізняються від еталонних
  • визначає, наскільки ресурсомісткі рішення
Про ресурсоємностіВ ранніх прототипах я пробував заміряти витрачений на проходження випробувань процесорний час, але навіть при тривалих (десятки мілісекунд) прогонах спостерігався розкид в ±10% часу на одне і те ж рішення, внесений операційною системою, з періодичними викидами +в 100-200%.
Так що в першому експерименті ресурсомісткість обчислюється сумарної складністю генотипу, а в другому підрахунком реально виконаних інструкцій коду

Селекція
Кожне покоління містить не більш ніж N рішень. Після застосування генетичних операторів, у нас максимум 2N рішень, притому в наступне покоління пройде, знову ж таки, не більше N з них.
За яким принципом формується наступне покоління рішень? Ми на етапі, коли кожне з рішень вже отримало оцінку фітнес-функції. Оцінки, зрозуміло, можна порівнювати один з одним. Таким чином, ми можемо відсортувати поточне покоління рішень. Далі бачиться логічним просто взяти X найкращих рішень, і сформувати з них наступне покоління. Однак, я вирішив не зупинятися на цьому, і включати в нове покоління Y випадкових рішень, що залишилися.
Наприклад, якщо X = Y, щоб рішенням пройти в наступне покоління, йому потрібно опинитися серед 25% кращих, або викинути 3 на тригранному кубику (якби такий існував). Досить гуманні умови, чи не так?
Так от, включення випадково вижили в наступне покоління потрібно для збереження видового різноманіття. Справа в тому що довго тримаються серед кращих схожі один на одного рішення витискає інші, і чим далі, тим швидше процес, адже часто буває що домінуюча гілка виявляється тупиковою.
Параметри X і Y, зрозуміло, є налаштованим. Я проганяв тести, як з випадковими вижили, так і без них, і довів справедливість їх додавання в алгоритм: в окремих випадках (при пошуку рішень підвищеної складності), вдавалося досягти хороших результатів з їх використанням (притому сумарна витрачається на пошук рішень потужність залишалася постійної, наприклад, X1 = 250, Y1 = 750 проти X2 = 1000, Y2=0).
Умови перемоги
Тут криється заковика: як зрозуміти, що пора закінчувати? Припустимо, рішення задовольняє нас за точністю результатів, але як бути з трудомісткістю? Раптом алгоритм зараз попрацює і видасть рішення за розфарбовування графів за O(n)? Утрирую, звичайно, але критерій зупинки роботи необхідно формалізувати. В моїй реалізації виконання алгоритму закінчується, коли Top 1 рішення не змінюється певну кількість поколінь (скорочено R — rounds). Відсутність ротації означає, що, по-перше, не знайшлося альтернативного рішення, яке б змогло перевершити краще поточне рішення; по-друге, краще поточне рішення не змогло породити поліпшену мутацію себе протягом заданого часу. Кількість поколінь, через яке наступає перемога кращого рішення, зазвичай велике число — щоб дійсно переконатися в тому, що еволюція не здатна просунутися далі, потрібна зміна кількох сотень (кількість варіюється залежно від складності самої задачі) поколінь.
На жаль, незважаючи на численні заходи, випадки коли еволюція заходить у глухий кут все ж бувають. Це відома проблема генетичних алгоритмів, коли основна популяція рішень зосереджується на локальному оптимумі, ігноруючи, в підсумку, шуканий глобальний оптимум. На це можна відповісти грою з параметрами: зменшенням квоти для переможців, збільшенням квоти для випадкових, і збільшенням часу домінування для перемоги, параллелизацией незалежних один від одного поколінь. Але все це вимагає потужностей\часу.
Конкретна реалізація
Як прийнято, все викладено на гітхабі (правда, поки без доків).
Тепер про те, що ми побачимо в конкретно моєї велосипеді реалізації:

  1. Вводиться поняття еталона (Model). Ставимося до нього, як до чорного ящика, з допомогою якого на основі набору вхідних даних (Input), можна отримати еталонний результат(Model Result).
  2. Справа (Case) просто містить набір вхідних даних і еталонний результат.
  3. Збираємо набір справ (Case group) на підставі сукупності вхідних даних (Input group).

  4. Дзвінок (або випробування) (Challenge) — це комплекс дій з проходження сформованого раніше набору справ. На плечах випробування також робота з оцінки результатів проходження, і порівнянні оцінок.
  5. У нас з'являється претендент (Challenger), що має певне рішення (Solution). Претендент вимовляє сакраментальне "виклик прийнятий!", і дізнається свою ступінь придатності (Score).

  6. у результаті У нас вибудовується ланцюжок композиції — рішення(Solution — надає рішення певного виду завдань) -> претендент(Challenger — проходить випробування) -> штам(Strain — беруть участь в природному відборі і еволюції(див. нижче))
  7. Є природний відбір (Natural Selection), який включає в себе випробування, і фільтрує надходить до нього групу штамів за заданими правилами.

  8. На верхньому рівні розташовується еволюція (Evolution), що, включаючи в себе природний відбір, керує всіма життєвими циклом штамів.
  9. Результатом роботи еволюції є штам-переможець, якого ми вшановуємо як героя, а потім уважно вивчаємо його, в тому числі і його родовід. І робимо висновки.
Така в загальних рисах моя реалізація генетичного алгоритму. За рахунок абстрактних класів (Ruby, ага >_<), вдалося написати в цілому незалежний від конкретної області завдань код.
У подальших експериментах дописувалися потрібні Input, Model, Solution, Score (що, звичайно, чимало).


Експеримент Перший: Формули
Взагалі, вірніше було назвати Перший Експеримент: Арифметичні вирази, але коли я вибирав ім'я базового класу виразів, то, недовго думаючи, зупинився на
Formula
, і далі в статті я буду називати арифметичні вирази формулами. В експерименті ми вводимо формули-еталони (та сама Model), що містять одну або кілька змінних величин. Наприклад:
x2 — 8*x + 2.5
У нас є набір значень змінних (Input Group, ага), наприклад:
  • x = 0;
  • x = 1;
  • x = 2;
  • ....
  • x = 255;
РішенняSolutions), які ми будемо порівнювати з еталонами, представляють із себе такі ж формули, але створювані випадково — послідовно мутуючі з базової формули (зазвичай це просто
x
). Оцінкою (Score) якості рішення є середнє відхилення результату від результату еталона, плюс ресурсомісткість рішення (сумарна вага операцій і аргументів формули).
Мутація формул
Як було згадано раніше, токенами формул є константи, змінні, і бінарні операції.
Як відбувається мутація формул? Вона зачіпає один з токенів, що містяться у формулі, і може піти трьома шляхами:
  1. grow — зростання, ускладнення
  2. shrink — зменшення, спрощення
  3. shift — видозміна з умовним збереженням складності
Ось таблиця відбувається з різними типами формул при різних видах мутації:






Формула → Мутація ↓ Константа Мінлива Бінарна операція grow стає змінною, або включається в нову випадкову бінарну операцію (з випадковим другим операндом) в нову випадкову бінарну операцію (з випадковим другим операндом) включається в нову випадкову бінарну операцію (з випадковим другим операндом) shrink неможливо зменшити, так що застосовуємо до неї операцію shift стає константою замість операції залишається лише один з операндів shift змінює своє значення на випадкову величину, що може поміняти тип (Float<->Int) стає іншої випадкової змінної (якщо це допустимо в даному контексті) або операнди міняються місцями, або змінюється вид операції, або відбувається спроба скорочення операції
Примітка 1 Скорочення формул це спроба заздалегідь провести операції над константами, де це можливо. Наприклад, "
(3+2)
" отримати "
5
", а "
8/(x/2)
" отримати "
(16/x)
". Завдання несподівано виявилася настільки нетривіальна, що змусила мене писати прототип рішення з вичерпним юнит-тестомі то, я не добився цього рекурсивного рішення, достающего константи для скорочення з будь-якої глибини. Розбиратися в цьому було захоплююче, але в якийсь момент мені довелося зупинити себе і обмежитися досягнутим рішенням, так як я дуже відхилився від основних завдань. У більшості ситуацій, скорочення і так повноцінно працює.
Примітка 2 У мутації бінарних операцій є особливість, в силу того, що операції мають вкладені в себе інші формули-операнди. Мутувати і операцію, і операнди — занадто велика зміна для одного кроку. Так що випадковим чином визначається, яка подія відбудеться: з імовірністю 20% мутує сама бінарна операція, з вірогідністю 40% мутує перший операнд, і з рештою 40% ймовірністю, мутує другий операнд. Не можу сказати, що співвідношення 20-40-40 ідеально, можливо слід було б ввести кореляцію ймовірності мутації операції в залежності від їх ваг (фактично, глибини вкладеності), але поки що працює так.

Результати
Тепер заради чого, власне, все затівалося:
Перший еталон — простий поліном:
x2 — 8*x + 2.5
X приймає значення від 0 до 255, з кроком 1
R = 64, X = 128, Y = 128
Прогони виконуються по три рази, тут відображено кращий результат з трьох. (Зазвичай всі три рази видають ідентичні результати, але зрідка буває, що мутації заходять у глухий кут і не можуть досягти навіть заданої точності)
Результати вразили мене в саме серце :) За 230 (включаючи ті R раз, коли Top 1 не змінювався) поколінь було виведено таке рішення:
(-13.500+((x-4)2))
Повна родовідЯк ви пам'ятаєте, один між поколінням допускається і більш однієї мутації.
x
(x-0)
((x-0)-0.050)
(0.050-(x-0))
(0.050-(x-1))
(x-1)
(x-1.000)
((x-1.000)--0.010)
((x-1.000)-0)
((x-1.000)-(1*0.005))
((x-1.000)/(1*0.005))
((x-1.020)/(1*0.005))
((x-1.020)/(0.005*1))
((x**1.020)/(0.005*1))
((x**1)/(0.005*1))
((x**1)/(0.005*(0.005+1)))
((x**1)/(0.005*(0.005+1.000)))
(x**2)
((x--0.079)**2)
((x-0)**2.000)
(((x-0)**2.000)/1)
(((x-0)**2)/1)
((((x-0)**2)-0)/1)
(((x-0)**2)-0)
(((x-0)**2)-0.000)
(((x-(0--1))**2)-0.000)
(((x-(0--2))**2)-0.000)
(((x-(0--2))**2)+0.000)
(((x-((0--2)--1))**2)+0.000)
(((x-((0--2)--1))**2)+-0.015)
(((x-((0--2)--1))**2)+0)
((-0.057+0)+((x-((0--2)--1))**2.000))
((-0.057+0)+((x-3)**2.000))
(((-0.057+0)**-1)+((x-3)**2.000))
(((-0.057+0)**-1)+((x-4)**2.000))
(((-0.057+0)**-1.000)+((x-4)**2.000))
(((-0.057+0.000)**-1.000)+((x-4)**2.000))
(((x-4)**2.000)+((-0.057+0.000)**-1.000))
(((x-4)**2)+((-0.057+0.000)**-1.000))
(((x-4)**2)+((-0.057+0.000)**-0.919))
((((x-4)**2)+((-0.057+0.000)**-0.919))+-0.048)
((((-0.057+0.000)**-0.919)+((x-4)**2))+-0.048)
((((-0.057+0.000)**-0.919)+((x-4)**2))+-0.037)
(((-0.057**-0.919)+((x-4)**2))+-0.037)
(-0.037+((-0.057**-0.919)+((x-4)**2)))
(-13.524+((x-4)**2))
(-13.500+((x-4)**2))


тобто після того, як результати обчислень остаточно стали збігатися з еталонними, він погнався за ресурсоємністю, і провів перетворення, і в результаті формула на основі природного відбору виграє по компактності!
Цікаво те, що такий результат я отримав, фактично, за помилку. При перших прогонах був заборонені види мутації, при яких додавалася ще одна змінна x. Як не дивно, так спрацював навіть краще, ніж при повноцінної мутації. Ось результати, коли баг був виправлено:
  • R = 250, X = 250, Y = 750, Точність = 0.001, (вага результату 49)
    (2.500+((x-8)*x))
  • R = 250, X = 1000, Y = 0, Точність = 0.001, (вага результату 60)
    (((x-1)*(-7+x))-4.500)
В даному випадку, варіант з квотою для випадкових один раз спіткнувся, але все ж зміг видати більш оптимальний результат, ніж другий варіант, який кожен з прогонів проходив рівно й одноманітно. Тут для кожного наближення результату до оптимуму вистачає, в основному, одного кроку мутації. В такому випадку все виявиться не так просто!


Другий еталон — натуральний логарифм:
ln(1 + x)
x приймає значення від 0 до 25.5, з кроком 0.1
Наші рішення позбавлені можливості використовувати логарифми безпосередньо, але даний еталон розкладається в ряд Тейлора:

От і подивимося, чи зможе рішення відтворити такий ряд з заданою точністю.
Спочатку, пробував прогони з точністю до 0.001, але після кількох діб наполегливої роботи алгоритму розв'язання досягли точності тільки близько 0.0016, а розмір виразів прагнув до тисячі символів, і я вирішив знизити планку точністю до 0.01. Результати такі:
  • R = 250, X = 250, Y = 750, Точність = 0.01, (вага результату 149)
    ((((-1.776-x)/19.717)+(((x*x)-0.318)**0.238))-(0.066/(x+0.136)))
  • R = 250, X = 1000, Y = 0, Точність = 0.01, (вага результату 174)
    (((-0.025*x)+(((x*x)**0.106)**2))/(1+(0.849/((x*x)+1))))
Як бачите, у разі включення випадкових вижили для даного еталону знайдено менш ресурсномістке рішення, зі збереженням заданої точності. Не те, щоб це сильно схоже на ряд Тейлора, але воно вважає вірно :)


Третій еталон — синус, що задається в радіанах:
sin(x)
x приймає значення від 0 до 6.28, з кроком 0.02
Знову ж таки, еталон розкладається в ряд Тейлора:

В даному випадку, враховуючи що при будь-якому x результат приймає значення від -1 до 1, точність визначення 0.01 була більш серйозним випробуванням, але алгоритм впорався.
  • R = 250, X = 250, Y = 750, Точність = 0.01, (вага результату 233)
    ((((-0.092**x)/2.395)+(((-1.179**((((x-1)*0.070)+-0.016)*4.149))-(0.253**x))+0.184))**(0.944-(x/-87)))
  • R = 250, X = 1000, Y = 0, Точність = 0.01, (вага результату 564)
    (((x+x)*((x*-0.082)**(x+x)))+(((x+x)**(0.073**x))*((((1-(-0.133*x))*(-1-x))*((x/-1)*(-0.090**(x--0.184))))+(((((-1.120+(x*((x+1)*-0.016)))**(-0.046/((0.045+x)**-1.928)))+(-0.164-(0.172**x)))*1.357)**0.881))))
Знову ж таки, зважаючи підвищеної складності еталона, кращого результату домоглася версія алгоритму з пулом випадковим рішень.


Четвертий еталон — вираз з чотирма (збіг? не думаю) змінними:
2*v + 3*x — 4*y + 5*z — 6
Кожна з змінних приймає значення від 0 до 3 c кроком 1, всього 256 комбінацій.
  • R = 250, X = 250, Y = 750, Точність = 0.01, (вага результату 254)
    ((y*0.155)+(-2.166+(((((z*4)-(((y-(x+(y/-0.931)))*2)+-0.105))+((v+(v-2))+-0.947))+x)+(z+-1))))
  • R = 250, X = 1000, Y = 0, Точність = 0.01, (вага результату 237)
    ((-3+(v+z))+(((v+((x-y)+(((( z+z)-(((0.028-z) x)+(y+y)))-y)+z)))+x)+-2.963))
Всупереч моїм очікуванням, трудомісткість порівняно з першим еталоном підскочила дуже серйозно. Начебто еталон не складний, можна спокійно крок за кроком нарощувати рішення, наближаючи результат до потрібного. Однак точність у 0.001 була так і не осилена! Тут я й почав підозрювати, що проблеми з масштабуванням завдань у нашого підходу серйозні.
Підсумки
В цілому, я залишився скоріше не задоволений отриманими результатами, особливо, з еталонів 2 і 3. Знадобилися тисячі поколінь, щоб вивести в результаті громіздкі формули. Я бачу три варіанти, чому це трапляється:
  1. Недосконалий механізм скорочення — наприклад, не вистачає понад далекоглядного розкриття дужок\винесення за дужки. З цієї формули не привести в зручний вид.
  2. Занадто спонтанна мутація, причому, чим більше формула, тим менша ймовірність правильного подальшого розвитку. Я подумував про створення "вичерпного" (exhaustive) механізму мутації, коли формується група умовно всіх можливих мутантів на базі оригіналу, і над нею виробляється перед-селекція. Дійдуть руки перевірити здогад, чи покращить це алгоритм, поки невідомо.
  3. Принципова непрактичність такого методу для знаходження рішень складних завдань. Бути може, цей підхід не так вже далеко пішов від спроб написати "Війну і мир" силами армії мавп з друкарськими машинками. Бути може, складність, необхідність аналітичного підходу, це природне і невід'ємне властивість таких завдань.КурйозЗгадав, як років десять тому цікавився стисненням даних, пробував сили в написанні свого рішення. Журився, що ніяк не вдається стискати рандомные патерни, поки мене не просвітили :) Може, і тут так?


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

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

Вибір більш складного контринтуитивен — навіщо еволюції навмисне ускладнення при однаковій ефективності? Так що з селекцією теж проблеми.
Можливо, до того моменту, як буде дописана основна частина коду, я поміняю цілі на більш прості — наприклад, на алгоритм знаходження індексу максимального елемента масиву. Сподіваюся, так у генетичного алгоритму буде хоч якесь відчутну перевагу перед брутфорсным побудовою рішення з перебором всіх доступних комбінацій.
Якщо буде про який успіх доповідати, буде і друга частина статті.
Закінчимо на цьому задумливо невизначеній ноті. Велике спасибі за приділений час!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.