Онлайн калькулятор Як з мухи зробити слона
Послідовно перетворює одне 4-х літерне слово на інше, змінюючи одну літеру попереднього слова на кожному кроці.
Ця сторінка існує завдяки наступним особам
- Як з мухи зробити слона. - Автор
- Калькулятор : Перетворення 4-х буквених слів за допомогою генетичного алгоритму - Автор
Нещодавно дитина принесла зі школи завдання. У п'ятому класі на уроках української словесності дітям задають такі завдання: скласти ланцюжок слів, кожне наступне з яких відрізняється від попереднього лише на одну літеру. Спочатку задано перше та останнє слово ланцюжка. Вирішивши припинити муки коханої доньки, яка протягом кількох годин марно намагалася зробити з мухи слона, я написав наступний калькулятор:
Перетворення 4-х буквених слів за допомогою генетичного алгоритму
Слово з якого треба отримати друге слово
Слово, в яке потрібно перетворити перше слово
Максимальна кількість елементів у кожному поколінні
Опис рішення
Спочатку я застосував "грубу силу" і спробував вирішити завдання в лоб. Суть мого наївного методу зводилася до побудови дерева слів, отриманих шляхом перебору всіх літер українського алфавіту та підстановки їх замість однієї з літер попереднього слова (див. рисунок).
З першого разу, звичайно, нічого не запрацювало — мій рекурсивний алгоритм швиденько переповнив обмежений стек джаваскрипту. Перетворення рекурсивного алгоритму на циклічний дало найбільш зручний результат - муха була трансформована в слона хвилин так за десять.
Отриманий результат придатний для доньки, але не для мене. Дотого ж, поки працювала програма, у мене було достатньо часу подумати над поліпшенням алгоритму та гіпотетичною можливістю мухи еволюціонувати у слона. Ця програмно-біологічна маячня в кінцевому підсумку привела мене до генетичного алгоритму, який дуже доречно підійшов для вирішення цього завдання і переродив муху в слона протягом декількох секунд.
Генетичний алгоритм
Генетичним алгоритм був названий так через подібність процесу пошуку рішення з біологічною еволюцією. Розв'язанням задачі є вектор слів, що задовольняють певний критерій (хромосома). На кожному кроці ми породжуємо кілька векторів (популяцію), після чого здійснюємо відбір найбільш придатних варіантів (життєздатних особин), т. е. виконуємо селекцію. На наступному етапі раніше отримані варіанти знову видозмінюються, породжуються нові варіанти (відбувається мутація) і так доти, поки не буде виконаний критерій зупинення алгоритму (у нашому випадку муха перетворюється на слона).
По суті, мій початковий алгоритм теж можна було віднести до генетичних (селекція здійснювалася шляхом перевірки за словником), але так як кількість породжених варіантів збільшувалася на кожному кроці, то зрештою всієї популяції нових особин для подальшого існування не залишалося життєвого простору (ресурсів процесора ).
У модифікованому алгоритмі було застосовано покращена функція селекції, яка відбирає лише схожі на кінцеве слово варіанти. Кількість найбільш життєздатних варіантів задається параметромРозмір популяції, що менше це число, то швидше працює алгоритм, що більше — то якісніше виходить результат.
Як додатковий критерій зупинки було введено обмеження на максимальний розмірланцюжка, для цього було введено ще один параметр. Алгоритм зупиниться, якщо після відтворення заданого числа поколінь не буде отримано результат.
Функція пристосованості (схожість поточного слова на кінцеве) оцінювала кожен варіант за 12 бальною шкалою.
- за кожну букву, що збігається за становищем і значенням з кінцевим результатом, нараховувалося 3 бали
- якщо голосна буква слова знаходилася на тому ж місці, що і інша голосна буква шуканого слова - 2 бали
- і один бал нараховувався просто за наявність голосної літери. Таким чином, кінцеве слово СЛОН оцінювалося в 12 балів, а початкова МУХА всього в 2.
Охочі детальніше ознайомитися з алгоритмом, можуть це зробити, шляхом дослідження вмісту функції calculate з javascript'а цієї сторінки.
Один наш користувач, який захоплюється побудовою подібних ланцюжків, попросив зробити Перетворення 5-літерних слів перестановкою однієї літери. Цей онлайн калькулятор бере 5-и літерні слова з довідника: Слова з 5-ти букв