ComputerEngineeringandApplications计算机工程与应用2007,43(30)
1 引言
2006年,珍珠、泰利等台风轮番席卷我国东南沿海,重庆
地区出现罕见的高温和干旱;2007年年初,一辆由乌鲁木齐开
往阿克苏的客运列车被大风掀翻,致3人死亡数10人受伤。诸
如此类的突发事件带来了巨大损失,而应急管理[1]的一个任务
就是在突发事件发生以后,尽快从应急服务点把救援物资运至
现场展开救援活动,因此应急设施的选定对应急管理的服务质
量有很大的影响。应急设施的选址问题[2,3]实际上是点覆盖问
题,所以是NP-hard的,用普通方法解决起来有难度。最常用的
两个衡量选址是否得当的标准是应急时间和应急成本[1]。
模拟退火算法(SimulatedAnnealing,SA)是由 Kirkpatrick
于1983年提出的一种随机优化算法[4],用固体物质的降温退火
过程来模拟一般组合优化问题的求解,直观简单,便于实现,适
用范围广,是一种有效的全局优化方法。近年来,模拟退火算法
在优化领域得到广泛深入的研究和应用[5-7],在求多目标优化问
题的Pareto最优解中,也得到很好的结果[8,9]。
2 问题的数学模型
给定一些应急点(事发点)和待选的应急服务点(出救点),
出救点到应急点的时间称为应急时间,多目标应急设施选址问
题为:如何以最低的成本设置一些出救点,使得突发事件发生
时,可以及时从出救点运送物资前往应急地点?通常,该问题有
两个目标,一个是设置出救点的成本最低;另一个是最长的应
急时间达到最小。
设 S={S1,S2,⋯,Sm}为待选的应急服务设施点组成的集合,
E={E1,E2,⋯,En}为应急地点组成的集合。定义矩阵 T1=(tij)m×n
和向量 T2=(tj)n×1、C=(ci)m×1,其中,tij为从待选的应急服务设施
点 Si到达应急点 Ej所需要的最短时间,tj为应急地点 Ej要求
的服务时间限期[1,9],ci为设置Si为应急服务设施点的费用。
由上述的T1和 T2,可以定义矩阵 A=(aij)m×n,其中当 aij>tj
时,aij=0;否则,aij=1[1]。
则多目标应急设施选址问题的模型如下:
minf1(X)=
m
i=1
!cixi
minf2(X)=max
i,j
{xitij} (1)
.
m
i=1
!aijxi≥1j=1,⋯,n
xi∈{0,1}i=1,2,⋯,m
模型(1)的解可用一个长度为 m的字符串 X=x1x2⋯xm表
示,其中,xj(j=1,⋯,m)取 0或 1,代表第 j个待选点是否被确
定为应急服务设施点。
多目标应急设施选址问题的模拟退火算法
韩 强
HANQiang
山东财政学院 工商管理学院,济南 250014
SchoolofBusinessManagement,ShandongUniversityofFinance,Ji’nan250014,China
E-mail:hanqiang18@
HAN anealing algorithm formulti-objectemergency location and
Applications,2007,43(30):182-183.
Abstract:Consideringthecostandemergencytimeinlocatingemergencyestablishment,mathematicalmodelofmulti-object
forthisproblem isdesignedinthechoiceofinitialsolution,thecontrolof
temperatureparameter, numericalexampledemonstratesthe
efficiencyofthisalgorithm.
Keywords:multipleobjects;emergencylocation;simulatedannealing;punishmentfunction
摘 要:考虑应急设施选址时的成本和应急时间因素,给出了多目标应急设施选址问题的模型,通过设置罚函数将该多约束问题
转化成易于计算机求解的简单约束模型,进而在初始解的选取、温度参数的控制、可行解的迭代策略和算法终止条件等方面为之
设计了模拟退火算法,并通过仿真证明了该算法的有效性。
关键词:多目标;应急设施选址;模拟退火;罚函数
文章编号:1002-8331(2007)30-0182-02 文献标识码:A 中图分类号:
◎工程与应用◎
基金项目:国家自然科学基金()。
作者简介:韩强(1980-),男,博士,副教授,主要研究方向:系统优化。
182
2007,43(30)
(下转216页)
目标
权重
最
优
解
w1
w2
x1
x2
x3
x4
1
1
1
1
0
2
1
0
0
1
3
1
0
0
1
4
0
0
1
1
5
1
1
1
0
仿真次数
最优综合
目标值
表1 仿真结果
模型(1)是一个多约束优化问题,直接对其进行求解比较
复杂,下面利用罚函数法对该模型进行转化。罚函数法[10]是一
类常用的约束条件处理技术,在模拟退火算法中处理不等式约
束很有效。
令 gj(X)=1-
m
i=1
!aijxi,j=1,2,⋯,n,选取罚函数为 p(X)=M
n
j=1
!max{gj(X),0},其中,M为罚因子。在求解过程中,可以通过
罚函数的函数值大小来体现解对模型(1)约束条件的满足程度,
罚函数的值越大,表明解的可行性越差,反之则表明该解可行
性较好,当 p(X)=0时就说明该解是真正的可行解。如果罚因
子 M设置的大小适当,模型(1)就可以转化为如下约束简单的
多目标问题:
minf1(X)=
m
i=1
!cixi
minf2(X)=max
i,j
{xitij} (2)
minp(X)
∈{0,1}i=1,2,⋯,m
当 X满足模型(1)的约束时,gj(X)≤0(j=1,2,⋯,n),则罚
函数 p(X)=0,即模型(2)的第三个目标已可以忽略,说明模型
(1)和(2)在可行域中具有相同的最优解和最优值;当 X不满
足(1)的约束时,则必存在 j∈{1,2,⋯,n},使得 gj(X)>0,此时
充分大的罚因子 M使得罚函数 p(X)变得非常大从而不能成
为最优点,因此优化过程可以继续。采用这种形式的罚函数计
算量最小,便于计算机实现。
3 模拟退火算法
针对多目标应急设施选址问题,模拟退火算法的设计将在
初始解的选取、温度参数的控制、可行解的迭代策略和算法终
止条件4个方面展开。
初始解的选取
随机产生 L个初始解和两个权值 w1、w2(w1+w2=1,w1≥0,
w2≥0),定义初始解对应的综合目标为 f(X)=w1f1(X)+w2f2(X)+
p(X),设 Fmax和 Fmin分别为 L个初始解综合目标的最大值和最
小值。
温度参数的控制
温度参数的控制包括初始温度的选取和温度下降策略。
由于模拟退火算法在降温过程中将不断产生更新的最优
解,所以为了提供充足的优化空间,就必须设置合理的初始温
度。如果初始温度太低,就容易落入局部最优解的陷阱而无法
跳出;初始温度太高又容易产生冗余的迭代,因此本文利用文
献[8]中的方法确定初始温度 t0为:t0=(Fmin-Fmax)/lnP0,其中,P0
为初始接受概率。
温度下降采用 Lundy和 Mees方法[11]:tk+1=tk/(1+!tk),其中
!=(t0-tf)/Kt0tf,tf为一给定的较小正整数,K为温度下降的最大
步数。
解的迭代策略
解的迭代策略包括邻域的确定和邻域内解的迭代方法。本
文所讨论问题的可行解是长度为 m的 0-1字符串,所以把可
行解 X0的邻域取为 X0的 m位分别发生 0-1转换产生的解组
成的集合,则任意可行解X邻居的个数为|N(X)|=m。在迭代过
程中,从当前解的邻域内随机产生新的可行解,且产生概率服
从均匀分布,即
GXX′=
1
|N(X)|
,X′∈N(X)
0, otherwis
%
e
且采用非时齐算法。
终止条件
为了让本文的模拟退火算法具有自适应性,同时设计两个
算法的出口,只要满足其中一个就可以退出。
(1)迭代总步数控制法:设定总的迭代步数 K,当迭代步数
超过K时,算法可以停止;
(2)基于不改进规则的控制法:如果当前最优解在连续 Q
步降温期间均没有被更新,则认为已收敛到最优解,算法停止。
总结前面的设置,下面给出多目标应急设施选址问题的模
拟退火算法:
(1)随机产生 L个初始解 X1,X2,⋯,XL和权值 w1、w2(w1+
w2=1,w1≥0,w2≥0),,分别计算 f(Xi),确定初始温度,确定出最
优解X*,令其为当前解X,令k=0;
(2)由当前解 X产生新解 X′,并计算它对应的目标值,令
k=k+1;
(3)产生0和1之间的随机数random(0,1),若exp[(f(X)-
f(X′)/tk]>random(0,1)或 f(X′)≤f(X),则用 X′代替 X*成为新
的当前解;若 f(X′)<f(X),则用 X′代替 X*成为新的当前最优
解;否则不变,返回步骤(2);
(4)若当前最优解已经在连续 Q步降温期间均未改变,则
输出当前最优解,算法停止;否则,转步骤(6);
(5)若 k=K,则输出当前最优解,算法停止;否则,降低温
度:tk+1=tk/(1+!tk),返回步骤(2)。
4 算例
假设应急地点为 E={E1,E2,E3,E4,E5,E6},备选的出救点集
合为
S={S1,S2,S3,S4},C={5,2,4,8},T1={6,7,7,5,6,7}
T2=
5 5 9 9 13 8
116 6 5 8 9
4 6 910 7 5
7 8 4 2 5
&
’
’
’
’
’
’
’
’
’’
(
)
*
*
*
*
*
*
*
*
**
+5
利用前面设计的模拟退火算法,取 P0=,K=1000,tf=10,
Q=10,M=1000,L=4,所得多目标 Pareto最优解的 5次仿真结
果如表1所示。
以上仿真结果每次运算时间均少于 ,表明该模拟退
火算法是求解多目标应急设施选址问题的有效算法。
(收稿日期:2007年5月)
韩 强:多目标应急设施选址问题的模拟退火算法 183
ComputerEngineeringandApplications计算机工程与应用2007,43(30)
(上接183页)
参考文献:
[1]何建敏,刘春林.应急管理与应急系统[M].北京:科学出版社,2005.
[2][J].
Computers&IndustrialEngineering,1999,37:595-612.
[3]LuisG,AcostaE,-basedheuristicsforahierar-
chicalcoveringlocationproblem [J].Computer& OperationsRe-
search,2003,30:65-180.
[4]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,
2001.
[5]宿洁,韩强.一类多约束最短路问题的模拟退火算法[J].计算机工
程,2004,30(19):21-22.
[6]沈薇,刘方爱.基于模拟退火算法的数据副本选择策略[J].计算机工
程与应用,2006,42(35):145-147.
[7]杨宇栋,朗茂祥,胡思继.有时间窗车辆路径问题的模型及其改进模
拟退火算法研究[J].管理工程学报,2006,20(3):104-107.
[8]王凌,郑大钟.多目标优化的一类模拟退火算法[J].计算机工程与应
用,2002,38(8):4-5.
[9]方磊,何建敏.给定限期条件下的应急服务系统优化选址模型[J].管
理工程学报,2004,18(1):48-51.
[10]刁在筠,郑汉鼎,刘家壮,等.运筹学[M].北京:高等教育出版社,
2001.
[11]LundyM,[J].Math-
ematicalProgramming,1986,34:111-124.
计算当前列的累积距离,而不用保存整个距离矩阵。每前进一
帧都进行更新,即按上式利用前一列的累积距离 D和当前列
的所有帧匹配距离 d(x,y),求出当前帧的累积距离,保存于矢
量d中,再把新的距离d赋值给D,作为新的累积距离,供下一
列使用。这样一直前进到 X轴上最后一列,矢量 D的第 M个
元素即为两个模板动态弯折的匹配距离。
5 实验结果及分析
考虑到对于孤立耳语的识别,DTW算法与HMM算法在相
同的环境条件下,识别效果相差不大,但 HMM算法要复杂的
多。本文采用DTW针对非特定人的耳语音进行实验。
实验中采用的样本库由通信中常用汉语耳语音数字(0~9)
构成,由多人历经一个多月的时间录制而成,合计 3000个。
8000Hz采样,采样精度为16bit。
为了比较不同特征参数在耳语中的识别效果,进行了三组
实验:第一组,采用 MFCC加△MFCC参数,识别率为 %;
第二组,采用 LPCC加△LPCC参数,识别率为 %;第三组,
采用 MFCC、△MFCC与 LPCC、△LPCC有效结合的模型,识别
率达%。所得结果见图4所示。
实验结果表明,单独使用 MFCC及△MFCC和单独使用
LPCC及△LPCC不如将 MFCC与 LPCC结合后识别效果好。
MFCC反映的是人对语音的听觉频率非线性特性,LPCC则反
映的是的声道生理结构的特点。LPCC弥补了MFCC不能描述
的声道特性,而它们的差分系数△MFCC和△LPCC反映了语
音及声道的动态特性,组合这些特征矢量可以较好地反映耳语
音的特征。
具体来说,虽然 MFCC符合人类的听觉特性,在有信道噪
声和频谱失真的情况下具有相对较好的稳健性。但是提取
MFCC参数的算法复杂度要大于其它方法,且 MFCC对于耳语
音的识别,存在以下问题:由于对数曲线的特点,fHz转化为 fMel
时,随着 fHz增大,在低频段 fMel增加较快,而高频段增加较慢,
所以传统MFCC参数在低频段放置的滤波器较多,权值较大,
而高频段则相反。而对于耳语音,由于其没有基频,同时第一共
振峰向上偏移,所以 500Hz以下耳语音能量较小,这些低频三
角滤波器获取的功率谱主要为噪声信号的频谱。这无疑会影响
识别的效果。因此,单独由MFCC作为特征参数不再具有明显
的优势。
由本次实验结果可以看出,MFCC与 LPCC对不同的耳语
孤立词识别各有优势,将两者结合可进行优势互补,提高耳语
音的识别率。
6 结论
本文在分析耳语音不同于正常音的声学特性的基础上,分
析了不同特征参数在耳语识别中的应用,建立了汉语耳语音孤
立字识别系统。通过实验比较,验证了 MFCC及△MFCC结合
LPCC及△LPCC可作为汉语耳语音自动识别的特征量。最佳
识别率提高到%。
但考虑到耳语音的信噪比比较低,汉语耳语音识别对环境
的要求较高,因此对耳语音的识别离实用还有一段距离。这将
有待于进一步的研究与探讨。(收稿日期:2007年3月)
参考文献:
[1]-
coveringvoice[J].JournaloftheCentralUniversityforNationali-
ties,1996,5(2):163-166.
[2]ItohT,TakedaK,-
peredspeech[C]//ProcICASSP,Orlando,Florida,USA,2002:389-392.
[3]MorrisRW,CIementsM whis-
pers[J].MedicalEngineering&Physics,2002,24(8):515-520.
[4][D].
GeoaInstituteofTechnology,USA,2002.
[5]沙丹青,栗学丽,徐柏龄.耳语音声调特征的研究[J].电声技术,2003
(11):4-7.
[6]栗学丽,丁慧,徐柏龄.基于熵函数的耳语音声韵分割法[J].声学学
报,2004,30(1):69-75.
[7]杨莉莉,李燕,徐柏龄.汉语耳语音库的建立与听觉实验研究[J].南
京大学学报:自然科学版,2005,41(3):311-317.
[8]林玮,杨莉莉,徐柏龄.基于修正 MFCC参数汉语耳语音的话者识
别[J].南京大学学报:自然科学版,2006,42(1):54-62.
216
