International Journal of Computational Intelligence Research (IJCIR)

Volume 2, Number 3 (2006)


Improving automatic design space exploration by integrating symbolic techniques into multi-objective evolutionary algorithms

Christian Haubelt, Thomas Schlichter, Jürgen Teich 

Department of Computer Science 12 University of Erlangen-Nuremberg, Germany


Solving Multi-objective Combinatorial Optimization Problems (MCOPs) is often a two fold problem: Firstly, the feasible region has to be identified in order to, secondly, improve the set of non-dominated solutions. In particular, problems where the construction of a single feasible solution is-complete are most challenging. In the present paper, we will propose a combination of Multi-Objective Evolutionary Algorithms (MOEAs) with Symbolic Techniques (STs) to solve this problem. Different Symbolic Techniques, such as Binary Decision Diagrams (BDDs), Multi-valued Decision Diagrams (MDDs), and SAT solvers as known from digital hardware verification will be considered in our methodology. Experimental results from the area of automatic design space exploration of embedded systems illustrate the benefits of our proposed approach. As a key result, the integration of STs in MOEAs is particularly useful in the presence of large search spaces containing only few feasible solutions.

Key words
MOEA, Symbolic Techniques, Design Space Exploration.