Почему этот генетический алгоритм застаивается?

Ответ 1

Я изучил эту проблему за последний месяц и сделал несколько интересных открытий:

• Использование непрозрачных полигонов на порядок увеличивает производительность рендеринга (и, соответственно, производительность функции фитнеса).
• Во всех вещах благоприятствуем многие небольшие изменения в результате резких больших изменений...
• При добавлении нового многоугольника дайте ему размер 1 пиксель вместо назначения его вершинам со случайными координатами. Это улучшает его шансы на выживание.
• При добавлении новой вершины вместо того, чтобы отбрасывать ее в произвольную позицию, она дает ту же позицию, что и существующая вершина в многоугольнике. Он не будет изменять полигон каким-либо заметным образом, но он откроет дверь для мутации "move vertex", чтобы перемещать больше вершин, чем это было раньше.
• При перемещении вершин предпочитайте много маленьких движений (3-10 пикселей за раз) вместо того, чтобы пытаться охватить весь холст.
• Если вы собираетесь затушить мутации с течением времени, уменьшите количество изменений в отличие от вероятности изменения.
• Эффекты демпфирования минимальны. Оказывается, если вы следовали вышеуказанным шагам (предпочитаете небольшие изменения), не должно быть никакой реальной необходимости влаги.
• Не используйте мутацию Crossover. Он вводит высокую скорость мутации, которая очень велика, но очень быстро высокая мутация становится ответственностью, потому что изображение, которое в основном сходится, отклонит все, кроме небольших мутаций.
• Не масштабируйте изображение в функции оценщика пригодности. Мне это потребовалось некоторое время, чтобы понять. Если ваше входное изображение 200x200, но оценщик пригодности масштабирует изображение до 100x100, прежде чем генерировать оценку пригодности, это приведет к появлению кандидатских решений, содержащих стейки/строки ошибок, которые невидимы для функции фитнеса, но явно не соответствуют конечному пользователю. Функция фитнеса должна обрабатывать весь образ или вообще не обрабатываться. Лучшим решением является масштабирование целевого изображения по всем направлениям, чтобы ваша фитнес-функция обрабатывала 100% пикселей. Если 100x100 слишком мало для отображения на экране, вы просто увеличиваете изображение. Теперь пользователь может четко видеть изображение, а функция фитнеса не пропускает ничего.
• Предотвращение создания самопересекающихся многоугольников. Они никогда не дают хороших результатов, поэтому мы можем существенно ускорить алгоритм, предотвращая создание мутаций. Реализация проверки самопересекающихся полигонов была болью в заднице, но в конце концов это стоило проблемы.

• Я изменил оценку пригодности для удаления скрытых полигонов (чисто по соображениям производительности):

  fitness += candidate.size();

  Это означает, что показатель пригодности никогда не достигнет нуля.

• Я увеличил максимальное количество полигонов от 50 до 65535.

  Когда я впервые попробовал запустить Watchmaker Mona Lisa, он будет работать в течение нескольких дней и не будет выглядеть совсем близко к целевому изображению. Алгоритм Роджера был лучше, но по-прежнему оставался на месте после часа. Используя новый алгоритм, мне удалось заново создать целевой образ менее чем за 15 минут. Оценка пригодности читает 150 000, но невооруженным взглядом кандидат выглядит почти идентично оригиналу.

  Я собрал диагностический дисплей, который показывает мне, что вся популяция эволюционирует с течением времени. Это также говорит мне, сколько уникальных кандидатов активно участвует в жизни населения в любой момент времени. Низкое число указывает на отсутствие дисперсии. Либо давление в популяции слишком велико, либо слишком низкие частоты мутаций. По моему опыту, приличное население содержит не менее 50% уникальных кандидатов.

  Я использовал этот диагностический дисплей для настройки алгоритма. Всякий раз, когда количество уникальных кандидатов было слишком низким, я бы увеличил скорость мутации. Всякий раз, когда алгоритм слишком быстро застаивался, я бы изучил, что происходит в населении. Очень часто я замечал, что количество мутаций слишком велико (цвета или вершины движутся слишком быстро).

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

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

  Если вы вспомните исходную проблему, о которой я сообщал, это то, что изображение кандидата уменьшалось до оценки, тем самым позволяя многим пикселям избежать обнаружения/коррекции. Вчера я включил сглаживание изображения, показанного пользователю. Я понял, что пока оценщик видит 100% пикселей (без масштабирования), я должен быть в безопасности, но оказывается, что этого недостаточно.

Взгляните на следующие изображения:

Включено сглаживание:

Сглаживание отключено:

Они показывают точно такие же кандидаты с включенным и отключенным сглаживанием. Обратите внимание, как в сглаженной версии есть "полосы" ошибок на лице, похожие на проблему, которую я видел, когда кандидат масштабировался. Оказывается, иногда кандидаты содержат многоугольники, которые вводят ошибки в изображение в виде "полос" (полигоны, полученные с точностью до пикселя). Интересно, что aliasing подавляет эти ошибки, поэтому функция оценщика не видит этого. Следовательно, пользователи видят целую кучу ошибок, которые функция фитнеса никогда не исправит. Звучит знакомо?

В заключение: вы всегда (всегда!) передаете функцию фитнеса точно такое же изображение, которое вы показываете пользователю. Лучше безопасно, чем жаль:)

Генетические алгоритмы - это очень весело. Я призываю вас поиграть с ними самостоятельно.