Преобразование слов с помощью генетического алгоритма

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

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

Статью про преобразование слов с помощью генетического алгоритма я написал специально для тебя. Если ты хотел бы внести свой вклад в развитие теории и практики, ты можешь написать коммент или статью отправив на мою почту в разделе контакты. Этим ты поможешь другим читателям, ведь ты хочешь это сделать? Надеюсь, что теперь ты понял что такое преобразование слов с помощью генетического алгоритма и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Реализация генетических алгоритмов

Из статьи мы узнали кратко, но содержательно про преобразование слов с помощью генетического алгоритма