Comments 20
А код примеров (с лабиринтом) доступен?
Хорошо бы еще и с реализацией на OpenCL
А недоработанность кода, думаю, хабражители простят, тема ведь не о коде, а о генах =)
Вообще, код писался для себя, так что его прочтение может вызвать тошноту, головокружение, рвоту и приступы эпилепсии, но вот: https://github.com/JGDger/ELTRUT
Насколько я понимаю определение генетического алгоритма, первый алгоритм в Вашей статье — не генетический (нет кроссинговера). Это больше похоже на случайные блуждания в пространстве решений, с отсевом по fitness. Если бы Ваши «существа» умели скрещиваться (например, обмениваться кусками маршрута на совпадающих точках лабиринта), сойтись могло сильно быстрее. Кроме того, рандомизацию часто имеет смысл добавлять не только в мутации, но и в отбор — например, убивать любое существо с вероятностью, антимонотонно зависящей от функции качества.
То есть генетические алгоритмы обязательно должны основываться именно на «половом» размножении?
В целом, да («Отличительной особенностью генетического алгоритма является акцент на использование оператора скрещивания»). Если особи не взаимодействуют друг с другом никак, это просто случайный поиск. Храним топ решений, как-то случайно их перефигачиваем, обновляем топ. Это сработает для монотонно улучшаемых задач, а вот если нужно слегка ухудшить решение, чтобы от него можно было дойти до более оптимального, будет хуже. В случае кроссинговера особи могут обмениваться удачными «частями» решения целиком, плюс хорошо, если любая особь может выжить с некоторой вероятностью.
Чем обусловлено отсутствие мутации у десяти лучших особей?
Полагаю нужно для того, чтобы не было деградации. Если всегда 10 лучших особей не будут изменятся, а появятся на некотором поколении особи лучше них, то уже новые 10 не будут мутировать. Если бы мутировали все особи, то лучше могли бы деградировать и алгоритм в этом случае явно справлялся бы с задачей хуже на бОльших объемах входных данных.
Хотя если вопрос именно в числе 10 особей, то вероятно просто выбор автора.
Хотя если вопрос именно в числе 10 особей, то вероятно просто выбор автора.
Как правило, мутировать лучших — это хорошее дело. Только надо и самих лучших в популяции оставлять тоже, тогда не будет деградации.
нет, вопрос не в количестве. Я, как и комментатор выше, полагаю лучше их также мутировать методом клонирование+мутирование.
Я об этом же подумал. Но автор не использует скрещивание, а оно тут как раз давало бы наиболее эффективные результаты с выборкой скрещивания полезных признаков. Ну или как-то так. Хотя, честно признаться, я в таком типе моделей не сильно разбираюсь. Пока только логически предполагаю на основе некоторых знаний в области.
Лучшие особи я решил оставлять без изменений как раз для того, чтобы они не деградировали, иначе любая мутация (а в большинстве своём они негативные) резко бы ухудшила их способности. Ну и в итоге это дало неплохой прирост в скорости нахождения решения (кстати, не совсем ясно, почему). Ещё раз оговорюсь, что это был эксперимент, и разработка велась по принципу «а что, если — о, работает».
Простое расстояние для первого лабиринта сломается, как только лабиринт примет вид «прямая ветка почти до выхода, а ответвления были в начале в сторону и назад»
Ты реализовал данный проект на Языке Программирования C#?
В чем смысл решения задач, оптимально решаемых другими методами, с помощью ГА? Кстати, по-моему скромному опыту, даже задачи оптимизации, где актуальны ГА, лучше решаются более простыми методами а ля иммитация отжига или даже простой градиентный спуск.
Посмотрите на этот сайт http://www.critticall.com/, этот чувак только этим и занимается.
Интересно бы увидеть как влияют пороги и число существ в поколении на скорость решения.
Sign up to leave a comment.
Генетическое программирование. ELTRUT-проблема