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

Question

Роджер Алсинг написал эволюционный алгоритм для воссоздания Моны Лизы с использованием C #. Его алгоритм прост:

1. Генерация случайной популяции размером два.
2. Замените наименее приспособленного человека клоном наиболее приспособленного.
3. Мутировать одного из людей.
4. Перейти к шагу 2

Существует инфраструктура Java Evolutionary Algorithm, которая называется Часовщик . Автор повторно реализовал проблему Моны Лизы, используя настоящий генетический алгоритм: http://watchmaker.uncommons.org/examples/monalisa.php

Все начинается достаточно хорошо, но в течение 30 минут реализация часовщика застаивается с плохим приближением, тогда как реализация Роджера выглядит близкой к завершению. Я пытался поиграть с настройками, но это не сильно помогло. Почему реализация Часовщика намного медленнее, чем у Роджера, и почему она застаивается?

Ссылки

• Роджер исходный код
• Исходный код часовщика

Answer 1

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

1. Использование непрозрачных полигонов повышает производительность рендеринга (и, соответственно, расширение функции пригодности) на порядок.
2. Во всем, отдавайте предпочтение множеству мелких изменений, а не радикально больших изменений ...
3. При добавлении нового многоугольника, присвойте ему размер 1 пиксель вместо того, чтобы назначать ему вершины со случайными координатами. Это повышает его шансы на выживание.
4. При добавлении новой вершины вместо того, чтобы сбрасывать ее в случайную позицию, присвойте ей ту же позицию, что и существующей вершине в многоугольнике. Он не изменит многоугольник каким-либо заметным образом, но откроет дверь для мутации «переместить вершину», чтобы переместить больше вершин, чем могло бы раньше.
5. При перемещении вершин предпочитайте много маленьких движений (3-10 пикселей за раз) вместо того, чтобы пытаться охватить весь холст.
6. Если вы собираетесь смягчать мутации с течением времени, уменьшите количество изменений, а не вероятность изменения.
7. Эффект демпфирования минимален. Оказывается, что если вы выполнили вышеупомянутые шаги (одобрите небольшие изменения), не должно быть никакой реальной необходимости ослаблять.
8. Не используйте кроссоверную мутацию. Он вводит высокую частоту мутаций, которая очень высока на раннем этапе, но очень быстро высокая мутация становится помехой, поскольку изображение, которое в основном сходится, отклонит все, кроме небольших мутаций.
9. Не масштабируйте изображение в функции оценки фитнеса. Это заняло у меня некоторое время, чтобы выяснить. Если ваше входное изображение имеет размер 200x200, но оценщик пригодности масштабирует изображение до 100x100, прежде чем генерировать оценку пригодности, это приведет к возможным решениям, содержащим стики / линии ошибок, которые невидимы для функции пригодности, но явно не соответствуют конечному пользователю. Фитнес-функция должна обрабатывать все изображение или не обрабатывать его вовсе. Лучшим решением является масштабирование целевого изображения по всем направлениям, чтобы ваша фитнес-функция обрабатывала 100% пикселей. Если 100x100 слишком мало для отображения на экране, вы просто увеличиваете изображение. Теперь пользователь может четко видеть изображение, и в фитнес-функции ничего не пропало.
10. Предотвращение создания самопересекающихся полигонов. Они никогда не дают хороших результатов, поэтому мы можем существенно ускорить алгоритм, не допуская их мутации. Реализация проверки для самопересекающихся многоугольников была болью в заднице, но в итоге это стоило того.

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

    fitness += candidate.size();

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

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

    Когда я впервые попробовал запустить пример часовщика Моны Лизы, он работал бы в течение нескольких дней и не смотрел ничего похожего на целевое изображение. Алгоритм Роджера был лучше, но все еще оставался на месте через час. Используя новый алгоритм, мне удалось воссоздать целевое изображение менее чем за 15 минут. Показатель пригодности составляет 150 000, но невооруженным глазом кандидат выглядит практически идентично оригиналу.

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

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

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

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

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

Посмотритена следующих изображениях:

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

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

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

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

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