Алгоритмы / [Из песочницы] EvoJ — удобный фреймворк для генетических алгоритмов

Здравствуйте, коллеги!
Здесь часто появляются статьи на тему генетических алгоритмов, разрешите и мне внести свои пять копеек.
Вот уже пару лет я виде хобби разрабатываю Java-фреймворк EvoJ посвященный ГА. Когда я только начинал работу с ГА самое большое неудобство представляла необходимость векторизации переменных составляющих решение, поэтому в своем фреймворке я постарался сделать векторизацию переменных прозрачной для программиста, возложив всю грязную работу на плечи фреймворка. Кроме того, так как ГА очень хорошо поддается распараллеливанию, я постарался сделать переход к многопоточности не менее легким.
Чтобы понять основную идею EvoJ расммотрим следующий пример. Для простоты допустим, что нам нужно найти минимум функции Z(x, y)=12 * x^2 + 8 * x + 9 * y^2. Естественно, эту задачу можно более эффективно решить не прибегая к ГА, но для начала давайте рассмотрим ее, а затем разберем пример раскрывающий всю силу EvoJ.
Итак, первым делом нам нужно создать Java-интерфейс содержащий необходимые нам переменные. Переменных у нас две: X и Y, создадим интерфейс содержащий геттеры для данных переменных.

public interface Solution {

@Range(min = "-10", max = "10")
double getX();

@Range(min = "-10", max = "10")
double getY();
}

Обратите внимание что сеттеры декларировать не обязательно, EvoJ сможет изменять переменные и без них. Однако, если Вы захотите имплементировать собственную стратегию мутации, то декларировать сеттеры придется — иначе Вы сами не сможете изменять переменные.
Обратите внимание на аннотацию @Range, она задает диапазон значений которые может принимать переменная. Переменные инициируются случайными значениями из заданного диапазона. Однако, в результате мутации они потенциально могут выйти за указанный диапазон. Это можно предотвратить использовав параметр strict=”true”, что не позволит переменной принять недопустимое значение, даже если вы попытаетесь его выставить используя сеттер метод.
Еще один момент на который стоит обратить здесь внимание, это то что все параметры всех аннотаций в EvoJ являются строками, это позволяет, как указывать непосредственно значение параметра, так и указать вместо конкретного значения имя property, чтобы жестко не указывать значения параметров аннотаций в compile-time.
Итак, интерфейс с переменными у нас есть, давайте напишем фитнесс-функицию. Фиттнесс-функция в EvoJ представлена интерфейсом:

public interface SolutionRating {

Comparable calcRating(T solution);

}

Здесь параметр T это наш интерфейс с переменными. Чем больше возвращаемое значение (согласно контракту Comparable) тем более приспособленным считается решение. Можно вернуть null, он считается самым маленьким значением фитнесс-функиции.
Рекомендуется имплементировать этот интерфейс опосредовано, через helper-классы, которые берут на себя некоторые сервисные функции: уничтожение старых решений (если задан максимальный срок жизни решения), кэширование значения функции для решений, которые не были отсеяны на предыдущей итерации ГА.
Фиттнесс-функция для нашего случая будет выглядеть следующим образом:

public class Rating extends AbstractSimpleRating {

public static double calcFunction(Solution solution) {
double x = solution.getX();
double y = solution.getY();
return 12 * x * x + 8 * x + 9 * y * y;
}

@Override
public Comparable doCalcRating(Solution solution) {
double fn = calcFunction(solution);
if (Double.isNaN(fn)) {
return null;
} else {
return -fn;
}
}
}

Здесь все довольно очевидно, мы просто берем и считаем нашу функцию используя переменные из нашего первого интерфейса. Так как мы ищем минимум, а контракт класса предполагает, что наилучшие решения должные иметь больший рейтинг, то мы возвращаем значение функции умноженное на -1.
Кроме того, мы отсеиваем левые решения (если получился NaN) возвращая null.
Ну вот, два главных компонента у нас есть, давайте заставим все это работать.

DefaultPoolFactory pf = new DefaultPoolFactory();
GenePool pool = pf.createPool(200, Solution.class, null);
DefaultHandler handler = new DefaultHandler(new Rating(), null, null, null);

handler.iterate(pool, 200);
Solution solution = pool.getBestSolution();

Давайте разберем код приведенный выше по строчкам:

DefaultPoolFactory pf = new DefaultPoolFactory();

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

GenePool pool = pf.createPool(200, Solution.class, null);

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

DefaultHandler handler = new DefaultHandler(new Rating(), null, null, null);

Хэндлер это воплощение генетического алгоритма, это совокупность стратегий мутации, скрещивания, отбора и расчета рейтинга. Из них обязательно самостоятельно имплементировать только расчет рейтинга — для всего остального есть стандартные реализации, которые будут использованы, если вместо соотвествуещего параметра передать null.

handler.iterate(pool, 200);

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

Solution solution = pool.getBestSolution();

Здесь мы получаем лучшее найденное решение. На экземпляре данного интерфейса можно свободно вызывать getX()/getY() чтобы получить значения искомых переменных.
Если решение Вас не устроит можно продолжить итерации ГА, пока не будет достигнуто желаемое качество решения.
Таким образом, чтобы решить задачу при помощи EvoJ надо:Создать интерфейс с переменнымим

Имплементировать интерфейс фитнесс-функиции

Создать популяцию решений и осуществить над ними нужное количество итерации ГА, используя код приведенные выше

Ну, это была разминка, теперь давайте посмотрим что может EvoJ на самом деле.
Допустим мы хотим аппроксиммировать полноцветное изображение ограниченным набором полигонов. Решение такой задачи описать единственным интерфейсом с простыми переменными нельзя, тут то и проявляется вся мощь EvoJ. Мы можем продекларировать следующий набор интерфейсов:

public interface PolyPicture {

@ListParams(length = "50")
List getPolygons();
}

public interface Polygon {

Colour getColor();

@ListParams(length = "8")
List getPoints();
}

public interface Point {

@Range(min = "-5", max = "325", strict = "true")
float getX();

@Range(min = "-5", max = "245", strict = "true")
float getY();

void setX(float x);

void setY(float y);
}

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);

}

На вершине интерфейс представляющий собой всю картину целиком, он состоит из единственного свойства — списка полигонов. Каждый полигон это цвет плюс список точек. Точка — это две координаты, цвет — три компоненты.
Из новых аннотаций стоит упомянуть @ListParams — задающую длину списка и некоторые другие свойства, и @MutationRange — задающую максимальный радиус мутации переменной, т.е. на сколько максимально переменная может измениться за один акт мутации.
Так же обратите внимание, что переменные описывающие компоненты цвета имеют жестко заданную область значений (strict=”true”).
Далее нам нужно реализовать фитнесс-функицию, как и в прошлый раз сделаем это расширив helper-класс. Ниже для экономии места приведен неполный код класса (оригинальный код расчитан на многопоточность и содержит множество неочевидных оптимицаций которые делают его плохо читаемым).

public class PictureRating extends AbstractSimpleRating {

public PictureRating(BufferedImage originalImage){....}

@Override
protected Comparable doCalcRating(PolyPicture picture) {
BufferedImage testImage = drawPicture(picture);
int[] originalPix = getPixels(originalImage);
int[] testPix = getPixels(testImage);
return -calcError(originalPix, testPix);
}
}

Здесь мы отрисовываем картинку описанную нашими интерфейсами, берем ее пиксели и сравниваем с пикселями оригинального изображения. В качестве результата возвращаем накопленное отклонение со знаком минус (больше ошибка — хуже решение, меньше ошибка — лучше решение).
Дальше напишем код сходный с примером, где мы искали минимум функции.

DefaultPoolFactory factory = new DefaultPoolFactory();
GenePool pool = factory.createPool(40, PolyPicture.class, null);
DemoRating rating = new DemoRating(PICTURE_TO_APPROXIMATE);
MultithreadedHandler handler = new MultithreadedHandler(2, rating, null, null, null);

handler.iterate(pool, 1000);

handler.shutdown();

Здесь есть одно отличие — MultithreadedHandler. Он отличается от простого хэндлера тем, что выполняет итерацию ГА над популяцией решений в несколько потоков (количество потоков задается первым параметром конструктора). Таким образом, если у вас процессор имеет несколько ядер, вы можете реально ускорить поиск решения всего лишь увеличив количество потоков. Например, решение приемлего качества для рассматриваемой задачи аппроксимации изображения на Core i7 со включенным HyperThreading в 8 потоков находится за 15-20 минут.
Многопоточный код в EvoJ написан чтобы минимизировать блокировки, что позволяет получить практически линейный прирост производительности с увеличением количества потоков (для максимальной производительности нужно чтобы число особей в популяции было кратно числу потоков, иначе некоторым потокам не хватит задач).
Еще стоит необходимо обратить внимание на строчку

handler.shutdown();

Она необходима чтобы завершить ожидающие executor-потоки.
Итак, это все что я хотел рассказать Вам про EvoJ. В качестве резюме приведу основные особенности EvoJ:отсутствие необходимости самостоятельно векторизовать переменные, можно сразу писать код в терминах доменной области

стандартные имплементации основных стратегий ГА (селекции, скрещивания, мутации)

декларативный контроль мутации (аннотации)

многопоточность из коробки

малый размер (120 кб) и отсутвтвие внешних зависимостей (да-да, Вам нужен только один jar файл)

расширяемость в любой точке (можно написать собственную имплементацию любой стратегии ГА — селекции, скрещивания и мутации)

Если Вы заинтересовались, то можете добавить EvoJ в свой Maven-проект следующим образом:сначал надо добавить ссылку на репозиторий (в центральный пока на выкладывал)

EvojHome
EvoJ
http://evoj-frmw.appspot.com/repository

затем непосредственно зависимость

net.sourceforge.evoj
evoj
2.1

Те кто не дружит с Maven могут скачать EvoJ непосредственно с сайта проекта http://evoj-frmw.appspot.com/. Там же есть копия этого туториала на английском языке, а так же подробное техническое руководство и результаты применения EvoJ для различных задач (аппроксимация изображений, обучение нейросетей).
Спасибо за внимание. С удовольствием отвечу на возникшие вопросы.