“Multi-objective Intrinsic Hardware Evolution”

Paul Kaufmann and Marco Platzner
University of Paderborn


Computer Engineering Group A robust embedded system has to adapt properly not only to changes in the environment but also to changes in the available resources. As an example, an autonomously moving vehicle might suddenly need to assign most of its computing resources to navigation, leaving less resources than anticipated for other tasks. Evolutionary techniques are well-suited to adapt to slow changes. For rapid changes, however, the speed of convergence of the evolutionary algorithm is not sufficient to react properly. While we envision environmental changes as rather slow, changes in the available resources are considered more rapid. In our project, we are concerned with intrinsically evolvable digital hardware. Besides their functional quality, the evolved hardware functions typically have objectives such as the required logic area, the maximum operation speed and the power consumption. These objectives are often conflicting and cannot be optimized simultaneously. A trade-off has to be found between the different objectives.

In this paper, we present a novel approach to evolvable embedded systems that is able to adapt to both slow and radical changes in the environment and the system state, respectively. First, a multi-objective evolutionary search algorithm with a selection scheme based on Pareto dominance is used to compute a set of reasonable trade-offs. Then, the decision is made which solution to use for the present situation. During operation, the systems adapts to slowly changing environmental conditions by the evolutionary search process. To handle radical changes, precomputed dominant solutions are stored in the system. When a radical change occurs, the system switches to a "good-enough" solution, and the online evolutionary process is restarted.

We will present details of the Cartesian Genetic Programming model used, the evolutionary technique, and the evaluation of the fitness with respect to several objectives. We will demonstrate our approach on two classes of applications. The first class of applications reveals an exact correctness measure, where everything less than 100% correctness is unacceptable. For such a scenario, treating the fitness as a constraint during the optimization process is a viable possibility. The second class of applications relies on a continuous fitness measure, such as the quality of a predictor inside an image compressing algorithm. For such a scenario, the functional quality is best handled as an objective.

2006 MAPLD International Conference Home Page