一种求解学区划分问题的混合启发式算法

发布时间：2021-06-08 17:42

　　针对目前求解学区划分问题算法搜索过程缺乏记忆,搜索效率不高,容易陷入局部最优而收敛慢等问题,该文提出一种多启动（M）框架下,迭代禁忌搜索（ITS）算法与模拟退火（SA）算法混合的M-ITS-SA算法。该算法包括构造初始解、禁忌搜索、SA算法优化与求解等。运用K-Medoids模型对学校分组后,采用M-ITS-SA算法对学区进行划分与优化,并从多个分区方案中求解最优分区方案。学区划分实验结果表明:该文提出的M-ITS-SA算法能够保证分区的空间连续性,适用于单校和多校划片,并在入学总距离上与混合元启发算法（M-ILS-SPP）保持相当的同时,大大降低了超额招生人数和总用时,具有良好的寻优能力和收敛性,优于M-ILS-SPP算法。 

【文章来源】：测绘科学. 2020,45(01)北大核心CSCD

【文章页数】：8 页

【部分图文】：

单校划片实验结果图

本文提出的M-ITS-SA算法是ITS与SA的组合式算法，主要包括构造初始解、ITS算法优化以及SA模型再优化与求解，在多启动机制下进行学区划分（图1）。在构造初始解过程中，采用随机选择的方式，在满足约束条件的情况下，随机选择待加入单元加入分区，在多次启动下获得多个不同的初始解。在ITS算法优化过程中，分别对已构造的初始解进行优化，随机选择待优化分区和邻域搜索算子，得到多个不同的优化解，但这些解不一定是最优解，还需要SA模型进行再优化。SA模型再优化过程中，同样采用随机的方式，随机选择待优化分区进行优化，从之前ITS算法优化生成的优化解中搜寻更优解。若多启动机制设定M次多启动次数，则可得到M个优化解，最后从M个优化解中求出最优解。M-ITS-SA算法的多启动、随机搜索机制，更大范围地搜寻到更优解，实现了算法的多样性。1.1 改进区域生长算法构造初始解

SA模型再优化流程图

【参考文献】：
期刊论文
[1]基于解空间优化的遗传算法的路径规划[J]. 王尧山,朱毅,卢军.  电子技术与软件工程. 2018(19)
[2]用于求解混合车辆路径问题的混合进化算法[J]. 孙启,金燕,何琨,徐凌轩.  计算机科学. 2018(04)
[3]求解最短路问题的改进禁忌搜索算法[J]. 程航,张磊.  交通科技与经济. 2018(02)
[4]基于加权距离成本的最优学区划分算法[J]. 栗敏光,董琳琳.  测绘与空间地理信息. 2017(12)
[5]改进遗传模拟退火算法在TSP优化中的应用[J]. 何庆,吴意乐,徐同伟.  控制与决策. 2018(02)
[6]学校分区问题混合元启发算法研究[J]. 孔云峰,朱艳芳,王玉璟.  地理学报. 2017(02)
[7]GIS空间分析在学区划分中的应用[J]. 董琳琳,栗敏光.  城市勘测. 2016(02)
[8]利用GIS与线性规划学校最优学区划分[J]. 孔云峰.  武汉大学学报(信息科学版). 2012(05)
[9]求解0-1二次规划问题的迭代禁忌搜索算法[J]. 张爱君,秦新强,龚春琼.  计算机工程. 2012(01)
[10]模拟退火算法求解TSP问题[J]. 冯剑,岳琪.  森林工程. 2008(01)

硕士论文
[1]局部搜索算法求解组合优化问题[D]. 张永飞.东北师范大学 2018
[2]基于局部搜索的分布式约束优化问题求解算法研究[D]. 余浙鹏.重庆大学 2017
[3]大数据环境中知识服务及K-medoids算法改进研究[D]. 谭黔林.广西大学 2016
[4]基于启发式算法求解路由与波长分配问题[D]. 燕圣峰.华中科技大学 2016
[5]图像的插值放大和多阈值区域生长算法的研究[D]. 马玉珍.东北大学 2008



本文编号：3218892