基于蚁群算法的环状燃气管网布置优化研究_技术研究

摘要

摘　要：将环状燃气管网布置优化问题转换为旅行商问题，采用蚁群算法进行求解，列举了算例。关键词：环状燃气管网布置优化旅行商问题蚁群算法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模型来更新信息素。