Zellulärer evolutionärer Algorithmus - Cellular evolutionary algorithm
Ein zellulärer Evolutionsalgorithmus ( cEA ) ist eine Art Evolutionsalgorithmus (EA), bei dem sich Individuen nicht willkürlich paaren können, sondern jeder mit seinen engeren Nachbarn interagiert, auf die ein grundlegender EA angewendet wird (Auswahl, Variation, Ersetzung).
Das zelluläre Modell simuliert die natürliche Evolution aus der Sicht des Individuums, was eine vorläufige Problemlösung (Optimierung, Lernen, Suche) codiert. Die wesentliche Idee dieses Modells besteht darin, der EA-Population eine spezielle Struktur bereitzustellen, die als zusammenhängender Graph definiert ist, in dem jeder Scheitelpunkt eine Person ist, die mit seinen nächsten Nachbarn kommuniziert. Insbesondere sind Individuen konzeptionell in ein Toroidnetz eingebunden und dürfen sich nur mit nahen Individuen rekombinieren. Dies führt uns zu einer Art Lokalität, die als Distanzisolation bekannt ist . Die Menge der potentiellen Partner eines Individuums wird seine Nachbarschaft genannt . Es ist bekannt, dass bei dieser Art von Algorithmus ähnliche Individuen dazu neigen, Nischen zu bilden, und diese Gruppen funktionieren so, als wären sie separate Subpopulationen (Inseln). Auf jeden Fall gibt es keine klare Grenze zwischen benachbarten Gruppen, und enge Nischen könnten leicht von kompetitiven Nischen besiedelt werden und möglicherweise den Lösungsinhalt während des Prozesses zusammenführen. Gleichzeitig können weiter entfernte Nischen langsamer betroffen sein.
Einführung
Ein zellulärer Evolutionsalgorithmus (cEA) entwickelt normalerweise ein strukturiertes zweidimensionales Gitter von Individuen, obwohl auch andere Topologien möglich sind. In diesem Raster werden während der Evolution auf natürliche Weise Cluster ähnlicher Individuen gebildet, die die Erforschung ihrer Grenzen fördern, während die Ausbeutung hauptsächlich durch direkten Wettbewerb und Verschmelzung in ihnen erfolgt.
Das Gitter ist normalerweise eine 2D-Toroidstruktur, obwohl die Anzahl der Dimensionen leicht erweitert (auf 3D) oder reduziert (auf 1D, z. B. einen Ring) werden kann. Die Nachbarschaft eines bestimmten Punktes des Gitters (an dem sich eine Person befindet) wird anhand der Entfernung von Manhattan zu anderen Punkten in der Bevölkerung definiert. Jeder Punkt des Gitters hat eine Nachbarschaft, die die Nachbarschaften von Personen in der Nähe überlappt. Im Basisalgorithmus haben alle Nachbarschaften die gleiche Größe und identische Formen. Die beiden am häufigsten verwendeten Stadtteile sind L5, auch Von Neumann oder NEWS (Nord, Ost, West und Süd) genannt, und C9, auch als Stadtteil Moore bekannt . Hier steht L für Linear, während C für Compact steht .
In cEAs können die Individuen nur im Reproduktionszyklus, in dem die Variationsoperatoren angewendet werden, mit ihren Nachbarn interagieren. Dieser Fortpflanzungszyklus wird in der Nachbarschaft jedes Individuums ausgeführt und besteht im Allgemeinen darin, zwei Elternteile unter seinen Nachbarn nach einem bestimmten Kriterium auszuwählen, die Variationsoperatoren auf sie anzuwenden (Rekombination und Mutation zum Beispiel) und das betrachtete Individuum durch das zu ersetzen kürzlich erstellte Nachkommen, die nach einem bestimmten Kriterium erstellt wurden, ersetzen beispielsweise, wenn die Nachkommen eine bessere Lösung darstellen als das betrachtete Individuum.
Synchron versus asynchron
In einem regulären synchronen cEA geht der Algorithmus von der ersten Person oben links nach rechts und dann zu den verschiedenen Zeilen über, indem die Informationen in der Population verwendet werden, um eine neue temporäre Population zu erstellen. Nach Abschluss der letzten Person unten rechts ist die temporäre Population mit den neu berechneten Personen voll, und der Ersetzungsschritt beginnt. Darin wird die alte Bevölkerung nach einem bestimmten Kriterium vollständig und synchron durch die neu berechnete ersetzt. Normalerweise hält der Ersatz das beste Individuum in der gleichen Position beider Populationen, dh es wird Elitismus verwendet.
Wir müssen beachten, dass wir gemäß der Aktualisierungsrichtlinie der verwendeten Population auch eine asynchrone cEA definieren können. Dies ist auch ein bekanntes Problem in zellularen Automaten . In asynchronen cEAs ändert sich die Reihenfolge, in der die Personen im Raster aktualisiert werden, abhängig vom verwendeten Kriterium: Linien-Sweep, fester Zufalls-Sweep, neuer Zufalls-Sweep und einheitliche Auswahl. Dies sind die vier häufigsten Methoden zur Aktualisierung der Bevölkerung. Alle von ihnen verwenden das neu berechnete Individuum (oder das Original, wenn besser) sofort für die Berechnungen seiner Nachbarn. Dies macht die Bevölkerung jederzeit individuell in verschiedenen Entwicklungsstadien und definiert eine sehr interessante neue Forschungslinie.
Die Überlappung der Nachbarschaften bietet einen impliziten Mechanismus für die Lösungsmigration in die cEA. Da sich die besten Lösungen reibungslos über die gesamte Bevölkerung ausbreiten, bleibt die genetische Vielfalt in der Bevölkerung länger erhalten als in nicht strukturierten EAs. Diese weiche Verteilung der besten Lösungen in der Bevölkerung ist eines der Hauptprobleme für den guten Kompromiss zwischen Exploration und Exploitation , den cEAs während der Suche durchführen. Es ist dann leicht zu erkennen, dass wir diesen Kompromiss (und damit den Grad der genetischen Vielfalt entlang der Evolution) optimieren können, indem wir (zum Beispiel) die Größe der verwendeten Nachbarschaft ändern, da der Überlappungsgrad zwischen den Nachbarschaften mit der Größe zunimmt der Nachbarschaft.
Ein cEA kann als zellularer Automat (CA) mit probabilistischen wiederbeschreibbaren Regeln angesehen werden, wobei das Alphabet der CA der potenziellen Anzahl von Lösungen des Problems entspricht. Wenn wir cEAs als eine Art CA betrachten, ist es daher möglich, Wissen aus dem Bereich der CAs in cEAs zu importieren, und tatsächlich ist dies eine interessante offene Forschungslinie.
Parallelität
Zelluläre EAs sind für Parallelität sehr zugänglich, wie sie üblicherweise in der Literatur zur parallelen Metaheuristik zu finden sind . Insbesondere kann die Feinkornparallelität verwendet werden, um jedem Einzelnen unabhängige Ausführungsthreads zuzuweisen, wodurch die gesamte cEA auf einer gleichzeitigen oder tatsächlich parallelen Hardwareplattform ausgeführt werden kann. Auf diese Weise können große Zeitersparnisse erzielt werden, wenn cEAs auf FPGAs oder GPUs ausgeführt werden .
Es ist jedoch wichtig zu betonen, dass cEAs ein Suchmodell sind, das sich in vielerlei Hinsicht von herkömmlichen EAs unterscheidet. Sie können auch auf sequentiellen und parallelen Plattformen ausgeführt werden, was die Tatsache verstärkt, dass das Modell und die Implementierung zwei unterschiedliche Konzepte sind.
Sehen Sie hier für eine vollständige Beschreibung über die Grundlagen für das Verständnis, Design und Anwendung von Ceas.
Siehe auch
- Mobilfunkautomat
- Zweiphasenentwicklung
- Enrique Alba
- Evolutionärer Algorithmus
- Metaheuristisch
- Parallele Metaheuristik
Verweise
- E. Alba, B. Dorronsoro, Zelluläre genetische Algorithmen , Springer-Verlag, ISBN 978-0-387-77609-5 , 2008
- AJ Nachbar, JJ Durillo, F. Luna, B. Dorronsoro, E. Alba, MOCell: Ein neuer zellulärer genetischer Algorithmus zur multiobjektiven Optimierung, International Journal of Intelligent Systems, 24: 726-746, 2009
- E. Alba, B. Dorronsoro, F. Luna, AJ Nachbar, P. Bouvry, L. Hogie, Ein zellulärer genetischer Algorithmus mit mehreren Zielen für eine optimale Rundfunkstrategie in Metropolitan MANETs , Computer Communications, 30 (4): 685-697, 2007
- E. Alba, B. Dorronsoro, Berechnen von neun neuen bisher besten Lösungen für kapazitiertes VRP mit einer zellulären GA , Information Processing Letters, Elsevier, 98 (6): 225-230, 30. Juni 2006
- M. Giacobini, M. Tomassini, A. Tettamanzi, E. Alba, Die Selektionsintensität in zellulären Evolutionsalgorithmen für reguläre Gitter , IEEE-Transaktionen zur evolutionären Berechnung, IEEE Press, 9 (5): 489-505, 2005
- E. Alba, B. Dorronsoro, Der Kompromiss zwischen Exploration und Exploitation in dynamischen zellgenetischen Algorithmen , IEEE-Transaktionen zur evolutionären Berechnung, IEEE Press, 9 (2) 126-142, 2005
