針對目前求解學區(qū)劃分問題算法搜索過程缺乏記憶,搜索效率不高,容易陷入局部最優(yōu)而收斂慢等問題,該文提出一種多啟動（M）框架下,迭代禁忌搜索（ITS）算法與模擬退火（SA）算法混合的M-ITS-SA算法。該算法包括構(gòu)造初始解、禁忌搜索、SA算法優(yōu)化與求解等。運用K-Medoids模型對學校分組后,采用M-ITS-SA算法對學區(qū)進行劃分與優(yōu)化,并從多個分區(qū)方案中求解最優(yōu)分區(qū)方案。學區(qū)劃分實驗結(jié)果表明:該文提出的M-ITS-SA算法能夠保證分區(qū)的空間連續(xù)性,適用于單校和多校劃片,并在入學總距離上與混合元啟發(fā)算法（M-ILS-SPP）保持相當?shù)耐瑫r,大大降低了超額招生人數(shù)和總用時,具有良好的尋優(yōu)能力和收斂性,優(yōu)于M-ILS-SPP算法。 

【文章來源】：測繪科學. 2020,45(01)北大核心CSCD

【文章頁數(shù)】：8 頁

【部分圖文】：

單校劃片實驗結(jié)果圖

本文提出的M-ITS-SA算法是ITS與SA的組合式算法，主要包括構(gòu)造初始解、ITS算法優(yōu)化以及SA模型再優(yōu)化與求解，在多啟動機制下進行學區(qū)劃分（圖1）。在構(gòu)造初始解過程中，采用隨機選擇的方式，在滿足約束條件的情況下，隨機選擇待加入單元加入分區(qū)，在多次啟動下獲得多個不同的初始解。在ITS算法優(yōu)化過程中，分別對已構(gòu)造的初始解進行優(yōu)化，隨機選擇待優(yōu)化分區(qū)和鄰域搜索算子，得到多個不同的優(yōu)化解，但這些解不一定是最優(yōu)解，還需要SA模型進行再優(yōu)化。SA模型再優(yōu)化過程中，同樣采用隨機的方式，隨機選擇待優(yōu)化分區(qū)進行優(yōu)化，從之前ITS算法優(yōu)化生成的優(yōu)化解中搜尋更優(yōu)解。若多啟動機制設(shè)定M次多啟動次數(shù)，則可得到M個優(yōu)化解，最后從M個優(yōu)化解中求出最優(yōu)解。M-ITS-SA算法的多啟動、隨機搜索機制，更大范圍地搜尋到更優(yōu)解，實現(xiàn)了算法的多樣性。1.1 改進區(qū)域生長算法構(gòu)造初始解

SA模型再優(yōu)化流程圖

【參考文獻】：
期刊論文
[1]基于解空間優(yōu)化的遺傳算法的路徑規(guī)劃[J]. 王堯山,朱毅,盧軍.  電子技術(shù)與軟件工程. 2018(19)
[2]用于求解混合車輛路徑問題的混合進化算法[J]. 孫啟,金燕,何琨,徐凌軒.  計算機科學. 2018(04)
[3]求解最短路問題的改進禁忌搜索算法[J]. 程航,張磊.  交通科技與經(jīng)濟. 2018(02)
[4]基于加權(quán)距離成本的最優(yōu)學區(qū)劃分算法[J]. 栗敏光,董琳琳.  測繪與空間地理信息. 2017(12)
[5]改進遺傳模擬退火算法在TSP優(yōu)化中的應(yīng)用[J]. 何慶,吳意樂,徐同偉.  控制與決策. 2018(02)
[6]學校分區(qū)問題混合元啟發(fā)算法研究[J]. 孔云峰,朱艷芳,王玉璟.  地理學報. 2017(02)
[7]GIS空間分析在學區(qū)劃分中的應(yīng)用[J]. 董琳琳,栗敏光.  城市勘測. 2016(02)
[8]利用GIS與線性規(guī)劃學校最優(yōu)學區(qū)劃分[J]. 孔云峰.  武漢大學學報(信息科學版). 2012(05)
[9]求解0-1二次規(guī)劃問題的迭代禁忌搜索算法[J]. 張愛君,秦新強,龔春瓊.  計算機工程. 2012(01)
[10]模擬退火算法求解TSP問題[J]. 馮劍,岳琪.  森林工程. 2008(01)

碩士論文
[1]局部搜索算法求解組合優(yōu)化問題[D]. 張永飛.東北師范大學 2018
[2]基于局部搜索的分布式約束優(yōu)化問題求解算法研究[D]. 余浙鵬.重慶大學 2017
[3]大數(shù)據(jù)環(huán)境中知識服務(wù)及K-medoids算法改進研究[D]. 譚黔林.廣西大學 2016
[4]基于啟發(fā)式算法求解路由與波長分配問題[D]. 燕圣峰.華中科技大學 2016
[5]圖像的插值放大和多閾值區(qū)域生長算法的研究[D]. 馬玉珍.東北大學 2008



本文編號：3218892