streamalism.org

1. Úvod

Cieľom tejto série je vysvetliť myšlienku genetických algoritmov a ukázať najznámejšie implementácie.

V tomto výučbe to urobíme popísať veľmi výkonnú knižnicu Jenetics Java, ktorú je možné použiť na riešenie rôznych optimalizačných problémov.

Ak máte pocit, že sa potrebujete dozvedieť viac informácií o genetických algoritmoch, odporúčame začať týmto článkom.

2. Ako to funguje?

Podľa jej oficiálnych dokumentov je Jenetics knižnica založená na evolučnom algoritme napísanom v jazyku Java. Evolučné algoritmy majú svoje korene v biológii, pretože využívajú mechanizmy inšpirované biologickou evolúciou, ako je reprodukcia, mutácia, rekombinácia a selekcia.

Jenetics sa implementuje pomocou Java Prúd rozhranie, takže funguje dobre so zvyškom Javy Prúd API.

Hlavné vlastnosti sú:

• bezfrikčná minimalizácia - nie je potrebné meniť alebo vylepšovať funkciu fitness; môžeme len zmeniť konfiguráciu Motor triedy a sme pripravení spustiť našu prvú aplikáciu
• závislosť zadarmo - na použitie protokolu Jenetics nie sú potrebné žiadne runtime knižnice tretích strán
• Java 8 pripravená Plná podpora pre Windows Prúd a výrazy lambda
• viacvláknové - vývojové kroky je možné vykonávať paralelne

Aby sme mohli používať Jenetics, musíme do našej pridať nasledujúcu závislosť pom.xml:

 io.jenetics jenetics 3.7.0 

Najnovšiu verziu nájdete v Maven Central.

3. Používajte puzdrá

Aby sme vyskúšali všetky funkcie Jenetics, pokúsime sa vyriešiť rôzne známe optimalizačné problémy, počnúc jednoduchým binárnym algoritmom a končiac problémom Knapsack.

3.1. Jednoduchý genetický algoritmus

Predpokladajme, že musíme vyriešiť najjednoduchší binárny problém, kde musíme optimalizovať polohy 1 bitov v chromozóme pozostávajúcich z 0 a 1. Najprv musíme definovať továreň vhodnú pre daný problém:

Továreň gtf = Genotype.of (BitChromozome.of (10, 0,5));

Vytvorili sme BitChromozóm s dĺžkou 10 a pravdepodobnosť výskytu 1 v chromozóme rovná 0,5.

Teraz vytvorme prostredie vykonávania:

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

The eval () metóda vráti počet bitov:

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

V poslednom kroku začneme vývoj a zhromažďujeme výsledky:

Výsledok genotypu = engine.stream () .limit (500) .collect (EvolutionResult.toBestGenotype ());

Konečný výsledok bude vyzerať podobne ako tento:

Pred evolúciou: [00000010 | 11111100] Po evolúcii: [00000000 | 11111111]

Podarilo sa nám optimalizovať polohu 1 v géne.

3.2. Problém s čiastkovou čiastkou

Ďalším prípadom použitia pre Jenetics je riešenie problému s čiastkovou čiastkou. Stručne povedané, výzvou na optimalizáciu je, že vzhľadom na množinu celých čísel musíme nájsť neprázdnu podmnožinu, ktorej súčet je nulový.

V serveri Jenetics sú preddefinované rozhrania na riešenie týchto problémov:

verejná trieda SubsetSum implementuje problém {// implementácia}

Ako vidíme, implementujeme Problém, ktorý má tri parametre:

• - typ argumentu problémovej fitnes funkcie, v našom prípade nemenná, usporiadaná, pevná veľkosť Celé číslo postupnosť ISeq
• - typ génu, s ktorým evolučný motor pracuje, v tomto prípade spočítateľný Celé číslo gény EnumGene
• - výsledný typ fitnes funkcie; tu je to Celé číslo

Aby bolo možné použiť Problém musíme prepísať dve metódy:

@ Verejná funkcia override fitness () {return subset -> Math.abs (subset.stream () .mapToInt (Integer :: intValue) .sum ()); } @ Override verejný kodek codec () {return codecs.ofSubSet (basicSet, size); }

V prvej definujeme našu fitnes funkciu, zatiaľ čo druhou je trieda obsahujúca továrenské metódy vytvárania bežných kódovaní problémov, napríklad na vyhľadanie najlepšej podmnožiny pevnej veľkosti z danej základnej množiny, ako je to v našom prípade.

Teraz môžeme prejsť k hlavnej časti. Na začiatku musíme vytvoriť podmnožinu, ktorú použijeme v probléme:

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

Upozorňujeme, že používame LCG64ShiftRandom generátor poskytovaný spoločnosťou Jenetics. V ďalšom kroku budujeme motor nášho riešenia:

V ďalšom kroku staviame motor nášho riešenia:

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

Snažíme sa minimalizovať výsledok (optimálny bude výsledok 0) nastavením veku fenotypu a alterantov použitých na alteráciu potomstva. V ďalšom kroku môžeme získať výsledok:

Fenotyp výsledok = engine.stream () .limit (limit.bySteadyFitness (55)) .collect (EvolutionResult.toBestPhenotype ());

Upozorňujeme, že používame bySteadyFitness () ktorý vráti predikát, ktorý skráti vývojový prúd, ak po danom počte generácií nenájdete lepší fenotyp a získate najlepší výsledok. Ak budeme mať šťastie a bude tu riešenie náhodne vytvorenej množiny, uvidíme niečo podobné tomuto:

Ak budeme mať šťastie a bude tu riešenie náhodne vytvorenej množiny, uvidíme niečo podobné tomuto:

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

V opačnom prípade bude súčet podmnožiny iný ako 0.

3.3. Problém s prvým nasadením batohu

Knižnica Jenetics nám umožňuje vyriešiť ešte zložitejšie problémy, ako napríklad problém s batohom. Stručne povedané, v tomto probléme máme v batohu obmedzený priestor a musíme sa rozhodnúť, ktoré predmety vložíme dovnútra.

Začnime s definíciou veľkosti tašky a počtu položiek:

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

V ďalšom kroku vygenerujeme náhodné pole obsahujúce Položka batohu objekty (definované veľkosť a hodnotu polia) a tieto položky náhodne vložíme do batohu pomocou metódy First Fit:

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

Ďalej musíme vytvoriť Motor:

Engine engine = Engine.builder (ff, BitChromosome.of (nItems, 0.5)) .populationSize (500) .survivorsSelector (new TournamentSelector (5)) .offspringSelector (new RouletteWheelSelector ()). Alterters (new Mutator (0.115), new SinglePointCrossover (0,16)) .build ();

Tu je potrebné poznamenať niekoľko bodov:

• počet obyvateľov je 500
• potomstvo bude vybrané prostredníctvom turnaja a výberu rulety
• ako sme to urobili v predchádzajúcej podsekcii, musíme tiež definovať alternátory pre novovytvoreného potomka

Jenetics má tiež jednu veľmi dôležitú vlastnosť. Môžeme ľahko zhromaždiť všetky štatistiky a postrehy z celého trvania simulácie. Urobíme to pomocou EvolutionStatistics trieda:

Štatistika EvolutionStatistics = EvolutionStatistics.ofNumber ();

Nakoniec spustíme simulácie:

Najlepší fenotyp = engine.stream () .limit (bySteadyFitness (7)) .limit (100) .peek (štatistika) .collect (toBestPhenotype ());

Upozorňujeme, že po každej generácii aktualizujeme štatistické údaje o hodnotení, ktoré sú obmedzené na 7 ustálených generácií a celkovo maximálne na 100 generácií. Podrobnejšie existujú dva možné scenáre:

• dosiahneme 7 stabilných generácií, potom sa simulácia zastaví
• nemôžeme získať 7 stabilných generácií za menej ako 100 generácií, takže simulácia sa zastaví kvôli druhej limit ()

Je dôležité mať obmedzený maximálny počet generácií, inak sa simulácie nemusia zastaviť v rozumnom čase.

Konečný výsledok obsahuje veľa informácií:

+ ------------------------------------------------- -------------------------- + | Časová štatistika + ------------------------------------------------- -------------------------- + | Výber: súčet = 0,039207931000 s; priemer = 0,003267327583 s | | Zmena: suma = 0,065145069000 s; priemer = 0,005428755750 s | | Výpočet zdatnosti: suma = 0,029678433000 s; priemer = 0,002473202750 s | | Celkové prevedenie: suma = 0,111383965000 s; priemer = 0,009281997083 s | + ------------------------------------------------- -------------------------- + | Štatistika vývoja + ------------------------------------------------- -------------------------- + | Generácie: 12 | | Zmenené: suma = 7 664; priemer = 638 6666666667 | | Zabité: suma = 0; priemer = 0,000000000 | | Neplatné: suma = 0; priemer = 0,000000000 | + ------------------------------------------------- -------------------------- + | Štatistika obyvateľstva + ------------------------------------------------- -------------------------- + | Vek: max = 10; priemer = 1,792167; var = 4,657748 | | Fitness: | | min = 0,000000000000 | | max = 716,684883338605 | | priemer = 587,012666759785 | | var = 17309,892287851708 | | std = 131,567063841418 | + ------------------------------------------------- -------------------------- +

Tentokrát sme mohli do najlepšieho scenára umiestniť položky v celkovej hodnote 716,68. Vidíme tiež podrobné štatistiky vývoja a času.

Ako testovať?

Je to pomerne jednoduchý proces - stačí otvoriť hlavný súbor súvisiaci s problémom a najskôr spustiť algoritmus. Keď už máme všeobecnú predstavu, môžeme sa začať hrať s parametrami.

4. Záver

V tomto článku sme sa venovali funkciám knižnice Jenetics na základe skutočných problémov s optimalizáciou.

Kód je k dispozícii ako projekt Maven na GitHub. Upozorňujeme, že sme poskytli príklady kódu pre ďalšie optimalizačné úlohy, ako sú napríklad problémy Springsteen Record (áno, existuje!) A Traveller Salesman.

Všetky články v sérii vrátane ďalších príkladov genetických algoritmov nájdete na nasledujúcich odkazoch:

• Ako navrhnúť genetický algoritmus v Jave
• Problém cestovného predajcu v Jave
• Optimalizácia kolónie mravcov
• Úvod do knižnice Jenetics (toto)