基于蟻群算法的m-團(tuán)隊(duì)定向問題研究

基于蟻群算法的m-團(tuán)隊(duì)定向問題研究

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