EVOlutionary Learning by Intelligent Variation and choice of suitable Operator sets (EVOLIVO)

Internally funded project


Acronym: EVOLIVO

Start date : 01.10.1998

End date : 31.03.2005

Website: https://www.cs12.tf.fau.de/forschung/projekte/evolivo


Project details

Short description

EVOLIVO - EVOlutionary Learning by Intelligent Variation and choice of suitable Operator sets – is the name of our project describing our research in the area of Evolutionary Algorithms and Programs including problems of analysis, improvement and on-line adaptation of existing standard operator sets (basically selection and recombination) and the development of new problem-specific operator sets and their application to problems of technical interest, in particular to automatic system synthesis. Recent research was focused on multi-objective optimization with uncertain objectives. Here, it is assumed that the objectives of a solution are not precisely known, but are given by intervals. These intervals determine the minimal and maximal values of an objective. An essential notion in multi-objective optimization is the term dominance describing the superiority of a solution over another solution. In case of uncertain objectives the dominance is no longer defined. This obviously restricts the use of multi-objective optimization methods in the presence of fuzzy objectives. In the EVOLIVO project we succeeded to generalize these optimization strategies by defining the so-called probability of dominance regarding uncertain objectives. These results are expected to have impact on other research areas outside the domain of embedded systems. Last year we successfully applied these multi-objective optimization strategies to the task of automatic design space exploration. Therein we proposed methods for hierarchical design space exploration using a class of so-called Pareto-Front-Arithmetics for the accelerated design space exploration. The idea of Pareto-Front-Arithmetics is that generally, optimization problems are of hierarchical nature and can be decomposed into sub-problems. By combining the partial results of the optimization, we have to consider the problem that, in general, a global optimum is not composed of optima of its sub-problems. This only holds for monotonous objective functions. The contribution of this project is that we have shown the viability of the combination of partial results leading to uncertain objectives for the top-level optimization problem. By using the dominance probability, we separated the optimization problem and we were able to construct good approximations of the overall solutions in a short time. Future work will focus on the integration of population-based optimization methods into dynamic systems. We will analyze the usability of these methods for online optimization. Target architectures are networked embedded systems. Beside Evolutionary Algorithms we will explore novel population-based optimization strategies like Ant Colony Optimization and Particle Swarm Optimization.

Scientific Abstract

EVOLIVO - lautet der Name dieses Projekts, das unsere Forschung im Bereich Evolutionärer Algorithmen und Programme beschreibt. Dazu gehören die Probleme der Analyse, der Verbesserung und Online-Adaption von existierenden Selektions- und Rekombinationsverfahren sowie die Entwicklung problemspezifischer bzw. bereichsspezifischer Operatormengen und deren Anwendung auf Probleme von technischem Interesse, insbesondere auf dem Gebiet der automatischen Systemsynthese.
Aktuelle Forschungsarbeiten beschäftigen sich mit multikriteriellen Optimierungsstrategien für unscharfe Zielgrößen. Hierbei wird davon ausgegangen, dass die Zielgrößen für eine gefundene Lösung nicht exakt bekannt, sondern z. B. durch ein Intervall gegeben sind. Das Intervall beschreibt hierbei den minimalen bzw. maximalen Wert, den diese Zielgröße annehmen kann. Ein essentieller Begriff im Zusammenhang mit der multikriteriellen Optimierung ist die so genannte Dominanz, die aussagt, dass eine Lösung besser als eine andere Lösung ist. Im Fall von unscharfen Zielgrößen ist diese Dominanz nun aber nicht mehr definiert, was den Einsatz von multikriteriellen Optimierungsverfahren im Umfeld von unscharfen Zielgrößen einzuschränken scheint. Innerhalb des Projektes EVOLIVO gelang nun jedoch die Verallgemeinerung dieser Optimierungsverfahren durch die Definition von „Dominanzwahrscheinlichkeiten“, die den unscharfen Zielgrößen Rechnung tragen. Diese Ergebnisse gehen weit über das Einsatzgebiet des Hardware-Software-Co-Designs hinaus.
Im letzten Jahr konnten diese multikriteriellen Optimierungsstrategien auf die automatische Entwurfsraumexploration erfolgreich angewendet werden. Hierbei kam die so genannte „Pareto-Front-Arithmetik“ zur schnellen Entwurfsraumexploration zum Einsatz. Die Idee hierbei war, dass Optimierungsprobleme im Allgemeinen hierarchischer Struktur sind, d. h. das gesamte Optimierungsproblem lässt sich in Teilprobleme zerlegen. Bei der Kombination der gefundenen Teilergebnisse ergeben sich nun jedoch Probleme derart, dass das globale Optimum nicht aus den Optima der Teilergebnisse bestehen muss. Dies gilt nur unter der Bedingung, dass alle Zielgrößen monoton sind. Der Beitrag dieses Projektes bestand nun darin, dass gezeigt werden konnte, dass sich die Teilergebnisse sehr wohl kombinieren ließen, wobei das Ergebnis unscharfe Zielgrößen für das gesamte Optimierungsproblem darstellt. Mit Hilfe der oben beschriebenen Dominanzwahrscheinlichkeit gelang es nun, durch die Zerlegung des Problems das Gesamtproblem zu verkleinern und schnell eine gute Approximation der Gesamtlösung zu konstruieren.
Zukünftige Arbeiten beschäftigen sich mit der Integration von populationsbasierten Optimierungsverfahren in dynamischen Systemen. Untersucht werden soll hierbei die Einsatzfähigkeit dieser Verfahren zur Online-Optimierung. Das Einsatzgebiet dieser neuen Verfahren stellen vernetzte eingebettete Systeme dar. Neben Evolutionären Algorithmen sollen auch weiterhin neuere populationsbasierte Optimierungsstrategien, wie „Ant-Colony-Optimization“ und „Particle-Swarm-Optimization“, untersucht werden.

Involved:

Contributing FAU Organisations: