發(fā)布時間：2021-11-20 13:28

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

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

【文章頁數】：8 頁

【部分圖文】：

改進遺傳算法流程圖

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

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

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

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



本文編號：3507421