国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

用量子蟻群算法求解大規(guī)模旅行商問題

2012-03-22 02:20:46煜,
上海理工大學(xué)學(xué)報 2012年4期
關(guān)鍵詞:比特量子螞蟻

李 煜, 馬 良

(1.上海理工大學(xué)管理學(xué)院,上海 200093;2.河南大學(xué)管理科學(xué)與工程研究所,開封 475004)

蟻群算法是一種來自生物界的隨機搜索尋優(yōu)方法,由意大利學(xué)者Colorni等[1-2]于20世紀90年代初期通過模擬自然界中螞蟻的尋徑行為,而提出的一種基于種群的啟發(fā)式仿生進化算法,并得到了廣泛的應(yīng)用[3-4].但蟻群算法在較大規(guī)模問題中計算時間偏長、運算精度低.本文將在基本的蟻群算法中融入量子計算理論,以進一步提高搜索效率和搜索精度.

量子優(yōu)化是由量子計算和量子信息論發(fā)展而來的,20世紀80年代初Benioff和Feynman提出了量子計算的概念,隨后Shor于1994年提出基于量子Fourier變換的大數(shù)質(zhì)因子分解算法,大數(shù)質(zhì)因子求解問題是公認的NP(non-deterministicpolynomial)問題,Shor算法將大數(shù)質(zhì)因子求解轉(zhuǎn)換為P(polynomial)問題.Grover于1996年提出無序數(shù)據(jù)庫的量子搜索算法,該算法則提供了經(jīng)典算法的根方加速,從此,量子計算以其獨特的計算性能引起了廣泛的矚目,并迅速成為研究的熱點[5-7].世界首臺通用編程量子計算機已經(jīng)于美國面世[8],其可在進一步改進后應(yīng)用于密碼破譯等方面.將量子計算技術(shù)應(yīng)用于優(yōu)化理論中,稱為量子優(yōu)化算法,可以解決經(jīng)典方法難以解決或無法解決的許多問題.量子蟻群算法是一種基于量子優(yōu)化原理的新的優(yōu)化方法,其將量子優(yōu)化和蟻群尋優(yōu)相結(jié)合,提高了旅行商問題(TSP)的運算精度.本文首先結(jié)合TSP給出量子蟻群算法的原理,然后用數(shù)值實驗說明其有效性.

1 量子蟻群算法

1.1 TSP的一般描述

TSP是一個典型的優(yōu)化組合問題,已被證明屬于NP完全問題.對于TSP的求解,一直以來都是學(xué)術(shù)界研究的熱點,精確算法主要有線性規(guī)劃算法、動態(tài)規(guī)劃算法和分支定界算法,但這些精確算法是指數(shù)級的,所能求解的問題規(guī)模非常有限,對n個城市而言,可能的路徑總數(shù)為n?。?n,隨著n數(shù)的增加,路徑數(shù)將急劇增長.由于現(xiàn)實中這些問題在許多領(lǐng)域都有著廣泛的應(yīng)用,因而尋找其實際而有效的算法就顯得頗為重要.盡管有指數(shù)級的算法可作精確求解,但隨著它們在大規(guī)模問題上的失效(組合爆炸),人們退而求其次,轉(zhuǎn)向?qū)ふ医扑惴ɑ騿l(fā)式算法.經(jīng)過幾十年的努力,取得了很大的進展[9-12].

TSP在圖論意義下又常常被稱為最小哈密頓圈問題,這里用數(shù)學(xué)的語言來進行描述.

記G=(V,E)為賦權(quán)圖,V={1,2,…,n}為頂點集,E為邊集,各頂點間的距離cij已知,cij>0,cij=∞,i,j∈V.設(shè)

則經(jīng)典TSP的數(shù)學(xué)模型為

式中,Z為目標函數(shù)值;|S|為集合S中所含圖G的頂點數(shù).

約束(1)和(2)意味著對每個點來說,僅有一條邊進和一條邊出;約束(3)則保證了沒有任何子回路解的產(chǎn)生.于是,滿足約束(1)~(3)的解構(gòu)成了一條哈密頓回路.

為簡便起見,本文中假定所考慮的都是歐氏意義下的完全圖;否則,可通過求任意兩點間的最短路轉(zhuǎn)化為等價的完全圖形式.

1.2 量子算法

量子算法是一種新發(fā)展起來的概率進化算法,它基于量子計算原理,利用量子計算的一些概念和理論,如量子位、量子疊加態(tài)等.量子比特是量子計算中保存信息的最小單元,一個量子比特可能處于,也可能處于,還可以是兩種狀態(tài)的線性疊加[7,13].因此,一個量子位可表示為

一個具有m個量子比特位的系統(tǒng)同時表示2m種狀態(tài),可以描述為

1.3 蟻群算法

蟻群算法(ant colony algorithm)是一種新穎的仿生算法,它抽象了自然界螞蟻的群體行為,吸收了昆蟲王國中螞蟻群體的行為特性,用螞蟻群在搜索食物源的過程中所體現(xiàn)出來的尋優(yōu)能力來解決一些離散系統(tǒng)優(yōu)化中的困難問題.該方法目前已經(jīng)成功地應(yīng)用于很多NP完備的組合優(yōu)化問題.

蟻群算法的轉(zhuǎn)移概率是一個非常重要的因素,它體現(xiàn)了人工螞蟻在移動時的尋優(yōu)特性,應(yīng)用在算法中主要體現(xiàn)在兩個方面,即信息素軌跡強度和距離,它們分別以一定的權(quán)重影響著轉(zhuǎn)移概率的值.

按照TSP的約束,在螞蟻的周游完成以前只能訪問未曾到過的節(jié)點,設(shè)螞蟻的數(shù)量為m,系統(tǒng)初始時將m只螞蟻隨機放在n個節(jié)點上,并設(shè)置了每邊的初始信息素濃度.為此設(shè)定一個禁忌表t[m][n].其中,t[k][f]表示螞蟻k在時刻t以前走過的點.螞蟻的一次周游構(gòu)造了問題的一個可行解.當(dāng)m只螞蟻都完成一次周游后,便在各自經(jīng)過的路徑的每一條邊上留下信息素.若算法經(jīng)過N次循環(huán)后停止,則基本蟻群算法的時間復(fù)雜度為Ο(N·m·n2).在實驗中,m一般取值與n為同一數(shù)量級,因此,整個算法的復(fù)雜度為Ο(N ·n3).

位于i處的螞蟻k移至其鄰域中結(jié)點j處的概率為

式中,ηij為邊?。╥,j)的能見度(visibility),即1/dij;τij為邊?。╥,j)的軌跡強度(intensity);α為軌跡的相對重要性,α≥0;β為能見度的相對重要性,β≥0;bij為邊?。╥,j)量子信息強度.

給定城市元素的集合C={c1,c2,…,cn},C中任意排列組合L={(c1…,ci,…,cj,…,cn),ci∈C,i,j=1,2,…,n},L為路徑(i,j)的長度.

信息素強度的更新方程為

式中,τi,j,t+1,τij,t分別為第t+1次和t次迭代的邊弧(i,j)的軌跡強度;Δτkij為螞蟻k在邊?。╥,j)上留下的單位長度軌跡信息素數(shù)量,ρ為信息強度的揮發(fā)性,0≤ρ<1.

式中,Q為螞蟻所留下軌跡數(shù)量的一個常數(shù).

1.4 量子蟻群算法

量子蟻群算法集量子計算和蟻群算法的優(yōu)點于一身,對它們?nèi)¢L補短,同基本的蟻群算法相比具有更好的搜索性能.量子算法可以根據(jù)不同的問題設(shè)計不同的量子門使得算法搜索到最優(yōu)解.量子門的設(shè)計有多種形式,但由于概率歸一化的要求,變換矩陣必須滿足酉正矩陣,酉性限制是對量子門的唯一限制.常用的有非門、受控非門、Hadamard門及量子旋轉(zhuǎn)門等.量子門是實現(xiàn)算法進化操作的執(zhí)行機構(gòu),通過量子門算子使量子比特的概率幅發(fā)生變化,推動量子個體向最優(yōu)解方向演化,本文設(shè)置的量子旋轉(zhuǎn)門為

式中,θ為旋轉(zhuǎn)的角度.

通過不斷地更新量子旋轉(zhuǎn)門U(θ)來更新量子比特qj,不斷地生成新的解X,比較解X的函數(shù)值,可以得到最好解b.量子旋轉(zhuǎn)門的調(diào)整方式可定義為

旋轉(zhuǎn)角的幅值直接影響算法的收斂速度和搜索能力.如果幅值過大,會導(dǎo)致早熟;如果幅值過小,會是收斂速度減慢.其值一般在0.001π~0.05π之間.其大小和方向根據(jù)關(guān)系式θi=Δθis(αi,βi)來確定,s(αi,βi)是決定θi的旋轉(zhuǎn)方向的符號函數(shù),Δθi是旋轉(zhuǎn)角度的大小.

由上述定義可知,量子蟻群算法的性能受到初始值的影響.在每一次迭代中,算法將會更新螞蟻的信息素,同時要進行量子門旋轉(zhuǎn)來更新量子比特,使得算法不斷地改進最優(yōu)解.

量子蟻群算法主要步驟描述如下:

步驟1 nc為迭代次數(shù),nc←0;

對τij和Δτij進行初始化;

將m個螞蟻置于n個頂點上.

步驟2 將各螞蟻的初始出發(fā)點置于當(dāng)前解集中;

對每個螞蟻k(k=1,2,…,m)按轉(zhuǎn)移概率pkij及其它要求移至下一頂點j;

將頂點j置于當(dāng)前解集中.

步驟3 計算各螞蟻的目標函數(shù)值Zk,k=1,2,…,m;

記錄當(dāng)前的最好解.

步驟4 按更新方程修改軌跡信息素強度.

步驟5 按量子旋轉(zhuǎn)門來更新量子信息.

步驟6 對各邊?。╥,j),置Δτij←0;nc←nc+1.

步驟7 若nc小于預(yù)定的迭代次數(shù)且無退化解(即找到的都是相同解),則轉(zhuǎn)步驟2.

步驟8 輸出目前的最好解.

2 數(shù)值實驗

為驗證量子蟻群算法的有效性,采用網(wǎng)上公布的標準問題庫TSPLIB中的實例(http://www.iwr.uniheidelberg. de/groups/comopt/software/TSPLIB95/tsp/).在Windows XP下用Delphi 7.0編制程序進行了計算.各種參數(shù)的設(shè)定如下:螞蟻數(shù)目為50,α取值為1~2,β取值為1~3,ρ=0.7,量子比特初始化為即所有的路徑被選擇的概率相等,并使用三邊交換算法(3-OPT)進行鄰域優(yōu)化.

現(xiàn)介紹部分問題得到的結(jié)果.B1為本算法求得的最優(yōu)解,B2為TSP庫中公布的最優(yōu)解的值,同最好解的偏差率R=(B1-B2)/B2,表1中問題名稱的數(shù)字為結(jié)點總個數(shù),且從小到大顯示.這里給出本算法求解部分的詳細情況,其余只給出結(jié)果,如表1所示.

表1 計算結(jié)果Tab.1 Calculation results

實例1 文件名:St70,其中,結(jié)點個數(shù)N=70,B2=675,本算法求解的結(jié)果為

螞蟻回路總長B1=675,等于公布的最好解.

螞蟻回路路徑P=1 36 29 13 70 35 69 31 38 59 22 66 63 57 15 24 19 7 2 4 18 42 32 3 8 26 55 49 28 14 20 30 44 68 27 46 45 25 39 61 40 9 17 43 41 6 53 5 10 52 60 12 34 21 33 62 54 48 67 11 64 65 56 51 50 58 37 47 16 23.

實例2 文件名:Berlin52,其中,N=52,B2=7 542,本算法求解的結(jié)果為

螞蟻回路總長B1=7 542,等于公布的最好解.

螞蟻回路路徑P=1 22 31 18 3 17 21 42 7 2 30 23 20 50 29 16 46 44 34 35 36 39 40 37 38 48 24 5 15 6 4 25 12 28 27 26 47 13 14 52 11 51 33 43 10 9 8 41 19 45 32 49.

從表1中的數(shù)據(jù)可以看出,量子蟻群算法在TSP求解過程中總體效果良好,部分算例的計算結(jié)果已達到公布的最優(yōu)解,算法結(jié)果與最好解的誤差率很小,說明該算法有較好的優(yōu)化性能.

3 結(jié)束語

量子蟻群算法建立在量子的態(tài)矢量表示的基礎(chǔ)之上,將量子比特的概率幅表示應(yīng)用于人工螞蟻的位置,并利用量子邏輯門實現(xiàn)量子比特的更新操作,從而實現(xiàn)了目標的優(yōu)化求解.根據(jù)旅行商問題的特點,利用量子比特的特點結(jié)合蟻群算法,給出了量子蟻群算法的描述,通過大量的數(shù)值測試探討了算法的求解性能,從數(shù)值模擬結(jié)果來看,本文給出的量子蟻群算法可以較快、較好地找到問題的最優(yōu)解或近似最優(yōu)解,是求解TSP的一個新的可行手段.

[1] Dorigo M,Maniezzo V,Ccolorni A.The ant system:Optimization by ant colony cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B,1996,26(1):29-41.

[2] Dorigo M,Gambardella L.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Transanctions on Evolutionary Computation,1997,1(1):53-66.

[3] 馬良,項培軍.螞蟻算法在組合優(yōu)化中的應(yīng)用[J].管理科學(xué)學(xué)報,2004,4(2):32-37.

[4] 馬良,朱剛,寧愛兵.蟻群優(yōu)化算法[M].北京:科學(xué)出版社,2008.

[5] Hey T.Quantum computing:An introduction[J].Computing &Control Engineering Journal,1999,10(3):105-112.

[6] Han K H,Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problem[C]//IEEE Proceedings of the 2000Congress on Evolutionary Computation.2001:1354-1360.

[7] Han K H,Kim J H.Quantum-inspired evolutionary algorithms with a new termination criterion[J].IEEE Transactions on Evolutionary Computation,2004,8(2):156-169.

[8] Hanneke D,Home J P,Jost J D,et al.Realization of a programmable two-qubit quantum processor[J].Nature Physics,2010,6:13-16.

[9] 孫聰,趙新超.旅行商問題研究及混合粒子群算法求解[J].計算機工程與應(yīng)用,2009,45(25):38-40.

[10] 馬良.求解最小比率TSP的一個算法[J].系統(tǒng)工程,1998,16(4):62-65.

[11] 馬良,蔣馥.多目標旅行售貨員問題的螞蟻算法求解[J].系統(tǒng)工程理論方法應(yīng)用,1999,8(4):23-27.

[12] 王宇平,李英華.求解TSP的量子遺傳算法[J].計算機學(xué)報,2007,30(5):748-755.

[13] Nielsen M A,Chuang I L.量子計算和量子信息(一)[M].北京:清華大學(xué)出版社,2006.

猜你喜歡
比特量子螞蟻
2022年諾貝爾物理學(xué)獎 從量子糾纏到量子通信
決定未來的量子計算
新量子通信線路保障網(wǎng)絡(luò)安全
比特幣還能投資嗎
海峽姐妹(2017年10期)2017-12-19 12:26:20
比特幣分裂
我們會“隱身”讓螞蟻來保護自己
螞蟻
比特幣一年漲135%重回5530元
銀行家(2017年1期)2017-02-15 20:27:20
一種簡便的超聲分散法制備碳量子點及表征
螞蟻找吃的等
伊宁县| 花垣县| 霍林郭勒市| 西藏| 晋城| 祁东县| 荣成市| 西乌珠穆沁旗| 霍林郭勒市| 马边| 福清市| 县级市| 涡阳县| 那曲县| 浮山县| 永善县| 黑河市| 三门县| 文登市| 枣阳市| 卫辉市| 安义县| 长岭县| 江华| 聂拉木县| 贵州省| 防城港市| 齐河县| 兰溪市| 特克斯县| 平果县| 万荣县| 六枝特区| 舒城县| 台中县| 双牌县| 屯门区| 额济纳旗| 烟台市| 陆川县| 商丘市|