 |
Multi-Objective
Evolutionary Algorithms
Theory and Application to Problems in Code Scheduling
and Hardware Synthesis
Abstract
Evolutionary algorithms possess several characteristics
that are desirable for problems involving i) multiple conflicting objectives,
and ii) intractably large and highly complex search spaces. This is typical
for many optimization problems in the field of computer engineering. Consider
the design of a computer system. An optimal design might be an architecture
that minimizes cost while minimizing the overall power consumption. However,
these goals are generally conflicting: low-power architectures substantially
increase cost, while cheap architectures usually need a lot of power - none
of these solutions can be said to be superior without further consideration.
As a consequence, there is no single optimum, but rather a set of alternative
optima, generally known as Pareto-optimal solutions. Evolutionary algorithms
are able to capture multiple Pareto-optimal solutions in a single simulation
run. Obtaining high convergence and diversity of solutions in low computational
time are the important issues in multi-objective optimization using evolutionary
algorithms.
Examples
of our current research works are given below.
One problem in MOEA is that an evolutionary algorithm
may loose the best solution during generations by performing recombination
among the solutions. A remedy to this problem are the so called Elitist MOEAs
that store the non-dominated solutions of each generation in an archive.
The problem resulting from archives, however, is that in each generation
the archive needs to be updated. The number of comparisons increases specially
when the number of individuals or when the size of the archive increases.
Here we investigate different kinds of data structures like Quad-trees
and linear lists for realizing the archives.
|
MOPSO -
Different from
evolutionary computation techniques, Particle Swarm Optimization (PSO) method
is motivated from the simulation of social behavior of bird flocking and
fish schooling. PSO was originally designed and developed by Eberhart and
Kennedy. However, it shares many similarities with evolutionary computation
techniques. The system is initialized with a population of random solutions
and searches for optima by updating generations. Unlike EA, PSO has no evolution
operators such as crossover and mutation. In PSO, the potential solutions
fly through the problem space by following the current optimum.
In PSO, each single solution is a "bird" in the search space. We call it "particle".
All of particles have fitness values which are evaluated by the fitness function
to be optimized and have velocities which direct the flying of the particles.
The particles fly through the problem space by following the current optimum
particle called guide.
|
Changing a PSO to optimize a multi-objective problem
requires a redefinition of what a guide is in order to obtain a front of
optimal solutions. In Multi-Objective Particle Swarm Optimization (MOPSO),
the Pareto-optimal solutions should be used to determine the guide for each
particle. But selecting the guide (the best local guide) from the set of
approximated Pareto-optimal solutions for each particle of the population
is very difficult yet an important problem for attaining convergence and
diversity of solutions. Here, we propose the Sigma method for finding the
local best guides.
- Download the program of the Sigma MOPSO
- Download an example of moving particles
Other researches on MOEA and MOPSO:
- Covering approximated Pareto-optimal fronts
- Diversity metric- Sigma diversity metric
- Hybrid MOEA: Hybrid MOEA (HMOEA)
is a combination of MOEA with Subdivision method to obtain controllable exploration
of the search space. Here, we cover the approximated Pareto-optimal front
of some multi-objective problems.
Hierarchical Chromosomes in System Synthesis -
We propose an approach for solving hierarchical multi-objective optimization
problems (MOPs). In realistic MOPs, two main challenges have to be considered:
(i) the complexity of the search space and (ii) the non-monotonicity of the
objective-space. Here, we introduce a hierarchical problem description (Chromosomes)
to deal with the complexity of the search space. Since evolutionary algorithms
have been proved to provide good solutions in non-monotonic objective-spaces,
we apply genetic operators also on the structure of hierarchical Chromosomes
This novel approach decreases exploration time substantially.
|
|
|
Visual Programming of Evolutionary
Algorithms - While an evolutionary algorithm
is a powerful optimization concept, one of its drawbacks is the difficulty
of implementing it. Users would require some programming expertise to write
a computer program that implement their algorithm according to their need.
This has to be done before they can carry out their design task, where they
should be really engaged in. A simple solution to this problem has been addressed
in our research group. In the right Figure a graphical user interface is
shown, where a user can construct his particular evolutionary algorithm graphically,
including entering the fitness function, chromosome structure, choosing operators
for selection and recombination as well as drawing the flowchart of the complete
evolutionary algorithm. Even hybrid combinations of different evolutionary
algorithm methods such as Genetic Algorithms operating on bitstrings and Genetic
Programming using tree-like Chromosomes can be achieved. For the graphical
input, java code will be emitted and the ready evolutionary algorithm is
compiled and can be run directly. The program has a comprehensive user interface
and also powerful graphical displays for ease-of-use and visualization of
simulation results.
|
Studienarbeiten and Diploma Theses
| 2010 | 25 M. Glaß, M. Lukasiewycz, C. Haubelt and J. Teich. Towards Scalable System-Level Reliability Analysis. To appear in Proceedings of the 2010 ACM/EDAC/IEEE Design Automation Conference (DAC 2010), Anaheim, CA, U.S.A., June 13-18, 2010. ©1
 | 24 T. Ziermann, N. Mühleis, S. Wildermann and J. Teich. Self-organizing Distributed Reinforcement Learning Algorithm to Achieve Fair Bandwidth Allocation for Priority-based Bus Communication. 1st IEEE Workshop on Self-Organizing Real-Time systems (SORT 2010), Camora, Spain, May 2010, invited Paper. ©1
 | 23 J. Sim, W. Wong, G. Walla, T. Ziermann and J. Teich. Interprocedural Placement-Aware Configuration Prefetching for FPGA-based Systems. To appear in Proceedings of the 18th Annual International IEEE Symposium on
Field-Programmable Custom Computing Machines (FCCM\'10), Charlotte, USA, May 02-04, 2010. ©1
  | 22 D. Ziener, F. Baueregger and J. Teich. Using the Power Side Channel of FPGAs for Communication. To appear in Proceedings of the 18th Annual International IEEE Symposium on
Field-Programmable Custom Computing Machines (FCCM'10), Charlotte, USA, May 02-04, 2010. ©1
 | 21 J. Angermeier, J. Teich, T. Kamphans and S. Fekete. Virtual Area Management: Multitasking on Dynamically Partially Reconfigurable Devices. To appear in Proceedings of 17th Reconfigurable Architectures Workshop (RAW 2010), Atlanta, USA, April 2010. ©1
 | 20 T. Ziermann and J. Teich. Adaptive Traffic Scheduling Techniques for Mixed Real-Time and Streaming Applications on Reconfigurable Hardware. To appear in Proceedings of 17th Reconfigurable Architectures Workshop (RAW), Atlanta, USA, April 19-20, 2010. ©2
 | 19 F. Reimann, A. Kern, C. Haubelt, T. Streichert and J. Teich. Echtzeitanalyse Ethernet-basierter E/E-Architekturen im Automobil. In: Proc. of Automotive meets Electronics (AmE 2010), to appear.. ©1
 | 18 T. Ziermann and J. Teich. Electromagnetic Compatibility (EMC) of CAN+. To appear in Proc. of Automotive meets Electronics (AmE 2010). ©1
 | 17 T. Ritscher, S. Helwig and R. Wanka. Design and Experimental Evaluation of Multiple Adaptation Layers in Self-optimizing Particle Swarm Optimization. Proc. IEEE Congress on Evolutionary Computation (CEC 2010), to appear. ©1
 | 16 J. Teich. DFG Priority Program 1148 Reconfigurable Computing - Achievements and Lessons Learned. DATE Friday Workshop The European Landscape of Reconfigurable Computing: Lessons Learned, new Perspectives and Innovations, Dresden, Germany, March 2010. Invited Talk. ©1
 | 15 H. Dutta, F. Hannig and J. Teich. PARO - A Design Tool for Synthesis of Hardware Accelerators for SoCs. Tool Presentation at the University Booth at Design, Automation and Test in Europe (DATE), Dresden, Germany, March 8-12, 2010. ©1
 | 14 M. Lukasiewycz, M. Glaß and J. Teich. Robust Design of Embedded Systems. To appear in Proceedings of Design, Automation and Test in Europe (DATE'10), Dresden, Germany, March 08-12, 2010. ©1
 | 13 C. Zebelein, J. Falk, C. Haubelt, J. Teich and R. Dorsch. Efficient High-Level Modeling in the Networking Domain. To appear in Proceedings of Design, Automation and Test in Europe (DATE'10), Dresden, Germany, March 08-12, 2010. ©1
 | 12 M. May, N. Wehn, A. Bouajila, J. Zeppenfeld, W. Stechele, A. Herkersdorf, D. Ziener and J. Teich. A Rapid Prototyping System for Error-Resilient Multi-Processor Systems-on-Chip. To appear in Proceedings of Design, Automation and Test in Europe (DATE\'10), Dresden, Germany, March 08-12, 2010. ©1
  | 11 R. Membarth, F. Hannig, J. Teich, M. Körner and W. Eckert. Comparison of Parallelization Frameworks for Shared Memory Multi-Core Architectures. Proceedings of the Embedded World Conference, Nuremberg, Germany, March 03-05, 2010. ©1
  | 10 M. Schmid, F. Hannig, J. Teich, R. Diefenbach, H. Pettendorf and H. Hornegger. Discourse on Extending Embedded Medical Image Processing Systems Using the High Speed Serial RapidIO Interconnect. To appear in Proceedings of the Embedded World Conference, Nuremberg, Germany, March 03-05, 2010.. ©1
 | 9 R. Kiesel, O. Löhlein, A. Terzis, M. Streubühr, C. Haubelt and J. Teich. Actor-oriented Modeling of Driver Assistance Systems for Efficient Multi-Core ECU Implementation.. In Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen, to appear, Dresden, Germany, February 2010. ©1
 | 8 J. Falk, C. Zebelein, C. Haubelt, J. Teich and R. Dorsch. Integrating Hardware/Firmware Verification Efforts Using SystemC High-Level Models. J. Falk, C. Zebelein, C. Haubelt, J. Teich and R. Dorsch
Integrating Hardware/Firmware Verification Efforts Using SystemC High-Level Models.
In 13. ITG/GI/GMM Workshop für Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen,
Fraunhofer IIS/EAS Dresden, pp. 137-146, February 22-24, 2010. ©1
  | 7 M. Platzner, J. Teich and N. Wehn. Dynamically Reconfigurable Systems - Architectures, Design Methods and Applications. Springer, Heidelberg, February 2010. ©1
 | 6 M. Mühlenthaler and R. Wanka. Improving Bitonic Sorting by Wire Elimination. Proc. 23rd PARS-Workshop on Parallel Systems and Architectures of the 23rd Int. Conf. on Architecture of Computing Systems (ARCS), pp. 15-22, 2010. ©1
  | 5 S. Fekete, T. Kamphans, N. Schweer, C. Tessars, J. van der Veen, A. Ahmadinia, J. Angermeier, D. Koch, M. Majer and J. Teich. ReCoNodes - Optimization Methods for Module Scheduling and Placement on Reconfigurable Hardware Devices. In Dynamically Reconfigurable Systems - Architectures, Design Methods and Applications, p. 199-222, Springer, Heidelberg, February 2010. ©1
 | 4 J. Angermeier, C. Bobda, M. Majer and J. Teich. Erlangen Slot Machine: An FPGA-Based Dynamically Reconfigurable Computing Platform. In Dynamically Reconfigurable Systems - Architectures, Design Methods and Applications, p. 51-71, Springer, Heidelberg, February 2010. ©1
 | 3 D. Koch, T. Streichert, C. Haubelt, F. Reimann and J. Teich. ReCoNets – Design Methodology for Embedded Systems Consisting of Small Networks of Reconfigurable Nodes and Connections. In Dynamically Reconfigurable Systems - Architectures, Design Methods and Applications, p. 223-244, Springer, Heidelberg, February 2010. ©1
 | 2 M. Glaß, D. Herrscher, H. Meier, M. Piastowski and P. Schoo. SEIS - Sicherheit in Eingebetteten IP-Basierten Systemen. In ATZelektronik. Volume 5(1), pp. 50-55, February 2010. ©1
   | 1 M. Glaß, M. Lukasiewycz, C. Haubelt and J. Teich. Lifetime Reliability Optimization for Embedded Systems: A System-Level Approach. Proceedings of IEEE International Workshop on Reliability Aware System Design and Test (RASDAT '10), pp. 17-22, Bangalore, India, January 07-08, 2010. ©1
  |
Copyrights:| ©1 | The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder. | | ©2 | ©2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. |
|