Как из мухи сделать слона.
Последовательно преобразует одно 4-х буквенное слово в другое, изменяя одну букву предыдущего слова на каждом шаге.
Недавно ребенок принес из школы задачку. В пятом классе на уроках русской словесности детям задают такие задания: составить цепочку слов, каждое последующее из которых, отличается от предыдущего всего на одну букву. Изначально задано первое и последнее слово цепочки. Решив прекратить мучения любимой дочки, которая в течение нескольких часов тщетно пыталась сделать из мухи слона, я написал следующий калькулятор:
Преобразование 4-х буквенных слов при помощи генетического алгоритма
Описание решения
Поначалу я применил «грубую силу» и попробовал решить задачу в лоб. Суть моего наивного метода сводилась к построению дерева слов, полученных путем перебора всех букв русского алфавита и подстановке их вместо одной из букв предыдущего слова (см. рисунок).
Каждое новое слово проверялось на отсутствие среди предшествующих, а также на наличие в словаре, который я перенес с сайта любителей кроссвордов в наш справочник Слова из 4-х букв (надеюсь, авторы сайта меня простят за эту вольность).
Далее, успешно проверенное слово включалось в дерево и для него снова проводилась аналогичная процедура, до тех пор, пока не будет найдено искомое слово.
С первого раза, конечно же, ничего не заработало — мой рекурсивный алгоритм быстренько переполнил ограниченный стек джаваскрипта. Преобразование рекурсивного алгоритма в циклический дало более удачный результат — муха была трансформирована в слона минут этак за 10.
Полученный результат был пригоден для дочки, но не для меня. К тому же, пока работала программа, у меня было достаточно времени поразмыслить над улучшением алгоритма и гипотетической возможностью мухи эволюционировать в слона. Этот программно-биологический бред в конечном итоге привел меня к генетическому алгоритму, который как нельзя кстати подошел для решения этой задачи и переродил муху в слона в течение нескольких секунд.
Генетический алгоритм
Генетическим алгоритм был назван так из-за сходства процесса поиска решения с биологической эволюцией. Решением задачи является вектор слов, удовлетворяющих некоторому критерию (хромосома). На каждом шаге мы порождаем несколько таких векторов (популяцию), после чего осуществляем отбор наиболее пригодных вариантов (жизнеспособных особей), т. е. выполняем селекцию. На последующем шаге ранее полученные варианты снова видоизменяются, порождаются новые варианты (происходит мутация) и так до тех пор, пока не будет выполнен критерий останова алгоритма (в нашем случае муха преобразуется в слона).
По сути, мой начальный алгоритм тоже можно было отнести к генетическим (селекция осуществлялась путем проверки по словарю), но так как число порожденных вариантов увеличивалось на каждом шаге, то в конечном итоге всей популяции новых особей для дальнейшего существования не оставалось жизненного пространства (ресурсов процессора).
В модифицированном алгоритме была применена улучшенная функция селекции, которая отбирает только самые похожие на конечное слово варианты. Количество самых жизнеспособных вариантов задается параметром Размер популяции, чем меньше это число, тем быстрее работает алгоритм, чем больше — тем качественнее получается результат.
В качестве дополнительного критерия останова было введено ограничение на максимальный размер цепочки, для этого был введен еще один параметр. Алгоритм остановится, если после воспроизводства заданного числа поколений не будет получен искомый результат.
Функция приспособленности (похожести текущего слова на конечное) оценивала каждый вариант по 12 бальной шкале.
- за каждую букву, совпадающую по положению и значению с конечным результатом, начислялось 3 балла
- если гласная буква слова находилась на том же месте, что и другая гласная буква искомого слова — 2 балла
- и один балл начислялся просто за наличие гласной буквы.
Таким образом, конечное слово СЛОН оценивалось в 12 баллов, а начальная МУХА всего в 2.
Желающие более детально ознакомиться с алгоритмом, могут это сделать, путем исследования содержимого функции calculate из javascript'а этой страницы.
P.S.
Один наш пользователь, увлекающийся построением подобных цепочек, попросил сделать Преобразование 5-и буквенных слов перестановкой одной буквы. Этот онлайн калькулятор берет 5-и буквенные слова из справочника: Слова из 5-и букв
Комментарии