数学执本与率用
改进蚁群算法在推广运输问题中的应用
刘期陈欣
(武汉轻工大学数学与计算机学院湖北式汉430000)
算法分析
摘要：传统的运输同题是管理运等季的一个研究重点问题。本丈针对现实中粮食收购点向根食存储仓运输的问题，为提高效群算法的效率,提出一种由两边向中间提索的策略，即在根食收购点和粮食存储仓分别投放双群,任意两竭蚁相避，则对应妈双完成一次路径披索。达样利用两组竭蚁的并行性，可以减少算法运行的时间成本，并设计对应的效群算法。伤真结累表明，该算法能有效求解问题的最优解。
关键词：蚁群算法运输同题大规模中图分类号：TP301.6
文献标识码:A
运输问题是一类应用广泛的现实问题。康特洛维奇和希契科克对于该问题进人了深人的研究，故而运输问题文称为“康一希问题”，对于运输间题，最经典的数学模型如下；设某种物资有m个产地A，其产量分别为a,i=1,2，...，m,有n个销地B,其销量分别为b,j=1， 2...,n.已知由产地A到销地B运输单位物资的运价为c..现在要确定总运费最小的运输方案。本文主要考虑现实中粮食收购点向粮食存储仓运输的问题。
1推广运输问题及其数学模型
用决策变量x,表示产地A到销地B的运量，对应的数学模型可以归结为如下：
minz: st.
Cx X=n X,=m
x≥0
由上可见，运输问题可以归结为一个线性规划问题。当然可以用经典的单纯形法求解，但由于其本身的特性，一般利用表上作业法，从而更简单更有效的解决。
本文针对现实中粮食收购点向粮食存储仓运输的问题，由于间题本身的特殊性，即没有产销的约束，所有的粮食都可以被收购。同时，不同的粮食存储仓收购的价格不一样，与粮食收购点的路程不样会导致运输成本不一样。设S=s，...5_是所有粮食收购点的集合,D={d,，...,d,I是所有粮食存储仓的集合。S,DCV,其中V是所有的节点结合。G=(SUD，Q)是一个路径的网络，QCE是所有链接S,D两个集合的所有可行路径，Vol是S到D的运输量，VC是对应的可变成本，对应的数学模型为：
,a,
Ifimieixa
Vor_S, +Vol, Vol, =0
s
Vol, Va,=j=
0--s- -0 M ×B, (Fol, + Vol,) ≥0 Fol,,Fol, ≥0
33A
B, (0,1)
fA
j = D fA
其中Vol.表示从节点i到节点的运输量。B.是一个0,1变量，用收稿日期：2016-09-18
文章编号：1007-9416(2016)11-0135-01
来表示从节点到节点的边是否被选取，E表示网络中的所有节点， T表示既不是起点也不是终点的节点集合，约束条件主要是对于每一个节点面言，必须是进出平衡的。而最短路进问题随着路径的增多，起计量指数增加。为了求解这个优化问题，引入智能算法一蚁群
算法来解决。 2蚊群算法
蚊群算法是一种基于蚂蚊在寻觅食物的过程中对于路径选择优化面提出的一种群智能算法，最初主要对于解决TSP问题。基本蚊群算法寻优机制包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调鉴自身结构，路径上经过的蚂蚊越多，信息量越大，则该路径越容易被选择；时间越长，信息量越小，在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。
b(t)表示t时刻位于元素的蚂蚁数目；,(t)为t时刻路径(i,j)上的信息量，N表示TSP的规模，d表示相邻两个城市之间的距离m为蚁群中蚂蚊的总数目，则m=E(b(t)i=1,2,,n)p*(t)表示在t时刻蚂蚊飞由元素(城市)转移到元素(城市)的状态转移概率；
在初始时刻各条路径上信息量，并设t,(0)=const，蚂蚊k(k=1， 2，，m)在运动过程中，根据各条路径上的信息量决定其转移方向。这里用tabu,(k=1,2，,m)来记录蚂蚊k当前所走过的城市，集合随着tabu,进化过程作动态调整。在搜索过程中，蚂数根据各条路径上的信息量及路径的启发信息来计算状态转移概率。
[3,(r)[,(r) / ([, ()[, (r)) p,
jE allowed je allowed
Aowed=C-tabu,表示蚂数k下一步允许选择的城市，α为信息启发式因子；6为期望启发式因子，其值越大，则该状态转移概率越接近于贪心规则，启发函数"(t)=1/d，显然，该启发函数表示蚂蚊从元素(城市)转移到元素(城市)的期望程度。
为了避免残留信息素过多引起残留信息淹没启发信息，在每只购蚊走完一步或者完成对所有Ⅱ个城市的通历后，要对残留信息进行更新。由此，t十n时刻在路径(i,j)上的信息量可按如下规则进行调整：
T,(t +n) = (1p)r (r)+r (r) f,() =Z(r,*(r)[k = 1,2, *-,m)
式中，0表示信息素挥发系数，则1-β表示信息素残留因子，为了防止信息的无限积累，P的取值范围为：[0,1)△T（t)表示本次循环中路径(i,j)上的信息素增量，初始时刻△,(0)=0,△t,(t)表示第k只蚂蚁在本次循环留在路径(i,)上的信息量。
·..下转第137页
作者简介：刘溯(1979一),男,湖北当阳人,颈士,现就职于式汉轻工大学数计学院,制教投,研究方向：智能计算。
135
方方数据