Предыдущая часть: Генетическая Мона Лиза
Чуть раньше, в материале про растеризацию полигонов, я давал ссылку на исходный код генетического алгоритма (автор Gabriele Greco), который работает в разы быстрее, чем изначально описанный. Дам её ещё раз:
http://www.ggsoft.org/archives/genetic_test.zip
Я разобрался, откуда берётся скорость, и выводы скорее печальны.
Эту программу нельзя назвать истинным генетическим алгоритмом. В ней отсутствует популяция, отбор и скрещивание. Мы работаем только с одной хромосомой, которая мутирует и переходит в следующее поколение, если её рейтинг оказался лучше.
То есть, мы мутируем один и тот же набор полигонов до тех пор, пока он не станет лучше. Если он не становится лучше, мутации просто не сохраняются и делается новая попытка.
Естественно, в таком случае программа работает существенно быстрее, так как не нужно обрабатывать всю популяцию из 20-50 хромосом.
Ускорению также способствует то, что хромосома изначально состоит всего из трёх полигонов, а новые полигоны добавляются в следующих поколениях как вариант мутации. (В оригинальной версии хромосома состоит сразу из 150 треугольников).
Полигоны также мутируют – у них могут появляться или исчезать вершины. То есть треугольник может развиться в десятиугольник и потом деградировать обратно в треугольник.
Использование полигонов позволяет получать более сложные конфигурации наложения слоёв друг на друга и теоретически повышает точность картинки.
Но даже если оставить просто треугольники, это не сильно влияет на результат, просто размер хромосомы становится чуть больше.
Хотя алгоритм довольно быстро (буквально за пару минут) выдаёт приличный результат, хочу пояснить, почему это тупик, и продолжать эту разработку бесполезно.
Замедление сходимости
Поначалу, когда полигонов мало, улучшения картинки происходят буквально за секунды. С ростом числа полигонов наступает замедление, но не столько из-за скорости процессора, сколько из-за теории вероятностей. Каждый полигон имеет шанс на мутацию, и мутация заключается в изменении каких-то параметров, будь то положение вершин, цвет или прозрачность. Когда достаточно большое количество полигонов (от 10) уже сложились в какую-то удачную конфигурацию, случайное изменение любого из них будет чаще вести к ухудшению.
Картинка складывается из цветовых слоёв, образующихся от наложения полупрозрачных полигонов друг на друга. Поэтому изменение цвета или положения всего одного полигона автоматически делает невалидными и все остальные, с которыми он пересекался.
Это будет способствовать тенденции к сохранению всего "удачного" конгломерата полигонов без изменений, и хотя глазом видно, что их можно ещё долго улучшать, случайные мутации дают такому развитию событий очень маленький шанс. В результате побеждают те мутации, которые добавляют новый полигон к уже имеющимся, а это еще сильнее ухудшает ситуацию.
В пределе это означает, что картинку можно полностью воспроизвести, когда на каждый пиксел будет наложен свой полигон размером в 1 пиксел. Но тогда задача полностью потеряет смысл.
По факту то, что мы можем получить в какое-то разумное время (час, два) и есть предел аппроксимации. Мы можем ждать дольше, например сутки и недели, но получим лишь мизерные улучшения. Нет, алгоритм всё время улучшает картинку, но чем дальше, тем медленнее, и в конце концов придётся просто очень долго ждать.
Бессмысленность скрещивания
Использованные методы скрещивания брали часть полигонов из одной хромосомы и часть из другой. Полигоны можно брать или со случайных мест, или как непрерывные цепочки. Но всё это никак не помогает.
Как уже говорилось выше, каждый полигон пересекается с какими-то другими. Поэтому роль каждого полигона в том, чтобы оставаться на своём месте. У нас есть рейтинг всей хромосомы, но нет рейтинга каждого полигона, т.е. "хороший" он или "плохой". Если мы берём один полигон из одной хромосомы и другой полигон из другой хромосомы, то без остальных полигонов они дадут совсем не тот эффект. Наложение будет не то, цвет будет не тот, следовательно и картинка получится совсем другая. То есть брать гены у успешных родителей и смешивать их – в данном случае плохая идея, это не приводит к появлению успешных потомков, а если и приводит, то опять же случайно.
Думаю, именно поэтому в данном алгоритме автор отказался от скрещивания, и в результате он сходится гораздо быстрее, чем оригинальный со скрещиванием. Хотя удивительно, что со скрещиванием тоже сходится – скорее вопреки.
В общем, перспектив у такого алгоритма нет. Но есть другие. Буду разбираться, если найду что-то интересное, то напишу. Код своей программы я не публикую, так как просто скопировал его с программы, указанной по ссылке. Там есть и исходники (на C++), и исполняемый файл – можете запускать и смотреть.
