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

Question

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

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

Существует инфраструктура Java Evolutionary Algorithm под названием Watchmaker. Автор повторно реализовал проблему Моны Лизы, используя подлинный генетический алгоритм: 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 минут. Показатель пригодности составляет 150000, но невооруженным глазом кандидат выглядит практически идентично оригиналу.

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

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

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

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

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

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

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

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

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

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

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