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

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Civil Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Garfinkle, Noah

Contributors dc:contributor

• Cai, Ximing

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

Statement dc:rights

• Copyright 2014 Noah Garfinkle

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/72816