發(fā)布時(shí)間：2021-06-08 17:42

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

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

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

【部分圖文】：

單校劃片實(shí)驗(yàn)結(jié)果圖

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

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

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

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



本文編號(hào)：3218892