Theory of Evolutionary Algorithms and Application to System Synthesis
by Tobias Blickle
ETH Diss No 11894
Examiner: Prof. Dr.
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.
Tobias Blickle. "Theory of Evolutionary Algorithms and Application to System
Synthesis", TIK-Schriftenreihe Nr. 17, vdf, Hochsch.-Verl. an der ETH Zürich,
1997, 272 pages. ISBN 3-7281-2433-8.
You can obtain a copy of the thesis by:
ordering a copy of the thesis from vdf
publisher or at your local book store for SFr 84.- (about US$ 95.-).
downloading the postscript file.
downloading the Adobe acrobat reader file (approx.
1.2 MB). Sorry for the bad preview quality but the printed version looks
downloading a short version in postscript with
list of contents, German and English abstract, and summary.