Forschungszentrum Karlsruhe - Wissenschaftliche Berichte - FZKA 6965
Eine neue Methodik zur Erhöhung der Leistungsfähigkeit Evolutionärer Algorithmen durch die Integration lokaler Suchverfahren
Wilfried Jakob
Zusammenfassung
Evolutionäre Algorithmen bilden die grundsätzlichen
Wirkmechanismen der belebten Natur in algorithmischer Form nach, um durch
Vererbung, Selektion und Überleben der Besten Lösungen iterativ zu verbessern.
Ihr Haupteinsatzgebiet ist die Bearbeitung komplexer Optimierungsprobleme, für
die es keine mathematischen Lösungen oder geeignete Heuristiken gibt oder es zu
aufwendig wäre, solche zu entwickeln. Beispielhaft seien Anordnungsprobleme,
Designoptimierungsaufgaben, Schedulingprobleme oder Reihenfolgeoptimierungen
genannt. Da die global suchenden Evolutionären Algorithmen in der Nähe des
Optimums schlecht konvergieren, sind nahezu alle erfolgreichen praktischen
Anwendungen sogenannte Hybride, bei denen der Evolutionäre Algorithmus durch
ein in der Regel problemspezifisches lokales Suchverfahren unterstützt wird.
Dadurch gelingt es zwar, die Konvergenzgeschwindigkeit zum Teil erheblich
(meist um Faktoren) zu steigern, andererseits wird aus dem allgemein
anwendbaren evolutionären Verfahren eine problemspezifische Lösung.
Ziel der vorliegenden Arbeit ist die Schaffung eines
allgemein anwendbaren hybriden Verfahrens, das die Vorteile der beteiligten
Algorithmenklassen, nämlich Robustheit und globales Suchverhalten einerseits
und Schnelligkeit andererseits unter Wahrung der allgemeinen Anwendbarkeit und
der Konvergenzsicherheit in sich vereint. Die neu entwickelte Methodik besteht
aus zwei Punkten: Erstens der Verwendung allgemein anwendbarer statt
problemspezifischer lokaler Suchalgorithmen und zweitens der Entwicklung eines
konvergenzabhängigen Steuerungsverfahrens zur Aufteilung der Rechenzeit
zwischen den beteiligten Algorithmen. Dazu wurde eine Metrik zur Bestimmung der
genotypischen Varianz zweier Individuen und darauf aufbauend ein Verfahren zu
Bestimmung der Nischenbildung in einer Population entwickelt. Dabei wurde
großer Wert darauf gelegt, daß die neue Methode bei allen populationsbasierten
Evolutionären Algorithmen angewandt werden kann.
Zur Überprüfung der beiden Ziele, Beibehaltung der
Konvergenzsicherheit und Erhöhung der Konvergenzgeschwindigkeit, wurde eine
Testimplementierung durchgeführt. Dazu wurde der Evolutionäre Algorithmus
GLEAM, der Aspekte der Evolutionsstrategie und der reellcodierten Genetischen
Algorithmen in sich vereint, und zwei erprobte ableitungsfreie lokale
Suchverfahren, nämlich der Rosenbrock-Algorithmus und das Complex-Verfahren
ausgewählt. Als Testfälle wurden fünf mathematische Benchmarkfunktionen und
drei praktische Probleme (Designoptimierung, Ressourcenoptimierung mit
Scheduling und kollisionsfreie Roboterbahnplanung) benutzt. Überprüft wurden die
Hybridisierungsarten Voroptimierung, Nachoptimierung und die (verzögerte)
direkte Integration der lokalen Algorithmen in die Nachkommensbildung des
Evolutionären Verfahrens, was durch die alternative Anwendung beider lokaler
Suchalgorithmen, Verfahrenskombinationen und -modifikationen zu insgesamt
dreizehn Hybriden führte. Die Experimente basierten auf je 100 Läufen pro
Hybrid und Parametrierung, wobei eine Einstellung nur dann als erfolgreich
galt, wenn alle 100 Läufe das vorgegebene Qualitätsziel erreichten. Als
Ergebnis kann zusammenfassend festgestellt werden, daß das Ziel der
Geschwindigkeitssteigerung unter Wahrung der Konvergenzsicherheit erreicht
wurde: Am eindrucksvollsten bei der Ressourcenplanung und bei der Funktion nach
Fletcher und Powell, die um den Faktor 90 bzw. 100 weniger Evaluationen im
Durchschnitt benötigten als GLEAM. Dabei erwies sich die (verzögerte) direkte
Integration als die beste Hybridisierungsart. Da leider keine allgemeingültige
Parametrierung angegeben werden kann und auch nicht klar ist, welches der
beiden lokalen Verfahren im Allgemeinen die besseren Resultate liefert,
schließt die Arbeit mit einer Empfehlung zur Vorgehensweise bei praktischen
Anwendungen und einem neuen Konzept zur adaptiven direkten Integration.
A
New Method for the Increased Performance of Evolutionary Algorithms
Abstract
Evolutionary
Algorithms form a procedure upon the pattern of the principals of biological
evolution for improving solutions iteratively by means of heredity, selection
and survival of the fittest. Their main area of application are complex
optimization problems, for which no mathematical solutions or suitable
heuristics exist or are too costly to develop. Examples for these tasks are
design optimization problems, scheduling, resource optimization or sequencing
problems. As the global searching Evolutionary Algorithm shows a poor
convergence close to the optimum, nearly all successful real world applications
use so called hybrids, where Evolutionary Algorithms are supported by, in most
cases, problem-specific local searchers. This results in a considerable acceleration
(frequently in the magnitude of factors) but turns the general applicable
Evolutionary Algorithm into a domain specific tool.
The goal of
the work on hand is the creation of a generally applicable hybrid procedure,
which combines the advantages of both classes of algorithms, i.e. the
robustness and globality of the search on the one hand and the speediness on
the other, while maintaining the generality and the convergence reliability.
The new method consists of two elements: The usage of generally applicable
local searchers instead of problem-specific ones and second, the development of
a convergence-based control procedure for distributing the computational power
between the basic algorithms involved. This procedure is based on new methods
for calculating the genotypic difference between individuals and for
determining established niches within a population. Great importance was
attached to the applicability of the new method to all population based
Evolutionary Algorithms.
To verify
the two goals of the preservation of the convergence reliability and the raise
of the convergence velocity a test implementation was performed. The
Evolutionary Algorithm GLEAM combining aspects of the Evolution Strategy and
the real-coded Genetic Algorithms was chosen together with two approved
derivation-free local search procedures, namely the Rosenbrock algorithm and
the COMPLEX procedure. Five mathematical benchmark functions and three real
world problems (design optimization, resource optimization in conjunction with
scheduling and collision-free robot path planning) served as test cases. Four
basic kinds of hybridization were investigated, pre-optimization of the initial
population, post-opti-mization of the GLEAM results and (delayed) direct
integration of the local search into the offspring production of the
Evolutionary Algorithm. Based on combinations and modifications of these kinds
and the two alternatively used local searchers this adds up to 13 hybrids. The
experiments were based on 100 runs per hybrid and parameterization and for a
success all runs had to accomplish the given target qualities. Summarizing the
results it can be stated that the goal of improving the velocity was achieved:
The most impressive speed-up was yielded by the resource optimization task and
Fletcher’s function which needed about 90 and 100 times less evaluations on
average than the average of best GLEAM run. The (delayed) direct integration
turned out to be the best kind of hybridization. Unfortunately no common
parameterization could be extracted from the experiments. For direct
integration the Rosen-brock procedure worked always but the COMPLEX algorithm
delivered better results in those cases were it worked at all. The text
concludes with a recommendation for practical applications of the results and
with a new concept for an adaptive direct integration to overcome the
parameterization problems.
VOLLTEXT
BIBLIOTHEK