Kantrekombinationsoperatör

Kantrekombinationsoperatorn ( ERO ) är en operator som skapar en bana som liknar en uppsättning befintliga banor (föräldrar) genom att titta på kanterna snarare än hörnen . Den huvudsakliga tillämpningen av detta är för överkorsning i genetiska algoritmer när en genotyp med icke-repeterande gensekvenser behövs, såsom för resandeförsäljarproblemet . Det beskrevs av Darrell Whitley och andra 1989.

Algoritm

ERO är baserad på en närliggande matris , som listar grannarna till varje nod i valfri förälder.

ERO crossover

Till exempel, i ett resande säljarproblem som det som visas, genereras nodkartan för föräldrarna CABDEF och ABCEFD (se illustration) genom att ta den första föräldern, säg "ABCEFD" och registrera dess omedelbara grannar, inklusive de som rullar runt slutet av strängen.

Därför;

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

...omvandlas till följande närliggande matris genom att ta varje nod i tur och ordning och lista dess anslutna grannar;

A: BD B: AC C: BE D: FA E: CF F: ED

Med samma operation utförd på den andra föräldern (CABDEF), produceras följande:

A: CB B: AD C: FA D: BE E: DF F: EC

Följt av att göra en sammanslutning av dessa två listor och ignorera eventuella dubbletter. Detta är så enkelt som att ta elementen i varje lista och lägga till dem för att skapa en lista med unika länkslutpunkter. I vårt exempel genererar detta;

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}

Resultatet är en annan närliggande matris , som lagrar länkarna för ett nätverk som beskrivs av alla länkar i föräldrarna. Observera att fler än två föräldrar kan anställas här för att ge fler olika länkar. Detta tillvägagångssätt kan dock resultera i suboptimala vägar.

Sedan, för att skapa en väg K , används följande algoritm:

        

         algoritm  ero  är  låt  K  vara den tomma listan låt  N  vara den första noden för en slumpmässig förälder.  medan  length(  K  ) < length(Förälder)  gör  K  :=  K  ,  N  (lägg till  N  till  K  ) Ta bort  N från   alla  grannlistor   om  N  :s grannlista inte är tom,  låt  N  * vara granne till  N  med minsta grannar i sin lista (eller en slumpmässig, om det skulle finnas flera)  annars  låt  N  * vara en slumpmässigt vald nod som inte är i  K  N  :=  N  * 

För att gå igenom exemplet väljer vi slumpmässigt en nod från de överordnade startpunkterna, {A, C}.

• () -> A. Vi tar bort A från alla grannmängder och finner att den minsta av B, C och D är B={C,D}.
• AB. De minsta uppsättningarna av C och D är C={E,F} och D={E,F}. Vi väljer slumpmässigt D.
• ABD. Minsta är E={C,F}, F={C,E}. Vi väljer F.
• ABDF. C={E}, E={C}. Vi väljer C.
• ABDFC. Den minsta mängden är E={}.
• ABDFCE. Längden på barnet är nu samma som föräldern, så vi är klara.

Observera att den enda kanten som introduceras i ABDFCE är AE.

Jämförelse med andra operatörer

Kantrekombination anses generellt vara ett bra alternativ för problem som resandeförsäljarproblemet. I en studie från 1999 vid universitetet i Baskien gav kantrekombination bättre resultat än alla andra crossover-operatörer inklusive delvis kartlagd crossover och cykelcrossover.