災情巡視問題的蟻群兩目標優化演算法研究

2023-02-09 10:06:03 字數 5119 閱讀 7305

厙向陽(西安科技大學電腦科學與技術學院,西安,710054)

(摘要:分析目前災情巡視問題求解方法存在的缺陷,歸納出災情巡視問題兩目標優化模型。針對災情巡視問題模型特點,引入蟻群演算法和多目標優化理論,提出兩個災情巡視問題的蟻群兩目標優化演算法:

演算法1將災情巡視問題的道路網路轉化為完全圖,增加m-1個(m為巡視組數)虛擬巡視起點,將災情巡視兩目標優化問題轉化為單旅行商兩目標優化問題,然後使用蟻群演算法和多目標優化理論進行迭代求解。演算法2使用乙隻螞蟻尋找乙個子迴路,m個子迴路構成乙個災情巡視可行方案,採用罰函式法和多目標優化理論構建增廣兩目標優化評價函式,使用g組,共g×m只螞蟻共同協作來發現災情巡視問題的最優解。演算法特點:

①演算法1將災情巡視兩目標優化問題轉化為單旅行商兩目標優化問題,可以充分利用已有蟻群演算法求解單旅行商問題的研究成果;②兩個演算法引入蟻群演算法,提高了演算法效率;③兩個演算法克服目前災情巡視問題的求解方法不嚴密性缺陷;④兩目標優化演算法可以為使用者提供多個滿足約束條件的pareto組合解,擴大了使用者選擇範圍,增強了演算法的適用性。演算法測試表明:災情巡視問題的蟻群兩目標優化演算法是完全可行和有效的。

關鍵詞:災情巡視問題;蟻群演算法;多目標優化;pareto解

中圖分類號:tp393.3文獻標識碼

2023年全國大學生數學建模競賽題目b:圖1為某縣的鄉(鎮)、村公路網示意圖。今年夏天該縣遭受水災。

為考察災情、組織自救,縣領導決定,帶領有關部門負責人到全縣各鄉(鎮)、村巡視。巡視路線指從縣**所在地出發,走遍各鄉(鎮)、村,又回到縣**所在地的路線。若分三組(路)巡視,試設計總路程最短且各組盡可能均衡的巡視路線。

文獻[1]把一般網路上多組最優巡視問題轉化為賦權完全圖上的多旅行商問題,增加m-1個(m為巡視組數)虛擬巡視起點,將多旅行商問題轉化為單旅行商問題,用對換調優演算法求解最優哈密頓的近似解,然後獲得原問題多組巡視情形下的近似最優解,根據均衡原則進行適當調整獲得滿意解。這一近似演算法存在如下缺點:①將交通網轉化為賦權完全圖,求得巡視路線除巡視起點外,其它結點可能存在多次巡視;②對換調優演算法作為一種近似演算法,效率和準確性低;③以巡視總路徑長度為單優化目標,未充分顧及到巡視子路線均衡目標,總巡視路程與巡視總成本相關,各組巡視路程均衡又與救災效率或時間相關,兩者同樣重要,甚至後者更為重要。

文獻[2][3]**了多旅行商問題的性質和解的特點,並給出近似解法,得出有意義的結論。文獻[4][5][6]將智慧型演算法如神經網路、遺傳演算法、蟻群演算法引入到多旅行商問題中,提高了演算法的效率和精確性。文獻[2]~[6]提出的演算法僅僅適用於完全圖和單目標優化多旅行商問題。

文獻[7]提出了任務均分的多旅行商兩目標優化模型,然後轉化為單目標優化模型,使用遺傳演算法求解,該演算法第一次提出了多旅行商多目標優化思想,但如何將多目標優化問題轉化為單目標優化問題就成為難點,而且僅僅適用於完全圖。災情巡視問題是乙個多目標整數規劃問題,目前的多目標蟻群優化演算法主要求解連續多目標優化問題[8][9],離散多目標優化問題不能直接使用。**以下部分將歸納出災情巡視問題兩目標優化模型,結合災情巡視問題及其兩目標優化模型特點,引入蟻群演算法和多目標優化理論,提出兩個災情巡視問題的蟻群兩目標優化演算法:

(1) 將災情巡視問題的道路網路轉化為完全圖,增加m-1個(m為巡視組數)虛擬巡視起點,將災情巡視兩目標優化問題的轉化為單旅行商兩目標優化問題,然後使用蟻群演算法和多目標優化理論進行迭代求解。(2) 每乙隻螞蟻尋找乙個子迴路,m個子迴路構成乙個災情巡視問題的可行解(巡視方案),採用罰函式法和多目標優化理論構建增廣兩目標優化評價函式,使用g組,共g×m只螞蟻共同協作來求解災情巡視問題的最優解。最後通過實驗測試演算法的可行性和有效性。

有乙個推銷員,從城市出發,按照任意順序遍訪城市(共n-1個)各一次,最後返回城市。已知從城市i到j的距離為,應按怎樣的次序訪問這些城市,使得總距離最少?

引入0-1整數變數:

1)單旅行商問題優化模型如式(2.1)~式(2.7)所示:

式(2.1)——目標函式;式(2.2)——訪問城市i後必須要有乙個即將訪問的確切城市;式(2.

3)——訪問城市j前必須有乙個剛剛訪問過的確切城市;式(2.4)——避免產生子巡迴的約束條件;式(2.5)~式(2.

7)——變數的定義域。

從圖論角度來說,單旅行商問題就是尋找哈密頓圈(hamilton)。對於完全圖,哈密頓圈肯定存在,式(2.1)~式(2.

7)有最優解。對於非完全圖,不一定存在哈密頓圈,亦優化模型式(2.1)~式(2.

7)不一定有可行解。當然非完全圖可以轉換為完全圖,再尋找哈密頓圈,但這樣獲得的解可能違背式(2.2)和式(2.

3)約束條件,為非可行解。

多旅行商問題是m個人從城市出發分頭去訪問城市(共n-1個),每個城市有且僅被乙個人訪問,所有人最後都回到城市,問怎樣安排使得m個人的總訪問路線最短? 多旅行商問題優化模型歸納如式(3.1)~式(3.

7)所示

式(3.1)~式(3.7)中變數和符號意義同前。

多旅行商問題通過增加m-1個(m為旅行商數)虛擬起點可以轉化為單旅行商模型,通過尋找哈密頓圈來求解。對於完全圖,哈密頓圈肯定存在,式(3.1)~式(3.

7)有最優解。對於非完全圖,不一定存在哈密頓圈,亦優化模型(3.1)~式(3.

7)不一定有可行解。對於非完全圖可以轉換為完全圖,再尋找哈密頓圈,得到所謂的「最優解」,但這樣的「最優解」可能違背式(3.2)和式(3.

3)約束條件,為非可行解。將交通網路轉換為完全圖實際上是放鬆了式(3.2)和式(3.

3)兩個約束條件。

災情巡視問題要求巡視總成本最低,救災效率高(巡視時間短)。災情巡視問題的優化目標可概括為總巡視路徑最小化,巡視時間最小化兩個目標函式,這兩個目標函式同樣重要。巡視時間最小化可以用巡視小組中最長路徑最小化來表示。

設災情巡視問題由m個巡視小組共同完成,引入0-1整數變數:

4)表示第個巡視小組巡視第個鄉鎮後再去巡視第個鄉鎮。第個巡視小組從結點出發,經過自己的子巡迴路線最後回到起點,個巡視小組共同完成乙個完整巡視。災情巡視問題兩目標優化模型如式(5.

1)~式(5.7)所示。

其中:式(5.1)——最小化目標函式向量,第乙個分量為總的巡視距離最小化分量,第二個分量為巡視小組中最長路徑最小化分量;式(5.

2)~(5.5)——各個結點的出度、入度小於等於m,大於等於1的約束條件,這樣可以保證各個結點至少被巡視1次;式(5.6)——各個結點的出度等於自己的入度;式(5.

7)——模型中變數的取值。其餘符號意義同前。

模型(5.1)~(5.7)是針對災情巡視問題中非完全圖歸納出的兩目標優化模型,主要放鬆了約束條件,該模型對於任何非完全圖和完全圖當然存在可行解和最優解。

模型(5.1)~(5.7)不要求各巡視小組必須從同乙個點出發,可以從不同的起點出發,經過巡視,最後回到各自起點即可。

災情巡視問題模型(5.1)~(5.7)是多目標0-1整數線性規劃問題,有58(網路結點數)×58(網路結點數)×3(巡視小組數)個變數。

為了提高演算法效率,可僅僅考慮網路直接鄰接的分支變數,災情巡視模型中也有190(網路中直接鄰接的分支數)×3(巡視小組數)個變數。由此看來,災情巡視問題是乙個大規模的np難題,傳統分枝定界法、回溯法和動態規劃方法根本無法有效求解。

1.可行解的構造方案

按照災情巡視問題特點,採用兩種方案構造災情巡視問題的可行解:

(1)轉化為增廣賦權完全圖,採用單旅行商螞蟻演算法構造可行解

使用網路中結點間最短路徑演算法[11]計算交通網路圖中所有結點間的最短路徑,將交通網路圖轉化為賦權完全網路圖。對m個災情巡視小組從同乙個結點()出發的情形,則用乙個m階邊權均無窮大的完全圖去代替結點,原圖中的與結點相連的結點均與中每一結點相連,得到增廣賦權完全圖。

在演算法的初始時刻,將g只螞蟻隨機放到n個結點,同時將每乙隻螞蟻的禁忌表中第乙個元素設定為它當前所在的結點,各路徑上的資訊素為。然後每只螞蟻根據路徑上殘留的資訊素量和啟發式資訊,獨立地選擇下乙個結點。在時刻,螞蟻從結點轉移到結點的概率為

6)其中,表示螞蟻下一步允許選擇的結點集合。禁忌表記錄了螞蟻當前走過的結點集合。當完全圖中n+m-1個結點都加入到中時,螞蟻便完成了一次周遊,此時螞蟻所走過的路徑便是tsp的乙個可行解。

使用完全圖中的結點將周遊路徑截成m段,每一段即為乙個子巡迴路徑,起點和終點為,m個子巡迴路徑構成乙個可行災情巡視方案。是乙個啟發式因子,表示螞蟻從結點轉移到結點的期望程度,通常取結點到結點間距離的倒數。和分別表示資訊素和啟發式因子的相對重要程度。

(2)m個子巡迴路徑共同構成乙個巡迴方案(可行解)

每乙隻螞蟻尋找乙個子迴路,m只螞蟻尋找的m個子迴路構成乙個災情巡視方案。有g組,共g×m只螞蟻共同協作來發現災情巡視問題的最優解。

對於第()組螞蟻()分配乙個子周遊列表,記錄第組螞蟻當前已經訪問過結點。第組螞蟻從結點出發,巡視一系列結點(並非所有結點)後,返回結點便構成乙個子巡迴路徑。第組中m個子巡迴路徑構成乙個巡視方案(可行解)。

在時刻,第組螞蟻從結點轉移到結點的轉移概率為

7)其中,——第組螞蟻下一步允許巡視的結點集合。——時刻,第個巡迴子路徑中邊的資訊素。其餘符號同前。

2路徑上資訊素的更新[5][12]

當螞蟻完成一次周遊或子巡迴路徑後,各周遊路徑或子巡迴路徑上資訊素根據式(8)更新

8)其中,表示路徑上資訊素的蒸發係數,1-表示資訊素的永續性係數。表示本次迭代後,邊上的資訊素的增量。表示第只螞蟻在本次迭代中留在邊上的資訊素量。表示為

(9)其中,——大於0的常數;——第只螞蟻在本次巡視中方案中的兩目標綜合評價值。

3.多目標評價方法

評價方法是多目標優化演算法的關鍵,目前多目標優化演算法主要是按照多目標評價型別來劃分的,主要有向量評價法、pareto排序和競爭方法、權重和方法和距離方法等[1][14][15]。對於蟻群演算法求解帶約束的單目標優化問題目前是使用罰函式[16]將帶約束的優化問題轉化為無約束的優化問題。對於帶約束的多目標優化可使用多目標評價方法加罰函式進行評價。

對於災情巡視問題,罰函式為沒有被任何巡視小組巡視的結點總數乘以懲罰因子(任意大正數)。

演算法:轉化為增廣賦權完全圖的蟻群兩目標優化演算法。

輸入:交通網路距離鄰接矩陣、災情巡視小組總數m。

輸出:pareto解及其在決策空間中對應的巡迴路徑。

方法:step0.使用最短路徑演算法計算交通網路中所有結點間的最短路徑,將交通網路圖轉化為賦權完全網路圖,並用乙個m階邊權均無窮大的完全圖去代替結點,原圖中與結點相連的結點均與中每一結點相連,得到增廣賦權完全圖。

step1.設定as相關引數,包括資訊相對重要程度、啟發因子相對重要程度、資訊蒸發係數,螞蟻釋放的資訊量、蟻群數量、最大迭代次數max_gen、pareto解個數。

step2.初始化。置迭代次數,對每一條邊設定(較小的正常數),,將只螞蟻隨機放到n個結點上。確定初始的pareto解。

螞蟻 蟻群 演算法的經典簡介以及相關說明

蟻群演算法 ant colony optimization,aco 又稱螞蟻演算法,是一種用來在圖中尋找優化路徑的機率型技術。它由marco dorigo於1992年在他的博士 中引入,其靈感 於螞蟻在尋找食物過程中發現路徑的行為。為什麼小小的螞蟻能夠找到食物?他們具有智慧型麼?設想,如果我們要為螞...

群面技巧處理問題的訣竅

群面 關於群面,沒有太多的經驗,一共也就參加過兩次。可是就在這僅有的兩次群面中,我都超常發揮了自己的潛力,獲得了最後的青睞。廢話不說了,談談群面的技巧。群面的型別一般有2種,一種是給大家乙個小課題,在規定時間內合作完成,比如聯想的搭橋題,或者是根據材料做乙個presentation 另一種是給乙個情...

關於巡視工作中發現徵管方面問題的整改措施

一 關於提前徵收稅款 少徵稅款問題 一是堅持依法治稅,落實收入原則。始終堅持 依法徵稅 應收盡收 堅決不收過頭稅,堅決防止和制止越權減免稅 的組織收入原則和 周口市地方稅務局關於組織收入工作的八項禁令 加強稅收徵管,堵塞稅收漏洞,提高徵收效率,努力實現稅收應收盡收。二是嚴肅稅收紀律,保證收入質量。加...