基于种子优化算法的救灾物资调度优化问题的研究

摘要:研究在救灾物资调度中,建立物资调度问题的数学模型,运用种子优化算法的思想求解该问题,并进行了实验计算。计算结果表明,用种子优化算法解决救灾物资调度问题,可以方便、快速地求得最优解或近似最优解。

关键词:物资调度;种子优化算法;适应度;父种

中图分类号:F244.0 文献标志码:A文章编号:1673-291X(2010)08-0252-02

1998年,我国南方发生的特大洪涝灾害,2003年的“非典”肆虐大半个中国,2006年珍珠、泰利,桑美等台风轮番席卷我国东南沿海而且重庆地区出现严重的干旱和高温,2008年的四川汶川特大地震灾害等,都给我们造成了重大的经济损失和人员伤亡,也显示出我国自然灾害应急响应能力有待提高。在此背景下,自然灾害预警、应急和灾后紧急救助已经成为我们关注、研究的重要课题。自然灾害发生以后,需要大量的救灾物资进行紧急调配,这种应急问题显著的特点就是时间的紧迫性,其时间效益高于经济效益。并且在进行物资调度的过程中要尽量做到在限定时间内救灾物资供应的同时兼顾费用问题[1]。对于应急物资的调度,许多学者进行了深入的研究,大多采用传统数学方法或传统的进化算法去求解。本文则采用种子优化算法的思想解决这种物资调度问题。种子优化算法在寻优结果和收敛速度方面明显优于基本遗传算法和粒子群优化算法,更适合进行对于实时性要求高的实际应用[2]。

一、 种子优化算法

1.算法思想

将待优化问题的问题域看作是土地,目标点所在的区域是最肥沃之地,根据目标函数值来确定该区域的肥沃程度,即越是背离最优目标值,其所代表的土地就越贫瘠,否则就越肥沃。一包种子被随机撒到土地上面,如果种子落到肥沃区域,其成长的概率和繁衍后代的机会就会很大;否则,就很可能被淘汰。经过多代繁衍,最终会有一颗植株生长在最富饶的土地上。经过算法抽象,将演化过程大大压缩,表现为在某几个强大植株附近大量涌现后代植株,如此循环往复,因此称该算法为种子优化算法(Seed Optimization Algorithm,SOA)[3]。

2.算法实现

算法中,种子个体用实值向量X={x1,x2,x3,……,xn}来表示,n的大小由问题本身决定。大量种子组成种子群体,它用sum表示,大小由初始化设定。种子被随机播撒到问题空间,其中适应度最大的几个种子称为父种,根据父种适应度的大小决定其后代的大小和分布情况。后代种子的分布以父种周边为主,父种的适应度值越大,其后代种子的数量就越多;否则,其后代种子的数量就越少,而且种子的分布更具有随机性[4]。

后代种子生成后,对所有种子的适应度再进行评价,选择适应度最优的种子作为父种候选。然后计算候选父种与同代其他父种的欧式距离是否满足设定的阀值,主要用来保证父种在空间上有较为合理的分布,避免算法过早收敛,提高算法的搜索效率和全局寻优性能.最后决定该种子是否作为本代的父种[5]。根据种子的进化方程,在生成的每个父种的传播范围内生成相应的后代种子群体。整个种子群体以此方式循环进化,直到得到理想的优化结果或一号父种(每代中的最优种子)不再变化为止[5]。

二、救灾物资调度问题的模型

本文的模型建立在以下假设条件之上:此系统为一次性消耗系统,即指当所有的货物到达应急地点后才能开始应急活动;运输过程中没有意外事件发生,即运输时间比较准确;应急物资总储备量充足,不需要额外生产和补给[6]。假设有m个物资储备点A1,A2,A3,……,Am,n个应急点B1,B2,B3,……,Bn,每个物资储备点可以提供的物资量依次为G1,G2,G3,……Gm,(Gi>0, i=l,2,……,m),各应急点所需的物资量依次为D1,D2,D3,……Dn,(Di>0,i=l,2,……,m)。记Gij(i=l,2,……,m;j=1,2,……,n)为应急点Bj,从储备点Ai实际调度的物资量。物资储备点Ai达到应急地点Bj的时间为Tij(Tij>0;i=l,2,……,m;j=1,2,……,n), 物资储备点Ai达到应急地点Bj的成本为Cij(Cij>0;i=l,2,……,m;j=1,2,……,n)。

fmin=■■xij・Tij・Cij (1)

s.t.■xijGij≤Gij(2)■xijGij=Dj(3)■Dj≤■Gi (4)T≤T0(5)xij={0,1} (6)

从m个物资储备点向n个应急点调度一种物资,使得时间小于预期T0,并且费用最低。根据题意,可建立上面的数学模型。其中,式(1)为目标函数;式(2)表示从一个储备点调度的物资数量总和不超过它的库存量;式(3)表示某个应急点调度的物资总量等于它的需求量;式(4)表示所有应急点所需物资的总量不超过所有储备库的库存量;式(5)表示调度时间不超过要求的时间;式(6)表示当该储备库被某个应急点调度的物资大于0时,xij等于1,否则等于0.

三、实例分析

2008年汶川大地震发生后,灾区房屋严重损坏,导致灾区急需大量救灾帐篷。假设计划在30小时内从储备库A1,A2,A3,向灾区应急点B1,B2分别调拨帐篷5万顶和8万顶帐篷[7]。储备库A1,A2,A3,库存帐篷数量及到灾区应急点B1,B2的时间和成本见表1,表2.

我们通过计算机模拟,得到这个问题的解x={1,1,1,1,1,0};Gij=(2,2,1,2,6,0);Tij={20,15,25,18,10,0};Cij={20,16,13,24,36,0};i={1,2,3}j={1,2}。所以,得到minT=max {xijTij}=25;minC=■■xijCij=109,fmin=■■xij・Tij・Cij=1757;适应度f=■=■。

本文针对我国长期来自然灾害经常发生、应急响应能力有待提高的现状,研究了自然灾害发生后,运用种子优化算法的思想解决救灾物资调度的优化问题。在此过程中,我们对这种要求时间最小、成本也最小的多对多物资调度问题建立了数学模型,并运用种子优化算法得到了可行解或满意解。但是,本文中我们是把这种多对对的问题进行了简化,我们的下一个研究目标是把诸如调度过程中的车辆路线的选择等方面考虑进去,以期达到这种复杂对多对多物资调度问题的时间最短、成本最低的目标[8]。

参考文献:

[1] 林浩,许维胜. 基于离散粒子群算法的应急物资调度系统研究[J].电脑知识与技术,2008,(3):1503-1511.

[2] 张晓明,王儒敬,宋良图. 一种新的进化算法:种子优化算法:模式识别与人工智能[J].2008,(5):677-681.

[3] 刘静,钟伟才,刘芳,焦李成. 组织进化数值优化算法[J].计算机学报, 2004,(2):157-167 .

[4] 徐宗本.模拟进化计算[M].//计算智能:第一册.北京:高等教育出版社,2004.

[5] Dote Y, Ovaska S J. Industrial applications of soft computing: A review. Proceedings of IEEE,2001,89(9):1243-1265

[6] Meijuan Gao,Jin Xu, Jingwen Tian,Hao Wu. Path Planning for Mobile Robot Based on Chaos Genetic Algorithm. Fourth International Conference on Natural Computation,Volume 4,2008:409-413.

[7] Gondro C.,Kinghorn BP. A simple geneticalgorithm for multiplesequence alignment. Genetics and Molecular Research,2007(6): 964-982.

[8] 张晓明,王儒敬.一种带逆反的粒子群算法[J].计算机科学,2006,33(10):156-159.