lightanddesign.ru
You might also like
Каждый шаг изменяет одну букву предыдущего слова, поочередно превращая одно четырехбуквенное слово в другое.
Недавно ребенок принес из школы проблему. В пятом классе на уроке русского языка дети выполняют следующие задания Создайте цепочку слов. Каждое слово отличается от предыдущего на одну букву. Во-первых, им дается первое и последнее слово в цепочке. Решив больше не мучить свою дочь, которой предстояло потратить несколько часов, пытаясь собрать мух в кучу, я написал следующий калькулятор:.
Преобразование четырехбуквенного слова с помощью генетического алгоритма
Описание решения.
Сначала я попытался решить эту проблему, применив "грубую силу". Суть моего наивного метода заключалась в создании дерева слов путем перебора всех букв русского алфавита и замены их на одну из букв предыдущего слова (см. схему).
Рост популяции без наблюдения с использованием наивного алгоритма.
Каждое новое слово проверялось на его отсутствие в предыдущем слове, а также на его наличие в словаре, перенесенном с сайта Crossword Friend на четырехбуквенное слово в справочнике (надеюсь, редактор сайта простит мне эту вольность). Далее тот же процесс повторялся до тех пор, пока слово не было успешно проверено и найдено в дереве.
Конечно, изначально ничего не работало. Мой рекурсивный алгоритм быстро перегрузил ограниченный стек javascript. Преобразование рекурсивного алгоритма в круговой алгоритм дало лучшие результаты. Муха превратилась в слона примерно за 10 минут.
Результаты были достаточно хороши для моей дочери, но не для меня. Кроме того, пока программа работала, у меня было достаточно времени подумать об улучшении алгоритма и о возможности гипотезы о том, что муха эволюционирует в слона. Этот бред биологического программирования в конечном итоге привел меня к генетическому алгоритму. Он прекрасно справился с поставленной задачей и в считанные секунды превратил муху в слона.
Генетические алгоритмы
Генетические алгоритмы названы так из-за схожести процесса поиска решений с биологической эволюцией. Решением этой задачи является вектор слов, удовлетворяющих определенным критериям (хромосомы). На каждом этапе создается множество таких векторов (популяций), а затем отбирается наиболее подходящий вариант (жизнеспособные особи). Другими словами, осуществляется выбор. На следующем этапе ранее сгенерированные варианты переделываются и создаются новые варианты (происходят мутации), пока не будет достигнут критерий остановки алгоритма (в данном случае, пока муха не превратится в слона).
На самом деле, мой оригинальный алгоритм также можно было бы считать генетическим (отбор проверялся по словарю), но поскольку количество генерируемых вариантов увеличивалось на каждом шаге, в конечном итоге во всей популяции новых особей не оставалось больше жизненного пространства (ресурсов процессора) для дальнейшего существования).
В модифицированном алгоритме реализован улучшенный механизм отбора, который выбирает только те варианты, которые наиболее похожи на целевое слово. Количество наиболее жизнеспособных вариантов задается параметром Population size. Чем меньше число, тем быстрее работает алгоритм, а чем больше число, тем лучше результаты.
В качестве дополнительного критерия остановки было введено ограничение на максимальный размер цепи, для чего был введен еще один параметр. После определенного количества итераций поколений алгоритм останавливается, если желаемый результат не может быть получен.
Функция адаптивности (сходство между текущим словом и последним словом) оценивала каждый вариант по 12-балльной шкале.
- Каждой букве было присвоено три балла, соответствующие положению и важности конечного результата.
- Если гласная буква в слове находится в той же позиции, что и другая гласная буква в целевом слове — 2 балла.
- И 1 балл присуждался за простое присутствие гласной. Так, последнее слово СЛОН получило 12 баллов, в то время как оригинальное МУХА — только 2 балла.
Если вы хотите узнать больше об алгоритме, ознакомьтесь с содержанием функции calculatejavascript на этой странице.
Один пользователь, которому нравилось создавать подобные цепочки, попросил преобразовать пятибуквенное слово в однобуквенное. Этот онлайн-калькулятор использует слово из 5 букв в справочнике: слово из 5 букв
