Operátor rekombinace hran - Edge recombination operator

The operátor hranové rekombinace (ERO) je operátor, který vytváří a cesta to je podobné jako u sady existujících cest (rodičů), když se podíváme spíše na hrany než na vrcholy. Hlavní aplikace je pro crossover v genetické algoritmy když je zapotřebí genotyp s neopakujícími se genovými sekvencemi, jako například pro problém obchodního cestujícího. Popsal to Darrell Whitley a další v roce 1989.[1]

Algoritmus

ERO je založen na matice sousedství, který uvádí seznam sousedů každého uzlu v libovolném nadřazeném objektu.

ERO crossover

Například v problému obchodního cestujícího, jako je ten, který je zobrazen, se mapa uzlů pro rodiče CABDEF a ABCEFD (viz obrázek) generuje tak, že se vezme první rodič, řekněme ‚ABCEFD 'a zaznamená jeho bezprostřední sousedy, včetně těch, které se valí kolem konce řetězce.

Proto;

... -> [A] <-> [B] <-> [C] <-> [E] <-> [F] <-> [D] <- ...

... se převede na následující matice sousedství tím, že postupně vezmeme každý uzel a uvedeme seznam jeho připojených sousedů;

A: B DB: A CC: B ED: F AE: C FF: E D

Se stejnou operací provedenou na druhém rodiči (CABDEF) se vytvoří následující:

A: C BB: A DC: F AD: B EE: D FF: E C

Následuje výroba unie z těchto dvou seznamů a ignorování duplikátů. To je stejně jednoduché jako převzetí prvků každého seznamu a jejich připojení k vygenerování seznamu jedinečných koncových bodů odkazu. V našem příkladu generování tohoto;

A: BCD = {B, D} ∪ {C, B} B: ACD = {A, C} ∪ {A, D} C: ABEF = {B, E} ∪ {F, A} D: ABEF = { F, A} ∪ {B, E} E: CDF = {C, F} ∪ {D, F} F: CDE = {E, D} ∪ {E, C}

Výsledek je jiný matice sousedství, který ukládá odkazy na síť popsanou všemi odkazy v rodičích. Pamatujte, že zde mohou být zaměstnáni více než dva rodiče, kteří poskytují různorodější odkazy. Tento přístup však může vyústit v neoptimální cesty.

Poté vytvořte cestu K., je použit následující algoritmus:[2]

algoritmus ero je    nechat K. být prázdný seznam ať N být prvním uzlem náhodného rodiče. zatímco délka(K.) dělat        K. := K., N   (připojit N na K.) Odebrat N ze všech seznamů sousedů li'NSeznam sousedů není prázdný pak            nechat N* být sousedem N s nejmenším počtem sousedů v seznamu (nebo náhodným, pokud by jich bylo více) jiný            nechat N* být náhodně vybraný uzel, který není v K.        N := N*

Abychom prošli příkladem, náhodně vybereme uzel z nadřazených výchozích bodů, {A, C}.

  • () -> A. Odebereme A ze všech sousedních sad a zjistíme, že nejmenší z B, C a D je B = {C, D}.
  • AB. Nejmenší sady C a D jsou C = {E, F} a D = {E, F}. Náhodně vybereme D.
  • ABD. Nejmenší jsou E = {C, F}, F = {C, E}. Vybíráme F.
  • ABDF. C = {E}, E = {C}. Vybereme C.
  • ABDFC. Nejmenší množina je E = {}.
  • ABDFCE. Délka dítěte je nyní stejná jako u rodiče, takže jsme hotoví.

Všimněte si, že jedinou hranou zavedenou v ABDFCE je AE.

Srovnání s ostatními operátory

Edge rekombinace je obecně považována za dobrou volbu pro problémy, jako je problém obchodního cestujícího. Ve studii z roku 1999 na Univerzita Baskicka, hranová rekombinace poskytla lepší výsledky než všichni ostatní operátoři crossoveru včetně částečně mapovaný crossover a crossover cyklu.[3]

Reference

  1. ^ Whitley, Darrell; Timothy Starkweather; D'Ann Fuquay (1989). "Problémy s plánováním a obchodní cestující: operátor rekombinace genetické hrany". Mezinárodní konference o genetických algoritmech. 133–140. ISBN  1-55860-066-3.
  2. ^ Darrell Whitley, Timothy Starkweather a Daniel Shaner: The Traveling Salesman and Sequence Scheduling: Quality Solutions using Genetic Edge Recombination v L. Davis (ed.): Příručka genetických algoritmů. Van Nostrand Reinhold, New York 1991
  3. ^ P. Larrañaga a kol .: Genetické algoritmy pro problém obchodního cestujícího: přehled zastoupení a provozovatelů. Recenze umělé inteligence, svazek 13, číslo 2, duben 1999, s. 129-170

Implementace