Improving Automatic Design Space Exploration by Integrating Symbolic Techniques into Multi-Objective Evolutionary Algorithms
Christian D. Haubelt, Thomas Schlichte, Jürgen Teich · International Journal of Computational Intelligence Research · 2006
Solving Multi-objective Combinatorial Optimization Problems (MCOPs) is often a twofold problem: Firstly, the feasible region has to be identified in order to, secondly, im- prove the set of non-dominated solutions. In particular, prob- lems where the construction of a single feasible solution is NP - complete are most challenging. In the present paper, we will pro- pose a combination of Multi-Objective Evolutionary Algorithms (MOEAs) with Symbolic Techniques (STs) to solve this problem. Different Symbolic Techniques, such as Binary Decision Dia- grams (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 sys- tems 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.