Genetický algoritmus je adaptívny heuristický vyhľadávací algoritmus inšpirovaný 'Darwinovou teóriou evolúcie v prírode .' Používa sa na riešenie optimalizačných problémov v strojovom učení. Je to jeden z dôležitých algoritmov, pretože pomáha riešiť zložité problémy, ktorých riešenie by trvalo dlho.

Genetické algoritmy sa široko používajú v rôznych aplikáciách v reálnom svete, napr. Navrhovanie elektronických obvodov, lámanie kódov, spracovanie obrazu a umelá kreativita.

V tejto téme podrobne vysvetlíme genetický algoritmus, vrátane základných terminológií používaných v genetickom algoritme, ako to funguje, výhody a obmedzenia genetického algoritmu atď.

Čo je to genetický algoritmus?

Predtým, ako pochopíme genetický algoritmus, najprv pochopme základné terminológie, aby sme lepšie porozumeli tomuto algoritmu:

Populácia:Populácia je podmnožinou všetkých možných alebo pravdepodobných riešení, ktoré môžu daný problém vyriešiť.Chromozómy:Chromozóm je jedným z riešení v populácii pre daný problém a zbierka génov generuje chromozóm.gén:Chromozóm je rozdelený na iný gén alebo je prvkom chromozómu.Alely:Alela je hodnota poskytnutá génu v konkrétnom chromozóme.Fitness funkcia:Funkcia fitness sa používa na určenie úrovne fyzickej zdatnosti jednotlivca v populácii. Znamená schopnosť jednotlivca súťažiť s inými jednotlivcami. V každej iterácii sú jednotlivci hodnotení na základe ich fitness funkcie.Genetickí operátori:V genetickom algoritme je najlepším jednotlivcom pár na regeneráciu potomstva lepšie ako rodičia. Genetické operátory tu zohrávajú úlohu pri zmene genetického zloženia ďalšej generácie.Výber

Po výpočte zdatnosti každého jestvujúceho v populácii sa výberovým procesom určí, ktorá z individualít v populácii sa dostane k reprodukcii a produkcii semena, ktoré vytvorí budúcu generáciu.

Dostupné typy štýlov výberu

Výber ruletového kolesa Výber udalosti Rankovaný výber

Takže teraz môžeme definovať genetický algoritmus ako heuristický vyhľadávací algoritmus na riešenie optimalizačných problémov. Je to podmnožina evolučných algoritmov, ktorá sa používa vo výpočtovej technike. Genetický algoritmus využíva koncepty genetického a prirodzeného výberu na riešenie problémov optimalizácie.

Ako funguje genetický algoritmus?

Genetický algoritmus pracuje na evolučnom generačnom cykle, aby vytvoril vysokokvalitné riešenia. Tieto algoritmy používajú rôzne operácie, ktoré buď rozširujú alebo nahradzujú populáciu, aby poskytli vylepšené riešenie prispôsobenia.

V podstate zahŕňa päť fáz na vyriešenie zložitých optimalizačných problémov, ktoré sú uvedené nižšie:

Inicializácia Fitness úloha Výber Rozmnožovanie Ukončenie

1. Inicializácia

Proces genetického algoritmu začína vygenerovaním množiny jedincov, ktorá sa nazýva populácia. Tu je riešením daného problému každý jednotlivec. Jednotlivec obsahuje alebo je charakterizovaný súborom parametrov nazývaných gény. Gény sa spájajú do reťazca a vytvárajú chromozómy, čo je riešením problému. Jednou z najpopulárnejších techník inicializácie je použitie náhodných binárnych reťazcov.

2. Fitness zadanie

Fitness funkcia sa používa na určenie toho, ako je jednotlivec fit? Znamená schopnosť jednotlivca súťažiť s inými jednotlivcami. V každej iterácii sú jednotlivci hodnotení na základe ich fitness funkcie. Funkcia fitness poskytuje každému jednotlivcovi skóre kondície. Toto skóre ďalej určuje pravdepodobnosť výberu na reprodukciu. Čím vyššie je skóre kondície, tým väčšia je šanca na výber na reprodukciu.

3. Výber

Fáza výberu zahŕňa výber jedincov na reprodukciu potomstva. Všetky vybrané jedince sú potom usporiadané do páru po dvoch, aby sa zvýšila reprodukcia. Potom títo jedinci prenesú svoje gény na ďalšiu generáciu.

K dispozícii sú tri typy metód výberu, ktorými sú:

• Výber ruletového kolesa
• Výber turnaja
• Výber na základe hodnotenia

4. Rozmnožovanie

Po výberovom procese nastáva v reprodukčnom kroku stvorenie dieťaťa. V tomto kroku genetický algoritmus používa dva operátory variácií, ktoré sa aplikujú na rodičovskú populáciu. Dvaja operátori zapojení do reprodukčnej fázy sú uvedení nižšie:

Crossover:Crossover hrá najvýznamnejšiu úlohu v reprodukčnej fáze genetického algoritmu. V tomto procese sa náhodne vyberie bod kríženia v rámci génov. Potom operátor kríženia vymení genetickú informáciu dvoch rodičov zo súčasnej generácie, aby vytvoril nového jedinca reprezentujúceho potomka.

Gény rodičov sa medzi sebou vymieňajú, kým sa nesplní bod kríženia. Títo novovytvorení potomkovia sa pridávajú k populácii. Tento proces sa tiež nazýva kríženie. Dostupné typy štýlov kríženia:
• Jeden bodový prechod
• Dvojbodový prechod
• Livrejový prechod
• Kríženie dedičných algoritmov
Mutácia
Mutačný operátor vloží náhodné gény do potomstva (nového dieťaťa), aby sa zachovala diverzita v populácii. Dá sa to urobiť prevrátením niektorých bitov v chromozómoch.
Mutácia pomáha pri riešení problému predčasnej konvergencie a zvyšuje diverzifikáciu. Nasledujúci obrázok ukazuje proces mutácie:
Dostupné typy štýlov mutácií,
Flip bitová mutácia Gaussova mutácia Výmena/swap mutácia

5. Ukončenie

Po fáze reprodukcie sa ako základ pre ukončenie použije kritérium zastavenia. Algoritmus sa ukončí po dosiahnutí prahovej vhodnosti riešenia. Identifikuje konečné riešenie ako najlepšie riešenie v populácii.

Všeobecný pracovný postup jednoduchého genetického algoritmu

Výhody genetického algoritmu

• Paralelné schopnosti genetických algoritmov sú najlepšie.
• Pomáha pri optimalizácii rôznych problémov, ako sú diskrétne funkcie, problémy s viacerými cieľmi a spojité funkcie.
• Poskytuje riešenie problému, ktoré sa časom zlepšuje.
• Genetický algoritmus nepotrebuje odvodené informácie.

Obmedzenia genetických algoritmov

• Genetické algoritmy nie sú efektívne algoritmy na riešenie jednoduchých problémov.
• Nezaručuje kvalitu konečného riešenia problému.
• Opakovaný výpočet hodnôt fitness môže spôsobiť určité výpočtové problémy.

Rozdiel medzi genetickými algoritmami a tradičnými algoritmami

• Vyhľadávací priestor je súbor všetkých možných riešení problému. V tradičnom algoritme sa zachováva iba jedna sada riešení, zatiaľ čo v genetickom algoritme možno použiť niekoľko sád riešení v priestore vyhľadávania.
• Tradičné algoritmy potrebujú viac informácií, aby mohli vykonať vyhľadávanie, zatiaľ čo genetické algoritmy potrebujú iba jednu objektívnu funkciu na výpočet zdatnosti jednotlivca.
• Tradičné algoritmy nemôžu fungovať paralelne, zatiaľ čo genetické algoritmy môžu fungovať paralelne (výpočet zdatnosti individualít je nezávislý).
• Jeden veľký rozdiel v genetických algoritmoch spočíva v tom, že dedičné algoritmy fungujú priamo na výsledkoch hľadačov, ale na ich reprezentáciách (alebo vykresľovaní), ktoré sa často označujú ako chromozómy.
• Jedným z veľkých rozdielov medzi tradičným algoritmom a genetickým algoritmom je to, že priamo nepracuje s kandidátskymi riešeniami.
• Tradičné algoritmy môžu nakoniec generovať iba jeden výsledok, zatiaľ čo genetické algoritmy môžu generovať viacero optimálnych výsledkov z rôznych generácií.
• Tradičný algoritmus s väčšou pravdepodobnosťou negeneruje optimálne výsledky, zatiaľ čo genetické algoritmy nezaručujú generovanie optimálnych globálnych výsledkov, ale je tu tiež veľká možnosť získať optimálny výsledok pre problém, pretože používa genetické operátory, ako sú Crossover a Mutation.
• Tradičné algoritmy sú svojou povahou deterministické, zatiaľ čo genetické algoritmy sú svojou povahou pravdepodobnostné a stochastické.