{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/99346"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/99346","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"High-performance evolutionary computation for scalable spatial optimization","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Liu, Yan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Informatics","degree_department":null,"school":null,"contributors":["Wang, Shaowen","Cho, Wendy","Cai, Ximing","McLafferty, Sara"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-03-13T15:48:44Z","date_published":"2018-03-13T15:48:44Z","updated_at":"2026-07-22T22:24:37Z","subjects":["Evolutionary algorithms","Spatial optimization","Partitioning","Combinatorial optimization","Heuristics","High-performance computing","Parallel and distributed computing","Redistricting","Election law"],"languages":["en"],"rights":["Copyright 2017 Yan Liu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/99346","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wang, Shaowen","Cho, Wendy","Cai, Ximing","McLafferty, Sara"]},{"key":"dc:creator","label":"Author","values":["Liu, Yan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-03-13T15:48:44Z","2017-12-01","2017-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Informatics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Evolutionary algorithms","Spatial optimization","Partitioning","Combinatorial optimization","Heuristics","High-performance computing","Parallel and distributed computing","Redistricting","Election law"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Yan Liu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/99346"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-03-13 without embargo terms","The student, Yan Liu, accepted the attached license on 2017-11-30 at 06:53.","The student, Yan Liu, submitted this Dissertation for approval on 2017-11-30 at 07:33.","This Dissertation was approved for publication on 2017-12-01 at 10:27.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11787 on 2018-03-13 at 10:09:27","Made available in DSpace on 2018-03-13T15:48:44Z (GMT). No. of bitstreams: 5 LIU-DISSERTATION-2017.pdf: 18519844 bytes, checksum: 01512d59e7ceccf01014d8a08118bc4a (MD5) LICENSE.txt: 4204 bytes, checksum: e3b4a1b3567bc9d36c11c595d4aed2b7 (MD5) RightsLink Printable License - PEAR.pdf: 131149 bytes, checksum: 4d8ca30c8cf7b1af475604cdff2d265b (MD5) RightsLink Printable License - PGAP.pdf: 130918 bytes, checksum: 1894ddac28d4499d140c6236c81066d5 (MD5) Rightslink-ElectionLaw-nolicensereq4authors-proof.pdf: 144205 bytes, checksum: 469fed59893677e0fc481f56bbc4f99d (MD5) Previous issue date: 2017-12-01"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["High-performance evolutionary computation for scalable spatial optimization"]}]}],"canonical_facts":{"dc:contributor":["Wang, Shaowen","Cho, Wendy","Cai, Ximing","McLafferty, Sara"],"dc:creator":["Liu, Yan"],"dc:date":["2018-03-13T15:48:44Z","2017-12-01","2017-12"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2018-03-13 without embargo terms","The student, Yan Liu, accepted the attached license on 2017-11-30 at 06:53.","The student, Yan Liu, submitted this Dissertation for approval on 2017-11-30 at 07:33.","This Dissertation was approved for publication on 2017-12-01 at 10:27.","DSpace SAF Submission Ingestion Package generated from Vireo submission #11787 on 2018-03-13 at 10:09:27","Made available in DSpace on 2018-03-13T15:48:44Z (GMT). No. of bitstreams: 5 LIU-DISSERTATION-2017.pdf: 18519844 bytes, checksum: 01512d59e7ceccf01014d8a08118bc4a (MD5) LICENSE.txt: 4204 bytes, checksum: e3b4a1b3567bc9d36c11c595d4aed2b7 (MD5) RightsLink Printable License - PEAR.pdf: 131149 bytes, checksum: 4d8ca30c8cf7b1af475604cdff2d265b (MD5) RightsLink Printable License - PGAP.pdf: 130918 bytes, checksum: 1894ddac28d4499d140c6236c81066d5 (MD5) Rightslink-ElectionLaw-nolicensereq4authors-proof.pdf: 144205 bytes, checksum: 469fed59893677e0fc481f56bbc4f99d (MD5) Previous issue date: 2017-12-01"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/99346"],"dc:language":["en"],"dc:rights":["Copyright 2017 Yan Liu"],"dc:subject":["Evolutionary algorithms","Spatial optimization","Partitioning","Combinatorial optimization","Heuristics","High-performance computing","Parallel and distributed computing","Redistricting","Election law"],"dc:title":["High-performance evolutionary computation for scalable spatial optimization"],"dc:type":["text"],"thesis:degree_discipline":["Informatics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:37Z"}