High-performance evolutionary computation for scalable spatial optimization

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Informatics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2018

Author dc:creator

• Liu, Yan

Contributors dc:contributor

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

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

Statement dc:rights

• Copyright 2017 Yan Liu

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

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