Theory of Evolutionary Algorithms and Application to System Synthesis

Thesis by Tobias Blickle

ETH Diss No 11894, ETH Zurich

Examiner: Prof. Dr. Lothar Thiele
Co-Examiner: Prof. Dr. Hans-Paul Schwefel
Date of defense: November, 1st. 1996

The subject of this thesis are Evolutionary Algorithms and their application to the automated synthesis and optimization of complex digital systems composed of hardware and software elements.

In Part I the probabilistic optimization method of Evolutionary Algorithms (EAs) is presented. EAs apply the principles of natural evolution (selection and random variation) to a random set of points (population of individuals) in the search space. Evolutionary Algorithms are first embedded in the context of global optimization and the most important and widely used methods for constraint-handling are introduced, including a new method called IOS (individual objective switching). This is followed by a new formal description of selection schemes based on fitness distributions. This description enables an extensive and uniform examination of various selection schemes leading to new insights about the impact of the selection method parameters on the optimization process. Subsequently the variation (recombination) process of Evolutionary Algorithms is examined. As different analysis techniques are necessary depending on the representation of the problem (e.g. bit string, vector, tree, graph) only the recombination process for tree-representation (Genetic Programming) is considered. A major part of the explanation treats the problem of ``bloating'', i.e., the tree-size increase during optimization. Furthermore, a new redundancy based explanation of bloating is given and several methods to avoid bloating are compared.

Part II is dedicated to the application of Evolutionary Algorithms to the optimization of complex digital systems. These systems are composed of hardware and software components and characterized by a high complexity caused by their heterogeneity (hardware/ software, electrical/mechanical, analog/digital). Computer-aided synthesis at the abstract system level is advantageous for application specific systems or embedded systems as it enables time-to-market to be reduced with a decrease in design errors and costs. The main task of system-synthesis is the transformation of a behavioral specification (for example given by an algorithm) into a structural specification, such as a composition of processors, general or dedicated hardware modules, memories and busses, while regarding various restrictions, e.g. maximum costs, data throughput rate, reaction time. Problems related to system synthesis are for example performance estimation, architecture optimization and design-space exploration.

This thesis introduces a formal description of system-synthesis based on a new graph model where the specification is translated into a specification graph. The main tasks of system-synthesis (allocation, binding and scheduling) are defined for this graph and the process of system synthesis is formulated as a constrained global optimization problem. This optimization problem is solved by Evolutionary Algorithms using the results of Part I of the thesis. Finally, an example of synthesizing implementations of a video codec chip is described demonstrating the effectiveness of the proposed methodology and the capability of the EA to obtain the Pareto points of the design space in a single optimization run.