Přehled genetického algoritmu

Optimalizační techniky jsou techniky, které se používají k nalezení nejlepšího řešení ze všech možných řešení dostupných za současných omezení. Genetický algoritmus je tedy takový optimalizační algoritmus, který je postaven na přirozeném evolučním procesu naší přírody. Zde se používá myšlenka přirozeného výběru a genetické dědičnosti. Na rozdíl od jiných algoritmů používá řízené náhodné vyhledávání, tj. Nalezení optimálního řešení počínaje náhodnou počáteční nákladovou funkcí a poté vyhledávání pouze v prostoru, který měl nejnižší náklady (ve vedeném směru). Vhodné, pokud pracujete s obrovskými a složitými datovými soubory.

Co je to genetický algoritmus?

Genetický algoritmus je založen na genetické struktuře a chování chromozomu populace. Následující věci jsou základem genetických algoritmů.

  • Každý chromozom naznačuje možné řešení. Populace je tedy sbírka chromozomů.
  • Každý jednotlivec v populaci se vyznačuje fitness funkcí. Řešením je lepší kondice.
  • Z dostupných jedinců v populaci se nejlepší jedinci používají k reprodukci potomků další generace.
  • Vyprodukovaný potomek bude mít vlastnosti obou rodičů a je výsledkem mutace. Mutace je malá změna v genové struktuře.

Fáze genetického algoritmu

Níže jsou uvedeny různé fáze genetického algoritmu:

1. Inicializace populace (kódování)

  • Každý gen představuje parametr (proměnné) v řešení. Tato kolekce parametrů, které tvoří řešení, je chromozom. Populace je sbírka chromozomů.
  • Pořadí genů v chromozomech.
  • Většinu času jsou chromozomy zobrazeny v binárním formátu jako 0 a 1, ale existují i ​​jiná kódování.

2. Fitness funkce

  • Z dostupných chromozomů musíme vybrat ty nejlepší pro reprodukci potomků, takže každému chromozomu je přiřazena hodnota kondice.
  • Skóre kondice pomáhá vybrat jednotlivce, kteří budou použity pro reprodukci.

3. Výběr

  • Hlavním cílem této fáze je najít region, kde jsou šance na nejlepší řešení větší.
  • Inspirací pro to je přežití nejvhodnějších.
  • Měla by to být rovnováha mezi průzkumem a využíváním vyhledávacího prostoru.
  • GA se snaží přesunout genotyp do vyšší kondice ve vyhledávacím prostoru.
  • Příliš silné zkreslení výběru fitness může vést k suboptimálním řešením.
  • Příliš malý výběr zkreslení způsobilosti vede k nezaostřenému vyhledávání.
  • Používá se tedy přiměřený výběr Fitness, který je také známý jako výběr ruletového kola, je genetický operátor používaný v genetických algoritmech pro výběr potenciálně užitečných řešení pro rekombinaci.

4. Reprodukce

Vytváření potomků probíhá dvěma způsoby:

  • Crossover
  • Mutace

a) Crossover

Crossover je nejdůležitější fází genetického algoritmu. Během křížení se vybere náhodný bod, zatímco se páruje pár rodičů za účelem generování potomků.

Existují 3 hlavní typy křížení.

  • Jednobodový přechod: Bod na chromozomech obou rodičů je vybrán náhodně a označen jako „křížový bod“. Bity napravo od tohoto bodu jsou vyměňovány mezi dvěma rodičovskými chromozomy.
  • Dvoubodové křížení: Dva křížené body jsou vybírány náhodně z rodičovských chromozomů. Bity mezi dvěma body jsou zaměněny mezi mateřskými organizmy.
  • Uniformní křížení: Při jednotném křížení je obvykle každý bit vybrán z obou rodičů se stejnou pravděpodobností.

Nové potomstvo se přidá do populace.

b) Mutace

U několika nově vzniklých potomků mohou být některé z jejich genů podrobeny mutaci s nízkou náhodnou pravděpodobností. To ukazuje, že některé z bitů v bitovém chromozomu lze převrátit. Mutace se stará o rozmanitost populace a zastaví předčasnou konvergenci.

5. Konvergence (kdy zastavit)

Málo pravidel, která říkají, kdy zastavit, je následující:

  • Pokud nedojde ke zlepšení kvality řešení po dokončení určitého počtu generací před rukou.
  • Když je dosaženo tvrdé a rychlé řady generací a času.
  • Až do získání přijatelného roztoku.

Aplikace genetického algoritmu

V této části se budeme zabývat některými oblastmi, ve kterých se genetický algoritmus často používá.

1. Cestování a směrování zásilek

Problém obchodního cestujícího je jednou z hlavních aplikací genetického algoritmu. Například, když je plánovač cesty požádán, aby naplánoval cestu, využil by genetického algoritmu, který nejen pomůže snížit celkové náklady na cestu, ale také zkrátit čas.GE se také používá pro plánování dodávky produktů z místa na místo co nejefektivnějším způsobem.

2. Robotika

Genetický algoritmus je široce používán v oblasti robotiky. Roboti se od sebe liší podle účelu, pro který jsou vyrobeni. Například jen málo z nich je sestaveno pro úkol vaření, málo z nich je postaveno pro úkoly výuky atd.

  • Výběr důležitých funkcí v daném datovém souboru.
  • V tradiční metodě jsou důležité funkce v datovém souboru vybírány pomocí následující metody. tj. podíváte se na důležitost tohoto modelu, poté nastavíte prahovou hodnotu pro prvky a pokud má prvek hodnotu důležitosti vyšší než prahovou hodnotu, je to považováno.
  • Zde však používáme metodu zvanou problém s batohem.
  • Znovu začneme s populací chromozomu, kde každý chromozom bude binární řetězec. 1 označuje „zahrnutí“ prvku do modelu a 0 označuje „vyloučení“ prvku v modelu.
  • Funkce fitness zde bude naší metrikou přesnosti soutěže. Čím přesnější bude naše sada chromozomů v predikční hodnotě, tím lépe bude.
  • Existuje mnoho dalších aplikací genetických algoritmů, jako je analýza DNA, aplikace plánování, návrh konstrukce.

Závěr

V současném scénáři je společnost GE používána ve velkých výrobních společnostech, jako jsou letadla atd., Za účelem optimalizace využití času a zdrojů. Další vědci hledají nové způsoby kombinování genetických algoritmů s jinými optimalizačními technikami.

Doporučené články

Toto je průvodce Co je genetický algoritmus? Zde diskutujeme úvod, fáze a aplikace genetického algoritmu. Můžete si také prohlédnout naše další doporučené články -

  1. Algoritmy směrování
  2. Druhy algoritmů
  3. Algoritmy neuronových sítí
  4. Algoritmy dolování dat
  5. průvodce příklady algoritmů C ++

Kategorie:

Velká data