Genetisk algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 januari 2020; kontroller kräver 17 redigeringar .

En genetisk algoritm är en  heuristisk sökalgoritm som används för att lösa optimerings- och modelleringsproblem genom slumpmässigt urval, kombination och variation av de önskade parametrarna med hjälp av mekanismer som liknar naturligt urval i naturen. Det är en typ av evolutionär beräkning som löser optimeringsproblem med hjälp av naturliga evolutionsmetoder som nedärvning , mutation , urval och överkorsning . En utmärkande egenskap hos den genetiska algoritmen är betoningen på användningen av "korsnings"-operatorn, som utför operationen av rekombination av kandidatlösningar, vars roll liknar rollen för korsning i naturen.

Historik

Det första arbetet med simulering av evolution utfördes 1954 av Nils Baricelli på en dator installerad vid Institute for Advanced Study vid Princeton University. [1] [2] Hans verk, publicerat samma år, väckte stor uppmärksamhet från allmänheten. Sedan 1957 [3] har den australiensiska genetikern Alex Fraser publicerat en serie artiklar som simulerar artificiellt urval bland organismer med flera kontroller för mätbara egenskaper. Detta banbrytande gjorde att datorsimulering av evolutionära processer och de metoder som beskrivs i böckerna av Fraser och Barnell (1970) [4] och Crosby (1973) [5] blev en vanligare aktivitet bland biologer från 1960-talet. Frasers simuleringar inkluderade alla väsentliga delar av moderna genetiska algoritmer. Utöver detta publicerade Hans-Joachim Bremermann en serie artiklar på 1960-talet som också tog tillvägagångssättet att använda en beslutspopulation som är föremål för rekombination, mutation och selektion i optimeringsproblem. Bremermanns forskning omfattade också inslag av moderna genetiska algoritmer. [6] Andra pionjärer inkluderar Richard Friedberg, George Friedman och Michael Conrad. Många tidiga verk har återutgivits av David B. Vogel (1998). [7]

Även om Baricelli i sin artikel från 1963 simulerade en maskins förmåga att spela ett enkelt spel, [8] blev artificiell evolution en accepterad optimeringsteknik efter Ingo Rechenbergs och Hans-Paul Schwefels arbete på 1960-talet och början av 1970-talet av det tjugonde. århundradet - Rechenbergs grupp kunde lösa komplexa tekniska problem enligt evolutionsstrategier . [9] [10] [11] [12] Ett annat tillvägagångssätt var Lawrence J. Vogels evolutionära programmeringsteknik , som föreslogs för att skapa artificiell intelligens. Evolutionär programmering använde ursprungligen tillståndsmaskiner för att förutsäga omständigheter, och mångfald och urval för att optimera förutsägelsens logik. Genetiska algoritmer blev särskilt populära tack vare John Hollands arbete i början av 70-talet och hans bok Adaptation in Natural and Artificial Systems (1975) [13] . Vogels forskning baserades på Hollands experiment med cellulära automater och hans (Hollands) skrifter skrivna vid University of Michigan . Holland introducerade ett formaliserat tillvägagångssätt för att förutsäga kvaliteten på nästa generation, känd som Scheme Theorem . Forskning inom genetiska algoritmer förblev till stor del teoretisk fram till mitten av 1980-talet, när den första internationella konferensen om genetiska algoritmer slutligen hölls i Pittsburgh, Pennsylvania (USA) .

Med det växande forskningsintresset har också datorkraften hos stationära datorer vuxit avsevärt, vilket gjort det möjligt att använda ny datorteknik i praktiken. I slutet av 80-talet började General Electric sälja världens första genetiska algoritmprodukt. De blev en uppsättning industriella datorverktyg. 1989, ett annat företag, Axcelis, Inc. släppte Evolver  , världens första kommersiella genetiska algoritmprodukt för stationära datorer. New York Times teknologijournalist John Markoff skrev [14] om Evolver 1990.

Beskrivning av algoritmen

Problemet är formaliserat på ett sådant sätt att dess lösning kan kodas som en vektor (" genotyp ") av gener, där varje gen kan vara en bit , ett nummer eller något annat objekt. I klassiska implementeringar av den genetiska algoritmen (GA) antas det att genotypen har en fast längd. Det finns dock varianter av GA som är fria från denna begränsning.

På något, vanligtvis slumpmässigt sätt, skapas många genotyper av den initiala populationen. De utvärderas med hjälp av en " fitnessfunktion ", där ett visst värde ("fitness") är associerat med varje genotyp, vilket avgör hur väl den fenotyp som beskrivs av den löser problemet.

När du väljer en " fitness- funktion " (eller fitness-funktion i den engelska litteraturen), är det viktigt att se till att dess "lättnad" är "smjuk".

Från den resulterande uppsättningen lösningar ("generationer"), med hänsyn till värdet av "fitness", väljs lösningar (vanligtvis har de bästa individerna större sannolikhet att väljas), på vilka "genetiska operatörer" tillämpas (i de flesta fall, " crossover " - crossover och " mutation " - mutation ), vilket resulterar i nya lösningar. För dem beräknas även konditionsvärdet, och sedan utförs valet (“selektion”) av de bästa lösningarna för nästa generation.

Denna uppsättning åtgärder upprepas iterativt och modellerar således en "evolutionär process" som varar i flera livscykler ( generationer ) tills algoritmens stoppkriterium är uppfyllt. Detta kriterium kan vara:

Genetiska algoritmer tjänar främst till att söka efter lösningar i flerdimensionella sökutrymmen.

Således kan följande stadier av den genetiska algoritmen särskiljas:

  1. Ställ in målfunktionen (fitness) för individer i befolkningen
  2. Skapa initial population
  1. Reproduktion (korsning)
  2. Mutation
  3. Beräkna det objektiva funktionsvärdet för alla individer
  4. Bildande av en ny generation (urval)
  5. Om stoppvillkoren är uppfyllda, då (slutet av slingan), annars (starten av slingan).

Skapande av den ursprungliga populationen

Innan det första steget måste du slumpmässigt skapa en initial population; även om det visar sig vara helt okonkurrenskraftigt är det troligt att den genetiska algoritmen ändå snabbt kommer att överföra den till en livskraftig population. I det första steget kan man alltså inte särskilt försöka göra individer för vältränade, det räcker att de motsvarar formatet på individer i befolkningen, och konditionsfunktionen kan beräknas på dem. Resultatet av det första steget är populationen H, bestående av N individer.

Urval (val)

I urvalsstadiet är det nödvändigt att välja ut en viss andel av hela befolkningen som kommer att förbli "levande" i detta evolutionsstadium. Det finns olika sätt att välja. Överlevnadssannolikheten för en individ h måste bero på konditionsfunktionsvärdet Fitness(h). Själva överlevnadsgraden är vanligtvis en parameter för den genetiska algoritmen, och den ges helt enkelt i förväg. Som ett resultat av selektion, av N individer av population H, måste sN-individer finnas kvar, som kommer att inkluderas i den slutliga populationen H'. Resten av individerna dör.

Föräldrarnas val

Reproduktion i genetiska algoritmer kräver flera föräldrar, vanligtvis två, för att få avkomma.

Det finns flera föräldravalsoperatorer:

  1. Panmixia - båda föräldrarna väljs slumpmässigt, varje individ i befolkningen har lika stor chans att bli vald
  2. Inavel - den första föräldern väljs slumpmässigt, och den andra väljs som är mest lik den första föräldern
  3. Utavel - den första föräldern väljs slumpmässigt, och den andra föräldern väljs, vilket är minst lika den första föräldern

Inavel och utavel finns i två former: fenotypisk och genotypisk. När det gäller den fenotypiska formen mäts likheten beroende på fitnessfunktionens värde (ju närmare värdena för den objektiva funktionen är, desto mer lika individerna), och i fallet med den genotypiska formen mäts likheten. beroende på representationen av genotypen (ju färre skillnader mellan genotyperna hos individer, desto mer lika individerna).

Reproduktion (Crossing)

Reproduktion i olika algoritmer definieras olika - det beror naturligtvis på datarepresentationen. Huvudkravet för reproduktion är att avkomman eller avkomman har möjlighet att ärva båda föräldrarnas egenskaper, "blanda" dem på något sätt.

Varför väljs vanligtvis individer för reproduktion ut från hela populationen H, och inte från de element av H' som överlevde vid det första steget (även om det senare alternativet också har rätt att existera)? Faktum är att den största nackdelen med många genetiska algoritmer är bristen på mångfald hos individer. Ganska snabbt sticker en enda genotyp ut, vilket är ett lokalt maximum, och då förlorar alla delar av befolkningen urval till den, och hela populationen "täpps igen" med kopior av denna individ. Det finns olika sätt att hantera en sådan oönskad effekt; en av dem är valet för reproduktion av inte de mest anpassade, utan i allmänhet alla individer. Detta tillvägagångssätt tvingar oss dock att lagra alla redan existerande individer, vilket ökar problemets beräkningskomplexitet. Därför används ofta metoder för att välja individer för korsning på ett sådant sätt att inte bara de mest anpassade, utan även andra individer med dålig kondition "förökar sig". Med detta tillvägagångssätt ökar mutationers roll för genotypens mångfald.

Mutationer

Detsamma gäller mutationer som för reproduktion: det finns en viss andel mutanter m, vilket är en parameter för den genetiska algoritmen, och vid mutationssteget måste du välja mN-individer och sedan ändra dem i enlighet med fördefinierade mutationsoperationer .

Kritik

Det finns flera skäl för kritik mot användningen av en genetisk algoritm i jämförelse med andra optimeringsmetoder:

Det finns många skeptiker om genomförbarheten av att använda genetiska algoritmer. Till exempel, Steven S. Skiena, professor i datateknik vid Stony Brook University, en välkänd forskare av algoritmer, vinnare av IEEE Institute Award, skriver [17] :

Jag personligen har aldrig stött på ett enda problem för vilka genetiska algoritmer skulle vara det lämpligaste verktyget. Dessutom har jag aldrig stött på några resultat av beräkningar som erhållits genom genetiska algoritmer som skulle göra ett positivt intryck på mig.

Tillämpningar av genetiska algoritmer

Genetiska algoritmer används för att lösa följande problem:

  1. Funktionsoptimering
  2. Optimering av databasfrågor
  3. Diverse problem på grafer ( problem med resande säljare , färgläggning, hitta matchningar)
  4. Upprätta och träna ett artificiellt neuralt nätverk
  5. Bygg uppgifter
  6. Schemaläggning
  7. Spelstrategier
  8. Approximationsteori
  9. konstgjort liv
  10. Bioinformatik ( proteinvikning )
  11. Syntes av finita automater
  12. Inställning av PID-regulatorer

Ett exempel på en enkel C++- implementering

Sök i endimensionell rymd, utan att korsa.

#include <cstdlib> #inkludera <ctime> #inkludera <algoritm> #include <iostream> #inkludera <nummer> int main () { srand (( osignerad int ) tid ( NULL )); const size_t N = 1000 ; int a [ N ] = { 0 }; för ( ; ; ) { //mutation till den slumpmässiga sidan av varje element: för ( storlek_ti = 0 ; i < N ; ++ i ) _ a [ i ] += (( rand () % 2 == 1 ) a 1 : -1 ); //välj nu det bästa, sorterat i stigande ordning std :: sort ( a , a + N ); //och då kommer de bästa att finnas i den andra halvan av arrayen. //kopiera det bästa till första halvan, där de lämnade avkomma, och de första dog: std :: kopia ( a + N / 2 , a + N , a ); //Titta nu på befolkningens genomsnittliga tillstånd. Som ni ser så blir det bättre och bättre. std :: cout << std :: ackumulera ( a , a + N , 0 ) / N << std :: endl ; } }

Ett exempel på en enkel implementering i Delphi

Sök i endimensionell rymd med sannolikhet för överlevnad, utan att korsa. (testad på Delphi XE)

program Program1 ; {$APPTYPE CONSOLE} {$R *.res} använder System . generika . Standardinställningar , System . generika . Samlingar , System . Sysutils ; konst N = 1000 ; Nh = Ndiv2 ; _ _ MaxPopulation = Hög ( heltal ) ; var A : array [ 1..N ] av heltal ; _ _ I , R , C , Points , Birth Rate : Heltal ; Iptr : ^ Heltal ; börja Randomize ; // Partiell population för I := 1 till N gör A [ I ] := Slumpmässig ( 2 ) ; upprepa // Mutation för I := 1 till N do A [ I ] := A [ I ] + ( - Slumpmässig ( 2 ) eller 1 ) ; // Urval, de bästa i slutet av TArray . Sortera < Heltal > ( A , TComparer < Heltal >. Standard ) ; // Preset Iptr := Addr ( A [ Nh + 1 ] ) ; Poäng := 0 ; Födelsefrekvens := 0 ; // Crossover -resultat för I := 1 till Nh börjar Inc ( Points , Iptr ^ ) ; // Slumpmässig övergångsframgång R := Slumpmässig ( 2 ) ; Inc ( Födelsefrekvens , R ) ; A [ I ] := Iptr ^ * R ; Iptr ^ := 0 ; Inc ( Iptr , 1 ) ; slut ; // Subtotal Inc ( C ) ; tills ( Points / N >= 1 ) eller ( C >= MaxPopulation ) ; Writeln ( Format ( 'Population %d (rate:%f) score:%f' , [ C , Birth Rate / Nh , Points / N ])) ; slut .

I kulturen

  • I filmen Virtuosity från 1995 odlas huvudskurkens hjärna av en genetisk algoritm som använder brottslingarnas minnen och beteendeegenskaper.

Anteckningar

  1. Barricelli, Nils AallEsempi numerici di processi di evoluzione  (neopr.)  // Methodos. - 1954. - S. 45-68 .
  2. Barricelli, Nils AallSymbiogenetiska evolutionsprocesser realiserade med artificiella metoder  (engelska)  // Methodos : journal. - 1957. - S. 143-182 .
  3. Fraser, AlexSimulering av genetiska system med automatiska digitala datorer. I. Introduktion  (engelska)  // Aust. J Biol. sci. : journal. - 1957. - Vol. 10 . - S. 484-491 .
  4. Fraser, Alex; Donald Burnell. Datormodeller i genetik  (neopr.) . - New York: McGraw-Hill Education , 1970. - ISBN 0-07-021904-4 .
  5. Crosby, Jack L. Datorsimulering i genetik  (obestämd) . - London: John Wiley & Sons , 1973. - ISBN 0-471-18880-8 .
  6. 02.27.96 - UC Berkeleys Hans Bremermann, professor emeritus och pionjär inom matematisk biologi, har dött vid 69 år . Hämtad 17 maj 2012. Arkiverad från originalet 23 mars 2012.
  7. Fogel, David B. (redaktör). Evolutionary Computation: The Fossil Record  (engelska) . - New York: Institute of Electrical and Electronics Engineers , 1998. - ISBN 0-7803-3481-7 .
  8. Barricelli, Nils Aall. Numerisk testning av evolutionsteorier. Del II. Preliminära tester av prestanda, symbiogenes och markliv  (engelska)  // Acta Biotheoretica : journal. - 1963. - Nej . 16 . - S. 99-126 .
  9. Rechenberg, Ingo. Evolutionsstrategi  (neopr.) . - Stuttgart: Holzmann-Froboog, 1973. - ISBN 3-7728-0373-3 .
  10. Schwefel, Hans-Paul. Numerische Optimierung von Computer-Modellen (PhD-avhandling)  (tyska) . — 1974.
  11. Schwefel, Hans-Paul. Numerisk optimering av datormodeller med Evolutionsstrategie : mit ena vergleichenden Einführung in die Hill-Climbing- och Zufallsstrategie  (tyska) . — Basel; Stuttgart: Birkhauser, 1977. - ISBN 3-7643-0876-1 .
  12. Schwefel, Hans-Paul. Numerisk optimering av datormodeller (Översättning av 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie  (engelska) . - Chichester; New York: Wiley, 1981. - ISBN 0-471-09988-0 .
  13. JH Holland. Anpassning i naturliga och artificiella system. University of Michigan Press, Ann Arbor, 1975.
  14. Markoff, John . Vad är det bästa svaret? Det är Survival of the Fittest , New York Times (29 augusti 1990). Arkiverad från originalet den 2 december 2010. Hämtad 9 augusti 2009.
  15. Melanie Mitchell. En introduktion till genetiska algoritmer . - MIT Press, 1998. - S. 167. - 226 sid. — ISBN 9780262631853 . Arkiverad 1 november 2018 på Wayback Machine
  16. Wolpert, DH, Macready, WG, 1995. Inga gratis lunchteorem för optimering. Santa Fe Institute, SFI-TR-05-010, Santa Fe.
  17. Steven S. Skiena. The Algoritm Design Manual. andra upplagan. Springer, 2008.

Böcker

  • Simon D. Algoritmer för evolutionär optimering. — M. : DMK Press, 2020. — 940 sid. - ISBN 978-5-97060-812-8 .
  • Emelyanov VV, Kureichik VV, Kureichik VM Teori och praktik av evolutionär modellering. - M. : Fizmatlit, 2003. - 432 sid. — ISBN 5-9221-0337-7 .
  • Kureichik V. M., Lebedev B. K., Lebedev O. K. Sökanpassning: teori och praktik. - M. : Fizmatlit, 2006. - 272 sid. — ISBN 5-9221-0749-6 .
  • Gladkov L. A., Kureichik V. V., Kureichik V. M. Genetiska algoritmer: Lärobok. - 2:a uppl. - M. : Fizmatlit, 2006. - 320 sid. - ISBN 5-9221-0510-8 .
  • Gladkov L.A., Kureichik V.V., Kureichik V.M. et al. Bioinspirerade metoder för optimering: monografi. - M. : Fizmatlit, 2009. - 384 sid. - ISBN 978-5-9221-1101-0 .
  • Rutkowska D., Pilinsky M., Rutkowski L. Neurala nätverk, genetiska algoritmer och fuzzy system = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. - 2:a uppl. - M . : Hot line-Telecom, 2008. - 452 sid. — ISBN 5-93517-103-1 .
  • Skobtsov Yu. A. Fundamentals of evolutionary computing. - Donetsk: DonNTU, 2008. - 326 sid. - ISBN 978-966-377-056-6 .

Länkar