Scientific Achievement
Spatial crossover and mutation operators improve effectiveness and efficiency of evolutionary algorithms on traversing rugged solution landscape in spatially-constrained decision space.
Significance and Impact
Spatially cognizant evolutionary algorithm operators provide intelligence-guided spatial moves within underlying non-linear decision space and preserve contiguity for large spatial partitioning problem-solving. They also enable optimization-based directional sampling of unknown spatial distributions.
Research Details
- Limitations of conventional evolutionary algorithm operators are found in handling strong spatial constraints in spatial optimization
- Novel heuristic-based spatial crossover and mutation operators are devised to solve the challenging spatial partitioning problem
- The proposed algorithm demonstrates desirable algorithmic and computational performance in both sequential and parallel implementations
Facility
The experiments conducted in this paper used the Extreme Science and Engineering Discovery Environment (XSEDE) resources, which are supported by National Science Foundation (NSF) grant number ACI-1548562. Specifically, it used the Bridges system, which is supported by NSF award number ACI-1445606, at the Pittsburgh Supercomputing Center (PSC). The performance study also used the ROGER supercomputer at the University of Illinois, which was supported by NSF Grant 1429699.
Publication
Yan Y. Liu and Wendy K. Tam Cho. 2020. A Spatially Explicit Evolutionary Algorithm for the Spatial Partitioning Problem. Journal of Applied Soft Computing: 90. May 2020. DOI: 10.1016/j.asoc.2020.106129
Funding
This work is supported in part by the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory, managed by UT-Battelle, LLC, for the US Department of Energy under contract DE-AC05-00OR22725.
Overview
Spatial optimization seeks optimal allocation or arrangement of spatial units under constraints such as distance, adjacency, contiguity, and pattern. Evolutionary Algorithms (EAs) are well-known optimization heuristics. However, classic EAs, based on a binary problem encoding and bit-operation-based offspring operators, are spatially unaware and do not capture topological and geometric relationships. Unsurprisingly when spatial characteristics are not explicitly considered in the design of EA operators, that EA becomes ineffective because satisfying spatial constraints is computationally expensive. We design and develop novel spatially explicit EA recombination operators, inspired by the path relinking and ejection chain heuristic strategies, that implement crossover and mutation using intelligently guided strategies in a spatially constrained decision space. Our spatial EA approach is general and slots well into the foundational theory of evolutionary algorithms for spatial optimization. We demonstrate improved solution quality and computational performance with a large-scale spatial partitioning application.
