提出一種基于自適應(yīng)層次譜聚類與遺傳優(yōu)化的算法求解大規(guī)模TSP,算法首先構(gòu)建一種自適應(yīng)相似矩陣,并應(yīng)用到譜聚類算法中實現(xiàn)城市的初步聚類,當(dāng)聚類城市規(guī)模超過設(shè)定閾值,用上述自適應(yīng)譜聚類算法進(jìn)行層次聚類,直到每類城市規(guī)模均小于閾值;其次,采用結(jié)合了最近鄰與禁忌思想的改進(jìn)遺傳算法求解GTSP,得類間最短回路;最后,用改進(jìn)遺傳算法求解每類城市群的最優(yōu)解,綜合類間GTSP最短回路以及類內(nèi)TSP最優(yōu)解,即得大規(guī)模旅行商問題的最優(yōu)解.實驗結(jié)果表明,該算法能夠取得相對較優(yōu)解且求解效率顯著提高. 

【文章來源】：云南師范大學(xué)學(xué)報(自然科學(xué)版). 2020,40(01)

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

【部分圖文】：

改進(jìn)遺傳算法流程圖

設(shè)該GTSP模型集合為G=V(,E），其中V=1{，2，…，s}，1～s表示類標(biāo)號；E為類間連線的集合，邊i(,j）的權(quán)值為Dij,i,j∈V，在該問題中，Dij�。�5）式定義的距離函數(shù)；類間路徑的優(yōu)化是尋找G的最短巡回路線，該巡回路線是類間連線最短回路，且最終在每個類中均可找到兩個類邊界點(diǎn)．經(jīng)過圖V集中每個類頂點(diǎn)恰好兩次（每類有兩個邊界點(diǎn)），即尋找經(jīng)過V集的不同類邊界點(diǎn)連線的最短巡回線路，圖2為類邊界點(diǎn)連線示意圖．則類間最短路徑總長度

為了驗證提出的基于自適應(yīng)層次譜聚類與遺傳優(yōu)化的算法的性能，在仿真環(huán)境Intel(R)Core(TM).i5-2450M CPU、4.00GB RAM、Window7(32bit）、MATLAB r2013a下，采用本文算法和傳統(tǒng)遺傳優(yōu)化算法，選用TSP標(biāo)準(zhǔn)測試庫TSPLIB[15]中的問題進(jìn)行數(shù)值實驗．在實驗中，兩算法參數(shù)設(shè)置相同，設(shè)置如下：種群大小Numpop=120、交叉概率crate=0.9、變異概率mrate=0.2、選擇率srate=0.3、隨機(jī)概率rrate=0.3和城市規(guī)模閾值thvalue=200，且設(shè)定類內(nèi)進(jìn)化代數(shù)、類間進(jìn)化代數(shù)以及遺傳算法進(jìn)化代數(shù)均為Iteration=300．表1為9個不同TSP實例的遺傳算法和本文算法實驗數(shù)據(jù)，9個TSP實例數(shù)據(jù)規(guī)模分別為150、198、280、417、535、783、1 000、1 379和5 915，數(shù)據(jù)整體呈遞增趨勢．由表1可以看出本文算法的最優(yōu)解均優(yōu)于遺傳算法最優(yōu)解，運(yùn)行時長更短，且遺傳算法結(jié)果誤差在10%～22%之間，本文算法結(jié)果誤差在3%～11%之間．圖3直觀地展示了兩算法在相同參數(shù)時，9個不同TSP實例的結(jié)果誤差和運(yùn)行時間的折線圖．由圖3(a）知，本文算法的結(jié)果誤差總體小于遺傳算法誤差，且隨著數(shù)據(jù)規(guī)模的增大，本文算法的結(jié)果優(yōu)勢更明顯；由圖3(b）知，本文算法的運(yùn)行時間均小于遺傳算法運(yùn)行時間，當(dāng)數(shù)據(jù)規(guī)模增大時，兩算法運(yùn)行時間整體呈上升趨勢，且本文算法在TSP數(shù)據(jù)規(guī)模增大時，用時優(yōu)勢更加明顯．由此可見，本文算法針對大規(guī)模TSP，有效避免收斂速度慢以及早熟現(xiàn)象，較大程度減少了運(yùn)算時間，提高了計算效率．6 總結(jié)

【參考文獻(xiàn)】：
期刊論文
[1]一種基于自適應(yīng)相似矩陣的譜聚類算法[J]. 王貝貝,楊明,燕慧超,孫笑仙.  河北工業(yè)科技. 2018(02)
[2]基于改進(jìn)遺傳算法的孔群數(shù)控加工路徑優(yōu)化[J]. 龔玉玲,武美萍,徐曉棟,龔非.  組合機(jī)床與自動化加工技術(shù). 2017(11)
[3]蟻群算法優(yōu)化和路徑規(guī)劃問題的應(yīng)用研究[J]. 潘曉萌,李冰.  科技通報. 2016(06)
[4]基于遺傳蟻群混合算法的孔群加工路徑優(yōu)化[J]. 王春香,郭曉妮.  機(jī)床與液壓. 2011(21)
[5]基于免疫記憶的人工免疫算法模型及其應(yīng)用[J]. 王磊,肖人彬.  模式識別與人工智能. 2002(04)

碩士論文
[1]旅行商問題的兩種智能算法[D]. 文永軍.西安電子科技大學(xué) 2010



本文編號：3507421