«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. Обратите внимание, что мы предоставили примеры кода для других задач оптимизации, таких как запись Спрингстина (да, она существует!) и задачи коммивояжера.
-
Все статьи серии, включая другие примеры генетических алгоритмов, можно найти по следующим ссылкам: