面向设施配置空间优化的量子进化算法

A quantum evolutionary algorithm for spatial optimization of facility allocation

设施配置空间优化旨在形成设施空间布局和调度的规划方案,是以地理信息为研究基础,以运筹建模为方法内核,以城市规划为应用导向的交叉研究问题,是一种典型高维多峰NP-Hard组合优化问题。设计并改进设施配置空间优化算法对提升规划方案适应度具有重要价值。本文剖析设施配置空间优化基本特征,引入实数编码量子进化算法,并重点构造四倍体量子染色体编码算子、总量约束算子,形成面向设施配置空间优化的量子进化算法(quantum evolutionary algorithm for spatial optimization of facility allocation, QEA-SOFA)。基于急救设施配置空间优化实例分析,QEA-SOFA算法可有效提升急救服务设施重定位优化公平性,较实数编码遗传算法提高66%。结果表明QEA-SOFA算法在高维多峰空间优化问题上全局搜索能力更强,且对空间异质区域局部搜索具有更大探测尺度,也揭示了量子进化机制在地理空间优化问题中的巨大潜力。

Spatial optimization of facility allocation that aims to form the spatial layout and dispatch plan of facilities is a typical high-dimensional multi-peak NP-Hard combinatorial optimization problem based on geographic information, operational research modeling, and urban planning. It is essential to improve the plan ’s quality to design and enhance the spatial optimization algorithm of facility allocation. This paper analyzes the critical characteristics in service facility allocation spatial optimization, introduces a real coding quantum evolution algorithm, and mainly establishes tetraploid quantum chromosome coding operator and capacity constraint operator for formulating the quantum evolution algorithm for spatial optimization of facility allocation(QEA-SOFA). Based on the emergency facility spatial optimization experiment, the QEA-SOFA algorithm can effectively improve the equality of the relocation optimization of emergency facilities by 66% compared with the real-coding genetic algorithm. The result demonstrates that the QEA-SOFA algorithm has better global search capability for high-dimensional multi-peak spatial optimization problems and has a more extensive search scale for local search of heterogeneous spatial regions, which reveals that the quantum evolution mechanism has a great deal of potential in solving geospatial optimization problems.