134:. In asynchronous cEAs the order in which the individuals in the grid are update changes depending on the criterion used: line sweep, fixed random sweep, new random sweep, and uniform choice. These are the four most usual ways of updating the population. All of them keep using the newly computed individual (or the original if better) for the computations of its neighbors immediately. This makes the population to hold at any time individual in different states of evolution, defining a very interesting new line of research.
35:
67:
138:
54:. It is known that, in this kind of algorithm, similar individuals tend to cluster creating niches, and these groups operate as if they were separate sub-populations (islands). Anyway, there is no clear borderline between adjacent groups, and close niches could be easily colonized by competitive niches and maybe merge solution contents during the process. Simultaneously, farther niches can be affected more slowly.
110:
certain criterion, applying the variation operators to them (recombination and mutation for example), and replacing the considered individual by the recently created offspring following a given criterion, for instance, replace if the offspring represents a better solution than the considered individual.
122:
cEA, the algorithm proceeds from the very first top left individual to the right and then to the several rows by using the information in the population to create a new temporary population. After finishing with the bottom-right last individual the temporary population is full with the newly computed
62:
A cellular evolutionary algorithm (cEA) usually evolves a structured bidimensional grid of individuals, although other topologies are also possible. In this grid, clusters of similar individuals are naturally created during evolution, promoting exploration in their boundaries, while exploitation is
45:
The cellular model simulates natural evolution from the point of view of the individual, which encodes a tentative (optimization, learning, search) problem solution. The essential idea of this model is to provide the EA population with a special structure defined as a connected graph, in which each
280:
168:(CA) with probabilistic rewritable rules, where the alphabet of the CA is equivalent to the potential number of solutions of the problem. Hence, if we see cEAs as a kind of CA, it is possible to import knowledge from the field of CAs to cEAs, and in fact this is an interesting open research line.
109:
In cEAs, the individuals can only interact with their neighbors in the reproductive cycle where the variation operators are applied. This reproductive cycle is executed inside the neighborhood of each individual and, generally, consists in selecting two parents among its neighbors according to a
148:
The overlap of the neighborhoods provides an implicit mechanism of solution migration to the cEA. Since the best solutions spread smoothly through the whole population, genetic diversity in the population is preserved longer than in non structured EAs. This soft dispersion of the best solutions
39:
Example evolution of a cEA depending on the shape of the population, from squared (left) to unidimensional ring (right). Darker colors mean better solutions. Observe how shapes different from the traditional square keep diversity (higher exploration) for a longer time. Four snapshots of cEAs at
81:
distance from it to others in the population. Each point of the grid has a neighborhood that overlaps the neighborhoods of nearby individuals. In the basic algorithm, all the neighborhoods have the same size and identical shapes. The two most commonly used neighborhoods are L5, also called
123:
individuals, and the replacement step starts. In it, the old population is completely and synchronously replaced with the newly computed one according to some criterion. Usually, the replacement keeps the best individual in the same position of both populations, that is, elitism is used.
180:. In particular, fine grain parallelism can be used to assign independent threads of execution to every individual, thus allowing the whole cEA to run on a concurrent or actually parallel hardware platform. In this way, large time reductions can be obtained when running cEAs on
191:
However, it is important to stress that cEAs are a model of search, in many senses different from traditional EAs. Also, they can be run in sequential and parallel platforms, reinforcing the fact that the model and the implementation are two different concepts.
76:
The grid is usually 2D toroidal structure, although the number of dimensions can be easily extended (to 3D) or reduced (to 1D, e.g. a ring). The neighborhood of a particular point of the grid (where an individual is placed) is defined in terms of the
142:
The ratio between the radii of the neighborhood to the topology defines the exploration/exploitation capability of the cEA. This could be even tuned during the run of the algorithm, giving the researcher a unique mechanism to search in very complex
46:
vertex is an individual who communicates with his nearest neighbors. Particularly, individuals are conceptually set in a toroidal mesh, and are only allowed to recombine with close individuals. This leads us to a kind of locality known as
161:(and hence, tune the genetic diversity level along the evolution) by modifying (for instance) the size of the neighborhood used, as the overlap degree between the neighborhoods grows according to the size of the neighborhood.
262:
A.J. Neighbor, J.J. 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
31:(EA) in which individuals cannot mate arbitrarily, but every one interacts with its closer neighbors on which a basic EA is applied (selection, variation, replacement).
339:
595:
332:
256:
590:
382:
377:
372:
628:
325:
649:
245:
196:
496:
491:
435:
455:
445:
199:
for a complete description on the fundamentals for the understanding, design, and application of cEAs.
267:
A Cellular Multi-Objective
Genetic Algorithm for Optimal Broadcasting Strategy in Metropolitan MANETs
308:
420:
367:
348:
126:
We must notice that according to the update policy of the population used, we could also define an
550:
476:
177:
545:
415:
362:
233:
223:
28:
580:
565:
273:
213:
71:
Example models of neighborhoods in cellular EAs: linear, compact, diamond and... any other!
287:
8:
524:
430:
471:
440:
410:
208:
176:
Cellular EAs are very amenable to parallelism, thus usually found in the literature of
165:
610:
585:
575:
529:
514:
425:
252:
131:
620:
600:
570:
560:
555:
312:
281:
The
Selection Intensity in Cellular Evolutionary Algorithms for Regular Lattices
519:
481:
450:
283:, IEEE Transactions on Evolutionary Computation, IEEE Press, 9(5):489-505, 2005
274:
Computing Nine New Best-So-Far
Solutions for Capacitated VRP with a Cellular GA
290:, IEEE Transactions on Evolutionary Computation, IEEE Press, 9(2)126-142, 2005
266:
149:
through the population is one of the main issues of the good tradeoff between
643:
506:
486:
228:
288:
The
Exploration/Exploitation Tradeoff in Dynamic Cellular Genetic Algorithms
34:
317:
218:
157:
that cEAs perform during the search. It is then easy to see that we could
605:
66:
137:
276:, Information Processing Letters, Elsevier, 98(6):225-230, 30 June 2006
392:
265:
E. Alba, B. Dorronsoro, F. Luna, A.J. Neighbor, P. Bouvry, L. Hogie,
300:
63:
mainly performed by direct competition and merging inside them.
405:
181:
86:
or NEWS (North, East, West and South), and C9, also known as
50:. The set of potential mates of an individual is called its
185:
406:
Covariance Matrix
Adaptation Evolution Strategy (CMA-ES)
305:
279:
M. Giacobini, M. Tomassini, A. Tettamanzi, E. Alba,
113:
306:NEO Research Group at University of Málaga, Spain
641:
269:, Computer Communications, 30(4):685-697, 2007
333:
347:
301:The site on Cellular Evolutionary Algorithms
340:
326:
596:No free lunch in search and optimization
136:
130:cEA. This is also a well-known issue in
65:
33:
642:
321:
591:Interactive evolutionary computation
383:Interactive evolutionary computation
378:Human-based evolutionary computation
373:Evolutionary multimodal optimization
13:
629:Evolutionary Computation (journal)
14:
661:
294:
401:Cellular evolutionary algorithm
114:Synchronous versus asynchronous
57:
21:cellular evolutionary algorithm
171:
16:Kind of evolutionary algorithm
1:
497:Bacterial Colony Optimization
239:
7:
492:Particle swarm optimization
436:Gene expression programming
248:Cellular Genetic Algorithms
202:
10:
666:
456:Learning classifier system
446:Natural evolution strategy
619:
538:
505:
464:
391:
355:
40:generations 0-50-100-150.
421:Evolutionary programming
368:Evolutionary data mining
349:Evolutionary computation
286:E. Alba, B. Dorronsoro,
272:E. Alba, B. Dorronsoro,
246:E. Alba, B. Dorronsoro,
650:Evolutionary algorithms
551:Artificial intelligence
477:Ant colony optimization
178:parallel metaheuristics
164:A cEA can be seen as a
546:Artificial development
416:Differential evolution
363:Evolutionary algorithm
234:Parallel metaheuristic
224:Evolutionary algorithm
145:
73:
42:
29:evolutionary algorithm
581:Fitness approximation
566:Evolutionary robotics
507:Metaheuristic methods
140:
69:
48:isolation by distance
37:
214:Dual-phase evolution
90:neighborhood. Here,
525:Gaussian adaptation
431:Genetic programming
251:, Springer-Verlag,
472:Swarm intelligence
465:Related techniques
441:Evolution strategy
411:Cultural algorithm
311:2018-09-28 at the
209:Cellular automaton
166:cellular automaton
159:tune this tradeoff
146:
74:
43:
637:
636:
611:Program synthesis
586:Genetic operators
576:Fitness landscape
530:Memetic algorithm
515:Firefly algorithm
426:Genetic algorithm
257:978-0-387-77609-5
132:cellular automata
657:
601:Machine learning
571:Fitness function
561:Digital organism
342:
335:
328:
319:
318:
665:
664:
660:
659:
658:
656:
655:
654:
640:
639:
638:
633:
615:
556:Artificial life
534:
501:
460:
387:
351:
346:
313:Wayback Machine
297:
242:
205:
174:
116:
60:
27:) is a kind of
17:
12:
11:
5:
663:
653:
652:
635:
634:
632:
631:
625:
623:
617:
616:
614:
613:
608:
603:
598:
593:
588:
583:
578:
573:
568:
563:
558:
553:
548:
542:
540:
539:Related topics
536:
535:
533:
532:
527:
522:
520:Harmony search
517:
511:
509:
503:
502:
500:
499:
494:
489:
484:
482:Bees algorithm
479:
474:
468:
466:
462:
461:
459:
458:
453:
451:Neuroevolution
448:
443:
438:
433:
428:
423:
418:
413:
408:
403:
397:
395:
389:
388:
386:
385:
380:
375:
370:
365:
359:
357:
353:
352:
345:
344:
337:
330:
322:
316:
315:
303:
296:
295:External links
293:
292:
291:
284:
277:
270:
263:
260:
241:
238:
237:
236:
231:
226:
221:
216:
211:
204:
201:
173:
170:
115:
112:
59:
56:
15:
9:
6:
4:
3:
2:
662:
651:
648:
647:
645:
630:
627:
626:
624:
622:
618:
612:
609:
607:
604:
602:
599:
597:
594:
592:
589:
587:
584:
582:
579:
577:
574:
572:
569:
567:
564:
562:
559:
557:
554:
552:
549:
547:
544:
543:
541:
537:
531:
528:
526:
523:
521:
518:
516:
513:
512:
510:
508:
504:
498:
495:
493:
490:
488:
487:Cuckoo search
485:
483:
480:
478:
475:
473:
470:
469:
467:
463:
457:
454:
452:
449:
447:
444:
442:
439:
437:
434:
432:
429:
427:
424:
422:
419:
417:
414:
412:
409:
407:
404:
402:
399:
398:
396:
394:
390:
384:
381:
379:
376:
374:
371:
369:
366:
364:
361:
360:
358:
354:
350:
343:
338:
336:
331:
329:
324:
323:
320:
314:
310:
307:
304:
302:
299:
298:
289:
285:
282:
278:
275:
271:
268:
264:
261:
258:
254:
250:
249:
244:
243:
235:
232:
230:
229:Metaheuristic
227:
225:
222:
220:
217:
215:
212:
210:
207:
206:
200:
198:
193:
189:
187:
183:
179:
169:
167:
162:
160:
156:
152:
144:
139:
135:
133:
129:
124:
121:
118:In a regular
111:
107:
105:
101:
97:
93:
89:
85:
80:
72:
68:
64:
55:
53:
49:
41:
36:
32:
30:
26:
22:
400:
247:
219:Enrique Alba
194:
190:
175:
163:
158:
155:exploitation
154:
150:
147:
141:
128:asynchronous
127:
125:
119:
117:
108:
103:
99:
95:
91:
87:
83:
78:
75:
70:
61:
58:Introduction
52:neighborhood
51:
47:
44:
38:
24:
20:
18:
606:Mating pool
356:Main Topics
172:Parallelism
151:exploration
143:landscapes.
120:synchronous
102:stands for
94:stands for
84:Von Neumann
393:Algorithms
240:References
79:Manhattan
644:Category
621:Journals
309:Archived
203:See also
104:Compact
259:, 2008
255:
98:while
96:Linear
182:FPGAs
88:Moore
253:ISBN
197:here
195:See
186:GPUs
153:and
184:or
25:cEA
646::
188:.
106:.
19:A
341:e
334:t
327:v
100:C
92:L
23:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
