GA-Framework

Development of an optimization framework based Genetic Algorithms (GA).

Starting Position

I4Ds deals with the solution of a variety of optimization problems, which cannot be solved analytically. The complexity of such problems makes it impossible to search for an exact solution within a reasonable time.
However, for practical applications it is often sufficient to determine an adequate approximation to the problem. Heuristic optimization methods qualify for such tasks and GA are a class of heuristic optimization methods. Genetic Algorithms have been successfully applied to a wide field of practical optimization problems in diverse disciplines like chemistry, biology, operations research and many engineering disciplines.

Objectives

Provide an optimization framework which can be used for a variability of optimization problems.

Approach

GA are a class of heuristic search methods based on the Darwinian principle of evolution. An initial population of candidate solutions (individuals) are generated by random. Thereafter, these individuals are exposed to an artificial evolution consisting of selection, mutation and recombination. Individuals which conform better to specific quality criteria have a higher chance to pass their genetic information to the next generation. Survival of the fittest ensures that the quality of the best individual will improve from generation to generation.  

Results

GA-Framework was initially developed in JAVA and parts of it were later ported to C++. In the meantime, it has been used for a variety of optimization problems:

  • Inspection route planning
  • Optimization of schedules
  • Optimization of decisions and their alternatives
  • Optimization of pedestrian currents
  • Optimization of the layout of cutting templates
  • Generation of logos

More Information

I4Ds has published following papers about applications using GA-Framework:

  • Märki, F.; Fischer, M; Kunz, J.; Haymaker, J. (2007): Decision Making for Schedule Optimization, Department of Civil Engineering, Stanford University. Stanford 2007, USA. Electronic version of the paper: http://cife.stanford.edu/online.publications/TR169.pdf  
  • Märki, F.; Vogel, M.; Fischer, M.; (2006): Process Plan Optimization using a Genetic Algorithm, published in the proceedings of “The 6th International Conference on the Practice and Theory of Automated Timetabling”, Brno, 30th August – 1st September 2006.
  • Märki, F.; Vogel, M.; Breit, M.; Fischer M. (2006): Interactive Toolbox for 4D-Modeling. Published at the Joint International Conference on Computing and Decision Making in Civil and Building Engineering 2006. Paper number IC-293, Montreal, Canada.
  • Märki, F.; Suter, M.A.; Vogel, M.; Breit, M.; (2004): Optimization of 4D Process Planning using Genetic Algorithms, published in the proceedings of the "Xth International Conference on Computing in Civil and Building Engineering", Weimar, 02-04 June 2004. Electronic version of the paper: http://www.i4ds.ch/forschung/4d/download/68.pdf.
  • Märki F.; Suter M.A.; (2003): Projektplanoptimierung mit Genetischen Algorithmen, Windisch, 27. November 2003. Electronic version of the paper: http://www.i4ds.ch/forschung/4d/download/DES.pdf

Project Participants

Lead

  • Prof. Dr. Manfred Vogel

Project team

  • Fabian Märki (JAVA)
  • Ruedi Müller (C++)