亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        一種基于鄰域搜索機制的旅行商問題求解?

        2015-08-02 11:07:11阮姍娜陳俊風(fēng)王思睿
        微處理機 2015年6期
        關(guān)鍵詞:鄰域個數(shù)概率

        阮姍娜,陳俊風(fēng),顧 菁,王思睿

        (河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院,常州213022)

        一種基于鄰域搜索機制的旅行商問題求解?

        阮姍娜,陳俊風(fēng),顧 菁,王思睿

        (河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院,常州213022)

        旅行商問題是一個經(jīng)典的數(shù)學(xué)組合優(yōu)化問題,其廣泛的工程應(yīng)用背景促進了旅行商問題求解方法的快速發(fā)展。針對旅行商問題中最優(yōu)路徑的連接特點,提出了兩種鄰域搜索方法:鄰域隨機性搜索法和鄰域概率性搜索法。這兩種鄰域搜索法對旅行商問題解的質(zhì)量具有一定的提高能力,其中,為了加快搜索速度,在算法前期采用了循環(huán)倒置算子。實驗結(jié)果表明算法在求解小規(guī)模旅行商問題時具有良好的尋優(yōu)性能。最后將該算法與標(biāo)準(zhǔn)遺傳算法結(jié)合,并進行了實驗結(jié)果對比。實驗數(shù)據(jù)顯示結(jié)合后的算法搜索性能優(yōu)于單一的兩種優(yōu)化算法,提高了算法搜索解的能力。

        旅行商問題;鄰域;隨機搜索;概率搜索;循環(huán)倒置;最優(yōu)路徑

        1 引 言

        旅行商問題(Traveling Salesman Problem,TSP)是組合優(yōu)化[1]中一個易于描述但至今尚未徹底解決的古老而又困難的問題,是著名的NP-h(huán)ard[2]問題。旅行商問題在工程上具有廣泛的實際應(yīng)用背景,最早應(yīng)用于校車路線的優(yōu)化。目前旅行商問題已廣泛應(yīng)用于電路板設(shè)計、城市規(guī)劃、交通運輸、物流配送等領(lǐng)域。因此,對旅行商問題進行研究具有重要意義,一直以來受到學(xué)者們的大量關(guān)注,是組合優(yōu)化領(lǐng)域中的研究熱點。

        針對目前不同的實際應(yīng)用背景衍生出了多種不同類型的旅行商問題,如非對稱旅行商問題、多旅行商問題、多目標(biāo)旅行商問題、黑白旅行商問題等,它們都可以轉(zhuǎn)換成旅行商問題進行求解。旅行商問題的求解方法主要分為以線性規(guī)劃法、分支定界法為代表的精確算法[3-4]和以啟發(fā)式算法為代表的近似算法[5-6]。近似算法求解性能優(yōu)于精確算法,應(yīng)用性也比精確算法廣。通過觀察旅行商問題中最優(yōu)路徑圖的每個城市連接特性后發(fā)現(xiàn),利用鄰域搜索機制、對各個城市的鄰域進行深度尋優(yōu)的思想對旅行商問題的求解找到了一個合適的近似算法。

        2 TSP描述

        TSP最早可追溯到18世紀(jì)騎士周游問題,又稱旅行推銷員問題[7]。

        TSP可描述為:推銷員打算到n個城市進行產(chǎn)品推銷,從其中一個城市出發(fā),要求找到一條通過所有城市再回到起點的最短路徑,每座城市必須且只能訪問一次。

        設(shè)n個城市集合為

        城市之間的距離為

        則上述問題轉(zhuǎn)化為如下優(yōu)化問題:

        其中kij為

        圖論語言描述則為:一個帶權(quán)圖G=(V,E),V={1,2,…,n}表示頂點集,E={eij=(i,j),i,j∈V,i≠j}表示邊集,尋求G的一個使邊長最小即權(quán)值最小的Hamilton回路[8]。

        3 鄰域搜索

        通過對最優(yōu)路徑圖研究后發(fā)現(xiàn),依據(jù)總體路徑最短的特征,每個城市在離自己距離較近的多個城市內(nèi)選擇合適的城市進行連接。并非所有城市都與自己的最近鄰城市連接。若所有城市選擇與最近鄰的城市相連,路徑很容易陷入局部最優(yōu)。因此本文根據(jù)最優(yōu)路徑各城市的這種連接特點,提出兩種新的鄰域搜索法,避免算法過早陷入局部最優(yōu)。

        3.1 鄰域范圍內(nèi)隨機搜索

        當(dāng)前所有N個個體的集合記為U={u1,u2,……,uN},對每個城市找出與其相鄰比較近的n個城市作為一個集合C={c1,c2,……,cn},n的個數(shù)選擇對最優(yōu)解的尋找有很大影響。針對當(dāng)前城市i,在由n個城市組成的鄰域范圍內(nèi)利用隨機選擇方式進行下個城市j的選擇。若C中所有城市都已被遍歷過,則選擇不包含在C內(nèi)、并離i最近的城市j作為下個城市訪問點,避免城市連線出現(xiàn)交叉現(xiàn)象。

        3.2 鄰域范圍內(nèi)概率搜索

        對于每個城市,找出與其相鄰較近的n個城市作為一個集合C,同時計算整體U的平均路徑長度。為了防止路徑過大的個體影響整體的平均值,在計算平均值時去除路徑最大的個體。統(tǒng)計路徑長度小于平均值的個體總數(shù)k。對于路徑長度小于均值的k個個體,統(tǒng)計與城市i相鄰的集合C中每個城市出現(xiàn)的次數(shù)m,計算C中每個城市出現(xiàn)的概率p=m/k,根據(jù)輪盤賭選擇方式選擇下一個訪問城市。若下個訪問城市的概率為0,則對為0的城市概率做歸一化處理,保證每個城市都可能被訪問到,防止最優(yōu)解被丟失。

        4 循環(huán)倒置算子

        為了加快前期尋找最優(yōu)解的速度,在算法初期采用了倒置算子[9],即隨機選取個體中的城市片段進行倒置,若倒置后個體的距離小于原先個體,則用新個體替換原先個體。為了不失去統(tǒng)一性,將個體中所有城市構(gòu)成一個循環(huán)圈,首尾附近的城市片段也可參與倒置操作,避免局部最優(yōu)城市片段的丟失,增加搜索到最優(yōu)解的概率。

        5 算法結(jié)構(gòu)

        根據(jù)以上描述,本文算法的基本結(jié)構(gòu)如下:

        (1)初始化:隨機生成N個個體,保持整體多樣性。設(shè)置最大進化迭代次數(shù)。

        (2)算法前期:采用循環(huán)倒置算子,使群體較快收斂到最優(yōu)值附近,實驗中前期的代數(shù)設(shè)為最大進化代數(shù)的1/5。

        (3)算法中期:循環(huán)倒置算子和鄰域搜索法共同進行,增加尋優(yōu)速度,提高尋優(yōu)概率。實驗中中期的代數(shù)設(shè)為最大進化代數(shù)的2/5。

        (4)算法后期:利用鄰域搜索法在全局中逐步尋找最優(yōu)解。

        (5)終止條件:當(dāng)達到最大迭代次數(shù)時算法停止,若沒有達到則返回到步驟(2)繼續(xù)迭代。

        6 實驗結(jié)果與分析

        實驗中用matlab.R2012a軟件實現(xiàn)算法對TSP的求解。初始化設(shè)置個體總個數(shù)為30,最大迭代次數(shù)400,TSP城市采用TSP數(shù)據(jù)庫中的burma14(最優(yōu)解為30.8785)。針對不同的鄰域城市個數(shù)n進行多次測試,實驗結(jié)果如表1所示。其中Ave表示程序運行10次后得到的平均值,Opt表示10次中得到的最優(yōu)值,K表示10次中得到最優(yōu)值的次數(shù)。

        表1 RSN和PSN在不同的n條件下得到的實驗結(jié)果

        由表1可知,鄰域搜索法在n為2到6時都可尋到最優(yōu)結(jié)果,但隨著鄰域個數(shù)的不同,得到的平均值不同,搜索到最優(yōu)值的次數(shù)也不相同。對于隨機性鄰域搜索,當(dāng)n=5時尋優(yōu)效果最佳;對于概率性鄰域搜索,當(dāng)n=4時尋優(yōu)效果最佳,并且概率性鄰域搜索成功率高于隨機性搜索成功率。

        根據(jù)以上實驗結(jié)果,對標(biāo)準(zhǔn)的30個城市(最優(yōu)解為423.7406)進行了測試。鄰域城市個數(shù)n分別為4、5和6,個體個數(shù)仍為30,最大迭代次數(shù)為800。由于遺傳算法具有全局性,最后將該算法的兩種情況分別與標(biāo)準(zhǔn)遺傳算法(SGA)結(jié)合,設(shè)置SGA的變異概率為0.05,交叉概率為0.9,種群大小為30,最大迭代次數(shù)為800代。得到的實驗結(jié)果如表2所示。

        結(jié)合后得出的實驗結(jié)果表2 不同n條件下RSN和PSN與SGA

        由表2可知,鄰域隨機搜索比概率尋優(yōu)效率高,但算法單獨運行時易陷入局部最優(yōu)。針對不同的城市規(guī)模應(yīng)設(shè)置不同的鄰域城市個數(shù)。該算法與SGA結(jié)合后在n=5時尋到了最優(yōu)解,提高了算法搜索效率,使得解的質(zhì)量得到了相應(yīng)提高。

        觀察表1和表2可知,此算法對于小規(guī)模的TSP搜索效果較好。與其它算法融合提高了算法搜索性能,增強了尋優(yōu)能力。但在實驗過程中總運行時間偏慢,因此該算法在運行速度上有待進一步加強。

        7 結(jié)束語

        基于鄰域搜索機制的旅行商問題求解主要是針對TSP中最優(yōu)解的城市連接規(guī)則,在鄰域范圍內(nèi)根據(jù)隨機尋優(yōu)和鄰域范圍內(nèi)概率尋優(yōu)的方法來求解TSP,實驗結(jié)果說明其具有一定的尋優(yōu)能力,并且與其它智能優(yōu)化算法的結(jié)合有助于算法性能的提高,因此本文方法與其它算法的融合將是下一步值得繼續(xù)研究的方向。

        [1] Lenstra JK,Kan A H G R,Shmoys D B.The traveling salesman problem:a guided tour of combinatorial optimization[M].New York:Wiley,1985.

        [2] Garey M R,Johnson D S.Computers and Intractability:a guide to the theory of NP-Completeness[M].San Francisco:Freeman W H,1979.

        [3] 楊忠程,徐新黎,葉雙挺.基于組合拆分策略求解TSP的動態(tài)規(guī)劃算法[J].計算機工程,2012,13(38):185-187.

        YANG Zhong-cheng,XU Xin-li,YE Shuang-ting.Dynamic programming algorithm based on combination and Division Strategy for Solving TSP[J].Computer Engineering,2012,13(38):185-187.

        [4] 周康,強小利.求解TSP算法[J].計算機工程與應(yīng)用,2007,43(29):43-47.

        Zhou Kang,Qiang Xiao-li,Tong Xiao-jun.Algorithm of TSP[J].Computer Engineering and Applications,2007,43(29):43-47.

        [5] Tang Q,Zeng J Y,Li H.A particle swarm optimization algorithm based on genetic selection strategy[M].Springer Berlin Heidelberg:Advances in Neural Networks ISNN 2009,2009.

        [6] Gao S,Zhang Z Y,Cao C G.A novel ant colony genetic hybrid algorithm[J].Journal of Software,2010,5(11):1179-1186.

        [7] 馬良.旅行推銷員問題的算法綜述[J].數(shù)學(xué)的實踐與認識,2000,30(4):156-165.

        Ma Liang.Algorithmic review on the travelling salesman problem[J].Mathematics in practice and theory,2000,30(4):156-165.

        [8] Garey M R,Johnson D S,Tarjan R E.The planar Hamiltonian circuit problem is NP-complete[J].SIAM Journal on Computing,1976,5(4):704-714.

        [9] 朱林杰.基于TSP的遺傳算法優(yōu)化研究[D].大連:大連理工大學(xué),2007.

        Zhu Lin-jie.The study of genetic algorithm optimization based on TSP[D].Dalian:Dalian University of Technology,2007.

        Solution to Traveling Salesman Problem Based on Neighborhood Search System

        Ruan Shanna,Chen Junfeng,Gu Jing,Wang Sirui
        (College of Internet of Things Engineering,Hohai University,Changzhou 213022,China)

        Traveling salesman problem,as a classic mathematical optimization problem,with the extensive background of engineering application,promotes the development of the solution methods.For the connected characteristics of the optimal path of the traveling salesman problem,this paper puts forward two kinds of neighborhood search methods,i.e.the random search method in the neighborhood and probabilistic search method in the neighborhood,which improve the quality of the solutions.Among them,in order to speed up the search speed,loop inversion operator is used in the early process of the algorithm.The experimental results show that the algorithm has a good optimization performance when solving traveling salesman problem with small scale.Finally,the proposed algorithm is combined with the standard genetic algorithm and compared with the standard genetic algorithm.The experimental data shows that the combinational algorithm is better than the single optimization ones and improves the searching ability.

        Traveling Salesman Problem;Neighborhood;Random search;Probabilistic search;Loop inversion;Optimal path

        10.3969/j.issn.1002-2279.2015.06.012

        TP301.6

        A

        1002-2279(2015)06-0044-03

        國家自然科學(xué)基金(61403121)

        阮姍娜(1990-),女,安徽省池州市人,碩士研究生,主研方向:智能信息處理。

        2015-03-18

        猜你喜歡
        鄰域個數(shù)概率
        第6講 “統(tǒng)計與概率”復(fù)習(xí)精講
        第6講 “統(tǒng)計與概率”復(fù)習(xí)精講
        怎樣數(shù)出小正方體的個數(shù)
        概率與統(tǒng)計(一)
        概率與統(tǒng)計(二)
        稀疏圖平方圖的染色數(shù)上界
        等腰三角形個數(shù)探索
        怎樣數(shù)出小木塊的個數(shù)
        怎樣數(shù)出小正方體的個數(shù)
        基于鄰域競賽的多目標(biāo)優(yōu)化算法
        品色永久免费| 国产av在线观看一区二区三区| 国产狂喷水潮免费网站www| 欧美日韩精品| 欧美日韩中文字幕久久伊人| 国产一级av理论手机在线| 亚洲久悠悠色悠在线播放| 国产精品毛片一区二区 | 成人午夜福利视频| 日产无人区一线二线三线新版| 日韩免费高清视频网站| 中文字幕乱码人妻在线| 蜜臀av在线播放一区二区三区| 久久精品无码中文字幕| 国产真实伦视频在线视频| 我揉搓少妇好久没做高潮| 久久人人爽爽爽人久久久| 天天爽天天爽天天爽| 精品丝袜国产在线播放| 中文字幕一二三四五六七区| 天堂中文官网在线| 久青草国产视频| 国产女主播视频一区二区三区| 国产一区二区三区av天堂| 国产精品免费观看久久| 精品九九视频| 毛片成人18毛片免费看| 亚洲av无码乱码在线观看裸奔| 日韩国产精品一区二区Hd| 亚洲中文字幕国产综合| 日韩极品视频免费观看| 熟妇丰满多毛的大隂户| 91超碰在线观看免费| 成人免费播放视频影院| 99久久婷婷国产综合精品青草免费| 亚洲第一网站免费视频| 97中文字幕一区二区| 日韩欧美中文字幕公布| 少妇饥渴xxhd麻豆xxhd骆驼| 久久精品综合国产二区| 中文字幕乱码熟女人妻在线|