Selection (evolusjonær algoritme)

I evolusjonære algoritmer (EA) er valg en mekanisme der enkeltpersoner velges fra en befolkning. I bredere forstand telles seleksjon ofte blant de genetiske operatorene , selv om seleksjon i EA ikke fungerer på gennivå, men på individnivå. Evolusjonære algoritmer søker en løsning på et optimaliseringsproblem ved hjelp av prinsipper for naturlig evolusjon . Valg brukes til å velge løsningskandidater (individer) for rekombinasjon ( foreldrevalg ) og for å bestemme neste generasjon ( miljøvalg ), for dette formålet brukes kvaliteten på løsningskandidatene, som tildeles dem av en treningsfunksjon . Den biologiske modellen er naturlig seleksjon . Fremgangsmåtene som er oppført, avviker hovedsakelig i valgpresset . Jo høyere utvalgstrykk, jo raskere konvergerer en befolkning seg mot en bestemt løsning, og søkeområdet blir ikke utforsket tilstrekkelig. Hvis trykket er for lavt, konvergerer ikke befolkningen selv etter lang beregningstid .

I prinsippet kan hver metode brukes for både foreldre- og miljøvalg; spesielle konsepter er etablert for de spesifikke typene evolusjonære algoritmer .

Vanlige metoder

Beste utvalg

Den enkleste metoden for å velge individer fra en populasjon av løsningskandidater er å sortere befolkningen etter egnethet og å overta de første individene. Når det gjelder valg av miljø, skilles det mellom hensynet til bare etterkommere ( kommautvalg :) eller foreldre og etterkommere ( pluss utvalg :) . ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle \ mu, \ lambda}$${\ displaystyle \ mu + \ lambda}$

Fitness-proporsjonalt utvalg tilsvarer å kaste rouletteballer i en bolle med kamre i forskjellige størrelser.

Like utvalgte valgpunkter i stokastisk universell prøvetaking

Fitness-proporsjonalt utvalg

Metoden for miljøvalg opprinnelig foreslått av John H. Holland for genetiske algoritmer er kondisjon-proporsjonal seleksjon. Valget av individer tilsvarer å kaste en ball i rulett , hver person får tildelt en del av roulettehjulet som tilsvarer deres egnethet. Enda dårligere løsningskandidater har sjansen til å bli valgt på denne måten, men i begynnelsen av optimaliseringen dominerer ofte noen få høyere kvalitetskandidater hele utvelgelsesprosessen, i tillegg til at personer over gjennomsnittet drar nytte av det faktum at hvert valg blir gjort individuelt og med hvert valg det er stor sannsynlighet for at de blir valgt. I denne forbindelse er stokastisk universell prøvetaking en forbedring. Her kastes like store baller med en gang. Selv om enkeltpersoner også kan velges flere ganger her, har stokastisk universell prøvetaking en mangfoldsbevarende effekt sammenlignet med utvalg proporsjonalt med kondisjon. ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n}$

Turneringsvalg

I turneringsvalget blir enkeltpersoner gjentatte ganger valgt fra befolkningen. Fitnessverdiene deres blir sammenlignet og de beste individene vinner (turneringen). Prosessen kjøres flere ganger. Fordelene er den enkle implementeringen, den lave kompleksiteten og det faktum at kondisjonsverdier ikke trenger å være tilgjengelig for hver enkelt, men bare for de som deltar i turneringene. Problemet er at de beste individene ikke nødvendigvis trenger å bli valgt. ${\ displaystyle k}$${\ displaystyle n}$

Rangering av utvalg

Når det gjelder rangvalg, avhenger utvalgssannsynligheten ikke direkte av fitness, men av fitnessrangeringen til et individ i befolkningen. Dette relativiserer store forskjeller i kondisjon, og de eksakte kondisjonsverdiene i seg selv trenger ikke å være tilgjengelige, men bare en sortering av individene etter kvalitet.

Individuelle bevis

1. ↑ Karsten Weicker: Evolusjonære algoritmer , side 70.
2. ↑ Robert Ghanea-Hercock: Applied Evolutionary Algorithms in Java , side 37
3. ↑ Hüseyin Bostanci: Klyngebasert dataanalyse basert på genetiske algoritmer i SAP-BI , side 26.
4. ^ Xinjie Yu, Mitsuo Gen: Introduksjon til evolusjonære algoritmer , 74.