streamalism.org

1. Úvod

Cieľom tejto série je: vysvetliť myšlienku genetických algoritmov.

Genetické algoritmy sú určené na riešenie problémov pomocou rovnakých procesov ako v prírode - na vyvinutie riešenia problému používajú kombináciu selekcie, rekombinácie a mutácie.

Začnime vysvetlením konceptu týchto algoritmov pomocou príkladu najjednoduchšieho binárneho genetického algoritmu.

2. Ako fungujú genetické algoritmy

Genetické algoritmy sú súčasťou evolučného počítania, čo je rýchlo rastúca oblasť umelej inteligencie.

Algoritmus začína a súbor riešení (reprezentovaný jednotlivcov) zavolal populácia. Riešenia z jednej populácie sa odoberajú a používajú na vytvorenie a nová populácia, pretože existuje šanca, že nová populácia bude lepšia ako stará populácia.

Jednotlivci, ktorí sú vybraní, aby vytvorili nové riešenia (potomkov) sa vyberajú podľa ich fitnes - čím sú vhodnejšie, tým väčšie sú šance na reprodukciu.

3. Binárny genetický algoritmus

Poďme sa pozrieť na základný proces jednoduchého genetického algoritmu.

3.1. Inicializácia

V kroku inicializácie sme vygenerovať náhodný Populácia ktorý slúži ako prvé riešenie. Najprv sa musíme rozhodnúť, aké veľké Populácia bude a aké je konečné riešenie, ktoré očakávame:

SimpleGeneticAlgorithm.runAlgorithm (50, "1011000100000100010000100000100111001000000100000100000000001111");

Vo vyššie uvedenom príklade Populácia veľkosť je 50 a správne riešenie predstavuje binárny bitový reťazec, ktorý môžeme kedykoľvek zmeniť.

V ďalšom kroku uložíme požadované riešenie a vytvoríme náhodné Populácia:

setSolution (riešenie); Populácia myPop = nová populácia (populačná veľkosť, true);

Teraz sme pripravení spustiť hlavnú slučku programu.

3.2. Kontrola fitnes

V hlavnej slučke programu sa chystáme vyhodnotiť každý Individuálne funkciou fitness (jednoduchými slovami, tým lepšie Individuálne znamená vyššiu hodnotu funkcie fitnes):

while (myPop.getFittest (). getFitness () <getMaxFitness ()) {System.out.println ("Generácia:" + generationCount + "Boli nájdené správne gény:" + myPop.getFittest (). getFitness ()); myPop = evolvePopulation (myPop); generationCount ++; }

Začnime vysvetlením ako sa dostaneme najschopnejší Individuálne:

public int getFitness (jednotlivec jednotlivec) {int fitness = 0; for (int i = 0; i <individual.getDefaultGeneLength () && i <solution.length; i ++) {if (individual.getSingleGene (i) == solution [i]) {fitness ++; }} vrátiť fitnes; }

Ako môžeme pozorovať, porovnávame dva Individuálne predmety kúsok po kúsku. Ak nenájdeme dokonalé riešenie, musíme prejsť k ďalšiemu kroku, ktorým je vývoj Populácia.

3.3. Potomkovia

V tomto kroku musíme vytvoriť nový Populácia. Najprv musíme Vyberte dvaja rodičia Individuálne predmety z a Populácia, podľa ich zdatnosti. Upozorňujeme, že je výhodné povoliť to najlepšie Individuálne zo súčasnej generácie preniesť do ďalšej, nezmenené. Táto stratégia sa nazýva Elitárstvo:

if (elitárstvo) {newPopulation.getIndividuals (). add (0, pop.getFittest ()); elitizmusOffset = 1; } else {elitismOffset = 0; }

Aby sme vybrali dvoch najlepších Individuálne predmety, ideme aplikovať stratégia výberu turnaja:

privátne Individuálne turnajSelekcia (Populačná populácia) {Populačný turnaj = nová populácia (turnajová veľkosť, nepravda); pre (int i = 0; i <turnajVeľkosť; i ++) {int randomId = (int) (Math.random () * pop.getIndividuals (). size ()); turnaj.getIndividuals (). add (i, pop.getIndividual (randomId)); } Individuálny test = turnaj.getFittest (); návrat najschopnejší; }

Víťaz každého turnaja (ten s najlepšou kondíciou) je vybraný do ďalšej fázy, ktorou je Crossover:

crossover súkromných osôb (Jednotlivec indiv1, Jednotlivec ind2) {Individual newSol = new Individual (); pre (int i = 0; i <newSol.getDefaultGeneLength (); i ++) {if (Math.random () <= uniformRate) {newSol.setSingleGene (i, indiv1.getSingleGene (i)); } else {newSol.setSingleGene (i, indiv2.getSingleGene (i)); }} vrátiť newSol; }

V crossoveri zameníme bity od každého vybraného Individuálne na náhodne zvolenom mieste. Celý proces prebieha v nasledujúcej slučke:

for (int i = elitismOffset; i <pop.getIndividuals (). size (); i ++) {Individual indiv1 = turnajSelection (pop); Jednotlivec indiv2 = turnajVýber (pop); Jednotlivec newIndiv = prechod (indiv1, indiv2); newPopulation.getIndividuals (). add (i, newIndiv); }

Ako vidíme, po crossoveri umiestňujeme nových potomkov do nového Populácia. Tento krok sa nazýva Prijatie.

Nakoniec môžeme vykonať a Mutácia. Mutácia sa používa na udržanie genetickej diverzity z jednej generácie a Populácia do ďalšej. Použili sme bitová inverzia typ mutácie, kde sa náhodné bity jednoducho invertujú:

private void mutate (Individual indiv) {for (int i = 0; i <indiv.getDefaultGeneLength (); i ++) {if (Math.random () <= mutationRate) {byte gen = (byte) Math.round (Math. random ()); indiv.setSingleGene (i, gén); }}}

V tomto návode sú pekne popísané všetky typy mutácií a výhybiek.

Potom opakujeme kroky z pododdielov 3.2 a 3.3, až kým nedosiahneme podmienku ukončenia, napríklad najlepšie riešenie.

4. Tipy a triky

Za účelom implementovať efektívny genetický algoritmus, musíme vyladiť súbor parametrov. Táto časť by vám mala poskytnúť niekoľko základných odporúčaní, ako začať s najdôležitejšími parametrami importu:

• Miera kríženia - mala by byť vysoká, asi 80%-95%
• Miera mutácií - mala by byť veľmi nízka, okolo 0.5%-1%.
• Veľkosť populácie - dobrá veľkosť populácie je asi 20-30, avšak pre niektoré problémy sú lepšie veľkosti 50-100
• Výber - základné výber rulety možno použiť s konceptom elitárstvo
• Typ kríženia a mutácie - záleží to na kódovaní a probléme

Upozorňujeme, že odporúčania na vyladenie sú často výsledkom empirických štúdií o genetických algoritmoch a môžu sa líšiť v závislosti od navrhovaných problémov.

5. Záver

Tento návod zavádza základy genetických algoritmov. Môžete sa dozvedieť viac o genetických algoritmoch bez akýchkoľvek predchádzajúcich vedomostí tejto oblasti, majúc iba základné znalosti programovania v počítači.

Kompletný zdrojový kód úryvkov kódu v tomto tutoriále je k dispozícii v projekte GitHub.

Upozorňujeme tiež, že program Lombok používame na generovanie getrov a setterov. Ako sa dá správne nakonfigurovať vo vašom IDE, si môžete skontrolovať v tomto článku.

Ďalšie príklady genetických algoritmov nájdete vo všetkých článkoch našej série:

• Ako navrhnúť genetický algoritmus? (toto)
• Problém cestovného predajcu v Jave