Files in this item

FilesDescriptionFormat

application/pdf

application/pdfLIU-DISSERTATION-2017.pdf (19MB)
(no description provided)PDF

Description

Title:High-performance evolutionary computation for scalable spatial optimization
Author(s):Liu, Yan
Director of Research:Wang, Shaowen
Doctoral Committee Chair(s):Wang, Shaowen
Doctoral Committee Member(s):Cho, Wendy; Cai, Ximing; McLafferty, Sara
Department / Program:Graduate College Programs
Discipline:Informatics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(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.
Issue Date:2017-12-01
Type:Text
URI:http://hdl.handle.net/2142/99346
Rights Information:Copyright 2017 Yan Liu
Date Available in IDEALS:2018-03-13
Date Deposited:2017-12


This item appears in the following Collection(s)

Item Statistics