|
6.4.
Аппроксимация изображений генетическим
алгоритмом при помощи EvoJ
В этом разделе рассматривается вопрос, как можно применить
генетический алгоритм для аппроксимации изображений
полигонами.
А.Е. Кононюк Дискретно-непрерывная математика
361
6.4.1. Выбор способа описания решения
Следуя традиционному пути решения задач при помощи EvoJ, для
начала выберем как мы опишем решения для нашей задачи.
Прямолинейным решением будет описать аппроксимацию как простой
список полигонов:
public interface PolyImage {
List
getCells();
}
Такой подход имеет право на жизнь, нам вполне удастся подобрать
удовлетворительную картинку рано или поздно. Cкорее всего поздно,
так как такой подход снижает эффективность скрещивания хороших
решений. И вот почему.
А.Е. Кононюк Дискретно-непрерывная математика
362
Представим для простоты следующую картинку.
Допустим у нас в генофонде есть два хороших решения, каждое из
которых отличается от идеального на один полигон.
А.Е. Кононюк Дискретно-непрерывная математика
363
Обратите внимание на одну особенность: в обоих случаях полигон
номер 0 идеально совпадает с одним из полигонов изображения, тогда
когда другой лежит где-то в стороне. Был бы здорово скрестить эти два
решения таким образом, чтобы в результате вместе оказались два
первых полигона из обоих решений, однако это не возможно — EvoJ
отображает все переменные на байтовый массив и при скрещивании
работает с байтами, не меняя порядка их следования.
Процесс кроссинговера разъясняется на следующем рисунке.
Таким образом два элемента с одинаковым индексом никак не могут
оказаться в результирующем решении.
Результат скрещивания скорее всего будет выглядеть так:
А.Е. Кононюк Дискретно-непрерывная математика
364
Что сильно скажется на эффективности скрещивания, значительно
замедлив эволюцию.
Обойти проблему можно, «правильно» засеяв исходную популяцию —
равномерно распределив полигоны по области изображения, таким
образом, чтобы расположение полигона в списке, согласовывалось с
его геометрическим расположением на рисунке. При этом придется
ограничить мутацию, чтобы полигоны не могли слишком далеко
«переползти».
Более продвинутый подход заключается в изначальном разделении
изображения на ячейки, с назначением каждой ячейке собственного
списка полигонов. В виде интерфейса Java это описывается так:
public interface PolyImage {
Colour getBkColor();
List>> getCells();
}
Внешний список задает ряды ячеек, следующий по вложенности —
столбцы, и, наконец, внутренний список — полигоны находящиеся в в
соответствующей ячейке. Такой подход автоматически обеспечивает
примерное соответствие положения полигона в байтовом массиве и его
геометрического места на рисунке.
Каждый полигон опишем как:
А.Е. Кононюк Дискретно-непрерывная математика
365
public interface Polygon {
List
getPoints();
Colour getColor();
int getOrder();
}
Здесь свойство order определяет глобальный порядок отрисовки
полигона. Цвет полигона опишем как:
public interface Colour {
@MutationRange("0.2")
@Range(min = "0", max = "1", strict = "true")
float getRed();
@MutationRange("0.2")
@Range(min = "0", max = "1", strict = "true")
float getGreen();
@MutationRange("0.2")
@Range(min = "0", max = "1", strict = "true")
float getBlue();
void setRed(float red);
void setGreen(float green);
void setBlue(float blue);
}
Иными словами, просто как три компоненты цвета, желающие еще
могут добавить альфа-канал, однако мы будем рисовать все полигоны с
50% прозрачностью, это снизит число безразличных мутаций.
Назначение аннотаций здесь очевидно. Точки полигона опишем как:
А.Е. Кононюк Дискретно-непрерывная математика
366
public interface Point {
int getX();
int getY();
}
При этом координаты X и Y будем считать относительно центра
ячейки, которой принадлежит полигон. Обратите внимание, что
аннотации регулирующие допустимые значения переменных
присутствуют только в описании цвета. Это связано с тем, что
допустимые значения координат зависят от размера изображения и от
конфигурации ячеек, а допустимые значения компоненты цвета —
вещи предопределенные. Кроме того, аннотацию на два внутренних
списка в интерфейсе
PolyImage
вообще никак повесить нельзя.
Чтобы задать все необходимые параметры мы воспользуемся
механизмом под названием Detached
Перейдем к программированию.
Do'stlaringiz bilan baham: | 
