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. Простой генетический алгоритм
Предположим, что нам нужно решить простейшую бинарную задачу, где нам нужно оптимизировать позиции битов 1 в хромосоме, состоящей из 0 и 1. Во-первых, нам нужно определить фабрику, подходящую для задачи:
Factory<Genotype<BitGene>> gtf = Genotype.of(BitChromosome.of(10, 0.5));
Мы создали битхромосому длиной 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
}
Как мы видим, мы реализуем Problem<T, G, C> с тремя параметрами:
<T>— тип аргумента функции пригодности задачи, в нашем случае неизменяемая, упорядоченнаяцелочисленнаяпоследовательностьфиксированного размера ISeq<Integer><G>— тип гена, с которым работает эволюционный движок, в данном случае счетныецелочисленныегеныEnumGene<Integer><C>– тип результата фитнес-функции; вот этоцелое число
Чтобы использовать интерфейс Problem<T, G, C> , нам нужно переопределить два метода:
@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;
На следующем шаге мы создадим случайный массив, содержащий объекты KnapsackItem (определяемые полями размера и значения ), и мы случайным образом поместим эти предметы в рюкзак, используя метод First Fit:
KnapsackFF ff = new KnapsackFF(Stream.generate(KnapsackItem::random)
.limit(nItems)
.toArray(KnapsackItem[]::new), ksSize);
Далее нам нужно создать Engine :
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 человек
- потомство будет выбрано с помощью турниров и выбора колеса рулетки
- как и в предыдущем подразделе, нам также нужно определить альтереры для вновь созданного потомка.
Также есть одна очень важная особенность Jenetics. Мы можем легко собрать всю статистику и информацию за все время моделирования. Мы собираемся сделать это с помощью класса EvolutionStatistics :
EvolutionStatistics<Double, ?> statistics = EvolutionStatistics.ofNumber();
Наконец, давайте запустим симуляции:
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 . Обратите внимание, что мы предоставили примеры кода для других задач оптимизации, таких как запись Спрингстина (да, она существует!) и задачи коммивояжера.
Все статьи серии, включая другие примеры генетических алгоритмов, можно найти по следующим ссылкам:
- Как разработать генетический алгоритм на Java
- Задача коммивояжера в Java
- Оптимизация муравьиной колонии
- Введение в библиотеку Jenetics (это)