TY - JOUR
T1 - A spatially explicit evolutionary algorithm for the spatial partitioning problem
AU - Liu, Yan Y.
AU - Cho, Wendy K.Tam
N1 - Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2020/5
Y1 - 2020/5
N2 - 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.
AB - 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.
KW - Combinatorial optimization
KW - Evolutionary algorithm
KW - Heuristics
KW - Parallel computing
KW - Spatial optimization
UR - http://www.scopus.com/inward/record.url?scp=85079355377&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85079355377&partnerID=8YFLogxK
U2 - 10.1016/j.asoc.2020.106129
DO - 10.1016/j.asoc.2020.106129
M3 - Article
AN - SCOPUS:85079355377
SN - 1568-4946
VL - 90
JO - Applied Soft Computing Journal
JF - Applied Soft Computing Journal
M1 - 106129
ER -