Theory of Evolutionary Algorithms and Application to System Synthesis   [EA]

by

Blickle, T.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: 1996
Keywords:genetic algorithms, genetic programming
Abstract:
The subject of this thesis are Evolutionary Algorithms [EA] and their application to the automated synthesis [AS] and optimization of complex digital systems composed of hardware and software elements. In Part I the probabilistic optimization method of Evolutionary Algorithms (EAs) [EA] is presented. EAs apply the principles of natural evolution (selection [NE] and random variation) to a random set of points (population of individuals) in the search space. Evolutionary Algorithms [SS] [EA] are first embedded in the context of global optimization [GO] and the most important and widely used methods for constraint- handling [CH] 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. [FD] 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 [EA] 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) [GP] 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 [EA] 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. [GO] [OP] This optimization problem [OP] is solved by Evolutionary Algorithms [EA] using the results of Part I of the thesis. Finally, an example of synthesizing implementations of a video codec chip H.261 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.
Notes:
Of special interest for this community might be chapter 5 that deals with recombination and bloating in GP YAGPLIC
URL(s):(G)zipped postscript
HTML

Review item:

Mark as doublet (will be reviewed)

Print entry



BibTex:
@PhdThesis{blickle:thesis,
  author =       "Tobias Blickle",
  title =        "Theory of Evolutionary Algorithms and Application to
                 System Synthesis",
  school =       "Swiss Federal Institute of Technology",
  year =         "1996",
  address =      "Zurich",
  publisher =    "vdf Verlag",
  publisher_address = "CH-8092 Zurich",
  month =        nov,
  keywords =     "genetic algorithms, genetic programming",
  ISBN =         "3-7281-2433-8",
  URL =          "http://www.tik.ee.ethz.ch/~blickle/diss.html",
  size =         "272 pages",
  abstract =     "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
                 H.261 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.",
  notes =        "Of special interest for this community might be
                 chapter 5 that deals with recombination and bloating in
                 GP YAGPLIC",
}