模拟追逐算法

刘　伟，谢月珊

(广东工业大学 应用数学学院，广东 广州 510006)

模拟追逐算法

刘伟，谢月珊

(广东工业大学 应用数学学院，广东 广州 510006)

摘要:提出了一种群体智能算法——模拟追逐算法.该算法模拟长跑比赛运动员追逐竞争过程，设计了追逐算子与探测算子.领先个体执行探测算子操作以便获得更优位置，落后个体为取得竞争优势，设定追赶目标，执行追逐算子操作，完成跟随超越，从而实现群体进化寻优.仿真实验表明，模拟追逐算法有较快的收敛速度和较高的求解精度，是一种稳定的优化算法.

关键词:模拟追逐；智能算法；探测算子；追逐算子

受生物的智能行为启发，一些学者建立数学模型，模拟其寻优能力提出了多种智能优化算法.遗传算法[1-4]是模拟自然界的生物选择、杂交、变异的进化过程的全局优化算法；粒子群算法[5-7]是模拟鸟群觅食过程的一种有效的全局寻优算法.这类仿生算法不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，为复杂系统优化提供了一种通用的求解框架，被广泛应用到函数优化[8]、组合优化[9]、自动控制[10-11]、生产调度[12]、图像处理[13-15]等领域.

在长跑比赛中，运动员为了获得好的成绩，需要采用正确的战术策略.如何调整自己的步伐，是跟跑还是领跑,冲刺时机选择等等都是比赛获胜的重要因素.长跑比赛实质就是追逐竞赛的过程.领先的运动员按自己的节奏，不断调整步伐奔向终点；落后的运动员结合自己的实力，设定视野范围，确定追逐目标，从而调整自己步伐，跟跑并超越对手.

借鉴追逐竞赛的过程，本文建立了数学模型并运用于优化问题的求解，提出了一种新的智能算法——模拟追逐算法.该算法通过追逐算子和探测算子作用，使个体不断调整步长，搜索到更优的位置，从而引导解不断地进化，最终实现全局寻优.数值实验验证了模拟追逐算法是一种有效的群体优化算法.

1模拟追逐算法

1.1基本原理

模拟追逐算法(Simulated Pursuit Algorithm,SPA)是模拟运动员长跑比赛的追逐过程行为所具有的智能性，为优化问题的解决提供了一种全局寻优算法.算法中运动员被称为“个体”或“解”，问题优化过程就是个体追逐过程.跑在比赛最前列的“个体”(最优个体)，为保持领先的位置，执行探测算子，尝试多次调整自己的步伐，计算出相应的新位置，若新位置优于原先位置，则选择较优的新位置替换最优个体位置，否则，最优个体位置保持不变.其他个体(非最优个体)执行追逐算子，首先个体根据战术需要，设定视野范围，确定追逐目标(个体)，若追逐目标数k>0,则根据追逐目标，计算出需要调整的步长，确定新位置，若k=0，即视野范围内没有追逐目标，则参照最优个体的位置调整步长，计算新位置，直至群体完成设定的进化迭代次数，算法终止.

1.2控制参数

在模拟追逐算法中，关键参数是预先设定好的，参数设置对算法运行效率有很大的影响，具体包括种群大小N、当前迭代次数TCur、最大迭代次数TMax、尝试次数m、视野范围r.

1.3追逐算子

步长Step为

(1)

(2)

(3)

由式(2)和(3)知,被追逐个体Xj的适应度越大，Fectorj越大，对个体Xi位置更新所需的步长贡献率越大 .所以

当k>0时，个体i的新位置为

(4)

否则k=0,个体i的新位置为

(5)

其中step1=Xb-Xi，其中Xb为最优个体 .

1.4探测算子

探测算子是通过一个随机扰动步长探测出最优个体可能的新位置.尝试次数为m,步长生成源P>0,向量维数为W. 扰动步长Step 2随机生成,其生成的代码(Matlab)为

Step2=0*ones(1,W);

q=1+fix(rand()·(W));

forj=1:q

a(j)=fix(1+rand()·W);

end

forj=1:q

k=a(j);

if (rand(1)<0.5)

Step2(k)=Step2(k)-rand()·P;

else

Step2(k)=Step2(k)+rand()·P;

end

end

1.5算法流程

模拟追逐算法步骤：

(1) 种群初始化与参数设置.

(2) 适应度计算，最优个体确定.

(3) 种群个体更新：若个体为最优个体，则执行探测算子；否则执行追逐算子.

(4) 算法终止条件是否满足，若满足，则算法结束；否则转步骤(2).

算法流程图如图1所示

图1　模拟追逐算法流程图

2仿真实验及结果分析

2.1追逐算子性能分析

为分析追逐算子的功能，对个体为100，向量维数为5的种群，视野范围取不同值，执行追逐算子测试.图2为随机选择编号为10，40，90的个体的50次迭代的进化曲线，图3为视野范围r分别为0.000 1、0.01、0.1、1时，种群最优个体的进化曲线.结果表明：种群中的个体在迭代过程中不断进化，并具有跳出局部最优解的能力；同时追逐算子对解的搜索精度与收敛速度的影响与视野范围大小有关，视野范围为0.01时算子搜索效果最佳；视野范围的设置与优化问题有关.

图2　不同个体的进化曲线

2.2实验结果与算法分析

为了检验模拟追逐算法的优化性能，本文选择文献[4]的自适应遗传算法(记为GA), 文献[7]中的带粒子释放和速度限制的粒子群算法(记为PSO)与模拟追逐算法比较, 通过6个标准的测试函数(如表1所示)测试3种算法的性能，数值实验在Matlab中完成.每个测试函数在相同条件下独立运行20次，记录最好结果、平均结果，算法成功率.

表1　测试函数

从表2可知，为了获得更好的优化效果，视野范围r取值与优化问题相关；对于6个测试函数，无论是单峰函数还是多峰函数，SPA测试的最优值、平均最优值均优于GA与PSO,说明新算法有很好的求解精度，特别是对于函数f3与f5，SPA均求解出理论最优值；对于6个测试函数分别设置其目标精度，除f2外，其余5个优化问题求解成功率均为100%，说明SPA优化求解有很好的稳定性.

从图4～图9可知，SPA比GA,PSO有更快的收敛速度，并且有跳出陷入局部最优解的能力；在相同精度下，算法SPA比算法GA,PSO需要的迭代次数更少；图8中，对于f5，虽然PSO与SPA算法均收敛于最优值，但算法SPA只需要62次迭代，而PSO需要128次迭代.

表2　计算结果

图4　各函数进化曲线

从上实验分析可以看出，与GA,PSO比较，SPA在收敛速度、求解精度、稳定性等方面均显示出其优越性，说明模拟追逐算法是一种有较强寻优能力的群体智能算法.

3实际应用

案例(选址问题) 假设要选定一个供应中心的位置,为城市中固定的m个用户服务，供应的商品可以是水、电、牛奶或其他货物.求供应中心的位置，使其到各个用户的距离(之和)最小.假设现有10个用户，位置为{(xi,yi)|

(2.517 8,3.246 3),(-2.984 1,3.307 0),(1.058 9,-3.219 7),(-1.772 0,0.375 1),(3.660 1,3.719 1),(-2.739 1,3.764 7),

(3.657 3,-0.117 0),(2.402 2,-2.864 9),(-0.625 9,3.325 9),(2.337 7,3.675 9)}.

解假设供应中心的位置C=(x，y),建立优化问题模型.

采用Matlab给出选址问题的精确最优解为(0.877 1， 2.117 1)，最优值为34.569 3.为使用模拟追逐算法求解，设置控制参数：TMax=10，N=10,r=0.5,m=5，G0=50,α=80.算法SPA计算出最优解与精确解一致,C*=(0.877 111 032 786 5，2.117 105 766 708 5),f*=34.569 318 766 834 06.算法进化曲线如图5所示，算法所求供应中心位置如图6所示.

图5　算法进化曲线

4结束语

SPA是一种对人类行为进行智能仿生的优化算法.融合了试探性开拓与有目的性的追逐相结合的优点，具有模型简单，优化性能高的优点.实验仿真结果证实了模拟追逐算法的优越性.

图6　供应中心位置

参考文献：

[1] RUNARSSON T P, YAO X. Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactions on Evolutionary Computation, 2000,4(3):284-294.

[2] DEEP K, THAKUR M.A new mutation operator for real coded genetic algorithms[J]. Applied Mathematics and Computation，2007,193:211-230.

[3] 刘伟,刘海林.基于外点法的混合遗传算法求解决约束优化问题[J].计算机应用, 2007, 27(1):238-240

LIU W,LIU H L. A hybrid genetic algorithm based on external point method for constrained optimization[J]. Journal of Computer Applications, 2007, 27(1):238-240.

[4] 梁旭，黄明.现代智能优化混合算法及其应用[M]. 北京：电子工业出版社，2012.

[5] RATNAWEERA A，HALGAMUGE S.Nonlinear inertia variation for dynamic adaption in particle swarm optimization[J]．Computers & Operation Research,2006,33(3):859-971．

[6] 刘伟,蔡前凤,刘海林.基于参数方程处理等式约束优化的粒子群算法[J]. 计算机工程与设计, 2008, 29(3):697-699.

LIU W, CAI Q F, LIU H L. A particle swarm optimization algorithm based on parametric equation method to handle equality constraints[J].Journal of Computer Engineering and Design, 2008, 29(3):697-699.

[7] 吴正科,杨青真. 带粒子释放和速度限制的粒子群算法[J]. 计算机应用研究, 2013, 30(3):682-684.

WU Z K,YANG Q Z. Particle swarm optimization with particle release and speed limit[J].Journal of Application Research of Computers,2013, 30(3):682-684.

[8] 倪全贵.粒子群遗传混合算法及其在函数优化上的应用[D].广州：华南理工大学数学科学学院, 2014.

[9] 马立肖,王江晴.遗传算法在组合优化问题中的应用[J].计算机工程与科学, 2005, 27(7):72-74.

MA L X, WANG J Q.Application of genetic algorithms in solving the optimal combination problem[J].Computer Engineering and Science, 2005, 27(7):72-74.

[10] 杨智民,王旭,庄显义.遗传算法在自动控制领域中的应用综述[J].信息与控制, 2000,29(4):329-339.

YANG Z M,WANG X,ZHUANG X Y. Survey of genetic algortihm′s application in field of automatic control[J].Information and Control, 2000,29(4):329-339.

[11] 张雅妮.基于粒子群算法模糊控制自动舵的研究与仿真[D].哈尔滨:哈尔滨工程大学自动化学院,2010.

[12] 黄胜忠.遗传算法在企业车间调度中的应用[J].微计算机信息, 2008, 7(3):266-267.

HUANG S Z.Application of genetic algorithm in the enterprise shop scheduling[J].Microcomputer Information, 2008, 7(3):266-267.

[13]朱峰,宋余庆,金华,等.改良遗传算法在图像多阈值分割中的应用[J].江苏大学学报(自然科学版),2003,24(6):66-69.

ZHU F, SONG Y Q,JIN H,et al.Improved genetie algorithm for multi-level threshold image segmentation[J].Journal of Jiangsu University(Natural Science Edition), 2003, 24(6):66-69.

[14] 乔军.遗传算法在图像处理中的应用[J].中国农业大学学报, 1998, 3(4):80-82.

QIAO J.Application of genetic algorithm for image proceeding[J].Journal of China Agricultural University,1998, 3(4):80-82.

[15] 宣兆新,陆金桂,石云,等.基于改进的遗传算法的图像恢复[J].计算机应用与软件, 2010, 27(3):252-254.

XUAN Z X,LU J G, SHI Y, et al. Image restoration based on improved genetic algorithm[J].Computer Applications and Software, 2010, 27(3):252-254.

A Simulated Pursuit Algorithm

Liu Wei， Xie Yue-shan

(School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China)

Abstract:A new simulated pursuit intelligent swarm algorithm is proposed. In the process of pursuit for athletes simulated in Long-distance Race, a pursuit operator and an exploring operator are presented. In the algorithm, the leader uses an exploring operator to obtain the better position, and the rest of individuals often use a pursuit operator to follow or surpass competitors and the population evolution is realized. The simulation results show that simulated pursuit algorithm is an effective and robust method with better solution accuracy and higher convergence speed.

Key words:simulated pursuit; intelligent algorithm; exploring operator; pursuit operator

收稿日期:2015-04-17

基金项目:国家自然科学基金资助项目(61202269)

作者简介:刘伟(1970-)，男，副教授，硕士生导师，主要研究方向为优化理论、智能计算.

doi:10.3969/j.issn.1007-7162.2016.02.006

中图分类号:TP301.6

文献标志码:A

文章编号:1007-7162(2016)02-0031-06