Design and analysis of genetic algorithms for two classes of spatial optimization

Garfinkle, Noah

Permalink

https://hdl.handle.net/2142/72816 Copy

Description

Title

Design and analysis of genetic algorithms for two classes of spatial optimization

Author(s)

Garfinkle, Noah

Issue Date

2015-01-21

Director of Research (if dissertation) or Advisor (if thesis)

Cai, Ximing

Department of Study

Civil & Environmental Eng

Discipline

Civil Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Genetic Algorithms
• Spatial Genetic Algorithm
• Spatial Evolutionary Algorithms
• Spatial Optimization

Abstract

Many decisions encountered in civil and environmental engineering have spatial implications. Whether deciding on water management strategies or protecting critical infrastructure, our designs cannot be separated from the world in which they will be built and operated. Common optimization techniques, however, struggle with the computational complexity of many problems in which we must make spatial decisions. Additionally, the techniques most commonly applied for optimizing spatial problems require significant simplifications to the problem before a solution can be attempted. These simplifications often include mandatory pre-processing of viable alternatives and reducing complicated coupled systems to simple objective functions, which typically must be separable and differentiable. Genetic algorithms (GA), which allow engineers to optimize problems through the direct implementation of domain-relevant simulations, have demonstrated significant utility for many engineering problems. Additionally, well-posed and executed GA are typically thought to be more efficient at searching complex solution spaces than many competing techniques. However, the classical GA often applied have several limitations which limit their effectiveness when solving spatial problems. As with most competing optimization techniques, classical GA does not inherently capture spatial relationships such as nearness (clustering) and similar features (stratification) between the decision variables. Because of this, classical GA may not be effective in ensuring the survival of good building-blocks for problems in which spatial patterns matter. This thesis explores the creation of two adapted forms of spatial genetic algorithms (SGA, also noted in literature as spatial evolutionary algorithms, SEA), customized to better capture spatial relationships and utilize spatial information. These algorithms seek to combine the desirable features of classical genetic algorithms with domain knowledge specific to spatial decision-making.

Graduation Semester

2014-12

Permalink

http://hdl.handle.net/2142/72816

Copyright and License Information

Copyright 2014 Noah Garfinkle

Owning Collections