A spatially explicit evolutionary algorithm for the spatial partitioning problem

Yan Y. Liu, Wendy K.Tam Cho

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Article number106129
JournalApplied Soft Computing Journal
Volume90
DOIs
StatePublished - May 2020

    Fingerprint

Keywords

  • Combinatorial optimization
  • Evolutionary algorithm
  • Heuristics
  • Parallel computing
  • Spatial optimization

ASJC Scopus subject areas

  • Software

Cite this