Crossover (genetický algoritmus) - Crossover (genetic algorithm)

Část seriálu o
Evoluční algoritmus
Genetický algoritmus
Genetické programování

V genetických algoritmech a evolučních výpočtech je crossover , nazývaný také rekombinace , genetickým operátorem používaným ke kombinování genetické informace dvou rodičů ke generování nových potomků. Je to jeden ze způsobů, jak stochasticky generovat nová řešení ze stávající populace, a je analogický přechodu , ke kterému dochází během sexuální reprodukce v biologii . Řešení lze také generovat klonováním existujícího řešení, které je analogické s nepohlavní reprodukcí . Nově generovaná řešení jsou před přidáním do populace obvykle mutována .

Různé algoritmy v evolučních výpočtech mohou k ukládání genetické informace používat různé datové struktury a každá genetická reprezentace může být rekombinována s různými operátory křížení. Typickými datovými strukturami, které lze rekombinovat s crossoverem, jsou bitová pole , vektory reálných čísel nebo stromy .

Příklady

Tradiční genetické algoritmy ukládají genetické informace do chromozomu představovaného bitovým polem . Crossover metody pro bitová pole jsou populární a ilustrativní příklad genetické rekombinace .

Jednobodový crossover

Bod na chromozomech obou rodičů je vybrán náhodně a je označen jako „křížový bod“. Bity napravo od tohoto bodu jsou zaměněny mezi dvěma rodičovskými chromozomy. To má za následek dva potomky, z nichž každý nese genetickou informaci od obou rodičů.

OnePointCrossover.svg

Crossover dvou bodů a bodů k

Při dvoubodovém křížení jsou dva křížové body náhodně vybrány z rodičovských chromozomů. Bity mezi těmito dvěma body jsou vyměňovány mezi mateřskými organismy.

TwoPointCrossover.svg

Dvoubodový výhybka je ekvivalentní provedení dvou jednobodových výhybek s různými výhybkami. Tuto strategii lze zobecnit na křížení bodu k pro jakékoli kladné celé číslo k, výběr bodů křížení k.

Rovnoměrný výhybka

V jednotném křížení je obvykle každý bit vybrán z kteréhokoli z rodičů se stejnou pravděpodobností. Někdy se používají jiné směšovací poměry, což vede k potomkům, kteří zdědí více genetické informace od jednoho rodiče než od druhého.

Crossover pro objednané seznamy

V některých genetických algoritmech ne všechny možné chromozomy představují platná řešení. V některých případech je možné použít specializované operátory křížení a mutace, které jsou navrženy tak, aby nedocházelo k porušování omezení problému.

Například genetický algoritmus řešící problém obchodního cestujícího může použít uspořádaný seznam měst k představení cesty řešení. Takový chromozom představuje platné řešení, pouze pokud seznam obsahuje všechna města, která musí prodejce navštívit. Použití výše uvedených výhybek bude mít často za následek chromozomy, které toto omezení porušují. Genetické algoritmy optimalizující pořadí daného seznamu tedy vyžadují různé operátory křížení, které zabrání generování neplatných řešení. Bylo publikováno mnoho takových crossoverů:

  1. částečně mapovaný crossover (PMX)
  2. crossover cyklu (CX)
  3. operátor crossover objednávky (OX1)
  4. operátor přechodu na základě objednávky (OX2)
  5. operátor přechodu na základě polohy (POS)
  6. operátor křížení hlasovacích rekombinací (VR)
  7. operátor výhybky ve střídavé poloze (AP)
  8. operátor sekvenční konstruktivní výhybky (SCX)
  9. operátor simulovaného binárního přechodu (SBX)

Mezi další možné metody patří operátor okrajové rekombinace . Alternativně lze k překonání zmíněného problému použít dvojité chromozomy.

Viz také

Reference

  • John Holland, Adaptation in Natural and Artificial Systems , University of Michigan Press , Ann Arbor, Michigan. 1975. ISBN  0-262-58111-6 .
  • Larry J. Eshelman, CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Netraditional Genetic Recombination , in Gregory JE Rawlins editor, Proceedings of the First Workshop on Foundations of Genetic Algorithms. stránky 265-283. Morgan Kaufmann, 1991. ISBN  1-55860-170-8 .
  • Tomasz D. Gwiazda, Genetic Algorithms Reference Vol.1 Crossover pro jednocílové problémy numerické optimalizace , Tomasz Gwiazda, Lomianki, 2006. ISBN  83-923958-3-2 .

externí odkazy