Cellular evolutionær algoritme - Cellular evolutionary algorithm
En cellulær evolutionær algoritme ( cEA ) er en slags evolutionær algoritme (EA), hvor individer ikke kan parre sig vilkårligt, men hver enkelt interagerer med sine tættere naboer, hvor en grundlæggende EA anvendes (udvælgelse, variation, erstatning).
Den cellulære model simulerer naturlig udvikling fra individets synspunkt, som koder for en foreløbig (optimering, læring, søgning) problemløsning. Den væsentlige idé med denne model er at give EA-befolkningen en særlig struktur defineret som en sammenhængende graf, hvor hvert toppunkt er et individ, der kommunikerer med sine nærmeste naboer. Især individer er konceptuelt indstillet i et toroideformet net og må kun rekombineres med nære individer. Dette fører os til en slags lokalitet kendt som isolation ved afstand . Sættet af potentielle hjælpere til et individ kaldes dets kvarter . Det er kendt, at lignende individer i denne form for algoritme har tendens til at gruppere nicher, og disse grupper fungerer som om de var separate underpopulationer (øer). Under alle omstændigheder er der ingen klar grænse mellem tilstødende grupper, og tætte nicher kunne let koloniseres af konkurrencedygtige nicher og måske fusionere løsningsindhold under processen. Samtidig kan længere nicher påvirkes langsommere.
Introduktion
En cellulær evolutionær algoritme (cEA) udvikler normalt et struktureret bidimensionelt gitter af individer, selvom andre topologier også er mulige. I dette gitter skabes klynger af lignende individer naturligt under evolutionen, der fremmer udforskning i deres grænser, mens udnyttelse hovedsageligt udføres af direkte konkurrence og sammenfletning indeni dem.
Gitteret er normalt 2D toroidestruktur, skønt antallet af dimensioner let kan udvides (til 3D) eller reduceres (til 1D, f.eks. En ring). Kvarteret for et bestemt punkt på nettet (hvor en person er placeret) er defineret i form af Manhattan afstand fra det til andre i befolkningen. Hvert punkt i gitteret har et kvarter, der overlapper kvartererne for nærliggende enkeltpersoner. I den grundlæggende algoritme har alle kvarterer samme størrelse og identiske former. De to mest anvendte kvarterer er L5, også kaldet Von Neumann eller NEWS (Nord, Øst, Vest og Syd) og C9, også kendt som Moore kvarter. Her står L for Linear, mens C står for Compact .
I cEA'er kan enkeltpersoner kun interagere med deres naboer i den reproduktive cyklus, hvor variationoperatorerne anvendes. Denne reproduktionscyklus udføres inden for hver enkelt persons kvarter og består generelt i at vælge to forældre blandt sine naboer i henhold til et bestemt kriterium, anvende variationsoperatorerne på dem (f.eks. Rekombination og mutation) og erstatte den betragtede person med for nylig oprettet afkom efter et givet kriterium, for eksempel erstatte hvis afkom repræsenterer en bedre løsning end den betragtede person.
Synkron versus asynkron
I en regelmæssig synkron cEA fortsætter algoritmen fra det allerførste øverste venstre individ til højre og derefter til de flere rækker ved at bruge informationen i befolkningen til at skabe en ny midlertidig befolkning. Efter at have afsluttet med den sidste nederste højre person er den midlertidige befolkning fuld med de nyberegnede personer, og udskiftningstrinnet starter. I den erstattes den gamle befolkning fuldstændigt og synkront med den nyberegnede ifølge et eller andet kriterium. Normalt holder udskiftningen det bedste individ i den samme position for begge befolkninger, dvs. elitisme bruges.
Vi skal bemærke, at vi i henhold til opdateringspolitikken for den anvendte befolkning også kunne definere en asynkron cEA. Dette er også et velkendt problem i mobilautomater . I asynkrone cEAs ændres rækkefølgen, som individerne i nettet opdateres, afhængigt af det anvendte kriterium: linjesveje, fast tilfældig fejning, ny tilfældig fejning og ensartet valg. Dette er de fire mest almindelige måder at opdatere befolkningen på. Alle fortsætter med at bruge den nyberegnede person (eller originalen, hvis bedre) til beregning af sine naboer med det samme. Dette får befolkningen til at holde sig til enhver tid individuel i forskellige evolutionstilstande og definerer en meget interessant ny forskningslinje.
Overlappingen af kvartererne giver en implicit mekanisme til løsningsmigration til cEA. Da de bedste løsninger spredes glat gennem hele befolkningen, bevares genetisk mangfoldighed i befolkningen længere end i ikke-strukturerede EA'er. Denne bløde spredning af de bedste løsninger gennem befolkningen er et af de vigtigste spørgsmål om den gode kompromis mellem efterforskning og udnyttelse, som cEA'er udfører under søgningen. Det er så let at se, at vi kunne indstille denne kompromis (og dermed indstille det genetiske mangfoldighedsniveau langs udviklingen) ved at ændre (for eksempel) størrelsen på det anvendte kvarter, da overlapningsgraden mellem kvartererne vokser i overensstemmelse med størrelsen i kvarteret.
En cEA kan ses som en cellulær automat (CA) med sandsynlige genskrivelige regler, hvor CA's alfabet svarer til det potentielle antal løsninger på problemet. Derfor, hvis vi ser cEA'er som en slags CA, er det muligt at importere viden fra CA'er til cEAs, og faktisk er dette en interessant åben forskningslinje.
Parallelisme
Cellulære EA'er er meget modtagelige for parallelisme, hvilket normalt findes i litteraturen om parallel metaheuristik . Især kan finkornsparallelitet bruges til at tildele uafhængige udførelsestråde til hvert individ, hvilket gør det muligt for hele cEA at køre på en samtidig eller faktisk parallel hardwareplatform. På denne måde kan der opnås store tidsreduktioner, når der køres cEA'er på FPGA'er eller GPU'er .
Det er dog vigtigt at understrege, at cEA'er er en søgemodel i mange forstand forskellig fra traditionelle EA'er. De kan også køres i sekventielle og parallelle platforme, hvilket forstærker det faktum, at modellen og implementeringen er to forskellige koncepter.
Se her for en komplet beskrivelse af fundamentet for forståelse, design og anvendelse af cEA'er.
Se også
- Cellular automat
- Dual-fase evolution
- Enrique Alba
- Evolutionær algoritme
- Metaheuristisk
- Parallel metaheuristisk
Referencer
- E. Alba, B. Dorronsoro, Cellular Genetic Algorithms , Springer-Verlag, ISBN 978-0-387-77609-5 , 2008
- AJ Neighbor, JJ Durillo, F. Luna, B. Dorronsoro, E. Alba, MOCell: A New Cellular Genetic Algorithm for Multiobjective Optimization, International Journal of Intelligent Systems, 24: 726-746, 2009
- E. Alba, B. Dorronsoro, F. Luna, AJ Neighbor, P. Bouvry, L. Hogie, A Cellular Multi-Objective Genetic Algorithm for Optimal Broadcasting Strategy in Metropolitan MANETs , Computer Communications, 30 (4): 685-697, 2007
- E. Alba, B. Dorronsoro, Computing Nine nye bedst-så-langt løsninger til Capacitated VRP med en Cellular GA , Information Processing Letters, Elsevier, 98 (6): 225-230, 30. juni 2006
- M. Giacobini, M. Tomassini, A. Tettamanzi, E. Alba, Selection Intensity in Cellular Evolutionary Algorithms for Regular Lattices , IEEE Transactions on Evolutionary Computation, IEEE Press, 9 (5): 489-505, 2005
- E. Alba, B. Dorronsoro, The Exploration / Exploitation Tradeoff in Dynamic Cellular Genetic Algorithms , IEEE Transactions on Evolutionary Computation, IEEE Press, 9 (2) 126-142, 2005
