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

doi:10.11947/j.AGCS.2023.20210295

测绘学报 ›› 2023, Vol. 52 ›› Issue (1): 142-154.doi: 10.11947/j.AGCS.2023.20210295

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

周鑫鑫^1,2, 袁林旺³, 吴长彬³, 韩佩佩³, 黄敬³, 俞肇元³

1. 南京邮电大学地理与生物信息学院, 江苏南京 210023;
2. 南京邮电大学江苏省智慧健康大数据分析与位置服务工程实验室, 江苏南京 210023;
3. 南京师范大学地理科学学院, 江苏南京 210023

收稿日期:2021-05-24 修回日期:2022-01-27 发布日期:2023-02-09
通讯作者: 俞肇元 E-mail:yuzhaoyuan@njnu.edu.cn
作者简介:周鑫鑫(1991—),男,博士,讲师,主要研究方向为空间智能及优化决策、自然资源智能遥感监测。E-mail: zhouxinxin@njupt.edu.cn
基金资助:
国家自然科学基金(41971404);南京邮电大学引进人才科研启动基金(自然科学)(NY221143);国家杰出青年科学基金(41625004)

A quantum evolutionary algorithm for spatial optimization of facility allocation

ZHOU Xinxin^1,2, YUAN Linwang³, WU Changbin³, HAN Peipei³, HUANG Jing³, YU Zhaoyuan³

1. School of Geography and Bioinformatics, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;
2. Smart Health Big Data Analysis and Location Services Engineering Research Center of Jiangsu Province, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;
3. School of Geographic Sciences, Nanjing Normal University, Nanjing 210023, China

Received:2021-05-24 Revised:2022-01-27 Published:2023-02-09
Supported by:
The National Natural Science Foundation of China (No.41971404);The Natural Science Research Start-up Foundation of Recruiting Talents of Nanjing University of Posts and Telecommunications (No.NY221143 );National Outstanding Youth Fund (No.41625004)

摘要/Abstract

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

关键词: 量子进化, 空间优化, 服务设施, 选址, 空间智能

Abstract: 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.

Key words: quantum evolution, spatial optimization, service facilities, location, spatial intelligence

中图分类号:

P209

周鑫鑫, 袁林旺, 吴长彬, 韩佩佩, 黄敬, 俞肇元. 面向设施配置空间优化的量子进化算法[J]. 测绘学报, 2023, 52(1): 142-154.

ZHOU Xinxin, YUAN Linwang, WU Changbin, HAN Peipei, HUANG Jing, YU Zhaoyuan. A quantum evolutionary algorithm for spatial optimization of facility allocation[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(1): 142-154.

参考文献

[1] LI Wenwen, CAO Kai, CHURCH R L. Cyberinfrastructure, GIS, and spatial optimization: opportunities and challenges[J]. International Journal of Geographical Information Science, 2016, 30(3): 427-431.
[2] 赵翔. 土地利用优化配置的多目标人工免疫优化模型研究[D]. 武汉: 武汉大学, 2013. ZHAO Xiang. Land use allocation optimization models based on multi-objective artificial immune systems[D].Wuhan: Wuhan University, 2013.
[3] 黎夏,李丹,刘小平.地理模拟优化系统(GeoSOS)及其在地理国情分析中的应用[J]. 测绘学报, 2017,46(10): 1598-1608.DOI: 10.11947/j.AGCS.2017.20170355. LI Xia, LI Dan, LIU Xiaoping. Geographical simulation and optimization system (GeoSOS) and its application in the analysis of geographic national conditions[J]. Acta Geodaetica et Cartographica Sinica, 2017,46(10): 1598-1608.DOI: 10.11947/j.AGCS.2017.20170355.
[4] 王楠, 吴巍, 胡细英, 等. 大型交通设施对房地产价格影响研究进展与评述[J]. 城市发展研究, 2018, 25(5): 13-18. WANG Nan, WU Wei, HU Xiying, et al. Research progress on the impacts of great traffic facilities on housing price[J]. Urban Development Studies, 2018, 25(5): 13-18.
[5] MCCORMACK R, COATES G. A simulation model to enable the optimization of ambulance fleet allocation and base station location for increased patient survival[J]. European Journal of Operational Research, 2015, 247(1): 294-309.
[6] TONG Daoqin, MURRAY A T. Spatial optimization in geography[J]. Annals of the Association of American Geographers, 2012, 102(6): 1290-1309.
[7] SHAREEFH, ISLAMM M, MOHAMEDA. A review of the stage-of-the-art charging technologies, placement methodologies, and impacts of electric vehicles[J]. Renewable and Sustainable Energy Reviews, 2016, 64: 403-420.
[8] 崔建鑫, 赵海霞. 城镇污水处理设施空间优化配置研究[J]. 中国环境科学, 2016, 36(3): 943-952. CUI Jianxin, ZHAO Haixia. Method for spatial optimal allocation of urban sewage treatment facilities[J]. China Environmental Science, 2016, 36(3): 943-952.
[9] 戴特奇, 廖聪, 胡科, 等. 公平导向的学校分配空间优化: 以北京石景山区为例[J]. 地理学报, 2017, 72(8): 1476-1485. DAI Teqi, LIAO Cong, HU Ke, et al. Secondary school allocation optimization towards equal access: a case study on Shijingshan District, Beijing[J]. Acta Geographica Sinica, 2017, 72(8): 1476-1485.
[10] DASKIN M S. Network and discrete location: models, algorithms, and applications[M]. 2nd ed Hoboken, New Jersey: John Wiley& Sons, Inc., 2013.
[11] DASKIN M S. What you should know about location modeling[J]. Naval Research Logistics, 2008, 55(4): 283-294.
[12] 谢顺平, 冯学智, 都金康. 基于网络Voronoi图启发式和群智能的最大覆盖空间优化[J]. 测绘学报, 2011,40(6): 778-784. XIE Shunping, FENG Xuezhi, DU Jinkang. Maximal covering spatial optimization based on network Voronoi diagrams heuristic and swarm intelligence[J]. Acta Geodaetica et Cartographica Sinica, 2011,40(6): 778-784.
[13] 程敏, 崔晓. 基于多目标改进免疫算法和GIS的养老机构空间配置优化研究: 以上海市虹口区为例[J]. 地理科学, 2018, 38(12): 2049-2057. CHENG Min, CUI Xiao. Spatial optimization configuration of the residential care homes based on the multi-objective improved immune algorithm and GIS:a case study of Hongkou District in Shanghai[J]. Scientia Geographica Sinica, 2018, 38(12): 2049-2057.
[14] 王海鹰, 秦奋, 张新长, 等. 基于蚁群优化算法的城市生态用地空间规划模型[J]. 地理科学, 2017, 37(3): 426-436. WANG Haiying, QIN Fen, ZHANG Xinchang, et al. The spatial planning model of urban ecological land based on ant colony optimization algorithm[J]. Scientia Geographica Sinica, 2017, 37(3): 426-436.
[15] FARAHANI R Z, FALLAH S, RUIZ R, et al. OR models in urban service facility location: a critical review of applications and future developments[J]. European Journal of Operational Research, 2019, 276(1): 1-27.
[16] 朱阿兴, 闾国年, 周成虎, 等. 地理相似性:地理学的第三定律?[J]. 地球信息科学学报, 2020, 22(4): 673-679. ZHU Axing, LÜ Guonian, ZHOU Chenghu, et al. Geographic similarity: third law of geography?[J]. Journal of Geo-Information Science, 2020, 22(4): 673-679.
[17] 王宝楠, 水恒华, 王苏敏, 等. 量子退火理论及其应用综述[J]. 中国科学: 物理学力学天文学, 2021, 51(8): 5-17. WANG Baonan, SHUI Henghua, WANG Sumin, et al. Theories and applications of quantum annealing: a literature survey[J]. Scientia Sinica(Physica,Mechanica & Astronomica), 2021, 51(8): 5-17.
[18] 范桁. 量子计算与量子模拟[J]. 物理学报, 2018, 67(12): 16-25. FAN Heng. Quantum computation and quantum simulation[J]. Acta Physica Sinica, 2018, 67(12): 16-25.
[19] 焦李成, 李阳阳,刘芳,等. 量子计算、优化与学习[M]北京:科学出版社. 2017. JIAO Licheng, LI Yangyang,LIU Fang,et al. Quantum computation, optimization and learning[M].Beijing:Science Press,2017.
[20] HAN K H, KIM J H. Genetic quantum algorithm and its application to combinatorial optimization problem[C]//Proceedings of the 2000 Congress on Evolutionary Computation.La Jolla, CA, USA:IEEE, 2002: 1354-1360.
[21] 钱洁, 王保华, 郑建国, 等. 多重二次背包问题的量子进化求解算法[J]. 计算机学报, 2015, 38(8): 1518-1529. QIAN Jie, WANG Baohua, ZHENG Jianguo, et al. A quantum evolutionary algorithm for quadratic multiple knapsack problem[J]. Chinese Journal of Computers, 2015, 38(8): 1518-1529.
[22] 吴伟彬, 刘哲, 杨昊, 等. 后量子密码算法的侧信道攻击与防御综述[J]. 软件学报, 2021, 32(4): 1165-1185. WU Weibin, LIU Zhe, YANG Hao, et al. Survey of side-channel attacks and countermeasures on post-quantum cryptography[J]. Journal of Software, 2021, 32(4): 1165-1185.
[23] 宋慧超, 刘晓楠, 王洪, 等. 基于Grover搜索算法的整数分解[J]. 计算机科学, 2021, 48(4): 20-25. SONG Huichao, LIU Xiaonan, WANG Hong, et al. Integer decomposition based on Grover search algorithm full text replacement[J]. Computer Science, 2021, 48(4): 20-25.
[24] SMITH-MILES K, LOPES L. Measuring instance difficulty for combinatorial optimization problems[J]. Computers& Operations Research, 2012, 39(5): 875-889.
[25] 周亮. 实数编码量子进化算法及在投资组合中的应用[D]. 上海: 东华大学, 2012. ZHOU Liang. Real-coded quantum evolutionary algorithm and its application in portfolio selection[D].Shanghai: Donghua University, 2012.
[26] HAN K H, KIM J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593.
[27] 杨淑媛, 焦李成, 刘芳. 量子进化算法[J]. 工程数学学报, 2006,23(2): 235-246. YANG Shuyuan, JIAO Licheng, LIU Fang. The quantum evolutionary algorithm[J]. Chinese Journal of Engineering Mathematics, 2006,23(2): 235-246.
[28] 赵新泉, 彭勇行. 管理决策分析[M]. 2版. 北京: 科学出版社, 2000. ZHAO Xinquan, PENG (Yong)(Hang|Xing). Management decision analysis[M]. 2nd ed. Beijing: Science Press, 2000.
[29] 高辉, 张锐. 改进实数编码量子进化算法及其在参数估计中的应用[J]. 控制与决策, 2011, 26(3): 418-422. GAO Hui, ZHANG Rui. Improved real-coded quantum evolutionary algorithms and its application on parameter estimation[J]. Control and Decision, 2011, 26(3): 418-422.
[30] 李昆仑, 关立伟. 实数编码量子共生演算法及其在云任务调度中的应用[J]. 计算机应用研究, 2019, 36(3): 786-791. LI Kunlun, GUAN Liwei. Real-coded quantum SOS algorithm and its application in cloud task scheduling[J]. Application Research of Computers, 2019, 36(3): 786-791.
[31] 覃朝勇, 郑建国, 朱佳俊. 一种实数编码量子进化算法及其收敛性[J]. 控制与决策, 2009, 24(6): 854-858, 863. QIN Chaoyong, ZHENG Jianguo, ZHU Jiajun. Real-coded quantum-inspired evolutionary algorithm and its convergence[J]. Control and Decision, 2009, 24(6): 854-858, 863.
[32] 张宇献, 钱小毅, 彭辉灯, 等. 基于等位基因的实数编码量子进化算法[J]. 仪器仪表学报, 2015, 36(9): 2129-2137. ZHANG Yuxian, QIAN Xiaoyi, PENG Huideng, et al. Real-coded quantum evolutionary algorithm based on allele[J]. Chinese Journal of Scientific Instrument, 2015, 36(9): 2129-2137.
[33] 钱小毅. 基于等位基因量子进化算法的经纱断头率优化研究[D]. 沈阳: 沈阳工业大学, 2016. QIAN Xiaoyi. Study on the end breakage rate optimization for warp based on allele quantum evolutionary algorithm[D].Shenyang: Shenyang University of Technology, 2016.
[34] 高辉, 徐光辉, 张锐, 等. 实数编码量子进化算法[J]. 控制与决策, 2008,23(1): 87-90. GAO Hui, XU Guanghui, ZHANG Rui, et al. Real-coded quantum evolutionary algorithm[J]. Control and Decision, 2008,23(1): 87-90.
[35] BROTCORNE L, LAPORTE G, SEMET F. Ambulance location and relocation models[J]. European Journal of Operational Research, 2003, 147(3): 451-463.
[36] WANG Fahui. Measurement, optimization, and impact of healthcare accessibility: amethodological review[J]. Annals of the Association of American Geographers, 2012, 102(5): 1104-1112.
[37] 张宇山. 进化算法的收敛性与时间复杂度分析的若干研究[D]. 广州: 华南理工大学, 2013. ZHANG Yushan. Some studies on the convergence and time complexity analysis of evolutionary algorithms[D].Guangzhou: South China University of Technology, 2013.
[38] 何键浩, 李绿周. 量子优化算法综述[J]. 计算机研究与发展, 2021, 58(9): 1823-1834. HE Jianhao, LI Lüzhou. An overview of quantum optimization[J]. Journal of Computer Research and Development, 2021, 58(9): 1823-1834.
[39] JIA Jingyuan, WANG Bo. The development of intelligent operation method of urban public infrastructure driven by accurate spatio-temporal information[J].Journal of Geodesy and Geoinformation Science, 2021, 4(2): 27-35.
[40] GUO Mengyu, WANG Shaowen. Quantum computing for solving spatial optimization problems[M]. Cham: Springer International Publishing, 2020: 97-113.

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

A quantum evolutionary algorithm for spatial optimization of facility allocation

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	程涛, 张洋, James Haworth. 基于网络和图的时空智能——概念、方法和应用[J]. 测绘学报, 2022, 51(7): 1629-1639.
[2]	朱庆, 张利国, 丁雨淋, 胡翰, 葛旭明, 刘铭崴, 王玮. 从实景三维建模到数字孪生建模[J]. 测绘学报, 2022, 51(6): 1040-1049.
[3]	张永生, 张振超, 童晓冲, 纪松, 于英, 赖广陵. 地理空间智能研究进展和面临的若干挑战[J]. 测绘学报, 2021, 50(9): 1137-1146.
[4]	蒋波涛, 王艳东, 叶信岳. 使用点评数据探测城市商业服务设施的发展规律[J]. 测绘学报, 2015, 44(9): 1022-1028.
[5]	谢顺平,冯学智,都金康. 基于网络Voronoi图启发式和群智能的最大覆盖空间优化[J]. 测绘学报, 2011, 40(6): 778-784.