Theory of Evolutionary Algorithms and Application to System Synthesis

Evolutionary Algorithms (EAs) apply the principles of natural evolution (selection and random variation) to a random set of points in the search space. EAs are embedded in the context of global optimization and methods for constraint-handling are introduced, including a new method. A new formal description of selection schemes based on fitness distributions is given that 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 a theoretical explanation of the "bloating" problem in Genetic Programming is given and several methods to avoid bloating are compared. EAs are applied to the optimization of complex digital systems composed of hardware and software components. The main task of this system-synthesis is the transformation of a behavioral specification into a structural specification, while regarding various restrictions. A formal description of system-synthesis based on a new graph model is introduced and the tasks of system-synthesis (allocation, binding and scheduling) are defined and formulated as a constrained global optimization problem which is solved using EAs and demonstrated at the example of synthesizing a video codec chip.