)其中，表示揮發(fā)因子，即每輪自然衰減的信息素的比例；為本輪各邊信息素的增量；為本輪最優(yōu)解．2.1.3信息素上下界確定信息素上下限的設定是MMAS區(qū)別其他ACO算法的一大特點，對每一條邊限定其信息素的界限，防止信息素的無限增加或減少．具體設置如下：(4)其中：tv表示一條可行路徑中包含的頂點數(shù)；=，為重構概率，一般取值為0.05；表示全局最優(yōu)值，故隨著算法運行過程中不斷有新的全局最優(yōu)解的發(fā)現(xiàn)，的值也隨之動態(tài)變化．2.2基本蟻群系統(tǒng)模型蟻群系統(tǒng)（ACS）是由ThomasStutzle等人在1997年在螞蟻系統(tǒng)算法的基礎上首次提出來的．與螞蟻系統(tǒng)相比，ACS做的一些改進：修改狀態(tài)轉移，加入偽隨機策略；加入局部更新策略抑制信息素的變化；詳細步驟如下．2.2.1狀態(tài)轉移當螞蟻k在當前頂點i選擇下一個將要移動到的頂點j時，依據(jù)式式(5)給出的偽隨機比例規(guī)則進行選擇．(5)其中，表示螞蟻k已經走過的頂點集合；為期望啟發(fā)式因子，表示啟發(fā)信息對路徑選擇的重要性；是初始設定的參數(shù)；是一個隨機數(shù)；S是根據(jù)式（1）決定的隨機變量．2.2.2局部信息素更新每只螞蟻在搜索過程中，依據(jù)式(6)的局部信息素更新規(guī)則對它們所經過的邊進行信息素更新．(6)其中，參數(shù)，是信息素的初始值；一般認為，效果較好；n代表頂點總數(shù)；代表由最近鄰算法得到的路徑長度．2.2.3全局信息素更新規(guī)則所有螞蟻完成一次循環(huán)搜索后，為了加快搜索速度，依據(jù)式(7)對全局最優(yōu)螞蟻所走的路徑進行全局信息素更新．(7)(8)其中，為信息素揮發(fā)因子；為目前找到的全局最優(yōu)路徑長度．一般認為效果較好．3局部搜索技術局部搜索技術，即通過對解進行局部擾動以達到改進解的效果．現(xiàn)有的主流局部搜索技術包括變異技術、2-opt、3-opt、鄰域搜索技術等[7]．下面將以TSP為例來說明上述技術的具體步驟．3.1變異技術所謂變異技術即依次交換路徑中間隔為t的兩個節(jié)點，以達到局部擾動及改進的效果．變異技術對于智能隨機算法，例如蟻群算法、遺傳算法、粒子群算法等，可以起到提高算法穩(wěn)定性的效果。令表示一條可行路徑c，，表示路徑c的長度，則變異技術的偽代碼如下：表1變異算法偽代碼Mutation(Tour)Begin=;t=Intervel;For(i=2;i<ns-k;i++){=;If(){=;}%EndIf}%EndForEnd實驗表明：當k>3后，改進效果很小，因此一般取k≤3．該變異算法的時間復雜度為O(n)．3.2k-opt算法k-opt算法是1973年Lin、Kernighan等[5]提出的，又稱為k-交換．其中最簡單的數(shù)2-opt，即依次交換原有路徑中的兩條邊使路徑依然有效且得到改進．在TSP問題中，2-opt常被用于破除所得路徑的交叉邊．如下圖，圖2為圖1經過2-opt破除交叉邊后所得．iii+1jj+1圖1iii+1jj+1圖22-opt算法偽代碼如下：表22-opt偽代碼2-opt(Tour)BeginTour=;For(i=1;i<m-3;i++){For(j=i+2;j<m;j++){;;If(){=Tour;For(k=0;k<(j-i)/2;k++){};Tournew=;;Tour=Tournew;}%EndIf}%EndFor}3-opt的原理同2-opt相同，但是相較2-opt的不同之處在于3條邊的交換方式有多種，所以可將3-opt分為以下改變原有路徑順序和不改變原有路徑順序兩種．圖33-opt示意圖圖3中的（b）為不改變原有路徑順序的3-opt，（c）為改變原有路徑的3-opt．本質都是為破除交叉變．3.3鄰域搜索技術鄰域搜索技術是針對選擇性旅行商問題[11]而設計的局部搜索技術，通過交換解的內部和外部的元素，以達到改進解的效果．它是從解的外部改進算法的技術．具體過程如下：表3鄰域搜索偽代碼Neighborhood_Searching(Tour)BeginTour=;For(j=1;j≤n-2;j++){;;;If(){;;}EndIf}%EndIf}%End4帶有自適應局部搜索技術的蟻群算法的應用在本節(jié)中，筆者將分別對同類商品的配送收集問題（1-PDTSP）、選擇性配送收集問題（1-TSP-SELPD）以及DNA雜交測序問題的特點進行分析，將這些特點嵌入蟻群算法之中，并加入適當?shù)木植克阉骷夹g，分別設計出三種不同的蟻群優(yōu)化算法來解決這三個問題．4.1同類商品配送收集問題4.1.11-PDTSP相關研究同類商品集送一體化的旅行商問題（one-commodityPickup-and-DeliveryTravelingSalesmanProblem，1-PDTSP）是著名的TSP問題的一類新變體[12]．生產實際中的許多可以重復利用的商品的配送收集問題，都可以歸結為1-PDTSP問題（如可重復使用的托盤、包裝、工具等）[13]．因此有效解決1-PDTSP問題，將會大大提高可重復利用商品調度優(yōu)化系統(tǒng)的效率，可對生產實踐產生巨大的效益．但相比基本的TSP問題，1-PDTSP有許多特殊之處在于[14]：其一，由一個特定的城市作為倉庫，其他作為客戶的城市根據(jù)其需求類型劃分為送貨客戶和取貨客戶兩類．所謂取貨客戶則是指存有一定數(shù)量物資需要取走的客戶，送貨客戶是指需求一定數(shù)量物資的客戶；其二，在1-PDTSP問題中送貨客戶所需的物資不僅可以來自倉庫，還可以直接來自于取貨客戶，即從取貨客戶取回的物資可以直接供送貨客戶使用；其三，載貨量有限的車輛需從指定的儲備物資充足和儲存空間足夠的倉庫出發(fā)，走完所有客戶最終返回倉庫．顯然，當車輛的容量足夠大時，1-PDTSP就變成基本的TSP問題，因此該問題是一類NP難問題．目前，關于1-PDTSP問題的研究較少．主要方法可分為兩種：其一，基于傳統(tǒng)的分支限界法的改進[12]，雖然這種方法在問題規(guī)模小和最大載重約束較小的時候具有較好的求解質量效果，但隨著規(guī)模的擴大和最大載重約束的增加，這種方法將由于時間復雜度太大而不可行；其二，針對大規(guī)模問題的啟發(fā)式算法策略，如遺傳算法[15]、混合GRASP/VND[16]和VNS/SA[17]等．雖然這些方法在一定程度上提高了求解速度能夠得到一個較為可行的解，但求解質量有待提高．ACS算法的特點在于通過對信息素采取全局更新和局部更新相結合的方法使得蟻群在探索新路徑和利用已有路徑之間達到更好的平衡，從而使獲得的解具有更好的全局性．因此，根據(jù)1-PDTSP問題的特點和ACS算法特點，改進ACS算法中的信息素初始化和更新規(guī)則，加入了“最優(yōu)替換原則”、并結合有載重約束的變量鄰域搜索算法，設計了求解1-PDTSP的改進ACS算法．4.1.2具有1-PDTSP特點的ACS求解算法由于1-PDTSP問題存在以下幾個特點：第一，配送點的商品可以來自倉庫和收集點；第二，只有一個倉庫；第三，載重量的約束．上述原因導致了ACS算法在解決1-PDTSP問題的過程中經常會出現(xiàn)“停止現(xiàn)象”，即螞蟻的可行域為空但仍有點還未走完．針對上述問題，本文將結合1-PDTSP問題的特點，試圖從ACS算法的信息素初始化和全局更新兩方面來進行改進．此外，為提高解的質量和加快收斂速度，設計了有載重約束的變量鄰域搜索算法．(1)信息素的初始化基本的ACS在初始化時將每條邊的信息素設置為一常量．對于本問題的特點，這種初始化方式無法很好的解決停止現(xiàn)象．本文將根據(jù)以下兩方面來進行信息素初始化的修改．首先，從對問題的自適應角度講，將所有邊的信息素初值賦予相同的值是不合適的．故本文考慮將信息素的初值按邊的長度來加以區(qū)分．其次，通過對問題特點的分析，造成停止現(xiàn)象的主要原因是配送收集點的比例分配問題，即螞蟻所經過的路徑中配送收集點數(shù)的比例應盡量接近1:1，否則就容易造成停止現(xiàn)象．故需要對連接不同類型頂點的邊賦予較高信息素．根據(jù)以上分析結果，對信息素的初值設置作如下修改：（8）（9）其中，表示各城市客戶的需求關系(當時，為送貨客戶，否則為取貨客戶)；表示兩城市間的距離，為圖中最大邊的長度，b和a為一個給定常量．(2)停止時的信息素更新策略為了預防停止現(xiàn)象，本文設計新的信息素更新策略來更新停止時路徑上的信息素，更新規(guī)則如下：（10）其中，I表示螞蟻出現(xiàn)停止現(xiàn)象時螞蟻所走過的邊的總數(shù)，i表示該邊屬于這條停止路徑的第i條邊(如圖4)．圖4停滯時的信息素更新策略通過上述方法來衰減停止路徑上的信息素，防止其他螞蟻重蹈停止的覆轍．(3)最優(yōu)替換原則上述改進策略可以有效預防停止現(xiàn)象，但還是不能徹底解決停止現(xiàn)象．為了能夠徹底解決這種現(xiàn)象，讓每次運算都能夠得到一個滿足條件的解．提出一種基于當前最優(yōu)解的替換策略．當螞蟻走到第i步時進入停止現(xiàn)象時，采用當前最優(yōu)解的前i步替換掉這輪的解，隨后繼續(xù)進行下一步選擇（如圖5）．圖5替換策略圖這實際上是蟻群算法在處理構造解過程中出現(xiàn)的構造可行解困難的一種技巧，其理論基礎源于蟻群算法的主要核心是尋找最接近最優(yōu)解的一個解，其主要思想是局部最優(yōu)解的質量越好，其越靠近全局最優(yōu)解．由此采用上面的替換法則是符合尋找最優(yōu)解算法思想．采用解替換的方法，可以解決停止現(xiàn)象，而且通過對最差解信息素的削弱，加快了算法的收斂速度,在當前最優(yōu)解上進行重新搜索可以更有效的提高解的質量．(4)具有載重約束的變量鄰域搜索算法變量鄰域搜索算法[7](VNS)的理論基礎源于局部最優(yōu)解質量越好，其越靠近全局最優(yōu)解這一規(guī)律．我們借鑒變量鄰域搜索的思想，選取加入載重約束的2-opt和變異策略為鄰域，對上述改進的ACS所得的解進行局部改進，得到如下算法偽代碼(表4)．其中,表示1-PDTSP問題的一個解，表示從頂點到的距離．表4變鄰域搜索算法算法偽代碼LocalSearchSearchfor1-PDTSP（Tour）BeginTour=;%一條可行路徑Zog=1;%狀態(tài)變量While(Zog){Tour=2-opt(Tour);Tour=Mutation(Tour);If(Tourisnotimprove){Zog=0;}%EndIf}%EndWhileFunction2-opt(Tour)BeginTour=;For(i=1;i<m-3;i++){For(j=i+2;j<m;j++){;%計算兩種情;%況下的距離If(){=Tour;For(k=0;k<(j-i)/2;k++){;};%刪除交叉邊Tournew=;IfJudge_Capacity(Tournew)%載重約束判斷{;Tour=Tournew;}%EndIf}%EndIf}%EndFor}%EndForEndFunctionMutation(Tour)BeginTour=;t=T,%變異策略中交換的相鄰兩點的間隔For(i=2;i<ns-t;i++){Tournew=;If(TournewObvalueimprove&&Judge_Capacity)%判斷優(yōu)化與否和載重約束{Tour=Tournew;}%EndIf}%EndForEnd4.2選擇性配送收集問題4.2.11-TSP-SELPD相關研究無線傳感網絡（WSNs）是由隨機布置在監(jiān)測區(qū)域內的大量的廉價微型傳感器節(jié)點組成，通過無線通信方式形成的一個多跳的自組織的網絡系統(tǒng)，其目的是協(xié)作地感知、采集和處理網絡覆蓋區(qū)域中感知對象的信息，并發(fā)送給觀察者[18]．其在醫(yī)療、環(huán)境、監(jiān)督、家庭自動化、運輸及其他許多鄰域都體現(xiàn)出廣闊的應用前景和極高的應用價值[19]．但WSNs的數(shù)據(jù)處理和執(zhí)行力有限，一個顯著約束是受到嚴格的能量限制．移動機器人有著強大的計算能力和移動性，但其感知能力的局限性限制了其智能的發(fā)展．WSNs不僅可以為移動機器人提供對全局的實時感知能力、對環(huán)境進行連續(xù)的，大范圍的監(jiān)測，還可以作為通信和計算的媒介，提高路徑最優(yōu)的能力．因此，產生了一個新的研究課題“無線傳感器網絡和機器人”（WSRNs）[20]．在WSRNs中，由于大量廉價傳感器的隨機分布，可能出現(xiàn)某一區(qū)域傳感器分布密集．因此并不是所有傳感器都工作．只需部分傳感器工作，能達到監(jiān)視所覆蓋的區(qū)域即可．（稱那些不需工作的傳感器為“passive”節(jié)點）．由于傳感器的能量有限，當經過一定時間后，傳感器因能量耗盡而失效（稱那些失效傳感器為“delivery”節(jié)點）．此時，對于該區(qū)域的監(jiān)視會減弱，故需要對整個網絡進行修復．修復前，每個“delivery”節(jié)點和“passive”節(jié)點向觀察者匯報它們的位置，隨后，觀察者派遣一個移動機器人對整個網絡進行修復，將網絡中的“passive”節(jié)點處的傳感器收集后用以替換那些“delivery”節(jié)點處的傳感器．最后，回到觀察者．這一過程在WSRNs中被重復很多次，因此，為機器人找出一條最短路徑對WSRNs具有重要意義．RafealFalcon[21]等人將上述問題進行具體定義如下：用完全圖來描述無線傳感器網絡(WSNs)，其中表示所有傳感器節(jié)點的集合，每個節(jié)點都對應一個需求（=1表示節(jié)點i為“passive”傳感器，=-1表示節(jié)點i為“失效”傳感器）．我們定義觀察者所在觀察站為，且．為邊集，表示從傳感器i到傳感器j的距離．機器人最多能攜帶個傳感器，且離開觀察站時的初始載貨量為（），該問題的目標即找到一條可行路徑，開始并結束于觀察站．一條可行路徑中沒有重復經過某個點，且所有的“失效”傳感器被替換，整個過程中不能違反機器人的載重約束．于是Rafeal等人將其命名為“Theone-commoditytravelingsalesmanproble-mwithselectivepickupanddelivery”(1-TSP-SELPD)，本文將其翻譯為選擇性配送收集問題．在這類問題中，一條可行路徑中包含的頂點數(shù)可以確切的表示為．其中．同類商品配送收集問題（1-PDTSP）與本問題有較高的相似性．但是，由于選擇性配送收集問題的特殊性，即并不是所有的節(jié)點都需要被訪問．故4.1.1節(jié)中介紹的1-PDTSP的求解算法在該問題上效果不佳．而蟻群算法自1999年M.Dorigo提出至今，經過眾多學者的研究改進，目前其理論體系已經近乎完善，并且在解決組合優(yōu)化問題上，顯示出極好的效果．且RafealFalcon等人在首次提出該問題時即選用最大最小螞蟻系統(tǒng)來解決[21]．因此，本節(jié)通過對文獻[9]中的最大最小螞蟻系統(tǒng)進行改進，用于求解該問題．4.2.2改進策略(1)參數(shù)的分析與自適應調整策略啟發(fā)式因子是反應在路徑構造過程中，螞蟻選擇下一個節(jié)點時考慮距離相對重要性的指標．它的大小直接反應螞蟻在選擇路徑時對距離的重視程度．當值過大時，螞蟻的貪心搜索占主導地位，這樣使得螞蟻迅速得到局部最優(yōu)解．但同時也存在使整個系統(tǒng)出現(xiàn)陷入局部最優(yōu)而停滯的風險．而當取較小值時，信息素的影響占主導地位．使其搜索過程趨向于概率隨機搜索，這樣會導致整個系統(tǒng)收斂速度過慢，從而影響收斂速度和解的質量．在前期，我們希望能盡快得到一個局部最優(yōu)解，之后使整個系統(tǒng)在此解周圍不斷探索尋找全局最優(yōu)解．故前期值應較大，隨著算法進行到后期，的值應較?。疄槭瓜到y(tǒng)達到上述變化，使其隨著空間信息素分布情況自行調整．本文設計值根據(jù)ANB（平均節(jié)點分支數(shù)[10]）來自適應調整，設計改進策略如下：（11）其中，為第輪的啟發(fā)因子值，ANB(t)表示第t輪的ANB數(shù)，與分別為所能取的最大與最小值，于是式（1）變成如下：（12）(2)信息素增量的改進在MMAS中，如式（3），其的取值為．對于MMAS算法而言，如果在整個算法過程中一直使用該值，會導致信算法解的質量下降．而若使的取值為（表示全局最優(yōu)解），則會導致信息素快速集中于某些而使系統(tǒng)對于更優(yōu)解的探索變得更加困難．故本文按如下策略進行改進：（13）（14）即當本輪所得最優(yōu)值與全局最優(yōu)偏差大于5%時，取，否則．于是式（2）式（3）變?yōu)椋?1）（13）(3)適用于1-TSP-SELPD的局部搜索策略為了加速算法收斂，同時采用2-opt和鄰域搜索兩種局部搜索策略，分別從解的內部和外部兩方面進行改進．首先，運用2-opt對解的內部進行局部搜索改進．由于該問題的中機器人存在載重量的限制，2-opt算法無法直接施行．故需要在執(zhí)行2-opt的之前判斷執(zhí)行后是否會違反機器人的載重約束．表示一條可行路徑c，，表示路徑c的長度，表示節(jié)點的一個鄰域集合，它由離最近的k個不在中的“passive”節(jié)點組成，由于該問題的特殊性，只有部分“passive”節(jié)點會被包含進路徑中，本文采用有效的k鄰域搜索策略，從解的外部來對解進行改進．對于一個子路徑，當，且存在，如果，則用b替換中的，從而達到改進的效果．表5有約束的局部優(yōu)化Algorithm1ConstrainedLocalOptionalfor1-TSP-SELPDBeginTour=;For(i=1;i<m-3;i++){For(j=i+2;j<m;j++){;;If(){=Tour;For(k=0;k<(j-i)/2;k++){};Tournew=;IfJudge_Capacity(Tournew){;Tour=Tournew;}}%EndIf}%EndFor}%ConstrainedLocalSearchingFor(j=1;j≤m-2;j++){IfPassive()%judgewhetherispassivesensorornot;;;If(){%Updatewiththebetterpassivesensor%intheneighborhoodofand;;}EndIf}%EndIf}%NeighborhoodSearchingEnd4.3DNA雜交測序問題4.3.1DNA雜交測序相關研究DNA測序是生物信息學中一項既重要又基本的課題，是了解基因結構和功能的重要基礎．19世紀80年代Bains[22]等人提出的雜交測序，是解決DNA測序的一種新型方法，因其高效性得到了眾多學者的認可和推廣．雜交測序分為兩個階段：第一階段，通過生物實驗中的探針[23]來探測未知目標序列的各個子片段，我們稱各探針所組成的集合為“光譜”．第二階段，拼接第一階段所得各探針用以重構未知目標序列，對于理想光譜[24],早在1989年，有人將該問題轉化為歐拉路徑問題并提出一種精確算法可以在多項式時間復雜度內得到精確解[25]．但是，由于實驗條件等各種客觀條件的限制，導致實際情況下幾乎不存在理想“光譜”，實驗所產生的錯誤可以分為兩類：正錯誤和負錯誤[24]．正錯誤指探針的錯誤搭配造成DNA序列片段的檢測錯誤；負錯誤指雜交不充分，探針無法檢測出該序列的所有DNA片段，導致DNA片段的丟失．另外，當該序列存在相同的DNA片段時，探針只能檢測出其中的一個DNA片段，這是一種特殊的負錯誤，稱之為重復錯誤．由于各種錯誤的存在，使得該問題成為了NP-難問題[26]．目前，提高DNA雜交測序的求解精度的方法主要分為兩類：第一，通過改進生物實驗方法，以減小實驗過程中產生的錯誤；第二，設計有效的重構算法，使其對有各種錯誤的光譜依然可以得到高精度的解．由于第一類方法的低效性，以及高成本等苛刻條件，因此，設計有效的重構算法迫在眉睫．目前，主要的重構算法有精確算法和啟發(fā)式算法．精確算法有分支定界算法[27]、動態(tài)規(guī)劃[25]等；啟發(fā)式搜索方法有Tau-Scatter搜索算法[28]、遺傳算法[23]、蟻群算法[29]、貪心算法[24]等．針對該問題本節(jié)采用改進的最大最小螞蟻系統(tǒng)進行求解．4.3.2求解DNA雜交測序的最大最小螞蟻系統(tǒng)(1)問題預處理DNA雜交測序問題可以轉化為選擇性非對稱旅行商問題[27]，其解是一條通路，這就意味著所有螞蟻將固定從一部分候選起點出發(fā)開始構造路徑．但是由于蟻群算自身的特點，當算法中所有螞蟻均從同一個起點出發(fā)來構造路徑時，將無法發(fā)揮算法的最佳效果，對最優(yōu)解的尋找不利，故加入一些處理技巧．在算法進行過程中，任然構造一條回路，而在算法的每輪迭代結束之時，將回路展開成通路，確定起點和終點，這樣就可以避免螞蟻系統(tǒng)從固定起點出發(fā)對算法性能的影響．普通旅行商問題，即求解最短哈密爾頓回路問題．而SBH則希望所得路徑的相鄰堿基片段之間的重合度越大越好(依然是哈密爾頓回路問題)，故其目標為所得路徑邊權值之和最大化．將上述過程抽象為函數(shù)ProbelmProcessing()．(2)基本DNA雜交測序的狀態(tài)轉移規(guī)則由于DNA雜交測序問題的規(guī)模普遍較大，MMAS的狀態(tài)轉移規(guī)則對于大規(guī)模的問題將出現(xiàn)收斂較慢的現(xiàn)象．故本文采用ACS的偽隨機策略來改進MMAS的狀態(tài)轉移． （14） （15）得到新的狀態(tài)轉移函數(shù)StateTransation()．對全局更新策略進行修改，同4.2.2節(jié)的信息素的增量改進．得到改進的全局更新函數(shù)GlobalRefresh()．(3)局部搜索技術根據(jù)局部最優(yōu)解質量越好，其越靠近全局最優(yōu)解這一定律，借鑒變量領域搜索的思想，采用變異策略，即依次順序交換解中間隔為T的兩個元素，若交換后解的目標有所改進，則交換，否則不交換．具體過程如下：令Tour為所得堿基序列，其中為一個堿基片段，表示以為前驅，為后繼的重合度．表6局部搜索算法偽代碼LocalSearch(Tour)BeginTour=;Zog=1;%用以標記變異策略對結果是否有改進While(Zog){Tour=Mutation(Tour);If(Tourisnotimprove){Zog=0;}%EndIf}%EndWhileMutation(Tour)BeginTour=;t=T;%變異策略中交換的相鄰兩點的間隔For(i=2;i<ns-t;i++){Tournew=;If(TournewObjectivevalueimprove){Tour=Tournew;}%EndIf}%EndForEnd(4)問題后處理最后，在算法得到全局最優(yōu)解之后，判斷其所得回路對應的DNA序列長度是否違反約束條件，若違反，對所得DNA序列進行后處理．隨后，將所得滿足長度約束的序列按目標值最大展開．后處理，即對所得DNA序列中的堿基片段進行刪減并將回路展開成通路的過程，在滿足長度約束的同時保持目標最大化．后處理原則：定義Tour為所得堿基序列，其中為一個堿基片段，表示以為前驅，為后繼的重合度．我們?yōu)槊總€賦予一個消去值，依次刪去值最小的堿基片段，直到滿足長度約束．用函數(shù)PostProcessing()來描述上述過程．(5)算法步驟最后，我們得到如下的求解DNA雜交測序的改進最大最小螞蟻系統(tǒng)的偽代碼如下：表7求解DNA雜交測序的改進最大最小螞蟻系統(tǒng)ImproveMMASForSBHBegainInput:probleminstanceInitializaParamenter()；%初始化算法的參數(shù)ProbelmProcessing()；%問題的預處理While(termination){For(step=1;step<=n;step++){For(ant=1;ant<=m;ant++){P=CaculateShiftProb(step,ant);%計算轉移概率StateTransation(P,ant);%狀態(tài)轉移}%EndFor}%EndForTour=LocalSearch(Tour);%基于變量領域的局部搜索技術CaculateObjectiveValue(Tour);%GlobleRefresh(BestTour,);%全局更新并限制信息素上下界termination=CaculateTermination();%}%EndWhileBestTour=PostProcessing(BestTour);Output:instancesolution5實驗結果與分析本節(jié)將對第4節(jié)中的三種蟻群算法分別進行實驗驗證．計算機配置為：WindowsXP操作系統(tǒng)下，3.4GHz的處理器、4GB內存．實驗軟件為Matlab2010b．5.11-PDTSP實驗結果與分析(1)數(shù)據(jù)集及比較算法為了驗證本文設計的改進蟻群系統(tǒng)(以下均用IACS表示)在求解1-PDTSP問題上的有效性，我們通過14個范例[12]來進行比較實驗(見表8)．其中，n表示圖中頂點數(shù)(規(guī)模)，Q是最大載重量．基本參數(shù)設置：=1，=2，=0.1，，b=5，a=0.1，螞蟻數(shù)量為30，最大迭代次數(shù)為100次．目前求解1-PDTSP效果最好的算法是文獻[17]中的算法，一個特殊的變量鄰域搜索算法（以下均用GVNS表示），因此我們用GVNS與IACS進行比較，結果見表8．(2)實驗結果表8中第1列是實例及目前最優(yōu)解，n是問題規(guī)模，Q是最大載重量；第2列是兩種比較算法．從表2可以得出，對于這14個范例，本文算法的各項指標都要優(yōu)于文獻[17]中算法，尤其在最好解和平均值上，本文算法要顯著優(yōu)于文獻[17]中算法，并且在多個案例中的最好解超過了目前最優(yōu)解，由此可見本文設計的有載重約束的蟻群算法在求解質量和穩(wěn)定性上有好的效果．表814個范例、最大載重為40的比較結果范例(n/Q)(目前最優(yōu)解)比較算法最好解最差解平均值偏差范例(n/Q)(目前最優(yōu)解)比較算法最好解最差解平均值偏差n100q40AGVNS7938793879380n200q40CGVNS1083310833108330IACS7896.007896.007896.000.00IACS10756.0010855.0010797.3339.95n100q40BGVNS8124813581276.32n200q40DGVNS11533116921159866.36IACS8083.008154.008087.7317.71IACS11471.0011812.0011658.9370.04n100q40CGVNS8441844184410n200q40EGVNS110421120011108.9591.21IACS8404.008417.008405.734.42IACS10979.0011196.0011066.9387.89n100q40DGVNS826483048293.911.24n300q40AGVNS134291366813486.75121.34IACS8224.008314.008280.4729.52IACS13428.0013786.0013555.8083.36n100q40EGVNS7960796079600n300q40BGVNS135631376113615.7102.67IACS7910.008021.007917.4027.69IACS13519.0013771.0013646.8068.38n200q40AGVNS110391117911055.6580.46n300q40CGVNS132631358013310112.2IACS10983.0011168.0011045.0061.30IACS13192.0013550.0013362.2796.81n200q40BGVNS111781129011213.4569.20n300q40DGVNS140081443114177.95131.69IACS11096.0011340.0011233.2063.62IACS13998.0014328.0014176.20110.435.21-TSP-SELPD實驗結果與分析(1)數(shù)據(jù)集及比較算法為證實該算法的有效性，筆者通過計算10個范例進行效果驗證．所以例子均來自于指定網站[30]．對于每個例子中，n表示圖中頂點數(shù)，其中觀察站坐標為（0,0），其余n-1個坐標隨機產生于[-500,500]2的矩形區(qū)域．且“delivery”頂點數(shù)與“passive”頂點數(shù)比例為嚴格的1：3．對于機器人的最大載重量Q，我們設置為兩個值：．當機器人從觀察站出發(fā)，我們考慮兩種情況，即空載出發(fā)和滿載出發(fā)，定義，，，，最大迭代次數(shù)為200次．(2)實驗結果在實驗中，我們測試以空載和滿載出發(fā)的兩種情況，比較基本最大最小螞蟻（MMAS）和4.2節(jié)改進的最大最小螞蟻（IMMAS+CLO），使它們分別在10個例子上同時計算30次，并考慮兩種情況的最大載重量，結果見表9：從表9可以發(fā)現(xiàn)，對于這10個例子的兩種最大載重量，IMMAS+CLO的各項指標都要優(yōu)于MMAS，尤其在最小值和平均值上，IMMAS+CLO要顯著優(yōu)于MMAS，由此可發(fā)現(xiàn)局部本文的改進策略在提高算法的穩(wěn)定性和解的質量上有顯著效果．表9比較算法實驗結果實例(n/Q)比較算法最好解最差解平均值偏差實例(n/Q)比較算法最好解最差解平均值偏差n20q1A(20/1)MMAS2694.002900.142775.6853.50n40q5A(40/5)MMAS3067.263200.603083.5135.67IMMAS+CLO2579.592579.592579.590.00IMMAS+CLO2942.333047.772972.1816.94n20q3A(20/3)MMAS2466.382701.492545.8056.67n50q3A(50/3)MMAS3953.824377.784145.7392.93IMMAS+CLO2214.882326.582220.4724.34IMMAS+CLO3439.233450.933440.973.13n30q2A(30/2)MMAS3283.123579.183476.32101.27n50q6A(50/6)MMAS3928.784428.214232.5482.55IMMAS+CLO3150.313194.633153.028.75IMMAS+CLO3612.873724.903675.9832.01n30q4A(30/4)MMAS2927.233286.073165.7264.83n60q4A(60/4)MMAS3696.784073.083855.6082.00IMMAS+CLO2786.532802.152795.127.77IMMAS+CLO3443.223547.253482.6621.23n40q3A(40/3)MMAS3568.384033.673837.96118.98n60q8A(60/8)MMAS4100.244344.084191.1162.59IMMAS+CLO3141.813231.433158.2422.12IMMAS+CLO3662.603834.523708.6830.885.3DNA雜交測序實驗結果與分析(1)數(shù)據(jù)集及比較算法由于DNA雜交測序問題目標的轉換，故修改狀態(tài)轉移中的啟發(fā)式因子=．經試驗表明，局部搜索中的交換點之間的間隔T=2時，對解的改進效果最好．數(shù)據(jù)集及比較算法為了驗證本文設計的蟻群算法的有效性，我們通過40個來自J.Blazewicz的主頁[31]的范例進行試驗對比,所有范例均來自實際人類的DNA片段．這40個范例的原始DNA序列長度均為600，且包含3-17個不等的重復錯誤，不包含正負錯誤．目前解決該批數(shù)據(jù)集最好的算法是文獻[23]中的算法，因此我們用文獻[23]中的改進混合遺傳算法(Revised-Hybrid-GA)以及文獻[28]中的禁忌分散搜索算法(Tau-and-scattersearch)與本文設計的新型蟻群系統(tǒng)(Novel-ACS)進行比較，每個案例將被兩種算法分別計算10次．(2)實驗結果實驗結果見表10，其中第1行和第2行是對該所有案例重復執(zhí)行10次，所得最佳結果的平均堿基利用率和平均相似度．相似度計算方法來自根據(jù)文獻[32]；第3行是本算法對該案例重復執(zhí)行10次相似度達到100%的案例個數(shù).從表10的結果來看，對于這40個范例，新型蟻群系統(tǒng)在平均相似度和達到最優(yōu)解的案例個數(shù)上都要明顯優(yōu)于其他兩種算法。而在平均利用率上，文獻[23]的取值達到最佳．表10算法比較結果Tau-and-scattersearchRevised-Hybrid-GANovel-ACSUsageofoligonucleotides(%)99.8410099.75Similarity(%)88.4390.7999.02No.ofoptimalsolutions14/4017/4023/40結束語通過對蟻群算法結合局部搜索技術的研究，對其原理和本質進行分析，然后將帶有局部搜索技術的蟻群算法應用于實際問題．首先，分別對同類商品的配送收集問題（1-PDTSP）、選擇性配送收集問題（1-TSP-SELPD）以及DNA雜交測序問題的特點進行分析，將這些問題的特點嵌入蟻群算法之中，并加入適當?shù)木植克阉骷夹g．實驗結果表明，對于DNA雜交測序問題和選擇行配送收集問題，本文設計的算法都具有非常好的效果，無論從解得精度以及穩(wěn)定性上．并且都對目前最優(yōu)的算法有所超越．但對于同類商品的配送收集問題，本文設計的算法并未能超越目前最優(yōu)算法，原因在于該算法已幾乎得到該問題的最優(yōu)解，但是本文所設計的算法在解決該問題時也都與當前最優(yōu)算法十分接近，且部分案例已超過．尤其在時間復雜度方面有很好的超越．本次研究的帶有局部搜索技術的蟻群算法在這三個問題上都達到了很好的效果，對于今后人們運用蟻群算法解決類似組合優(yōu)化問題將有重大意義．參考文獻M.Dortgo，V.Maniezzo，A.Colorni．Antsystem：OptimizationbyacolonycooperatingAgents[J]．IEEETrans．onSystems，Man，andCyberneticsPartB：Cybernetics，1996，26(1)：29-41．B.Yu，Z.-Z.Yang，Anantcolonyoptimizationmodel：Theperiodvehicleroutingproblemwithtimewindows[J]．TransportationResearchPartE，2011，47：166-181．PintoPC，N.ageleA，DejoriM，etal.UsingalocaldiscoveryantalgorithmforBayesiannetworkstructurelearning[J]．IEEETransEvolComput，2009，13(4)：767-779．WangZhangqi，ZhuXiaoguang，HanQingyao．MobileRobotPathPlanningbasedonParameterOptimizationAntColonyAlgorithm[J]．ProcediaEngineering，2011，15：2738-2741．LinS，KernighanB.W．Aneffectiveheuristicalgorithmforthetravellingsalesmanproblem[J]．OperationsResearch，1973，21：498–516．MouLian-Ming,DaiXi-Li,“Anovelantcolonysystemforsolvingtheone-commoditytravelingsalesmanproblemwithselectivepickupanddelivery.”,NaturalComputation(ICNC),2012，32：1096–1101．NenadMladenovic′,DraganUro?evic′,Sa?¨dHanafi,AleksandarIlic′.Ageneralvariableneighborhoodsearchfortheone-commoditypickup-and-deliverytravellingsalesmanproblem[J].EuropeanJournalofOperationalResearch,2012，220：270-285．ThomasStutzle，Manuellopez-ibanez，etal．Aconclseoverviewofapplicationsofantcolonyoptimization[J]．WileyEncyclopediaofOperationsresearchandManagementScience，2010：1-16．T.StutzleandH.Hoos.MAX-MINAntSysterm[J].FutureGenerationComputerSystems，2000，09：889-914．MarcoDorigo,LucaMariaGambardella.AntColonySystem:ACooperativeLearningApproachtotheTravelingSalesmanProblem[J].IEEETRANSACTIONSONEVOLUTIONARYCOMPUTATION,1997，01：53-66．BlazewiczJ，F(xiàn)ormanowiczP，KasprzakM，eta1．DNAsequencingwithpositiveandnegativeerrors[J]．1999，6：113-123．Hernández-Pérez,H.,&SalazarGonzález,J.J.Abranch-and-cutalgorithmforatravelingsalesmanproblemwithpickupanddelivery[J].DiscreteAppliedMathematics,2004，145：126–139．Hernández-Pérez,H,&SalazarGonzález,J.J.Heuristicsfortheone-commoditypickup-and-deliverytravelingsalesmanproblem.TransportationScience，2004，38：245–255．Hip′olitoHern′ez-P′erez，Juan-Jos′eSalazar-Gonz′alez.TheOne-commodityPickup-and-DeliveryTravelingSalesmanProblem:InequalitiesandAlgorithms，2007，07：5-25．FanggengZhao，SujianLiatel.GeneticAlgorithmfortheone-commoditypickup-and-deliverytravelingsalesmanproblem[J].Computers&IndustrialEngineering，2009，56：1642-1648．H.RODRIGUEZ-MARTIN,I.ANDSALAZAR-GONZALEZ,J-J.AhybridGRASP/VNDheuristicfortheone-commoditypickup-and-deliverytravelingsalesmanproblem[J].Computers&OperationsResearch，2008，36(05)：1639-1645．NenadMladenovic,DraganUro?evic,Sa?dHanafi,AleksandarIlic.Ageneralvariableneighborhoodsearchfortheone-commoditypickup-and-deliverytravellingsalesmanproblem[J].EuropeanJournalofOperationalResearch，2012，220：270-285．劉幀，王祁，丁明理．基于多目標群決策協(xié)調技術的WSN移動節(jié)點導航方法[J]．機器人，2009，31（4）：335-341．薛晗，陶溢，馬宏緒．基于無線傳感器網絡的未知環(huán)境下移動機器人實時路徑規(guī)劃[J]．計算機應用研究，2008，25（7）：2029-2032．袁慶丹，王宇華．應用無線傳感器網絡實現(xiàn)移動機器人的節(jié)點定位[J]．佛山科學技術學院學報，2010,28（6）：47-50．RafaelFalcon，XuLi，AmiyaNayakandIvanStojmenovic．Theone-CommodityTravelingSalesmanProblemwithSelectivePickupandDelivery：anAntColonyApproach[C]．Evolutionar