Evolutionær algoritme - Evolutionary algorithm
Del af en serie om |
Kunstig intelligens |
---|
I beregningsmæssige intelligens (CI), en evolutionær algoritme ( EA ) er en delmængde af evolutionær beregning , en generisk populationsbaseret meta-heuristik optimering algoritme . En EA bruger mekanismer inspireret af biologisk evolution , såsom reproduktion , mutation , rekombination og selektion . Kandidatløsninger til optimeringsproblemet spiller individernes rolle i en befolkning, og fitnessfunktionen bestemmer kvaliteten af løsningerne (se også tabsfunktion ). Udviklingen af befolkningen finder derefter sted efter den gentagne anvendelse af ovenstående operatører.
Evolutionære algoritmer udfører ofte godt tilnærmelsesværdige løsninger til alle typer problemer, fordi de ideelt set ikke antager noget om det underliggende fitnesslandskab . Teknikker fra evolutionære algoritmer anvendt til modellering af biologisk evolution er generelt begrænset til udforskninger af mikroevolutionære processer og planlægningsmodeller baseret på cellulære processer. I de fleste virkelige applikationer af EA'er er beregningskompleksitet en forbudende faktor. Faktisk skyldes denne beregningskompleksitet evaluering af fitnessfunktioner. Fitness -tilnærmelse er en af løsningerne til at overvinde denne vanskelighed. Tilsyneladende simpel EA kan imidlertid løse ofte komplekse problemer; derfor er der muligvis ingen direkte forbindelse mellem algoritmekompleksitet og problemkompleksitet.
Implementering
Det følgende er et eksempel på en generisk enkelt-objektiv genetisk algoritme .
Trin et: Generer den oprindelige population af individer tilfældigt. (Første generation)
Trin to: Gentag følgende regenerationstrin indtil afslutning:
- Evaluer hver enkelt persons egnethed i befolkningen (tidsbegrænsning, tilstrækkelig kondition opnået osv.)
- Vælg de bedst egnede personer til reproduktion . (Forældre)
- Avl nye individer gennem crossover og mutationsoperationer for at føde afkom .
- Udskift de mindst egnede personer i befolkningen med nye individer.
Typer
Lignende teknikker er forskellige i genetisk repræsentation og andre implementeringsdetaljer og arten af det særlige anvendte problem.
- Genetisk algoritme - Dette er den mest populære type EA. Man søger løsningen af et problem i form af talstrenge (traditionelt binært, selvom de bedste repræsentationer normalt er dem, der afspejler noget om problemet, der skal løses), ved at anvende operatorer som rekombination og mutation (nogle gange en, nogle gange begge) . Denne type EA bruges ofte i optimeringsproblemer .
- Genetisk programmering - Her er løsningerne i form af computerprogrammer, og deres egnethed bestemmes af deres evne til at løse et beregningsproblem. Der er mange varianter af genetisk programmering, herunder kartesisk genetisk programmering , programmering af genekspression , grammatisk udvikling , lineær genetisk programmering , programmering af flere udtryk osv.
- Evolutionær programmering - Ligner genetisk programmering, men programmets struktur er fast, og dens numeriske parametre får lov til at udvikle sig.
- Evolutionstrategi -Arbejder med vektorer af reelle tal som repræsentationer af løsninger og bruger typisk selvtilpassende mutationshastigheder.
- Differential evolution - Baseret på vektorforskelle og er derfor primært velegnet til numeriske optimeringsproblemer .
- Neuroevolution - Ligner genetisk programmering, men genomerne repræsenterer kunstige neurale netværk ved at beskrive struktur og forbindelsesvægte. Genomkodningen kan være direkte eller indirekte.
- Lærende klassificeringssystem - Her er løsningen et sæt klassifikatorer (regler eller betingelser). En Michigan-LCS udvikler sig på niveau med individuelle klassifikatorer, mens en Pittsburgh-LCS bruger populationer af klassificeringssæt. Oprindeligt var klassifikatorer kun binære, men inkluderer nu virkelige, neurale net- eller S-udtrykstyper . Fitness bestemmes typisk enten med en styrke- eller nøjagtighedsbaseret forstærkningslæring eller tilgang til overvåget læring .
Sammenligning med biologiske processer
En mulig begrænsning af mange evolutionære algoritmer er deres mangel på en klar genotype -fænotype -sondring . I naturen gennemgår den befrugtede ægcelle en kompleks proces kendt som embryogenese for at blive en moden fænotype . Denne indirekte kodning menes at gøre den genetiske søgning mere robust (dvs. reducere sandsynligheden for dødelige mutationer) og kan også forbedre udviklingen af organismen. Sådanne indirekte (også kendt som generative eller udviklingsmæssige) kodninger gør det også muligt for evolution at udnytte regelmæssigheden i miljøet. Det seneste arbejde inden for kunstig embryogeni eller kunstige udviklingssystemer søger at løse disse bekymringer. Og programmering af genekspression udforsker med succes et genotype -fænotypesystem, hvor genotypen består af lineære multigeniske kromosomer med fast længde, og fænotypen består af flere ekspressionstræer eller computerprogrammer i forskellige størrelser og former.
Relaterede teknikker
Swarm algoritmer inkluderer
- Myrkolonioptimering er baseret på ideerne om myrfodring ved feromonkommunikation for at danne stier. Primært velegnet til kombinatorisk optimering og grafproblemer .
- Runner-root-algoritmen (RRA) er inspireret af funktionen af løbere og rødder af planter i naturen
- Kunstig bi -kolonialgoritme er baseret på honningbiens fodringsadfærd. Primært foreslået til numerisk optimering og udvidet til at løse kombinatoriske, begrænsede og multi-objektive optimeringsproblemer.
- Bieralgoritme er baseret på honningbiers foderadfærd. Det er blevet anvendt i mange applikationer, såsom routing og planlægning.
- Cuckoo søgning er inspireret af den rugende parasitisme af Gøg arter. Det bruger også Lévy -flyvninger , og dermed passer det til globale optimeringsproblemer .
- Partikelsværmsoptimering er baseret på ideerne om dyrs flokadfærd. Også primært velegnet til numeriske optimeringsproblemer .
Andre befolkningsbaserede metaheuristiske metoder
- Jagtsøgning - En metode inspireret af gruppejagt på nogle dyr som ulve, der organiserer deres position for at omgive byttet, hver af dem i forhold til de andres og især deres leders position. Det er en kontinuerlig optimeringsmetode tilpasset som en kombinatorisk optimeringsmetode.
- Adaptiv dimensionel søgning -I modsætning til naturinspirerede metaheuristiske teknikker implementerer en adaptiv dimensionel søgningsalgoritme ikke nogen metafor som et underliggende princip. Den bruger snarere en simpel præstationsorienteret metode baseret på opdateringen af parameteren for søgedimensionalitetsforhold (SDR) ved hver iteration.
- Firefly -algoritmen er inspireret af ildfluers adfærd, der tiltrækker hinanden ved blinkende lys. Dette er især nyttigt til multimodal optimering.
- Harmonisøgning - Baseret på ideerne om musikers adfærd i søgen efter bedre harmonier. Denne algoritme er velegnet til kombinatorisk optimering samt parameteroptimering.
- Gaussisk tilpasning - Baseret på informationsteori. Anvendes til maksimering af produktionsudbytte, middelværdi eller gennemsnitlig information . Se f.eks. Entropi i termodynamik og informationsteori .
- Memetisk algoritme -En hybridmetode, der er inspireret af Richard Dawkins forestilling om et meme, har normalt en form af en populationsbaseret algoritme kombineret med individuelle læringsprocedurer, der er i stand til at udføre lokale forfininger. Fremhæver udnyttelsen af problemspecifik viden, og forsøger at orkestrere lokal og global søgning på en synergistisk måde.
Eksempler
I 2020 erklærede Google , at deres AutoML-Zero med succes kan genopdage klassiske algoritmer såsom begrebet neurale netværk.
Computersimuleringerne Tierra og Avida forsøger at modellere makroevolutionær dynamik.
Galleri
En EA-søgning med to befolkninger over en begrænset Rosenbrock-funktion med afgrænset globalt optimalt.
En EA-søgning med to befolkninger over en begrænset Rosenbrock-funktion . Globalt optimalt er ikke begrænset.
En EA-søgning med to befolkninger efter en afgrænset optima af Simionescus funktion .
Referencer
eksterne links
Bibliografi
- Ashlock, D. (2006), Evolutionær beregning til modellering og optimering , Springer, ISBN 0-387-22196-4 .
- Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms , Oxford Univ. Trykke.
- Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation , Oxford Univ. Trykke.
- Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetic Programming - An Introduction , Morgan Kaufmann, San Francisco
- Eiben, AE, Smith, JE (2003), Introduction to Evolutionary Computing , Springer.
- Holland, JH (1992), Adaptation in Natural and Artificial Systems , University of Michigan Press, Ann Arbor
- Michalewicz Z., Fogel DB (2004). Sådan løses det: Moderne Heuristik, Springer.
- Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010). "Bin Packing/Covering with Delivery, løst med udviklingen af algoritmer". 2010 IEEE Femte internationale konference om bioinspireret computing: teorier og applikationer (BIC-TA) . s. 298–302. doi : 10.1109/BICTA.2010.5645312 . ISBN 978-1-4244-6437-1. S2CID 16875144 .
- Poli, R .; Langdon, WB; McPhee, NF (2008). En feltguide til genetisk programmering . Lulu.com, frit tilgængeligt fra internettet. ISBN 978-1-4092-0073-4. Arkiveret fra originalen 2016-05-27 . Hentet 2011-03-05 .
- Price, K., Storn, RM, Lampinen, JA, (2005). "Differentiel udvikling: En praktisk tilgang til global optimering" , Springer.
- Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (ph.d. -afhandling). Genoptrykt af Fromman-Holzboog (1973).
- Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (ph.d.-afhandling). Genoptrykt af Birkhäuser (1977).
- Simon, D. (2013): Evolutionary Optimization Algorithms , Wiley.
- Computational Intelligence: A Methodological Introduction af Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, ISBN 978-1-4471-5012-1
- Rahman, Rosshairy Abd .; Kendall, Graham; Ramli, Razamin; Jamari, Zainoddin; Ku-Mahamud, Ku Ruhana (2017). "Rejefoderformulering via evolutionær algoritme med effektheuristik til håndtering af begrænsninger" . Kompleksitet . 2017 : 1–12. doi : 10.1155/2017/7053710 .