«Введение в библиотеку Jenetics»

«1. Введение

Целью этой серии статей является объяснение идеи генетических алгоритмов и демонстрация наиболее известных реализаций.

В этом уроке мы опишем очень мощную Java-библиотеку Jenetics, которую можно использовать для решения различных задач оптимизации.

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

2. Как это работает?

Согласно официальным документам, Jenetics — это библиотека, основанная на эволюционном алгоритме, написанном на Java. Эволюционные алгоритмы уходят своими корнями в биологию, поскольку они используют механизмы, вдохновленные биологической эволюцией, такие как размножение, мутация, рекомбинация и отбор.

Jenetics реализован с использованием интерфейса Java Stream, поэтому он без проблем работает с остальной частью API Java Stream.

Основные функции:

минимизация без трения – нет необходимости изменять или настраивать фитнес-функцию; мы можем просто изменить конфигурацию класса Engine, и мы готовы запустить наше первое приложение без зависимостей — для использования Jenetics Java 8 не требуется сторонних библиотек среды выполнения — полная поддержка Stream и лямбда-выражений, многопоточность — эволюционные шаги могут выполняться параллельно

Чтобы использовать Jenetics, нам нужно добавить следующую зависимость в наш pom.xml:

<dependency>
    <groupId>io.jenetics</groupId>
    <artifactId>jenetics</artifactId>
    <version>3.7.0</version>
</dependency>

Последнюю версию можно найти в Maven Central.

3. Варианты использования

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

3.1. Простой генетический алгоритм

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

Factory<Genotype<BitGene>> gtf = Genotype.of(BitChromosome.of(10, 0.5));

Мы создали BitChromosome с длиной 10 и вероятностью наличия единиц в хромосоме, равной 0,5.

Теперь давайте создадим среду выполнения:

Engine<BitGene, Integer> engine
  = Engine.builder(SimpleGeneticAlgorithm::eval, gtf).build();

Метод eval() возвращает количество битов:

private Integer eval(Genotype<BitGene> gt) {
    return gt.getChromosome().as(BitChromosome.class).bitCount();
}

На последнем шаге мы запускаем эволюцию и собираем результаты:

Genotype<BitGene> result = engine.stream()
  .limit(500)
  .collect(EvolutionResult.toBestGenotype());

Конечный результат будет выглядеть примерно так:

Before the evolution:
[00000010|11111100]
After the evolution:
[00000000|11111111]

Нам удалось оптимизировать положение единиц в гене.

3.2. Задача о сумме подмножеств

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

В Jenetics есть предопределенные интерфейсы для решения таких задач:

public class SubsetSum implements Problem<ISeq<Integer>, EnumGene<Integer>, Integer> {
    // implementation
}

Как мы видим, мы реализуем Задачу\u003cT, G, C\u003e, которая имеет три параметра:

\u003cT\u003e †\» тип аргумента функции пригодности задачи, в нашем случае неизменяемая, упорядоченная целочисленная последовательность фиксированного размера ISeq\u003cInteger\u003e \u003cG\u003e — тип гена, с которым работает механизм эволюции, в данном случае счетные целочисленные гены EnumGene \u003cInteger\u003e \u003cC\u003e – тип результата фитнес-функции; здесь это целое число

Чтобы использовать интерфейс Problem\u003cT, G, C\u003e, нам нужно переопределить два метода:

@Override
public Function<ISeq<Integer>, Integer> fitness() {
    return subset -> Math.abs(subset.stream()
      .mapToInt(Integer::intValue).sum());
}

@Override
public Codec<ISeq<Integer>, EnumGene<Integer>> codec() {
    return codecs.ofSubSet(basicSet, size);
}

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

Теперь можно переходить к основной части. В начале нам нужно создать подмножество для использования в задаче:

SubsetSum problem = of(500, 15, new LCG64ShiftRandom(101010));

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

На следующем шаге строим движок нашего решения:

Engine<EnumGene<Integer>, Integer> engine = Engine.builder(problem)
  .minimizing()
  .maximalPhenotypeAge(5)
  .alterers(new PartiallyMatchedCrossover<>(0.4), new Mutator<>(0.3))
  .build();

Пытаемся минимизировать результат (оптимально результат будет 0 ) путем установки возраста фенотипа и альтераторов, используемых для изменения потомства. На следующем шаге мы можем получить результат:

Phenotype<EnumGene<Integer>, Integer> result = engine.stream()
  .limit(limit.bySteadyFitness(55))
  .collect(EvolutionResult.toBestPhenotype());

«

«Обратите внимание, что мы используем функцию bySteadyFitness(), которая возвращает предикат, который усекает поток эволюции, если после заданного количества поколений не может быть найден лучший фенотип, и собирает лучший результат. Если нам повезет, и есть решение для случайно созданного набора, мы увидим что-то похожее на это:

[85|-76|178|-197|91|-106|-70|-243|-41|-98|94|-213|139|238|219] --> 0

Если нам повезет, и есть решение для случайно созданного набора, мы увидим что-то похожее к этому:

В противном случае сумма подмножества будет отличной от 0.

3.3. Задача о ранце первой подгонки

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

int nItems = 15;
double ksSize = nItems * 100.0 / 3.0;

Давайте начнем с определения размера сумки и количества предметов:

KnapsackFF ff = new KnapsackFF(Stream.generate(KnapsackItem::random)
  .limit(nItems)
  .toArray(KnapsackItem[]::new), ksSize);

На следующем шаге мы сгенерируем случайный массив, содержащий объекты KnapsackItem (определяемые полями размера и значения), и мы поместим их предметы случайным образом внутри рюкзака, используя метод First Fit:

Engine<BitGene, Double> engine
  = Engine.builder(ff, BitChromosome.of(nItems, 0.5))
  .populationSize(500)
  .survivorsSelector(new TournamentSelector<>(5))
  .offspringSelector(new RouletteWheelSelector<>())
  .alterers(new Mutator<>(0.115), new SinglePointCrossover<>(0.16))
  .build();

Далее нам нужно создать движок:

Здесь следует отметить несколько моментов:

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

EvolutionStatistics<Double, ?> statistics = EvolutionStatistics.ofNumber();

Также есть одна очень важная особенность Jenetics. Мы можем легко собрать всю статистику и информацию за все время моделирования. Мы собираемся сделать это с помощью класса EvolutionStatistics:

Phenotype<BitGene, Double> best = engine.stream()
  .limit(bySteadyFitness(7))
  .limit(100)
  .peek(statistics)
  .collect(toBestPhenotype());

Наконец, давайте запустим симуляции:

Обратите внимание, что мы обновляем оценочную статистику после каждого поколения, которое ограничено 7 устойчивыми поколения и максимум 100 поколений в сумме. Более подробно возможны два сценария:

мы достигаем 7 устойчивых поколений, затем симуляция останавливается мы не можем получить 7 устойчивых генераций менее чем за 100 генераций, поэтому симуляция останавливается из-за второго предела()

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

+---------------------------------------------------------------------------+
|  Time statistics                                                          |
+---------------------------------------------------------------------------+
|             Selection: sum=0,039207931000 s; mean=0,003267327583 s        |
|              Altering: sum=0,065145069000 s; mean=0,005428755750 s        |
|   Fitness calculation: sum=0,029678433000 s; mean=0,002473202750 s        |
|     Overall execution: sum=0,111383965000 s; mean=0,009281997083 s        |
+---------------------------------------------------------------------------+
|  Evolution statistics                                                     |
+---------------------------------------------------------------------------+
|           Generations: 12                                                 |
|               Altered: sum=7 664; mean=638,666666667                      |
|                Killed: sum=0; mean=0,000000000                            |
|              Invalids: sum=0; mean=0,000000000                            |
+---------------------------------------------------------------------------+
|  Population statistics                                                    |
+---------------------------------------------------------------------------+
|                   Age: max=10; mean=1,792167; var=4,657748                |
|               Fitness:                                                    |
|                      min  = 0,000000000000                                |
|                      max  = 716,684883338605                              |
|                      mean = 587,012666759785                              |
|                      var  = 17309,892287851708                            |
|                      std  = 131,567063841418                              |
+---------------------------------------------------------------------------+

Окончательный результат содержит много информации:

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

Как проверить?

Это довольно простой процесс — просто откройте основной файл, связанный с проблемой, и сначала запустите алгоритм. Как только у нас появится общее представление, мы можем начать играть с параметрами.

4. Заключение

В этой статье мы рассмотрели возможности библиотеки Jenetics на основе реальных задач оптимизации.

Код доступен в виде проекта Maven на GitHub. Обратите внимание, что мы предоставили примеры кода для других задач оптимизации, таких как запись Спрингстина (да, она существует!) и задачи коммивояжера.

Все статьи серии, включая другие примеры генетических алгоритмов, можно найти по следующим ссылкам: