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.
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.
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:
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.
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.
Reproduktion i genetiska algoritmer kräver flera föräldrar, vanligtvis två, för att få avkomma.
Det finns flera föräldravalsoperatorer:
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 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.
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 .
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.
Genetiska algoritmer används för att lösa följande problem:
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 ; } }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 .Ordböcker och uppslagsverk | ||||
---|---|---|---|---|
|
_ | Optimeringsmetoder|
---|---|
En-dimensionell |
|
Noll ordning | |
Första beställning | |
andra beställning | |
Stokastisk | |
Linjära programmeringsmetoder _ | |
Icke -linjära programmeringsmetoder |
Maskininlärning och datautvinning | |
---|---|
Uppgifter | |
Att lära sig med en lärare | |
klusteranalys | |
Dimensionalitetsreduktion | |
Strukturell prognos | |
Anomali upptäckt | |
Grafisk probabilistiska modeller | |
Neurala nätverk | |
Förstärkningsinlärning |
|
Teori | |
Tidskrifter och konferenser |
|