[Все статьи]

Пример решения задачи методами ГА с помощью библиотеки EvoJ

EvoJ  это OpenSource проект распространяемый под лицензией GPL. Домашняя страница проекта http://evoj.sourceforge.net. Проект EvoJ задуман как расширяемый каркас классов Java для решения всевозможных задач оптимизации с помощью эволюционных (генетических) алгоритмов. Для использования EvoJ программист должен имплементировать лишь один простой интерфейс состоящий из одного метода. Все остальные шаги алгоритма берет на себя EvoJ.

Рассмотрим использование этой библиотеки на примере поиска минимума функции.

Найдем минимум функции Z(x,y)=12 * x * x + 8 * x + 9 * y * y.  Чтобы приступить к решению задачи нужно определиться с двумя вопросами: а) как хранить переменные, б) как считать рейтинг.

Договоримся в данной задаче решение хранить в виде двух чисел типа Double, следующих друг за другом. В библиотеке EvoJ к рейтингу предъявляетя одно требование: чем лучше решение, тем больше должно быть значение рейтинга. В нашей задаче, решение тем лучше, чем меньше значение функции Z(x,y). Чтобы привести это в соотвествие с требованиями EvoJ будем считать рейтинг как -Z(x,y).

Перейдем к коду, который должен разъяснить порядок использования библиотеки EvoJ.

Файл: Main.java:


package net.sourceforge.evoj.examples.simpleminimum;

import net.sourceforge.evoj.GenePool;
import net.sourceforge.evoj.params.ParameterMapping;
import net.sourceforge.evoj.params.ParameterType;

public class Main {

    public static void main(String[] args) {
        ParameterMapping mp = new ParameterMapping();
        mp.addParam("X", ParameterType.DOUBLE);
        mp.addParam("Y", ParameterType.DOUBLE);

        GenePool gp = new GenePool(200, mp.getDNASize(), new Rating());
        gp.iterate(100);

        double x = mp.getDouble("X", gp.getChampion());
        double y = mp.getDouble("Y", gp.getChampion());
        System.out.println("X=" + x);
        System.out.println("Y=" + y);
        System.out.println("Rating=" + gp.getChampion().getRating());
        System.out.println("Age=" + gp.getChampion().getAge());
    }
}

Файл Rating.java


package net.sourceforge.evoj.examples.simpleminimum;

import net.sourceforge.evoj.Individual;
import net.sourceforge.evoj.RatingStrategy;

public class Rating implements RatingStrategy {

    public void calcRating(Individual[] pool, int eliteCount) {
        for (Individual i : pool) {
                double x = i.getDouble(0);
                double y = i.getDouble(8);
                double fn = 12 * x * x + 8 * x + 9 * y * y;
                if (Double.isNaN(fn)) {
                    i.setRating(Double.NEGATIVE_INFINITY);
                } else {
                    i.setRating(-fn);
                }
        }
    }
}

Программа начинается с создания объекта класса ParameterMapping, который облегчает запись и чтение переменных из ДНК. Далее этом объекте создаются две переменные с именами X и Y типа Double.

Следующим шагом является создание объекта класса GenePool (генофонд), который в качестве парамтра получает размер желаемые размер популяции, размер ДНК особей популяции, вычисленные с помощью ParameterMapping, а так же ссылку на объект реализующий интерфейс RatingStrategy (о нем мы поговорим ниже).

После того как объект класса GenePool создан, можно приступать к итерациям, для этого служит метод GenePool.iterate(int), который осуществляет заданное число итераций с генофондом.

Так как рассматриваемая задача довольно проста, для ее решения достаточно примерно 100 итераций. После которых можно прочитать значения перменных из ДНК чемпиона (наилучшего решения).

Поговорим теперь об интерфейсе RatingStrategy. Это единственный интерфейс, который пользователь должеy имплементировать, чтобы воспользоваться возможностями библиотеки EvoJ. В рассматриваемом примере данный интерфейс реализуется классом Rating.

RatingStrategy имеет всего один метод calcRating, который в качестве параметра получает массив объектов класса Individual, которые представляют собой абстракцию ДНК (хромосомы, если пользоваться классической терминологией), а так же параметр eliteCount, который указывает на количество элитарных особей в генофонде. Элитарными считаются первые несколько особей с наивысшим рейтингом, определенному по результатам предыдущей итерации. По умолчанию это число принимается равным 10% от размера популяции. Пользователь может менять это число с помощью метода GenePool.setEliteCount(int elite). Так как элитарные особи пережили предыдущую итерацию, рейтинг у них уже посчитан и пересчитывать его нет не обходимости, однако, вы можете это сделать, если рейтинг опредляется не в абсолютных величинах, а в относительных в пределах популяции.

В рассматриваемом примере метод calcRating читает переменные Х и Y из ДНК каждой особи (обратите внимание, что здесь это делается напрямую, без посредника в виде ParameterMapping) и считает значение функции Z(x,y). Далее, рассматриваемой особи присвается рейтинг, как значение -Z(x,y). Обратите внмание, что особям, чья ДНК приводит к неверному расчету значения функции, присвается рейтинг равный минут бесконечности, что на следующей итерации поместит их в конец списка.

Общее описание библиотеки EvoJ

Главными классами библиотеки EvoJ являются три класса:

  • Individual
  • GenePool
  • RatingStrategy

Класс Individual представляет собой хранилище ДНК. Все переменные хранятся в байтовом массиве, размер которого задается при вызове конструктора класса.

Получить доступ в данный массив можно используя методы get/setInteger, get/setShort, get/setByte, get/setLong, get/setDouble, get/setFloat. Все эти методы в качестве одного из параметров требуют смещение в байтах относительно начала массива ДНК особи.

 Пользователю следует самому решить, в каком месте массива он будет хранить переменные решения своей задачи. При этом нужно помнить сколько байт занимают соответствующие типы данных (Byte – 1, Short – 2, Integer/Float – 4, Long/Double – 8) и недопускать перекрытия пространства отведенного под разные переменные при  чтении, записи.

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

Следующим важным классом является класс GenePool, он представляет собой реализацию популяции особей.

Основной конструктор класса требует трех параметров:

  • размер популяции,
  • размер ДНК особи,
  • ссылка на клаcс реализующий интерфейс RatingStrategy.

 Конструтор заполяет начальную популяцию объектами класса Individual со случайными генами.

 Главным методом класса GenePool является метод iterate() в котором реализован общий генетический алгоритм:

  • селекция
  • размножение
  • мутация
  • оценка.

 

За реализацию каждого из этапов отвечает определенный интерфейс, все они кроме RatingStrategy реализованы в проекте EvoJ. Поэтому имплементировать самостоятельно их требуется только в особых случаях. В общем случае самостоятельно необходим имплементировать только метод RatingStrategy.calcRating(Individual[] pool, int eliteCount).

 Цикл использования класса GenePool заклчается в вызове iterate(), и последующей проверкой найденного решения путем вызова метода getChampion(), который возвращает экземпляр класса Individual с наивысшим рейтингом. За одну итерацию, как правило, приемлемое решение не находится, поэтому созданы такие методы как iterate(int), который вызывает метод iterate() заданное число раз, и метод iterate(SuccessStrategy), который вызывает метод iterate()  пока класс, имплементирующий интерфейс SuccessStrategy не укажет, что можно остановаиться. Интерфейс SuccessStrategy является специфичным для решаемой задачи, поэтому в библиотеке EvoJ нет его имплементаций. Пользователь может это сделать сам, хотя это не является обязательным.

Самой важной частью, с точки зрения пользователя является интерфейс RatingStrategy, так как от его имлементации пользователем библиотеки зависит успешность поставленной задачи.

Данный интерфейс декларирован как:


public interface RatingStrategy {
    public void calcRating(Individual[] pool, int eliteCount);
}

В данный метод передается массив всех экземпляров класса Individual составляющих GenePool, данный массив будет отсортирован по убыванию рейтига особей, т.е. в ячейке pool[0] будет находиться особь с наивысшим рейтингов. Переменная eliteCount указывает сколько первых особей в массиве являются элитарными, т.е. особями пережившими предыдущую итерацию. У них рейтинг уже установлен, и, как правило, пересчитывать его не нужно. Однако, если рейтинг является не абсолютной величиной, а зависит от текущего соотношения сил в массиве, то и этим особям нужно пересчитать рейтинг.

Имплементатор интерфейса должен установить рейтинг для каждой особи путем вызова метода setRating(double).

Следует избегать использования Double.NAN и Double.POSITIVE_INFINITY в качестве значений рейтинга, если, конечно эти значения не соответствуют оптимальному решению.

С другой стороны рекоммендуется использовать Double.NEGATIVE_INFINITY для обозначения особей, которые подлежат ликвидации в конце текущей итерации. Дело в том, что сортировка производится в конце итерации и особи с рейтингом Double.NEGATIVE_INFINITY окажутся в конце списка.

И так, подведем итог раздела. Чтобы решить какую либо задачу с помощью библиотеки EvoJ, необходимо:

  • определиться с количеством и типом переменных входящих в состав решения, чтобы определить необходимый размер ДНК
  • определиться со способом вычисления критерия оптимальности решения (рейтингом), при этом лучшему решению должен соответствовать больший рейтинг
  •  имплементировать интерфейс RatingStrategy
  • создать экземпляр класса GenePool, передав в конструктор размер популяции, размер ДНК и указатель на интерфейс RatingStrategy.
  • вызывать методы interate() до тех пор пока не будет найдено преемлемое решение.

В большинстве случаев этого достаточно. Вся остальная логика генетического алгоритма реализуется библиотекой.

Адаптация генетического алгоритма

В стандартной релизации операции порождения начальных значений, селекции, репликации и мутации реализуются библиотекой EvoJ на уровне битов. Библиотека не знает какого типа переменные содержатся в ДНК и как они там расположены.

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

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

Чтобы предотвратить такую ситуацию, можно переопределить стратегии генерации и мутации, в некоторых случаях необходимо переопределить стратегии репликации или селекции.

За все эти стратегии отвечают следующие интерфейсы:

  • BirthStrategy – стратегия порождения начальных значений
  • SelectionStrategy – стратегия выбора особей для размножения
  • ReplicationStrategy – стратегия создания новой особи из двух родительских
  • MutationStrategy – стратегия мутации особи

 

Поговорим подробнее о каждом из этих интерфейсов.

Интерфейс BirthStrategy

Данный интерфейс декларирован как:


public interface BirthStrategy {
    public Individual getNewIndividual();
    public int getDNASize();
}

Метод getNewIndividual() должен вернуть новый экземпляр класса Individual с ДНК заполненной случайными значениям, соответствущими текущей стратегии.

Метод getDNASize() должен возвращать размер ДНК особей по рождаемых данной стратегией.

Интерфейс SelectionStrategy

Данный интерфейс декларирован как:


public interface SelectionStrategy {
    public void performSelection(Individual[] pool, int eliteCount, ParentPair pair);
}

Метод performSelection() должен заполнить поля экземпляра класса ParentPair, переданного в качестве параметра, ссылками на объекты Individual из массива pool.

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

Интерфейс ReplicationStrategy

Интерфейс декларирован как:


public interface ReplicationStrategy {
        public void setChildDNA(Individual child, Individual parent1, Individual parent2);
}

Система вызывает метод setChildDNA сразу после вызова SelectionStrategy.performSelection и передает сюда указатели на двух родителей, гены которых необходимо смешать и записать получившийся результат в ДНК особи child.

Необходимо заметить, что в ходе репликации не создается новых экземпляров класса Individual, вместо этого затираются ДНК существующих неэлитарных особей. Это сделано в целях оптимизации времени выполнения и экономии памяти.

Интерфейс MutationStrategy

Данный интерфейс декларирован как:


public interface MutationStrategy {
    public void mutate(Individual i);
}

Метод mutate вызывается для каждой особи созданной с помошью предыдущего интерфейса.

Реализация метода mutate должна неким случайным образом изменить ДНК данной особи. Не обязательно изменять ДНК у каждой переданой особи, определенное число особей рекоммендуется оставить неизменными.

Рекомендуется следующий шаблон реализации метода mutate:


public void mutate(Individual i){
	if (random.nextDouble()<0.4){ //мутируем 40% переданных особей
		doMutate(i);
	}
}

Все вышеперечисленные интерфейсы должны быть реализованы в threadsafe манере.

Для  подмены стандартных стратегий, которые использует класс GenePool предназначен конструктор:

public GenePool(int size, int dnaSize, BirthStrategy birthStrategy, SelectionStrategy selectionStrategy, ReplicationStrategy replicationStrategy, MutationStrategy mutationStrategy, RatingStrategy ratingStrategy)

Параметры имеют следующее значение:

size – размер популяции;

dnaSize – размер ДНК особей для инициализации, этот парметр игнорируется если параметр birthStrategy не равен null;

birthStrategy – указатель на реализаци ю интерфейса BirthStrategy. Если данный параметр равен null, то используется страндартная стратегия случайного порождения особей с размером ДНК равным dnaSize;

selectionStrategy – указатель на реализацию интерфейса SelectionStrategy. Если данный параметр равен null, то используется стандартная стратегия селекции;

replicationStrategy – указатель на реализацию интерфейса ReplicationStrategy. Если данный параметр равен null, то используется стандартная стратегия репликации;

mutationStrategy – указатель на реализацию интерфейса MutationStrategy. Если данный параметр равен null, то используется стандартная стратегия мутации;

ratingStrategy – указатель на реализацию интерфейса RatingStrategy. Данный параметр не может быть равен null.

Многопоточность в EvoJ

Так как эволюционные алгоритмы сопряжены с большим числом итераций, неизбежно возникает необходимость наиболее полного использованиия возможностей современных процессоров, а именно многоядерности.

Для этого создан класс MultiThreadedGenePool, который реализует островную модель многопоточности. Он не является наследником от GenePool, как может показаться из названия.

Данный класс использует готовые экземпляры класса GenePool и управляет ими в разных потоках.

В кратце схема работы класса такова: для каждого из указанных экземпляров GenePool класс создает отдельный поток и ждет команды пользователя. По сигналу пользователя всем потокам дается команда произвести заданное число итераций с соответствующим GenePool. По окончании интераций потоки переходят в режим ожидания, а  MultiThreadedGenePool в зависимости от настроек пересаживает элитарные особи между переданными GenePool. И ждет следующей команды на производство итераций.

Таким образом для использования многопоточности необходимо создать массив GenePool и передать его в конструктор  MultiThreadedGenePool. Затем вызывать метод iterate у  MultiThreadedGenePool, по окончании которго стоит вызвать метод getChampion, чтобы получить наилучшее решение среди всех GenePool в массиве, чтобы решить стоит ли продолжать итерации.

Особо эффективно происходит поиск решения, если в массиве находятся экземпляры GenePool с различными стратегиями репликации, мутации и.т.д.

Однако к экземплярам GenePool, передаваемым в массиве предъявляется два требования: они должны иметь одинаковый размер генома особей, и одинаковую RatingStrategy, что определяется по вызыву метода equals().

Ссылки

[На верх страницы]
Loading... Загрузка...