论文部分内容阅读
摘 要：为进行区域交通的协调控制, 针对微粒群算法的优缺点，提出基于全局最优退火的微粒群算法.该算法能增强算法探索和开发的能力，避免计算量过度增加.典型测试函数结果显示，能提高算法搜索速度、搜索精度.仿真结果表明,该方法应用于区域交通协调控制信号配时，可获得更低的车辆平均延误和平均停车率.
关键词：微粒群优化； 退火； 函数优化； 信号配时
中图分类号：U491.54； TP182文献标志码：A
PSO with Gbest annealed and its application in traffic control
XU Bowei1, LI Junjun2, WEI Lin1
（1.Lab Administration, Shanghai Maritime Univ., Shanghai 200136, China;
2.College of Engineering Science & Technology, Shanghai Ocean Univ., Shanghai 200090, China）
Abstract： For the coordination control of urban traffic, a sort of particle swarm optimization algorithm with Gbest annealed is proposed according to the advantage and disadvantage of the particle swarm algorithm. This algorithm can enhance the exploration and exploitation ability of the algorithm andthe computation time is well controlled at the same time. The results from typical function optimization problems show that this method possesses good convergent performance with faster convergent rate. It indicates that signal timing optimization to urban traffic based on this algorithm in simulation can get lower average delay and stop rate of vehicles.
Key words：particle swarm optimization； annealing； function optimization； signal timing
0 引 言
城市交通系统是个随机性很强的复杂系统.应用区域交通协调控制减少车辆延误、缓解交通拥挤以及提高道路通行率，成为当今城市交通问题研究的热点之一.目前，TRANSYT，SCOOT，SCATS和RHODES等一些区域交通控制系统都易陷入局部极小点，且我国城市交通状况与国外有一定差距，控制效果不理想.［1-3］因此，一些研究人员尝试将智能计算技术应用于区域交通协调控制的信号配时.［3-6］微粒群优化（Particle Swarm Optimization, PSO）算法是种新的进化计算技术（Evolutionary Computation），最先由EBERHART等［7-8］提出.标准微粒群算法全局搜索能力强，但易陷入局部极值.模拟退火（Simulated Annealing，SA）算法［9］是基于金属退火的机理建立起的1种全局最优方法，具有较强的局部搜索能力，但对整个空间的搜索能力不强.因此，一些文献［10-11］提出将微粒群算法和模拟退火算法结合的混合优化算法，虽能提高算法性能，但增加算法复杂度，效率不高.
针对标准微粒群算法的特点，提出1种基于全局最优退火的微粒群算法，能提高算法探索和开发的能力，避免陷入局部极值，增加的计算量也较少.
1 区域交通协调控制
TRRL(英国运输与道路研究所)研究结果表明，只要围绕每个交叉口的小区能取得1个接近整体最小值的性能指标值PI，则整个路网范围的性能指标值也会接近其整体最小值.［1］因此，在路网条件一定时，区域交通协调控制参数优化模型的目标函数是使PI最小.优化模型［2-3］如下
J=min PI=
∑NTt=1∑NLi=1∑NJj=1(DijtWDijMD+SijtWSijMS)(1)
约束条件Ψ=(c,θ,)∈Ω0(2)
∑NLKk=1(ik+Iik)=c (i=1,2,…,NL)(3)
cmin≤c≤cmax(4)
minik≤ik≤maxik
(i=1,2,…,NL; k=1,2,…,Nk)(5)
0≤θi(i+1)≤c, θ(i+1)i=c-θi(i+1)
(i=1,2,…,NL-1)(6)式中：PI为路网性能指标;Dijt和Sijt分别为时间间隔t，路口i，交通流j的延误和停车数；WDij和WSij分别为路口i，交通流j的延误权重和停车权重；MD和MS分别为单位延误和单位停车数的总能耗；Ψ为信号配时参数c，θ和的组合；NT，NL和NJ分别为计算的时间间隔数、路口数和车流数；c，cmin和cmax分别为协调控制的路口周期、最小周期和最大周期；θ为路口之间的相位差，θi(i+1)和θ(i+1)i分别为路口i与i+1之间的相位差和路口i+1与i之间的相位差；ik，minik和maxik分别为路口i和相位k的绿时、最小绿时和最大绿时；Iik表示路口i和相位k的损失时间；NLK表示路口i相位数；i，j和k分别表示路口、交通流和相位编号.
式(1)中：Dijt=DUijt+DRijt(7)
Sijt=SUijt+SRijt(8)式中：DUijt，DRijt，SUijt和SRijt分别为时间间隔t，路口i，交通流j的均衡延误、随机与过饱和延误、均衡停车数以及随机与过饱和停车数.DRijt和SRijt由下式可得：DRijt=Δt2［(Uijt+Vijt)1/2-Uijt］(9)
Uijt=(1-ρijt)(μijtΔt)2+8CijLij(t-1)(2μijtΔt-4Cij)+
2(2Cijρijt-Lij(t-1))μijtΔt(2μijtΔt-4Cij)(10)
Vijt=2Cij(2Lij(t-1)+ρijtμijtΔt)2μijtΔt-2Cij(11)
Lijt=12ijt12ijt(12)
ijt=(1-ρijt)(μijtΔt)2+2CijLij(t-1)(μijtΔt-Cij)+
(2Cijρijt-Lij(t-1))μijtΔt(μijtΔt-Cij)(13)
ijt=4Cij(2Lij(t-1)+ρijtμijtΔt)2μijtΔt-Cij(14)
SRijt=2Δt1-exp-DRijt2cΔtqijt(15)式中：μijt和ρijt分别为在时间间隔t，路口i，交通流j的交通容量和饱和度；Lij(t-1)为t-1时间间隔结束时在路口i，交通流j的队列长度（即t时间间隔初始队列长）；Cij为路口i，交通流j的P-K(Pollaczek-Khintchine)数；Δt为时间间隔长度；qijt为时间间隔t，路口i，交通流j的交通流平均到达率.
2 标准微粒群优化算法
SHI等［12］对EBERHART等提出的基本PSO算法模型进行系统改进，形成当前的标准版本.
设f为定义在D维欧氏空间ED的某一区域S上的函数，N表示微粒数，Xi=(Xi1,Xi2,…,XiD)T∈S，Vi=(Vi1,Vi2,…,ViD)T以及f(Xi)分别为第i个微粒在S中的位置、速度和此时的适应度，i=1,2,…,N.Xpbi=(Xpbi1，Xpbi2，…，XpbiD)T为第i个微粒在搜索过程中到达过的最佳位置，Xgb=(Xgb1,Xgb2,…,XgbD)T为整个微粒群中全部微粒遇到的最优解.系统初始化过程将微粒随机分布在整个解空间，通过迭代逐步取得优化解，每个微粒均通过跟踪Xpbi和Xgb确定自身的移动规律.具体描述如下：Vt+1id=ωVtid+c1R(Xpbid-Xtid)+c2R(Xgbd-Xtid)(16)
Xt+1id=Xtid+Vt+1id(17)式中：d=1,2,…,D；t=1，2，…，tmax为迭代次数，c1和c2为2个常数，称为认知与社会参数；R为［0,1］之间的随机数；ω为惯量.微粒的速度Vid被1个最大速度Vmax,d限制,如果当前对微粒的加速导致其在某维的速度Vid超过该维的最大速度Vmax,d，则该维的速度被限制为Vmax,d.
3 基于全局最优退火的微粒群算法
标准微粒群算法全局搜索能力较强，但易陷入局部极值.模拟退火算法具有较强的局部搜索能力，能使搜索过程避免陷入局部最优解，与PSO算法形成互补.如果对所有微粒都采用模拟退火操作，虽能提高算法的搜索精度，但计算量却大大增加.
在微粒群搜索中，全局最优Xgb处于带领种群运动的牵头地位，它的调整对提高PSO算法的计算效率作用很大.若在算法迭代过程中，Xgb出现调整，在算法迭代初期，易发现更优的Xgb，能加快种群搜索速度；在算法迭代后期，易使种群进入其他区域进行搜索，使算法跳出局部最优.同时，调整的计算量不大，不会给计算增加复杂度.
因此，在微粒群每次迭代结束之前，对Xgb进行模拟退火操作，提出1种基于全局最优退火的微粒群(Particle Swarm Optimization Algorithm with Gbest Annealed, GBAPSO)算法.
3.1 全局最优的退火操作
在模拟退火算法中，新个体在原个体周围随机产生.以原个体为中心，设定1个区间，新个体就在该区间内随机产生，将此区间称为退火区间.退火区间的中心、半径分别称为退火中心、退火半径，退火中心即为原个体所处位置.
随着算法迭代次数增加，退火半径逐代线性减小.若算法最终迭代次数为M，令第1代Xgb第d维的退火半径为Rgb1d，最后1代Xgb第d维的退火半径为RgbMd，则第t代Xgb第d维的退火半径Rgbtd=Rbg1d-Rgbtd-RgbMdM-1·(t-1)(18)一般微粒第d维的取值范围为一区间，若区间的半径为Rd，则Rgb1d=α·Rd(19)
RbgMd=β·Rd(20)式中：0<β<α<1.
全局最优Xgb从原状态变为新状态的接受概率由模拟退火中的Metropolis规则确定p=1Enew exp-(Enew-Eold)T(t)Enew≥Eold(21)式中：Enew和Eold为全局最优新状态和原状态的适应度；T(t)为PSO算法第t代时的温度，采用经典模拟退火算法的降温方式：T(t)=T0lg(1+t)(22)3.2 GBAPSO算法步骤
(1)初始化微粒群，包括随机位置和速度；(2)计算各微粒的适应度；(3)将Xtid作为Xpbid，通过比较设置Xgbd的索引号；(4)对Xbgd按第3.1节执行SA算法一步搜索得到1个新的Xgbd；(5)按式(16)和(17)迭代生成下一代微粒群；(6)计算各微粒的适应度；(7)比较更新Xpbid和Xgbd；(8)对Xgbd按第3.1节执行SA算法一步搜索得到1个新的Xgbd；(9)如未达到终止条件，返回(5)，如达到终止条件，则输出结果，程序结束.
3.3 GBAPSO算法计算复杂度分析
在标准PSO算法中，假设单个微粒每代按迭代公式生成下代微粒时间为Tg，计算适应度时间为Tf，比较更新两极值时间为Tu；在GBAPSO算法中，假设全局最优执行退火操作获得新状态的时间为Ｔsa，确定新状态是否接受的时间为Ta.
若微粒群规模为N，最终迭代次数为M，则标准PSO算法的计算时间TPSO约为N·M·(Tg+Tf+Tu)；GBAPSO算法的计算时间TGBAPSO约为N·M·(Tg+Tf+Tu)+M·(Tsa+Tf+Ta)；有
TPSOTGBAPSO≈
NM(Tg+Tf+Tu)NM(Tg+Tf+Tu)+M(Tsa+Tf+Ta)×100%=
Tg+Tf+TuTg+1+1NTf+Tu+1N(Tsa+Ta)×100%(23)
式中：Tsa TPSOTGBAPSO>Tg+Tf+Tu1+1NTg+1+2NTf+Tu×100%>
Tg+Tf+Tu1+2N(Tg+Tf+Tu)×100%=
NN+2×100%(24)
一般情况下，N远大于2.因此，当种群规模、迭代次数相同时，PSO算法与GBAPSO算法计算量很接近.即GBAPSO算法相对于PSO算法，增加的计算量很小.
4 算法性能测试
为验证方法的有效性，首先应用PSO算法、基于模拟退火的微粒群优化(SAPSO)算法和GBAPSO算法对文献［11］中测试函数F1~F6进行仿真分析.种群规模为20，ω=0.729，c1=1.494 45，c2=1.494 45，Vmax,d设为微粒动态范围的30%.GBAPSO算法中α=0.2，β=0.05.表1给出这3种方法各重复20次计算的收敛率、平均收敛代数及平均收敛时间.
表1 标准测试函数优化结果算法性能F1F2F3F4F5F6PSO收敛率/%701001003510035平均收敛代数62.3641.55131.6593.1457186.14平均收敛时间/s0.021 20.026 10.057 10.024 70.018 10.060 3SAPSO收敛率/%1001001006010090平均收敛代数38.2430.6891.4962.7625.2370.24平均收敛时间/s0.020 70.023 80.054 00.023 10.013 90.050 8GBAPSO收敛率/%10095100659590平均收敛代数41.0632.4494.8261.3724.5173.42平均收敛时间/s0.016 40.018 20.042 90.017 20.011 80.043 4
由表1可以看出，在6个标准测试函数中，GBAPSO算法的收敛率、收敛速度均优于PSO算法；GBAPSO算法的收敛率、平均收敛代数与SAPSO算法相当，但平均收敛时间大为减少.可见GBAPSO算法在增强PSO算法搜索精度的同时，能明显提高收敛速度.
5 基于GBAPSO算法的区域交通协调控制在优化周期和相位差时，周期以周期增量的形式、相位差以提前和推迟协调相位起时时间若干秒的方式优化，既缩小可行解空间，也便于控制周期、相位差的增量范围.公式如下：c=c+Δc(25)
-tid min≤tid≤tid max(26)式中：Δc为周期增加（或减少）时间；式(26)限制路口i协调相位起始时间推迟（或超前）的时间范围.
以此方法处理周期和相位约束.采用惩罚函数法处理其他约束，在式(1)上增加对应的惩罚项，作为求解的适应度函数.
对如图1所示的12交叉口区域道路网进行仿真计算.不考虑行人和公交车影响，饱和流量为2 400 辆/h，最大排队长度为56 辆，车辆平均启动时间为2 s，周期为40 s至120 s，黄灯时间为2 s，红灯时间为3 s，最小、最大绿灯时间分别为12 s和120 s.仿真平台为TSIS 5.1.图1 区域道路网示意
采用遗传算法(GA)、PSO算法和GBAPSO算法进行求解.GA算法染色体个数为40，交叉率取0.6，变异率取0.01；PSO算法、GBAPSO算法微粒个数为40，ω=0.729，c1=1.494 45，c2=1.494 45；GBAPSO算法α=0.2，β=0.05.3种方法最大迭代次数均设为100，各计算50次，仿真结果见表2.
表2 各方法最优结果交通需求车辆平均延误/(s·辆-1)平均停车率/%GAPSOGBAPSOGAPSOGBAPSO70030.326.925.6107.095.989.280032.828.127.1120.8108.6102.41 10044.140.238.6148.6136.9125.71 20059.272.255.2199.5218.8195.11 800106.7118.5101.2210.7236.1202.72 000163.2158.4152.5227.1245.3218.4
由表2可知，GBAPSO算法获得更优的交通配时优化结果，车辆平均延误时间、车辆平均停车率较其他2种方法都明显减少.
6 结 论
针对标准微粒群算法易于陷入局部极值的缺点，提出1种基于全局最优退火的微粒群算法.该方法仅对微粒群算法的全局最优进行退火操作，在提高算法搜索效果的同时，控制计算量的增加.函数测试表明，能明显提高收敛速度.将该方法应用于1个12交叉口的区域交通信号配时问题，获得更优结果.
参考文献：
［1］刘智勇. 智能交通控制理论及其应用［M］. 北京: 科学出版社, 2003: 51-55.
［2］WONG S C, WONG W T, LEUNG C M, et al. Group-based optimization of a time-dependent TRANSYT traffic model for area traffic control［J］. Transportation Res Part B, 2002, 36(4): 291-312.
［3］CEYLAN H, BELL M G. Traffic signal timing optimization based on genetic algorithm approach, including drivers’ routing［J］. Transportation Res Part B, 2004, 38(4): 329-342.
［4］董超俊, 刘智勇, 邱祖廉. 基于混沌遗传算法的区域交通计算机控制配时优化［J］. 计算机工程与应用, 2004, 40(29): 32-34.
［5］刘智勇, 李水友. 基于免疫遗传算法的区域交通协调自适应控制［J］. 控制理论与应用, 2006, 23(1): 119-125.
［6］王春雷, 钱勇生. 基于双向并行灾变粒子群算法的区域交通控制［J］. 计算机工程与应用, 2007, 43(34): 229-232.
［7］EBERHART R C, KENNEDY J. A new optimizer using particles swarm theory［C］ // Proc 6th Int Symposium on Micro Machine and Human Science, Nagoya: IEEE Press, 1995: 39-43.
［8］EBERHART R C, KENNEDY J. Particles swarm optimization［C］ // IEEE Int Conf on Neural Network, Perth: IEEE Press, 1995: 1942-1948.
［9］KIRKPATRICK S, Jr GELATT C D, VECCHI M P. Optimization by simulated annealing［J］. Sci, 1983: 671-680.
［10］高鹰, 谢胜利. 基于模拟退火的粒子群优化算法［J］. 计算机工程与应用, 2004, 40(1): 47-50.
［11］LI Junjun, WANG Xihuai. A modified particle swarm optimization algorithm［C］// Proc 5th World Congress on Intelligent Control and Automation, Hangzhou: IEEE Press, 2004: 354-356．
［12］SHI Yuhui, EBERHART R. A modified particle swarm optimizer［C］// Proc IEEE Int Conf on Evolutionary Computation. Anchorage: IEEE Press, 1998: 69-73.
(编辑 陈锋杰)
关键词：微粒群优化； 退火； 函数优化； 信号配时
中图分类号：U491.54； TP182文献标志码：A
PSO with Gbest annealed and its application in traffic control
XU Bowei1, LI Junjun2, WEI Lin1
（1.Lab Administration, Shanghai Maritime Univ., Shanghai 200136, China;
2.College of Engineering Science & Technology, Shanghai Ocean Univ., Shanghai 200090, China）
Abstract： For the coordination control of urban traffic, a sort of particle swarm optimization algorithm with Gbest annealed is proposed according to the advantage and disadvantage of the particle swarm algorithm. This algorithm can enhance the exploration and exploitation ability of the algorithm andthe computation time is well controlled at the same time. The results from typical function optimization problems show that this method possesses good convergent performance with faster convergent rate. It indicates that signal timing optimization to urban traffic based on this algorithm in simulation can get lower average delay and stop rate of vehicles.
Key words：particle swarm optimization； annealing； function optimization； signal timing
0 引 言
城市交通系统是个随机性很强的复杂系统.应用区域交通协调控制减少车辆延误、缓解交通拥挤以及提高道路通行率，成为当今城市交通问题研究的热点之一.目前，TRANSYT，SCOOT，SCATS和RHODES等一些区域交通控制系统都易陷入局部极小点，且我国城市交通状况与国外有一定差距，控制效果不理想.［1-3］因此，一些研究人员尝试将智能计算技术应用于区域交通协调控制的信号配时.［3-6］微粒群优化（Particle Swarm Optimization, PSO）算法是种新的进化计算技术（Evolutionary Computation），最先由EBERHART等［7-8］提出.标准微粒群算法全局搜索能力强，但易陷入局部极值.模拟退火（Simulated Annealing，SA）算法［9］是基于金属退火的机理建立起的1种全局最优方法，具有较强的局部搜索能力，但对整个空间的搜索能力不强.因此，一些文献［10-11］提出将微粒群算法和模拟退火算法结合的混合优化算法，虽能提高算法性能，但增加算法复杂度，效率不高.
针对标准微粒群算法的特点，提出1种基于全局最优退火的微粒群算法，能提高算法探索和开发的能力，避免陷入局部极值，增加的计算量也较少.
1 区域交通协调控制
TRRL(英国运输与道路研究所)研究结果表明，只要围绕每个交叉口的小区能取得1个接近整体最小值的性能指标值PI，则整个路网范围的性能指标值也会接近其整体最小值.［1］因此，在路网条件一定时，区域交通协调控制参数优化模型的目标函数是使PI最小.优化模型［2-3］如下
J=min PI=
∑NTt=1∑NLi=1∑NJj=1(DijtWDijMD+SijtWSijMS)(1)
约束条件Ψ=(c,θ,)∈Ω0(2)
∑NLKk=1(ik+Iik)=c (i=1,2,…,NL)(3)
cmin≤c≤cmax(4)
minik≤ik≤maxik
(i=1,2,…,NL; k=1,2,…,Nk)(5)
0≤θi(i+1)≤c, θ(i+1)i=c-θi(i+1)
(i=1,2,…,NL-1)(6)式中：PI为路网性能指标;Dijt和Sijt分别为时间间隔t，路口i，交通流j的延误和停车数；WDij和WSij分别为路口i，交通流j的延误权重和停车权重；MD和MS分别为单位延误和单位停车数的总能耗；Ψ为信号配时参数c，θ和的组合；NT，NL和NJ分别为计算的时间间隔数、路口数和车流数；c，cmin和cmax分别为协调控制的路口周期、最小周期和最大周期；θ为路口之间的相位差，θi(i+1)和θ(i+1)i分别为路口i与i+1之间的相位差和路口i+1与i之间的相位差；ik，minik和maxik分别为路口i和相位k的绿时、最小绿时和最大绿时；Iik表示路口i和相位k的损失时间；NLK表示路口i相位数；i，j和k分别表示路口、交通流和相位编号.
式(1)中：Dijt=DUijt+DRijt(7)
Sijt=SUijt+SRijt(8)式中：DUijt，DRijt，SUijt和SRijt分别为时间间隔t，路口i，交通流j的均衡延误、随机与过饱和延误、均衡停车数以及随机与过饱和停车数.DRijt和SRijt由下式可得：DRijt=Δt2［(Uijt+Vijt)1/2-Uijt］(9)
Uijt=(1-ρijt)(μijtΔt)2+8CijLij(t-1)(2μijtΔt-4Cij)+
2(2Cijρijt-Lij(t-1))μijtΔt(2μijtΔt-4Cij)(10)
Vijt=2Cij(2Lij(t-1)+ρijtμijtΔt)2μijtΔt-2Cij(11)
Lijt=12ijt12ijt(12)
ijt=(1-ρijt)(μijtΔt)2+2CijLij(t-1)(μijtΔt-Cij)+
(2Cijρijt-Lij(t-1))μijtΔt(μijtΔt-Cij)(13)
ijt=4Cij(2Lij(t-1)+ρijtμijtΔt)2μijtΔt-Cij(14)
SRijt=2Δt1-exp-DRijt2cΔtqijt(15)式中：μijt和ρijt分别为在时间间隔t，路口i，交通流j的交通容量和饱和度；Lij(t-1)为t-1时间间隔结束时在路口i，交通流j的队列长度（即t时间间隔初始队列长）；Cij为路口i，交通流j的P-K(Pollaczek-Khintchine)数；Δt为时间间隔长度；qijt为时间间隔t，路口i，交通流j的交通流平均到达率.
2 标准微粒群优化算法
SHI等［12］对EBERHART等提出的基本PSO算法模型进行系统改进，形成当前的标准版本.
设f为定义在D维欧氏空间ED的某一区域S上的函数，N表示微粒数，Xi=(Xi1,Xi2,…,XiD)T∈S，Vi=(Vi1,Vi2,…,ViD)T以及f(Xi)分别为第i个微粒在S中的位置、速度和此时的适应度，i=1,2,…,N.Xpbi=(Xpbi1，Xpbi2，…，XpbiD)T为第i个微粒在搜索过程中到达过的最佳位置，Xgb=(Xgb1,Xgb2,…,XgbD)T为整个微粒群中全部微粒遇到的最优解.系统初始化过程将微粒随机分布在整个解空间，通过迭代逐步取得优化解，每个微粒均通过跟踪Xpbi和Xgb确定自身的移动规律.具体描述如下：Vt+1id=ωVtid+c1R(Xpbid-Xtid)+c2R(Xgbd-Xtid)(16)
Xt+1id=Xtid+Vt+1id(17)式中：d=1,2,…,D；t=1，2，…，tmax为迭代次数，c1和c2为2个常数，称为认知与社会参数；R为［0,1］之间的随机数；ω为惯量.微粒的速度Vid被1个最大速度Vmax,d限制,如果当前对微粒的加速导致其在某维的速度Vid超过该维的最大速度Vmax,d，则该维的速度被限制为Vmax,d.
3 基于全局最优退火的微粒群算法
标准微粒群算法全局搜索能力较强，但易陷入局部极值.模拟退火算法具有较强的局部搜索能力，能使搜索过程避免陷入局部最优解，与PSO算法形成互补.如果对所有微粒都采用模拟退火操作，虽能提高算法的搜索精度，但计算量却大大增加.
在微粒群搜索中，全局最优Xgb处于带领种群运动的牵头地位，它的调整对提高PSO算法的计算效率作用很大.若在算法迭代过程中，Xgb出现调整，在算法迭代初期，易发现更优的Xgb，能加快种群搜索速度；在算法迭代后期，易使种群进入其他区域进行搜索，使算法跳出局部最优.同时，调整的计算量不大，不会给计算增加复杂度.
因此，在微粒群每次迭代结束之前，对Xgb进行模拟退火操作，提出1种基于全局最优退火的微粒群(Particle Swarm Optimization Algorithm with Gbest Annealed, GBAPSO)算法.
3.1 全局最优的退火操作
在模拟退火算法中，新个体在原个体周围随机产生.以原个体为中心，设定1个区间，新个体就在该区间内随机产生，将此区间称为退火区间.退火区间的中心、半径分别称为退火中心、退火半径，退火中心即为原个体所处位置.
随着算法迭代次数增加，退火半径逐代线性减小.若算法最终迭代次数为M，令第1代Xgb第d维的退火半径为Rgb1d，最后1代Xgb第d维的退火半径为RgbMd，则第t代Xgb第d维的退火半径Rgbtd=Rbg1d-Rgbtd-RgbMdM-1·(t-1)(18)一般微粒第d维的取值范围为一区间，若区间的半径为Rd，则Rgb1d=α·Rd(19)
RbgMd=β·Rd(20)式中：0<β<α<1.
全局最优Xgb从原状态变为新状态的接受概率由模拟退火中的Metropolis规则确定p=1Enew
(1)初始化微粒群，包括随机位置和速度；(2)计算各微粒的适应度；(3)将Xtid作为Xpbid，通过比较设置Xgbd的索引号；(4)对Xbgd按第3.1节执行SA算法一步搜索得到1个新的Xgbd；(5)按式(16)和(17)迭代生成下一代微粒群；(6)计算各微粒的适应度；(7)比较更新Xpbid和Xgbd；(8)对Xgbd按第3.1节执行SA算法一步搜索得到1个新的Xgbd；(9)如未达到终止条件，返回(5)，如达到终止条件，则输出结果，程序结束.
3.3 GBAPSO算法计算复杂度分析
在标准PSO算法中，假设单个微粒每代按迭代公式生成下代微粒时间为Tg，计算适应度时间为Tf，比较更新两极值时间为Tu；在GBAPSO算法中，假设全局最优执行退火操作获得新状态的时间为Ｔsa，确定新状态是否接受的时间为Ta.
若微粒群规模为N，最终迭代次数为M，则标准PSO算法的计算时间TPSO约为N·M·(Tg+Tf+Tu)；GBAPSO算法的计算时间TGBAPSO约为N·M·(Tg+Tf+Tu)+M·(Tsa+Tf+Ta)；有
TPSOTGBAPSO≈
NM(Tg+Tf+Tu)NM(Tg+Tf+Tu)+M(Tsa+Tf+Ta)×100%=
Tg+Tf+TuTg+1+1NTf+Tu+1N(Tsa+Ta)×100%(23)
式中：Tsa
Tg+Tf+Tu1+2N(Tg+Tf+Tu)×100%=
NN+2×100%(24)
一般情况下，N远大于2.因此，当种群规模、迭代次数相同时，PSO算法与GBAPSO算法计算量很接近.即GBAPSO算法相对于PSO算法，增加的计算量很小.
4 算法性能测试
为验证方法的有效性，首先应用PSO算法、基于模拟退火的微粒群优化(SAPSO)算法和GBAPSO算法对文献［11］中测试函数F1~F6进行仿真分析.种群规模为20，ω=0.729，c1=1.494 45，c2=1.494 45，Vmax,d设为微粒动态范围的30%.GBAPSO算法中α=0.2，β=0.05.表1给出这3种方法各重复20次计算的收敛率、平均收敛代数及平均收敛时间.
表1 标准测试函数优化结果算法性能F1F2F3F4F5F6PSO收敛率/%701001003510035平均收敛代数62.3641.55131.6593.1457186.14平均收敛时间/s0.021 20.026 10.057 10.024 70.018 10.060 3SAPSO收敛率/%1001001006010090平均收敛代数38.2430.6891.4962.7625.2370.24平均收敛时间/s0.020 70.023 80.054 00.023 10.013 90.050 8GBAPSO收敛率/%10095100659590平均收敛代数41.0632.4494.8261.3724.5173.42平均收敛时间/s0.016 40.018 20.042 90.017 20.011 80.043 4
由表1可以看出，在6个标准测试函数中，GBAPSO算法的收敛率、收敛速度均优于PSO算法；GBAPSO算法的收敛率、平均收敛代数与SAPSO算法相当，但平均收敛时间大为减少.可见GBAPSO算法在增强PSO算法搜索精度的同时，能明显提高收敛速度.
5 基于GBAPSO算法的区域交通协调控制在优化周期和相位差时，周期以周期增量的形式、相位差以提前和推迟协调相位起时时间若干秒的方式优化，既缩小可行解空间，也便于控制周期、相位差的增量范围.公式如下：c=c+Δc(25)
-tid min≤tid≤tid max(26)式中：Δc为周期增加（或减少）时间；式(26)限制路口i协调相位起始时间推迟（或超前）的时间范围.
以此方法处理周期和相位约束.采用惩罚函数法处理其他约束，在式(1)上增加对应的惩罚项，作为求解的适应度函数.
对如图1所示的12交叉口区域道路网进行仿真计算.不考虑行人和公交车影响，饱和流量为2 400 辆/h，最大排队长度为56 辆，车辆平均启动时间为2 s，周期为40 s至120 s，黄灯时间为2 s，红灯时间为3 s，最小、最大绿灯时间分别为12 s和120 s.仿真平台为TSIS 5.1.图1 区域道路网示意
采用遗传算法(GA)、PSO算法和GBAPSO算法进行求解.GA算法染色体个数为40，交叉率取0.6，变异率取0.01；PSO算法、GBAPSO算法微粒个数为40，ω=0.729，c1=1.494 45，c2=1.494 45；GBAPSO算法α=0.2，β=0.05.3种方法最大迭代次数均设为100，各计算50次，仿真结果见表2.
表2 各方法最优结果交通需求车辆平均延误/(s·辆-1)平均停车率/%GAPSOGBAPSOGAPSOGBAPSO70030.326.925.6107.095.989.280032.828.127.1120.8108.6102.41 10044.140.238.6148.6136.9125.71 20059.272.255.2199.5218.8195.11 800106.7118.5101.2210.7236.1202.72 000163.2158.4152.5227.1245.3218.4
由表2可知，GBAPSO算法获得更优的交通配时优化结果，车辆平均延误时间、车辆平均停车率较其他2种方法都明显减少.
6 结 论
针对标准微粒群算法易于陷入局部极值的缺点，提出1种基于全局最优退火的微粒群算法.该方法仅对微粒群算法的全局最优进行退火操作，在提高算法搜索效果的同时，控制计算量的增加.函数测试表明，能明显提高收敛速度.将该方法应用于1个12交叉口的区域交通信号配时问题，获得更优结果.
参考文献：
［1］刘智勇. 智能交通控制理论及其应用［M］. 北京: 科学出版社, 2003: 51-55.
［2］WONG S C, WONG W T, LEUNG C M, et al. Group-based optimization of a time-dependent TRANSYT traffic model for area traffic control［J］. Transportation Res Part B, 2002, 36(4): 291-312.
［3］CEYLAN H, BELL M G. Traffic signal timing optimization based on genetic algorithm approach, including drivers’ routing［J］. Transportation Res Part B, 2004, 38(4): 329-342.
［4］董超俊, 刘智勇, 邱祖廉. 基于混沌遗传算法的区域交通计算机控制配时优化［J］. 计算机工程与应用, 2004, 40(29): 32-34.
［5］刘智勇, 李水友. 基于免疫遗传算法的区域交通协调自适应控制［J］. 控制理论与应用, 2006, 23(1): 119-125.
［6］王春雷, 钱勇生. 基于双向并行灾变粒子群算法的区域交通控制［J］. 计算机工程与应用, 2007, 43(34): 229-232.
［7］EBERHART R C, KENNEDY J. A new optimizer using particles swarm theory［C］ // Proc 6th Int Symposium on Micro Machine and Human Science, Nagoya: IEEE Press, 1995: 39-43.
［8］EBERHART R C, KENNEDY J. Particles swarm optimization［C］ // IEEE Int Conf on Neural Network, Perth: IEEE Press, 1995: 1942-1948.
［9］KIRKPATRICK S, Jr GELATT C D, VECCHI M P. Optimization by simulated annealing［J］. Sci, 1983: 671-680.
［10］高鹰, 谢胜利. 基于模拟退火的粒子群优化算法［J］. 计算机工程与应用, 2004, 40(1): 47-50.
［11］LI Junjun, WANG Xihuai. A modified particle swarm optimization algorithm［C］// Proc 5th World Congress on Intelligent Control and Automation, Hangzhou: IEEE Press, 2004: 354-356．
［12］SHI Yuhui, EBERHART R. A modified particle swarm optimizer［C］// Proc IEEE Int Conf on Evolutionary Computation. Anchorage: IEEE Press, 1998: 69-73.
(编辑 陈锋杰)