基于蟻群算法的環狀燃氣管網布置優化研究

摘要

摘　要：將環狀燃氣管網布置優化問題轉換為旅行商問題，采用蟻群算法進行求解，列舉了算例。關鍵詞：環狀燃氣管網布置優化旅行商問題蟻群算法Layout Optimization of Loop Ga

摘　要：將環狀燃氣管網布置優化問題轉換為旅行商問題，采用蟻群算法進行求解，列舉了算例。

關鍵詞：環狀燃氣管網布置優化旅行商問題蟻群算法

Layout Optimization of Loop Gas Pipe Network Based on Ant Colony Algorithm

Abstract：The layout optimization problem of loop gas pipe network is converted into a traveling salesman problem，and solution is performed by ant colony algorithm．The calculation examples are enumerated．

Keywords：loop gas pipe network；layout optimization；traveling salesman problem；ant colony algorithm

在設計燃氣管網時，設計人員通常根據經驗確定布置形式，這使得管網的合理性有待探討。此外，國內外學者對枝狀管網的布置優化問題研究較多，對環狀管網的布置優化研究較少^[1-5]。本文將環狀燃氣管網布置優化問題轉換為旅行商問題(Traveling Salesman Problem，簡稱TSP)，采用蟻群算法進行求解。

1　TSP

TSP是圖論領域中著名問題之一。形象地說，TSP是指一名旅行售貨員從一座城市出發，訪問每座城市恰好一次，再回到出發城市，最終使得旅費最低。對于燃氣管網，將調壓站、調壓裝置視為TSP中的“城市(節點)”，節點之間敷設的燃氣管道造價視為“旅費”，要求從起始節點出發，訪問剩余的每個節點恰好一次，再回到起始節點，要求燃氣管道造價最低。由此可知，環狀燃氣管網的布置優化問題與TSP十分相似，因此可以將環狀燃氣管網布置優

化問題轉換為TSP。

2　蟻群算法

蟻群算法(Ant Colony Algorithm，ACA)是1991年M．Dorigo提出的一種智能算法。該算法來源于螞蟻種群的覓食行為，其本質是一個龐大的智能體系，具有很強的容錯性及并行計算能力，可與其他算法無縫銜接。

2.1　蟻群算法的數學模型

為了方便討論，設bi(t)表示t時刻位于節點i的螞蟻數量，則螞蟻總數量m的表達式為：

式中m——螞蟻總數量

n——節點總數

n個節點的集合為：

C＝{c1，c2，c3，…，cn}

式中C——n個節點的集合

c1…cn——集合C中的元素

節點i與j路徑長度的集合為：

L＝{lijúci，cjÌC}

式中L——集合C中節點i與j路徑長度的集合

lij——節點i與j路徑長度，m

xi、yi——節點i在二維坐標系(xOy)中的坐標

xi、yi——節點歹在二維坐標系(xOy)中的坐標

t時刻節點i與j路徑上殘留信息量集合G的表達式為：

G＝{tij(t)ú ci，cj，ÌC}

式中G——t時刻節點i與j路徑上殘留信息量集合

tij(t)——t時刻節點i與j路徑上的殘留信息量，在初始時刻各條路徑上殘留信息量相等

螞蟻k(1，2，3，…，m)的運動方向是根據各條路徑上的殘留信息量來確定的，t時刻螞蟻k由節點i轉移到節點j的狀態轉移概率為：

式中Pij(t)——t時刻螞蟻k由節點i轉移到節點j的狀態轉移概率

a——信息啟發式因子，表示軌跡的相對重要性

hij(t)——啟發函數

b——期望啟發式因子，表示能見度的相對重要性

A——螞蟻k下一步允許選擇的節點集合，A＝{C-B}，B表示螞蟻k已經走過的節點集合

需要注意的是，在每只螞蟻走完一步或者完成對所有n個節點的遍歷后，要對殘留信息進行更新處理，否則過多的殘留信息會淹沒啟發信息。因此，在螞蟻經過一個節點或經過所有節點完成一個循環所需的時間T后，即t+T時刻在節點i與j路徑上的殘留信息量tij(t+T)可按以下規則進行調整：

式中tij(t+T)——t+T時刻在節點i與j路徑上的殘留信息量

r——信息素揮發系數，取值范圍為[0，1)

Dtij(t)——本次循環中節點i與j路徑上的信息素增量，初始時刻為0

Dtij,k(t)——本次循環中第k只螞蟻在節點i與j路徑上的信息素增量

M．Dorigo提出了3種不同的信息素更新模型，分別為：Ant-Cycle模型、Ant-Quantity模型、Ant-Density模型，差別在于對Dtij,k(t)的求解方法不同。在求解Dtij,k(t)時，Ant-Quantity模型、Ant-Density模型采用局部信息(即螞蟻完成一步便更新當前路徑上的信息素)，而Ant-Cycle模型采用整體信息(即螞蟻完成一個循環后才更新所有路徑上的信息素)。Ant-Cycle模型更適用于求解TSP，因此本文采用Ant-Cycle模型來更新信息素。