基于蟻群算法的m-團隊定向問題研究

基于蟻群算法的m-團隊定向問題研究

定向運動是一項工人運動。參與者可以通過識別和使用地圖來使用正確的地圖和指針，從起點出發(fā)，在規(guī)定的時間內(nèi)，盡可能多地訪問具有不同分數(shù)的固定點，并達到規(guī)定的結(jié)束點。超過此點的人將失去資格，并以獲得更高的分數(shù)。在獲得相同分數(shù)的情況下，總時間最短的人將獲得勝利。定向運動的目標就是在總的時限情況下,最大化獲取的總分數(shù)。因為存在時限,參賽選手必須精心設(shè)計自己的路線,選擇點標子集進行到訪,以最大化獲取分數(shù),這就是單選手定向運動。團隊定向運動是對單選手定向運動的擴展,比賽中一個團隊由多名選手組成,根據(jù)比賽規(guī)則,每名選手從相同的出發(fā)點出發(fā),在規(guī)定的時限條件下選擇點標到訪,并最終到達設(shè)定的終止點。比賽中,每個點標只能由一名隊員到訪并獲取相應(yīng)的分值。團隊比賽中需要設(shè)計每名選手的行進路線,以求取在設(shè)定條件下團隊總分最大化。定向問題與有總旅行費用限制的TSP問題類似,可用來建模許多實際問題,如總能力限制條件下車輛路徑問題、多目標售貨問題、家庭燃料配送問題等。目前對定向問題的優(yōu)化有多種方法,如啟發(fā)式方法、車輛路徑法、分枝界定法、整數(shù)規(guī)劃法、動態(tài)規(guī)劃法、人工神經(jīng)網(wǎng)絡(luò)法等。本文針對團隊定向問題,提出了子群個體協(xié)作模式,子群中個體通過訪問禁忌表交換彼此訪問點標信息,最終給出每位選手參賽路徑的蟻群優(yōu)化算法。1cij點標集記G=(V,E)為完全圖,V={1,2,…,n}為點標集,E為點標集之間的邊集,各點標之間的距離為cij(cij>0,cii=∞,i,j∈V),cij也可表示為i,j點之間其他類型旅行代價。在點標集V中,每個點標i具有相應(yīng)的分值si>0(i≠1,n)。設(shè)團隊中有m個隊員,則目標為在V中尋找m條路徑經(jīng)過點標集的分值和最大,且每個隊員通過每條路徑的時間不能超過Tmax,定義變量:則m–團隊定向問題為其中,Pk表示第k個選手越野速度,式(4)限定了每位選手不能超時,式(5)保證每處點標只能由至多一位選手到訪,式(6)、式(7)確保m條路線均從出發(fā)點出發(fā),到終止點結(jié)束。2基于控制策略的殘留信息考量蟻群算法是近年來出現(xiàn)的一種新的仿生類算法,它吸收了生物世界中螞蟻的行為特性。研究發(fā)現(xiàn),在螞蟻群找到食物時,它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻與螞蟻之間有一種非常重要的通信媒介,即它們在移動過程中所釋放的一種特有分泌物——信息素(pheromone),螞蟻可以覺察到彼此之間的信息素并影響自己的行為。當某些路徑上走過的螞蟻較少時,其信息素量也就相應(yīng)較小,且信息素隨著時間而逐漸揮發(fā),信息素強度會越來越弱,后來螞蟻選擇這些路徑的可能性就會越來越小。與之相對,當某條路徑上走過的螞蟻較多時,信息素數(shù)量就越多,以致強度增大,將吸引更多的螞蟻選擇該路徑。通過這種內(nèi)在的搜索機制,便逐漸形成了一種最佳路線。蟻群算法具有并行性、魯棒性、正反饋等特點。蟻群算法自問世以來,已在多方面表現(xiàn)出相當好的性能,如在TSP問題,二次分配問題(QAP0、多目標TSP、交通分配、著色問題、集成電路布線、網(wǎng)絡(luò)路由等)。利用蟻群算法解TSP問題時,將m只螞蟻放入到n個隨機選擇的城市中,每只螞蟻的每一步行動是,根據(jù)一定的依據(jù)選擇下一個它還沒有訪問的城市;同時在完成一步(從一個城市到達另一城市0或一個循環(huán)(完成對所有n個城市訪問0后,更新所有路徑上的殘留信息濃度。選擇下一城市的依據(jù)主要是兩點:τij(t)為t時刻連接城市i和j的路徑上殘留信息濃度,ηij為由城市i轉(zhuǎn)移到城市j的啟發(fā)信息,該啟發(fā)信息是由要解決的問題給出的,由一定算法實現(xiàn)。t時刻位于城市i的螞蟻k選擇城市j為目標城市的概率是式中,α為殘留信息的相對重要程度;β為期望值(或啟發(fā)性信息)的相對重要程度;Nik為所有可能的目標城市,即還沒有到訪的城市;P_(ij)k(t)為t時刻螞蟻k由i城市到j(luò)城市的概率。對于殘留信息素在算法中引發(fā)揮發(fā)機制進行處理,以避免信息素過渡積累。每只螞蟻完成一個循環(huán)后,相應(yīng)邊上的信息素濃度為式中,ρ為殘留信息的保留部分;1-ρ為殘留信息在t到t+n時間段內(nèi)揮發(fā)部分,ρ為小于1的常數(shù);?τkij為螞蟻k在時間段t到t+n內(nèi)的訪問過程中,在i到j(luò)的路徑上留下的殘留信息濃度。3簽到路徑迭代定向問題求解與一般TSP問題、VRP問題不同,定向問題解為點標集V的子集。求解過程是一個選擇到訪的點標集,并優(yōu)化到訪路徑的過程。在各種啟發(fā)式求解方法中,首先采用不同選擇到訪的點標集,然后利用TSP、VRP等方法優(yōu)化到訪路徑,此過程反復(fù)迭代,最終滿足條件獲取分數(shù)最高的解為最終解。m–定向問題求解需為每名參賽選手選擇行進路線,并優(yōu)化到訪順序,最終滿足約束條件的團隊總分最高者為最終解。適用于m–定向問題蟻群優(yōu)化算法偽代碼如下://終止條件是否滿足?//判斷子群中每只螞蟻是否到終點//隨機確定子群中哪只螞蟻應(yīng)前進//螞蟻確定前行,隨機前行?if(nextpointisfeasible)//下一點標滿足條件elseif(nopointisfeasible)//已無可行點標//子群中該螞蟻到達終點}//局部優(yōu)化每條路線}//在線更新信息素//最優(yōu)p個子群參與離線更新}3.1團隊合作關(guān)系m–團隊定向問題求解中需為m個參賽選手選擇不同越野路線,在蟻群算法為表示團隊中m個參賽選手之間這種關(guān)系,設(shè)計的算法中采用子蟻群的概念表示團隊之間合作關(guān)系,子蟻群的內(nèi)螞蟻的個數(shù)為m,每只螞蟻表示一名參賽選手,不同螞蟻個體間通過到訪點標禁忌表實現(xiàn)已訪問點標信息交換。蟻群子群表示m–團隊,不同子群通過信息素交換經(jīng)過路徑信息實現(xiàn)協(xié)作,控制蟻群中每只螞蟻的行進路線,實現(xiàn)優(yōu)化路線的選擇。3.2團隊定向問題P_(ij)k中的啟發(fā)性信息ηij與優(yōu)化目標直接相關(guān),它直接影響每只螞蟻的行進方向,m–團隊定向問題中,優(yōu)化目標是在滿足時限條件下團隊得分最高,在算法中ηij定義為該啟發(fā)性信息ηij定義提高了得分率高的點標的被選擇概率。3.3間數(shù)確定與隨機進線通過算法設(shè)計的優(yōu)化算法中為保證最大概率找到最優(yōu)解,算法中兩處采用隨機選擇的方式控制蟻群的行為,但隨著優(yōu)化時間或代數(shù)0的增加,逐漸降低隨機性,提高確定性,保證算法收斂。子群中各螞蟻以相同概率被選擇行進,隨著時間推進,子群中各螞蟻按順序交替行進;每只螞蟻行進中,采用以下方式選擇下一點標:p為間均勻分布的隨機數(shù),λ、ζ為螞蟻行確定與隨機控制變量。隨著時間推移,ζ→ε,在后面實例計算中ε=0.1,λ=0.7。3.4進路線局部尋優(yōu)在子群中每只螞蟻均到達終點后,采用啟發(fā)式方法對行進路線局部尋優(yōu),采用的主要優(yōu)化策略有不同路線點標交叉、同路線中單點移動、未經(jīng)過點標插入等,如果總的得分值或所需時間有改善,則以新解作為子群可行解。3.5線更新信息素濃度式在所有螞蟻均從起始點標到達終止點標,并對路線進行局部尋優(yōu)后,在線更新信息素濃度式中,ρ為0～1之間的常系數(shù);在所有子群中螞蟻從起始點標到達終止點標后,從所有子群中找出總分值最高的p個子群,利用p個子群的信息素進行離線更新式中,γ為0～1之間的常系數(shù)。4團隊定向問題求解算法為驗證提出算法的可行性和有效性,對m–團隊問題進行建模,模型中共有20個點標,其中1號點標為出發(fā)點,20號點標為終點,其余18個點標如果到訪可獲得相應(yīng)分值,不能直接到訪兩點標間距離為一非常大的數(shù)值,可直接到訪兩個點標間均有相應(yīng)的距離,在給定隊員人數(shù)和每名隊員允許最大經(jīng)過距離條件下,求解最大得分和每名隊員的行進路線。采用提出的優(yōu)化算法,對3名隊員20個點標問題的團隊定向問題進行求解,計算過程采用子群規(guī)模為50,每個子群內(nèi)有3只螞蟻協(xié)作,每只螞蟻代表1名隊員,在線更新信息素時ρ取0.7,離線更新中γ取0.5,最優(yōu)子群個數(shù)p取4。經(jīng)過優(yōu)化后,20個點標中有17個點標被選擇經(jīng)過,3個隊員的經(jīng)過路線分別為:1→6→13→16→14→10→9→12→20,1→15→7→19→5→20,1→2→18→4→3→20。5基于昆蟲群的m–團隊問題求解方法本文描述了團隊定向問題模型和目標,并針對m–團隊定向問題提出了基于蟻群算法的求解方法。算法中利用子群中螞蟻表示團隊中隊員合作,子群中螞蟻間通過禁忌表方式交換已到達訪點標,保證了團隊中隊員到訪點標的唯一性。算法中蟻群在各條可行路徑上留下的信息素影響各子群的路徑選擇行為,進而影響到訪點標集的選擇,算法中局部尋優(yōu)和個體行進路線選擇機制進行路徑優(yōu)化。仿真實驗結(jié)果證明了提出的基于蟻群算法的m–團隊問題求解方法的可行性和有效性。begin:initialize://初始化所有參數(shù)及系統(tǒng)τij=C;tabu＿pointsk=startpoint;while(notterminationcondtion){fork=1toant＿num//依次計算每個子群{while(existantnotarriveendpoints){randomselectoneantmovenext;selectnextpointsbyP_(ij)~korrandom;{calculateget＿scorekj;calculateroute＿lengthkj;addnextpointtoroute;a