High-performance evolutionary computation for scalable spatial optimization

Liu, Yan

Permalink

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

Description

Title

High-performance evolutionary computation for scalable spatial optimization

Author(s)

Liu, Yan

Issue Date

2017-12-01

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

Wang, Shaowen

Doctoral Committee Chair(s)

Wang, Shaowen

Committee Member(s)

• Cho, Wendy
• Cai, Ximing
• McLafferty, Sara

Department of Study

Graduate College Programs

Discipline

Informatics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Evolutionary algorithms
• Spatial optimization
• Partitioning
• Combinatorial optimization
• Heuristics
• High-performance computing
• Parallel and distributed computing
• Redistricting
• Election law

Abstract

Spatial optimization (SO) is an important and prolific field of interdisciplinary research. Spatial optimization methods seek optimal allocation or arrangement of spatial units under spatial constraints such as distance, adjacency, contiguity, partition, etc. As spatial granularity becomes finer and problem formulations incorporate increasingly complex compositions of spatial information, the performance of spatial optimization solvers becomes more imperative. My research focuses on scalable spatial optimization methods within the evolutionary algorithm (EA) framework. The computational scalability challenge in EA is addressed by developing a parallel EA library that eliminates the costly global synchronization in massively parallel computing environment and scales to 131,072 processors. Classic EA operators are based on linear recombination and experience serious problems in traversing the decision space with non-linear spatial configurations. I propose a spatially explicit EA framework that couples graph representations of spatial constraints with intelligent guided search heuristics such as path relinking and ejection chain to effectively explore SO decision space. As a result, novel spatial recombination operators are developed to handle strong spatial constraints effectively and are generic to incorporate problem-specific spatial characteristics. This framework is employed to solve large political redistricting problems. Voting district-level redistricting problems are solved and sampled to create billions of feasible districting plans that adhere to Supreme Court mandates, suitable for statistical analyses of redistricting phenomena such as gerrymandering.

Graduation Semester

2017-12

Type of Resource

text

Permalink

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

Copyright and License Information

Copyright 2017 Yan Liu

Owning Collections