基于迭代局部搜索的区划问题算法研究

作     者：孔云峰 KONG Yunfeng

作者机构：河南大学黄河中下游数字地理技术教育部重点实验室开封475000 河南大学地理与环境学院开封475000 

出 版 物：《地球信息科学学报》 (Journal of Geo-information Science)

年 卷 期：2022年第24卷第9期

页      面：1730-1741页

核心收录：

学科分类：081603[工学-地图制图学与地理信息工程] 081802[工学-地球探测与信息技术] 07[理学] 08[工学] 070503[理学-地图学与地理信息系统] 0818[工学-地质资源与地质工程] 0705[理学-地理学] 0816[工学-测绘科学与技术] 

基　　金：国家自然科学基金项目(41871307) 

主　　题：区划 区划问题 目标函数 迭代局部搜索 基准测试 案例研究 

摘      要：区划问题是将特定地理区域划分为若干空间连续的分区,满足分区内差异最小和分区间差异最大这一基本原则,广泛应用于地理、环境、生态、经济、农业、城市等领域。1960s以来,学者尝试建立各种区划问题数学模型,设计了一系列的求解算法,代表性的算法主要有:AZP、ARISEL、SKATER和REDCAP。本文提出了一个基于迭代局部搜索(ILS)的区划问题算法,进一步提升算法性能。该算法主要机制包括:邻域单元移动搜索改进分区质量;参照中心单元快速计算分区方差,提升算法速度;使用扰动机制跳出当前解局部最优状态;更新分区中心点提升分区方案目标值;使用群搜索探索更大的解空间;以及算法各步骤中通过分区空间连续判断和破碎修复保持分区空间连续。55个基准案例测试表明:ILS算法求解质量优于ARISEL和SKATER算法。一个多指标气候分区实验也表明:ILS算法求解质量优于SKATER、REDCAP和ARISEL算法。