Evolutionär beräkning

För tidskriften, se Evolutionary Computation (journal) .
Del av en serie om
Evolutionsbiologi
Darwin's finches by Gould.jpg
Darwins finkar av John Gould
Processer och resultat
Naturhistoria
Evolutionsteorins historia
Fält och applikationer
Sociala konsekvenser
Del av en serie om den
evolutionära algoritmen
Genetisk algoritm
Genetisk programmering

Inom datavetenskap är evolutionär beräkning en familj av algoritmer för global optimering inspirerad av biologisk evolution , och underområdet artificiell intelligens och soft computing som studerar dessa algoritmer. I tekniska termer är de en familj av populationsbaserade försök och felproblemlösare med en metaheuristisk eller stokastisk optimeringskaraktär .

I evolutionär beräkning genereras en första uppsättning av kandidatlösningar och uppdateras iterativt. Varje ny generation produceras genom att stokastiskt ta bort mindre önskade lösningar och införa små slumpmässiga förändringar. I biologisk terminologi utsätts en population av lösningar för naturligt urval (eller artificiellt urval ) och mutation . Som ett resultat kommer befolkningen gradvis att utvecklas för att öka i kondition , i detta fall den valda fitnessfunktionen för algoritmen.

Evolutionära beräkningstekniker kan producera mycket optimerade lösningar i ett brett spektrum av probleminställningar, vilket gör dem populära inom datavetenskap . Det finns många varianter och tillägg som passar mer specifika problemgrupper och datastrukturer. Evolutionära beräkningar används också ibland inom evolutionär biologi som en experimentell procedur i silico för att studera vanliga aspekter av allmänna evolutionära processer.

Historia

Konceptet att efterlikna evolutionära processer för att lösa problem har sitt ursprung före tillkomsten av datorer, som när Alan Turing föreslog en metod för genetisk sökning 1948. Turings u-maskiner av B-typ liknar primitiva neurala nätverk , och kopplingar mellan neuroner lärdes in via en sorts genetisk algoritm . Hans u-maskiner av P-typ liknar en metod för förstärkningsinlärning , där signaler om njutning och smärta styr maskinen att lära sig vissa beteenden. Men Turings tidning blev opublicerad fram till 1968, och han dog 1954, så detta tidiga arbete hade liten eller ingen effekt på området för evolutionära beräkningar som skulle utvecklas.

Evolutionär datoranvändning som ett område började på allvar på 1950- och 1960-talen. Det gjordes flera oberoende försök att använda evolutionsprocessen i datoranvändning vid denna tid, som utvecklades separat i ungefär 15 år. Tre grenar dök upp på olika platser för att uppnå detta mål: evolutionsstrategier , evolutionär programmering och genetiska algoritmer . En fjärde gren, genetisk programmering , uppstod så småningom i början av 1990-talet. Dessa tillvägagångssätt skiljer sig åt i urvalsmetoden, de tillåtna mutationerna och representationen av genetiska data. På 1990-talet hade skillnaderna mellan de historiska grenarna börjat suddas ut, och termen "evolutionär datoranvändning" myntades 1991 för att beteckna ett fält som existerar över alla fyra paradigm.

År 1962 initierade Lawrence J. Fogel forskningen om evolutionär programmering i USA, som ansågs vara en strävan efter artificiell intelligens . I detta system används finita tillståndsmaskiner för att lösa ett förutsägelseproblem: dessa maskiner skulle muteras (lägga till eller ta bort tillstånd, eller ändra reglerna för tillståndsövergång), och de bästa av dessa muterade maskiner skulle utvecklas ytterligare i kommande generationer . Den slutliga finita tillståndsmaskinen kan användas för att generera förutsägelser vid behov. Den evolutionära programmeringsmetoden tillämpades framgångsrikt på förutsägelseproblem, systemidentifiering och automatisk kontroll. Det utökades så småningom för att hantera tidsseriedata och modellera utvecklingen av spelstrategier.

1964 introducerade Ingo Rechenberg och Hans-Paul Schwefel paradigmet för evolutionsstrategier i Tyskland. Eftersom traditionella för gradientnedstigning ger resultat som kan fastna i lokala minima, föreslog Rechenberg och Schwefel att slumpmässiga mutationer (tillämpade på alla parametrar för någon lösningsvektor) kan användas för att undkomma dessa minima. Barnlösningar genererades från föräldralösningar, och den mer framgångsrika av de två behölls för framtida generationer. Denna teknik användes först av de två för att framgångsrikt lösa optimeringsproblem inom vätskedynamik . Inledningsvis utfördes denna optimeringsteknik utan datorer, istället förlitade sig på tärningar för att bestämma slumpmässiga mutationer. År 1965 utfördes beräkningarna helt maskinellt.

John Henry Holland introducerade genetiska algoritmer på 1960-talet, och den vidareutvecklades vid University of Michigan på 1970-talet. Medan de andra tillvägagångssätten var fokuserade på att lösa problem, syftade Holland främst till att använda genetiska algoritmer för att studera anpassning och bestämma hur den kan simuleras. Populationer av kromosomer, representerade som bitsträngar, transformerades genom en artificiell urvalsprocess, där specifika "allel"-bitar i bitsträngen valdes. Bland andra mutationsmetoder användes interaktioner mellan kromosomer för att simulera rekombinationen av DNA mellan olika organismer. Medan tidigare metoder bara spårade en enda optimal organism åt gången (att ha barn som konkurrerar med föräldrar), spårade Hollands genetiska algoritmer stora populationer (med många organismer som konkurrerar varje generation).

På 1990-talet uppstod ett nytt tillvägagångssätt för evolutionär beräkning som kom att kallas genetisk programmering , som bland annat förespråkades av John Koza . I denna klass av algoritmer var ämnet evolution i sig självt ett program skrivet i ett programmeringsspråk på hög nivå (det hade gjorts några tidigare försök så tidigt som 1958 att använda maskinkod, men de hade liten framgång). För Koza var programmen Lisp S-uttryck , som kan ses som träd av deluttryck. Denna representation tillåter program att byta underträd, vilket representerar en sorts genetisk blandning. Program poängsätts baserat på hur väl de utför en viss uppgift, och poängen används för artificiellt urval. Sekvensinduktion, mönsterigenkänning och planering var alla framgångsrika tillämpningar av det genetiska programmeringsparadigmet.

Många andra figurer spelade en roll i historien om evolutionär datoranvändning, även om deras arbete inte alltid passade in i en av de stora historiska grenarna av området. De tidigaste beräkningssimuleringarna av evolution med evolutionära algoritmer och artificiella livstekniker utfördes av Nils Aall Barricelli 1953, med de första resultaten publicerade 1954. En annan pionjär på 1950-talet var Alex Fraser , som publicerade en serie artiklar om simulering av artificiellt urval . När det akademiska intresset växte tillät dramatiska ökningar av datorernas kraft praktiska tillämpningar, inklusive den automatiska utvecklingen av datorprogram. Evolutionära algoritmer används nu för att lösa flerdimensionella problem mer effektivt än mjukvara producerad av mänskliga designers, och även för att optimera designen av system.

Tekniker

Evolutionära datortekniker involverar mestadels metaheuristiska optimeringsalgoritmer . I stort sett omfattar fältet:

En genomgående katalog med många andra nyligen föreslagna algoritmer har publicerats i Evolutionary Computation Bestiary . Det är viktigt att notera att många nya algoritmer har dålig experimentell validering.

Evolutionära algoritmer

Huvudartikel: Evolutionär algoritm

Evolutionära algoritmer utgör en delmängd av evolutionära beräkningar i det att de i allmänhet bara involverar tekniker som implementerar mekanismer inspirerade av biologisk evolution såsom reproduktion , mutation , rekombination , naturligt urval och survival of the fittest . Kandidatlösningar på optimeringsproblemet spelar rollen som individer i en population, och kostnadsfunktionen bestämmer i vilken miljö lösningarna "lever" (se även fitnessfunktion ). Utvecklingen av populationen sker sedan efter upprepad applicering av ovanstående operatorer.

I denna process finns det två huvudkrafter som ligger till grund för evolutionära system: Rekombinationsmutation och crossover skapar den nödvändiga mångfalden och underlättar därigenom nyhet, medan selektion fungerar som en krafthöjande kvalitet.

Många aspekter av en sådan evolutionär process är stokastiska . Ändrade delar av information på grund av rekombination och mutation väljs slumpmässigt. Å andra sidan kan urvalsoperatorer vara antingen deterministiska eller stokastiska. I det senare fallet har individer med högre kondition en högre chans att bli utvalda än individer med lägre kondition , men vanligtvis har även de svaga individerna en chans att bli förälder eller att överleva.

Evolutionära algoritmer och biologi

Huvudartikel: Evolutionär algoritm

Genetiska algoritmer levererar metoder för att modellera biologiska system och systembiologi som är kopplade till teorin om dynamiska system , eftersom de används för att förutsäga systemets framtida tillstånd. Detta är bara ett levande (men kanske missvisande) sätt att uppmärksamma den ordnade, välkontrollerade och mycket strukturerade karaktären av utveckling inom biologi.

Men användningen av algoritmer och informatik, i synnerhet av beräkningsteori , utöver analogin till dynamiska system, är också relevant för att förstå själva evolutionen.

Denna uppfattning har förtjänsten att erkänna att det inte finns någon central kontroll över utvecklingen; organismer utvecklas som ett resultat av lokala interaktioner inom och mellan celler. De mest lovande idéerna om paralleller med programutveckling verkar för oss vara sådana som pekar på en till synes nära analogi mellan processer inom celler och lågnivådriften hos moderna datorer. Således är biologiska system som beräkningsmaskiner som bearbetar ingångsinformation för att beräkna nästa tillstånd, så att biologiska system är närmare en beräkning än klassiska dynamiska system.

Dessutom, efter begrepp från beräkningsteorin , är mikroprocesser i biologiska organismer i grunden ofullständiga och oavgjorda ( fullständighet (logik) ), vilket antyder att "det finns mer än en grov metafor bakom analogin mellan celler och datorer.

Analogin med beräkning sträcker sig också till förhållandet mellan arvssystem och biologisk struktur, vilket ofta anses avslöja ett av de mest pressande problemen när det gäller att förklara livets ursprung.

Evolutionära automater , en generalisering av evolutionära Turing-maskiner , har introducerats för att mer exakt undersöka egenskaperna hos biologiska och evolutionära beräkningar. I synnerhet tillåter de att erhålla nya resultat om uttrycksfullhet hos evolutionär beräkning. Detta bekräftar det initiala resultatet om oavgörbarheten hos naturlig evolution och evolutionära algoritmer och processer. Evolutionära ändliga automater , den enklaste underklassen av evolutionära automater som arbetar i terminalläge kan acceptera godtyckliga språk över ett givet alfabet, inklusive icke-rekursivt uppräknade (t.ex. diagonaliseringsspråk) och rekursivt uppräknade men inte rekursiva språk (t.ex. språket i den universella Turing-maskinen ).

Anmärkningsvärda utövare

Listan över aktiva forskare är naturligtvis dynamisk och inte uttömmande. En nätverksanalys av samhället publicerades 2007.

Konferenser

Huvudkonferenserna inom området evolutionära beräkningar inkluderar

Se även

externa länkar

Bibliografi


Hämtad från " https://en.wikipedia.org/w/index.php?title=Evolutionary_computation&oldid=1138754006 "