Въведение в библиотеката Jenetics

1. Въведение

Целта на тази поредица е да обясни идеята за генетичните алгоритми и да покаже най-известните реализации.

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

Ако смятате, че трябва да научите повече за генетичните алгоритми, препоръчваме да започнете с тази статия.

2. Как работи?

Според официалните си документи Jenetics е библиотека, базирана на еволюционен алгоритъм, написан на Java. Еволюционните алгоритми имат своите корени в биологията, тъй като използват механизми, вдъхновени от биологичната еволюция, като репродукция, мутация, рекомбинация и селекция.

Jenetics се реализира с помощта на интерфейса Java Stream , така че работи безпроблемно с останалата част от API на Java Stream .

Основните характеристики са:

  • минимизиране без триене - няма нужда да променяте или променяте фитнес функцията; можем просто да променим конфигурацията на класа Engine и сме готови да стартираме първото си приложение
  • без зависимост - няма изпълними библиотеки на трети страни, необходими за използване на Jenetics
  • Готов за Java 8 - пълна поддръжка за поточни и ламбда изрази
  • многонишкови - еволюционни стъпки могат да се изпълняват паралелно

За да използваме Jenetics, трябва да добавим следната зависимост в нашия pom.xml :

 io.jenetics jenetics 3.7.0 

Най-новата версия може да бъде намерена в Maven Central.

3. Използвайте калъфи

За да тестваме всички функции на Jenetics, ще се опитаме да решим различни добре познати проблеми с оптимизацията, започвайки от простия двоичен алгоритъм и завършвайки с проблема Knapsack.

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

Нека приемем, че трябва да решим най-простия двоичен проблем, където трябва да оптимизираме позициите на 1 бита в хромозомата, състоящ се от 0 и 1. Първо, трябва да определим фабриката, подходяща за проблема:

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

Създадохме BitChromosome с дължина 10 и вероятността да имаме 1 в хромозомата равна на 0,5.

Сега нека създадем среда за изпълнение:

Engine engine = Engine.builder(SimpleGeneticAlgorithm::eval, gtf).build();

Методът eval () връща броя на битовете:

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

В последната стъпка започваме еволюцията и събираме резултатите:

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

Крайният резултат ще изглежда подобно на този:

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

Успяхме да оптимизираме позицията на 1 в гена.

3.2. Проблем със сумата на подмножеството

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

В Jenetics има предварително дефинирани интерфейси за решаване на такива проблеми:

public class SubsetSum implements Problem
    
      { // implementation }
    

Както виждаме, ние прилагаме проблема , който има три параметъра:

  • - типът аргумент на функцията за фитнес на проблема, в нашия случай неизменяема, подредена, с фиксиран размер Integer последователност ISeq
  • - типът на гена, с който двигателят за еволюция работи, в този случай, преброими Integer гени EnumGene
  • - типа резултат на фитнес функцията; тук е цяло число

За да използваме проблемния интерфейс, трябва да заменим два метода:

@Override public Function
    
      fitness() { return subset -> Math.abs(subset.stream() .mapToInt(Integer::intValue).sum()); } @Override public Codec
     
       codec() { return codecs.ofSubSet(basicSet, size); }
     
    

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

Сега можем да преминем към основната част. В началото трябва да създадем подмножество, което да използваме в проблема:

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

Моля, обърнете внимание, че използваме генератора LCG64ShiftRandom, предоставен от Jenetics. В следващата стъпка ние изграждаме двигателя на нашето решение:

В следващата стъпка ние изграждаме двигателя на нашето решение:

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

Опитваме се да минимизираме резултата (оптимално резултатът ще бъде 0), като определяме възрастта на фенотипа и променящите се, използвани за промяна на потомството. В следващата стъпка можем да получим резултата:

Phenotype
    
      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. Раница First Fit Проблем

Библиотеката 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 = 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 statistics = EvolutionStatistics.ofNumber();

И накрая, нека стартираме симулациите:

Phenotype best = engine.stream() .limit(bySteadyFitness(7)) .limit(100) .peek(statistics) .collect(toBestPhenotype());

Моля, имайте предвид, че актуализираме статистическите данни за оценка след всяко поколение, което е ограничено до 7 стабилни поколения и максимум 100 поколения общо. По-подробно има два възможни сценария:

  • постигаме 7 стабилни поколения, след което симулацията спира
  • не можем да получим 7 стабилни поколения за по-малко от 100 поколения, така че симулацията спира поради втората граница ()

It's important to have maximum generations limit, otherwise, the simulations may not stop in a reasonable time.

The final result contains a lot of information:

+---------------------------------------------------------------------------+ | 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 | +---------------------------------------------------------------------------+

This particular time, we were able to put items with a total value of 716,68 in the best scenario. We also can see the detailed statistics of evolution and time.

How to test?

It is a fairly simple process — just open the main file related to the problem and first run the algorithm. Once we have a general idea, then we can start playing with the parameters.

4. Conclusion

In this article, we covered the Jenetics library features based on real optimization problems.

The code is available as a Maven project on GitHub. Please note that we provided the code examples for more optimization challenges, such as the Springsteen Record (yes, it exists!) and Traveling Salesman problems.

За всички статии от поредицата, включително други примери за генетични алгоритми, разгледайте следните връзки:

  • Как да проектирам генетичен алгоритъм в Java
  • Проблемът с пътуващия продавач в Java
  • Оптимизация на колонията на мравки
  • Въведение в библиотеката на Jenetics (това)