智能系统：求解旅行商问题的混合粒子群优化算法

第7卷第2期 智能系统学报 Vol.7 No.2 2012年4月 CAAI Transactions on Intelligent Systems Apr.2012 D0I:10.3969/i.issn.16734785.201104014 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20120316.1014.001.html 求解旅行商问题的混合粒子群优化算法 沈继红'，王侃2 (1.哈尔滨工程大学理学院，黑龙江哈尔滨150001；2.哈尔滨工程大学自动化学院，黑龙江哈尔滨150001) 摘要：为高效解决旅行商问题，结合光学寻优算法、混沌优化算法、粒子群优化算法，提出了一种新的混合智能优 化算法，应用光学寻优算法的优点，为粒子群中粒子找到了一组最优的初始值，引入交换子、交换序列、混沌序列，提 出了适合旅行商问题的光学混沌粒子群算一并严格证明了新算法的稳定性、收敛性.数值实验仿真结果表明，该 算法收敛速度快、迭代次数少，能快速找到令人满意的最优解，为解决旅行商问题提供了新的思路。 关键词：旅行商问题；混沌优化算法；费马原理；粒子群算法：光学寻优算法 中图分类号：TP301.6文献标志码：A文章编号：16734785(2012)02017409 The light ray particle swarm optimization for solving the traveling salesman problem SHEN Jihong',WANG Kan2 (1.College of Science,Harbin Engineering University,Harbin 150001,China;2.College of Automation,Harbin Engineering Univer- sity,Harbin 150001,China) Abstract:A new hybrid intelligent optimization was given to solve the traveling salesman problem (TSP)by intro- ducing the thought of an LRO algorithm,chaos optimization algorithm,and particle swarm optimization(PSO).A group of optimal initial values were found by using the features of LRO.Next,by employing the method of discrete chaotic particle swarm optimization and introducing the swap operator,swap sequence,and chaos sequence,an op- tical chaos PSO adaptive for the TSP problem was proposed.The stability and convergence of the optimization was proved decisively.The numerical simulation results show that this new optimization method has a good convergence rate and less iterative steps,thus allowing a satisfactory solution to be found rapidly.The method provides a new in- spiration for solving the TSP problem. Keywords:travel salesman problem;chaos optimization algorithm;Ferma's principle;particle swarm optimiza- tion;light ray optimization 优化问题可以自然分为2类：一类是连续变量 优解的精确算法和找到近似解的近似算法.完全枚举 的优化问题；另一类是离散变量的优化问题，即所谓 法、动态规划法和全局搜索算法属于精确算法.TSP 的组合优化问题.旅行商问题(travel salesman prob 问题精确算法的运行时间是指数级复杂度，难以适应 lem,TSP)是组合优化问题中的一个著名NP难题， 大规模的实例，随着对TSP问题的认识加深，精确算 TSP因其典型性已经成为许多启发式搜索、优化算 法的研究越来越少.近年来受到自然界的启发，人们 法的间接比较标准.同时TSP也是一个具有广泛的 提出了各种各样的计算智能方法，如人工神经网络、 应用背景与重要理论价值的组合优化难题，对求解 遗传算法、蚁群优化算法、粒子群优化算法和人工免 该问题高效的全局优化算法的研究，一直被科学界 疫系统等.智能优化算法为解决TSP问题提供了新的 和工程界所高度重视， 思路，它们被广泛地应用于各种NP难题的优化问题 TSP问题的求解方法归纳起来可以分为得到最 求解，虽然不能保证获取最优解，但在问题规模较大 时也可以在可行时间内找到满意的解。 收稿日期：201104-24.网络出版日期：2012-03-16 基金项目：黑龙江省自然科学基金资助项目(F200931). 粒子群优化算法(（particle swarm optimization, 通信作者：王侃.E-mail:wangkan198600@163.com. PS0)是一种群智能优化方法，它是由美国社会心理

第2期 沈继红，等：求解旅行商问题的混合粒子群优化算法 ·175· 学家Kennedy和电气工程师R.Eberhart在1995年 个粒子的位置用：=（x,x,…,n)表示；第i个 提出的，它利用了生物群体中信息共享的思想，其概 粒子的速度变化率用：=(，"2，…，"n)表示；第i 念简单、易于实现，同时又有深刻的智能背景，既适 个粒子迄今为止搜索的得最好位置为P:=(P:,P2, 合科学研究，又适合工程应用.因此，PS0一经提出， “,Po）,记为pt,整个粒子群迄今为止搜索到的最 就引起了众多学者的关注，得到了非常广泛的应用. 好位置为Pg=(Pg1P,…,P),记为8，对于每 为解决组合优化问题，Kennedy等)首先提出了 一次迭代，第i个粒子在第D维运动的表达式如下： Ps0算法的离散二进制版；Clere!21提出了求解TsP (t+1)=ow(t)+c2rand()·[p(t)-x:(t)]+ 问题的离散粒子群优化算法，对TSP问题的求解重 crrand().[pi(t)-xi(t)], 新定义粒子的位置、速度和相关运算，但其性能与其 x(t+1)=x(t)+v(t+1), 他算法相比仍有不小的差距；高尚等3]在粒子群算 1≤i≤n,1≤d≤D. 法中加人遗传算法思想，构造了混合算法；Hendlass 式中：c1、c2为正常数，称为加速因子；rand()为[0， 等4通过对离散PS0的每个粒子增加记忆功能，成 1]之间的随机数；o称为惯性因子.第d维的位置和 功解决了一个小规模的TSP;王康平等[51通过引入 速度的变化范围为[-am,4n]和[-4"4m], “交换子”和“交换序”的概念，给出了另一种解决 如果在某一维中迭代的x”超过了取值边界则按 TSP的PSO方法，为求解TSP问题提供了新的思 照边界取值. 路.但在算法的收敛速度方面以及在城市规模较大 1.2光学寻优算法 的情况下，现有文献中的粒子群算法都存在着一定 光学寻优算法借鉴了费马定理，利用光在传播过 的缺陷，本文试图通过与其他智能优化算法的结合 程中自动寻优的机制，将光的折射与反射原理与最优 来解决这一问题.光学寻优算法「6]是2007年沈继红 化的寻优过程联系起来，给出一种新的最优化搜索算 教授提出的模拟光自然属性的智能优化算法，利用 法.这种算法将坐标空间设想为填充了具有不同折射 在可行域中填充正方形介质，模拟光的折射以及反 率的介质的空间，如图1所示，将搜索路径设想为光 射现象，通过最基本光学定律找到最优值，算法迭代 的传播路径，通过光的折射原理，使搜索方向趋向于 机理简单、收敛速度快，具有很强的并行计算能力. 目标函数值减小的方向，通过光的反射原理，改变搜 2010年，李焱等1给出了基于正六边形网络的光学 索方向，使得搜索在折射无法进行时继续下去 寻优算法，在高维迭代中具有良好的仿真效果，李加 莲等8]给出了光学寻优算法的基本理论证明，并与 其他算法进行了比较，完善了算法的理论体系.本文 通过正方形网络光学寻优算法的搜索机制形成初始 粒子群，加入混沌优化的思想，并引入“交换子”概 念，利用离散粒子群算法求解TSP问题，提出了一 种新的解决TSP问题的光学混沌粒子群算法. 1混合粒子群优化算法的构建 1.1旅行商问题以及标准粒子群算法 TSP的描述十分简单，即寻找一条最短的遍历 -2 N个城市的路径，其数学描述如下： 图1在可行域中填充介质 设有N个城市的集合C={c1,c2,…,cw},每2 Fig.1 Filling medium in feasible region 个城市之间的距离为d(c,c)∈R,其中c,C∈C 针对以下问题进行研究： (1≤i,j≤N),求使目标函数 minf八X),X∈ECRxR N- T。=∑(cT,cTw)+d(cTΠw,c） 式中：f(X)是正函数，即H(x,y）∈M,f(x,y)>0. X是可行解，M是f(X)的可行域，R×R是二维实数 达到最小的城市序列(c,cna,…,cnm),其中， 空间.P为第i次的搜索方向，h、?为网格步长.对 Π(1)，Π(2)，…，Π(N)是1,2，…，N的全排列， 1998年，Shi等9给出了标准的PS0算法的数 于第i次迭代，令搜索以P方向在矩形分块D:中 学描述：设搜索空间为D维空间，粒子数为n,第i 搜索到点X⑧=(x:,y:),并在X⑧点改变搜索方向， 到达X:+山点，方向的迭代关系满足：

·176 智能系统学报 第7卷 1)若in4≤1，发生折射，如图2(a)所示. 少的路径，光的传播在不同介质中速度不同，运用光 V: 学寻优的思想可以很容易地得到粒子群的一组性能 sin c;=U 良好的初始粒子，大大减少算法的迭代次数 sin i+1 Vi+l 定义1当前城市密度，从当前城市到其他未 式中：a为D中的入射角，ac+1为D+1中的折射角，： 被遍历过的城市的最短路径 为光在D:中的传播速度，可设定为D:中Xi+)= 定义2前沿城市密度.去除已经遍历的城市， (+1,y:+1)点的函数值.：+1为光在D+1中的传播速 剩余城市路径的平均值. 度，可设定为D+1中X+)=(+1y+1)点的函数值. 定义3TSP问题中的反射.从当前城市开始， 2)若+ina,>1,发生反射，如图2(b)所示. 随机选择一条与未被遍历城市的路径 定义4TSP问题中的折射.从当前城市开始， 0:=0i+1 选择与未被遍历城市之间最短的路径. 式中：a为D中的入射角，a+1为D1中的反射角. 光学寻优初始化初始值的过程如下： 图3~4是加入了多个临界面的水平以及竖直方向的搜 1)随机选择一个城市作为出发点，选择与当前 索路径光学寻优算法能快速找到最优搜索路径. 城市之间的最短路径城市作为下一个遍历点， 2)计算当前城市密度与前沿城市密度. 3)如果当前城市密度小于前沿城市密度，则发 生折射，选择与未被遍历城市之间最短路径城市作 为下一个遍历点；如果当前城市密度大于前沿城市 密度，随机选择一个未被遍历的城市作为下一个遍 历城市， 4)重复3)的过程直到所有的城市都被遍历. a)折射 b)反射 5)将每一个城市都作为起点，依据光学寻优的思 图2基于反射和折射搜索方向的更新 想形成V个城市序列，作为混沌粒子群算法的初值， Fig.2 Updating searching direction based on reflection and refraction 2光学混沌粒子群算法 2.1TSP问题中的混沌粒子群算法 梯 2.1.1TSP问题中混沌粒子群算法的相关定义 定义5交换子.2个城市序列oX:=[x,x 降 …]与X,=[a…xn],如果2个序列在相同 的位置，数值不相同，即x.≠.，称(x.,n)为城市 序列的交换子，即为V(x。x。) 图3增加多个临界面光路的更新 定义6交换序列.由交换子组成的序列V= Fig.3 Updating light line after adding [V1V2…Vn],其中n为2个城市对应序列相同，但 数值不同的位置个数 定义7粒子的位置.粒子的位置是由城市序 列X=[X,X2…X.]表示，m为城市的个数； 粒子的速度.粒子的速度V=[V。V,…Vm.], 其中Vm,表示交换子，速度为交换序列。 2.1.2交换子与交换序列的运算法则 图4增加水平竖直临界面 1)位置与交换子的加法. Fig.4 Adding horizontal and many critical surfaces 位置与速度的加法形成新的城市序列：设X= vertical critical surfaces [XX2…Xm]为城市序列，V(X,X)为交换，则 1.3TSP问题中的光学寻优思想 X=[X X2..X:X Xm]+Vi(xi,X)= 光学寻优算法遵循费马原理，费马原理表明，光 [XX2…XX:Xm] (1) 在介质中从一点向另一点传播时，总是沿着时间最 X=[XX2…XXXn]为新形成的城市序列

第2期 沈继红，等：求解旅行商问题的混合粒子群优化算法 。177. 例1： 公式变为： X[436215]+(1,2)=X2[346215]. V(k+1)=oV(k)+9(P:-X(k)+ 2)位置与位置的减法. 82(Ght-X,(k), 位置与位置的减法形成交换序列即生成新速 X(k+1)=f(x:(k))+V(k+1).(4) 度：V=X:-X,其中X、X为城市序号.先找到与 式中：9、2为(0,1)的数(x)为x(k)向量从小到大 第1个城市序列中第1个元素相同的第2个城市序 排列下标形成的向量函数，X(k)为当前城市序列，X: 列位置，形成交换子v(1,),然后将此交换子作用 (k+1)为新生成的城市序列，P为当前个体最好序 在第1个序列上得到新的第1个序列，再找到新的 列，G,为全局最好序列.P-X(k)=V,G 第1个城市序列与第2个城市序列数值相同的第1 X(k)=Vc表示为交换序列，9(P-X:(k)表示 个位置，形成交换子v(2,),依次进行下去，得到2 当概率小于，时发生交换操作，当概率大于9，不进 个城市序列的交换序列. 行操作，城市序列保持不变 例2： 2.2光学混沌粒子群算法步骤 X1[436215]-X2[562143]= 1)利用1.3中光学寻优的思想初始化粒子群， V((1,5)+(2,6)+v(4,6)+(5,6). 从每一个城市出发，得到N个初始值良好的城市序 3)交换子的数乘. 列：随机生成混沌序列Z(1)并运用函数f(x)得到 速度的数乘具有概率意义，例如V。=c·Va,其 城市序列X 中c∈[0,1]是一个常数，在计算V时，对V中的每 一维速度V生成一个(0,1)的随机数。 开始 =rand <e: (2) 0,其他， 运用光学寻优算法初 始化粒子群，找到一组 4)混沌思想. 性能优良的初始序列 通常一类非常简单却又广泛应用的混沌系统是 利用混沌优化思想 Logistic映，其定义如下u: 产生初始混沌序列 zk+1=uz(1-zk),k∈（0,1) (3) z并生成城市序列 式中：z为实值序列，u为参数，研究表明当3.571448≤ 进彳迭代找到种罪 u≤4时，该混沌映射处于混沌状态，把3.571448≤u≤4 中的Pn和G 称为混沌区域Logistic混沌映射所生成的序列具有如 下混沌特性：①非周期的序列；②该混沌序列不收敛； ③z.可以遍历整个(0,1)区域， 更新混沌序列生成新的城巾 序列.计算当前序列P与 本文取w=4,设城市数量为n,按照顺序随机地 G之间的交换序列，利用 生成(0,1)的n个随机数，构成向量序列Z(k)=[z 式(4)生成新的交换序列 甜 (k)2(k)…乙n(k)],将z1,z2,…,乙n按照从小到大 排列1,2，…，n的下标号构成城市序列X=[XX 判断是否满 N 的 足终止条作 …X,],按照式(1)生成向量，然后对Z(k+1)中元 素从小到大进行排列下标号1,2，…，n构成新的城 r 市序列X(+D=[X4+,X+2…X(a+.].混沌遍 计算生成 生成新的 新的城市序列 城巾序列 历的引入，有效地增加了城市序列的多样性. 更新粒子 的位置 例3： 输出最终的城巾序 Z(k)= 列并计算最短路径 [0.27850.54690.95750.96490.15760.9706]. 生成的城市序列为X=[412346],运用式(3)， 结束 Z(k+1)= [0.80370.99120.16270.13550.53110.1142]. 图5混合粒子群算法的流程 Fig.5 A flow sheet of mixed particle swarm algorithm 生成新的城市序列为X+1=[643512]. 针对TSP问题，结合混沌思想的粒子群的更新 2)如果满足最优条件，最短城市距离不再

·178. 智能系统学报 第7卷 变一或者达到最大迭代次数转到5)，如不满足条 2.4光学混沌粒子群算法收敛性分析 件对初始种群进行更新，找到个体最好位置P,以 V,(K+1)=oV:(k)+8(Pet-X(k))+ 及全局最好位置Gt 82(Gt-X:(k), 3)根据式(4)更新城市序列； X:(K+1)=f(x:(k))+V(k+1). ①根据式(1)和(3)计算混沌生成序列Z()并 根据混沌序列的更新以及例3可得f(x:(k) 运用函数f(x)得到新的城市序列X; 是线性映射，可以写成城市序列与交换子的线性组 ②运用例2的思想计算交换序列， 合的形式：fx:(k)=X(k)+Bv(k).Be[0,1],线 Pbon;-Xi(k)=Vp(k),Ghomt -X:(k)=VG(k) 性系统变成如下形式： ③根据式(2)计算p:(P-X:(k)+ V,(k+1)=oV:(k)+c(Pet:-X:(k)+ p2(G:-X:(k);p1、p2为执行操作的控制概率。 c2(G:-X:(k)）, ④根据以上3个结果结合式(4)得到新的城市 X:(k+1)=X:(k)+B:(k)+V:(k+1). 序列X(k+1). 为了方便计算与分析，首先将空间简化为一维 4)迭代次数增加，更新粒子的位置转到2) 空间，将模型转化为式(5)： 5)输出最优城市序列，并输出最短距离。 y:(t+1)=wov:(t)+9[Pet-,(t)]+ 2.3混合算法时间复杂度分析 82[Gke-x(t)], 算法的时间复杂度是对算法运行时间的度量， x:(t+1)=x:(t)+:(t)+:(t+1).(5) 用来表示算法的计算效率的高低。算法的时间复杂 令8=91+2，记Pbet=p:(t),Ge:=pg（t)， 度的大小在一定程度上反映了算法性能的优劣，忽 并对模型进行简化可得表达式： 略硬件及环境因素，假设每次执行时硬件条件和环 ":(t+1)=ov:(t)-x:(t)+9P:(t)+9P(t), 境条件是完全一致的.设城市数量为n,运行迭代次 x:(t+1)=(w+B)y:(t)+(1-8)x:(t)+ 数为m,则光学混沌粒子群算法的时间复杂度量级 9P:(t)+8Pg(t). 为0(m(2n2+1). 整理记为式(6)： 以下来说明该算法的时间复杂度数量级为O(m :(t+1)1 (6) (2n2+1)).根据混合算法的特点首先应用光学寻 x:(t) Pa(t) 优算法初始化城市序列，并应用混沌方法生成新的 城市序列，然后应用粒子群算法的核心思想不断地 更新城市序列直到满足条件 通过标准粒子群算法的数学描述可以将系统变 1)以一次迭代为例，城市数量为n,随机选取城 为离散线性系统，这里假定在t次迭代之后粒子找 市作为城市序列初始点，并应用光学寻优算法进行 到最优位置时，P、gm将保持不变，式(6)中 初始化，需要n(n-1)次运算，所以时间复杂度为 p(t)Pg(t)不随着时间变化. 0(n2-n). 定理1当w<1+B,B<91+92<20+2+B 2)应用混沌思想更新城市序列，对N个序列都 时，线性定常离散系统(6)渐近稳定，并且系统收 进行更新，时间复杂度为O(n). 敛 3)n个序列用来计算适应度函数的时间复杂度 0 为O(n),在此基础上进一步确定个体极值以及群 x,(t+1) 9:(t)+9pg(t) 体极值，计算交换子序列从而对每一个城市序列进 01+02 行更新，此步骤一共运行的时间复杂度为O(n2). 证明通过系统(6)以及模型(5)的表达式可 4)在一次迭代完成之后判断是否达到终止条 将x:(t)消去得到如下的差分表达式： 件，操作的时间复杂度为0(1). :(t+2)+(9+92-0-1):(t+1)+ 通过以上的分析可以得出1)~4)的时间复杂 (0-B):(t)=0. (7) 度为0(2n2+1),假设整体算法的迭代次数为m,则 对式(7)求特征方程可得 混合算法的整体运行时间为0(m(2n2+1)).因此 A2+（91+92-0-1)入+0-B=0. 整体算法的时间复杂度与城市的序列以及算法的运 为了对式(7)进行稳定性分析，用双曲线性变换将离散 行代数有关，如何在保证精确度的前提下减少迭代 次数也就成了控制算法运行时间的关键因素 系统转化为线性系统，令入=“+1带入式(7)得： 4-1

第2期 沈继红，等：求解旅行商问题的混合粒子群优化算法 ·179· (份+（线+--少}w-B=0 Gct,lim:(t)=0.无论参数Be[0,l]如何选择，在 满足参数条件(9)的情况下，本文提出的光学混沌 (91+92-B)2+(2-20+2B)u+ 算法收敛到全局最好位置，即城市序列收敛到全局 (20+2-91-92-β)=0. (8) 最好位置，交换子序列收敛到空操作 根据劳斯-赫尔维茨判据]，很容易得到表达式： 01+92-B>0, 3数值仿真 1-0+B>0, 20+2-91-92-B>0. 首先运用30个城市的标准TSP测试数据Oli- 可得，当0<1+B,B<01+92<2w+2+B时，线性 ver30对算法性能进行评估，运用蚁群算法、遗传算 定常离散系统(6)渐进稳定. 法、模拟退火方法、禁忌搜索方法1，混沌粒子群算 当系统(6)稳定， 法以及光学混沌粒子群算法，在最大迭代次数M,= -481+ 300的限定下分别对测试城市进行计算，根据定理1 x:(t) p(t) 设定91=0.5,92=0.5,0采用线性递减原则，t为 [t】=4w[0]+ 当前的迭代次数，0=0.6-(t/M,)*0.5,混沌系数 ,(t+1) x(0)J u=4.每种算法运行20次，对比如图6所示(X、Y的 B1+A+A2+…+A)P,)] 散点坐标图，取计算最好效果).各种算法计算的最 Ps(t) 好结果、最差结果以及平均迭代次数如表1所示. 表1对于Oliver30的算法效果对比 Table 1 Algorithm contrast effects of Oliver30 Oliver30 当参数满足条件(8)，1A|<1,所以， 智能优化算法 最优路径 最差路径 平均 迭代次数 蚁群算法 425.6491 430.8201 88 遗传算法 439.3595 472.4746 213 模拟退火 429.3803 435.7182 175 禁忌搜索 492.2025497.0792 195 粒子群优化算法 425.8201455.9862 253 (1-A)-BP,()1 混沌粒子群 424.5730441.1031 272 P() 光学混沌粒子群 423.7406423.7406113 B 从表1结果中可以看出，这4种经典智能算法精 (1-A)-B B (0+B-1) (1-0）】 度有所差异，在有限次迭代的情况下得到的最优解效 B8 B 果一般，如果设置较高的迭代次数，精度能达到满意 r921 0 0 的要求，不过迭代次数较高，往往容易收敛到局部最 92J B 92B 优点.本文构建的混沌粒子群算法以及加入光学原理 LB B- 的混沌粒子群算法具有良好的精度，对比于基本的粒 0 07 =2 子群优化算法改进效果显著，在最大迭代次数上限为 9B02B 300的情况下，可以找到精确的结果，其中光学混合 LB B 粒子群算法性能更为突出，每次运行都能找到最优值 0 281-9 423.7406.在迭代次数上，蚁群算法具有较快的收敛 p(t)+8p(t) 速度，但容易陷入局部最优点，影响算法的精度.同比 91+902 与其他的5种算法，光学混沌粒子群算法在收敛速度 有，()-2.tPO,,(0-0.当选 上有很大的优势.从图7中可以看出光学混沌粒子群 91+92 算法具有很强的收敛速度. 代次数足够大必然P=G,所以1mx:(t)=

·180 智能系统学报 第7卷 100 100 80 60 60 40 0 20 0 第300步最短距离为425.649 第300步最短距离为425.820 0 102030405060708090100 102030405060708090100 X (a)蚁群算法 (e)粒子群优化算法 100 100 80 60 60 20 第300步最短雨离为439.3595 第300步最短距离为424.573 0 102030405060708090100 102030405060708090100 (b)遗传算法5 ()混沌粒子群算法 100 100 80 80 60 60 40 40 20 20 第300步最短℉离为423.7406 第300步最短距离为429.3803“ 102030405060708090100 102030405060708090100 (g)光学混合算法 (c)模拟退火算法 图67种算法Oliver.30效果对比 Fig.6 Seven contrast figures of Oliver30 100 620 ·一禁忌搜索算法 文巾算法 580 80 混沌粒子群算法 蚁群算法 540 60 路500g a 40 460 20 第300步最短距离为492.202 420 0 204060 80100120140160180200 102030405060708090100 进化代数 子 图70 liver3.04种算法进化曲线 (d)禁忌搜索算法 Fig.7 Four evolutionary curves of Oliver30

第2期 沈继红，等：求解旅行商问题的混合粒子群优化算法 181 本文提出的光学混沌粒子群算法的GUI界面 实验相同，最大迭代次数300，每种算法计算20次 如图8所示，得到的最优城市序列为(28,27,26,25， 所得的数据。 24,15,14,8,7,11,10,21,20,19,18,9,3,2,1,6,5 表2对于51个城市问题eil51的算法效果对比 4,13,12,30,23,22,17,16,29),平均迭代113次迭 Table 2 Algorithm contrast effects of eil51 代找到最优解，混沌粒子群算法得到的最好结果为 eil51 424.6918,平均迭代次数为272，远远大于光学混沌 智能优化算法 平均 最优路径 最差路径 算法，无论是迭代时间、算法精度都要劣于加入光学 迭代次数 寻优思想的粒子群算法.光学寻优算法初始化的本质 蚁群算法 450.9815 455.8169 四 就是要减少迭代次数，提高算法精度，原因就在于用 遗传算法 467.9805 490.1634 259 光学寻优思想形成的初始解与最优序列之间部分区 摸拟退火 439.3299 444.6047 172 域序列是相似的，甚至是完全相同的，这样在运用粒 禁忌搜索 491.8765 544.4865 277 子群算法迭代时就减少了迭代次数.混沌方法具备的 粒子群优化算法 456.5339 487.7408 264 全局遍历性在保证算法的精度前提下，加强了算法跳 出局部最优点的能力，增强了算法的适用性 混沌粒子群 434.6222439.0065 289 光学混合粒子群 426.7229436.7741 156 在TSP城市规模增大的情况下，光学混沌粒子 群算法的优势得到明显体现，无论是算法精度还是 算法的收敛速度都要好于其他算法.从以上结果可 以看出本文提出的基于光学原理的混合粒子群算法 相比于其他优化算法具有良好的效果，能成功解决 中大型TSP路径优化问题并保持较高的精度，加入 的光学寻优思想能大大节约迭代次数，保证算法在 规定的迭代次数内找到最优解 470编 表3是对测试问题CH130的对比数据，CH130 是相对复杂的130个城市的TSP问题，最大迭代次 图8光学混合算法GUI效果图 数设定为500，每种算法运行20次，误差计算是对 Fig.8 GUI interface 比于CH130给出的精确解6110，应用最优路径计 表2是对测试问题eil51,参数设置与0 Dliver30 算得出，所有数据如表3所示。 表3对于130个城市问题CH130的算法效果对比 Table 3 Algorithm contrast effects of CH130 CH130 智能优化算法 最优路径 最差路径 平均 迭代次数 误差/% 蚁群算法 6417.9875 6430.9665 151 5.02 遗传算法 7118.2572 7322.3878 432 16.51 模拟退火 6350.4431 6471.0394 266 3.92 禁忌搜素 10516.1795 12258.2495 354 72.11 粒子群优化算法 8134.7704 8234.6089 407 33.13 混沌粒子群 6314.9633 6523.8705 425 3.34 光学混合粒子群 6210.4220 6256.5195 395 1.64 从结果可以看出，对于较大规模的TSP问题光 无论是从迭代时间搜索精度，还是误差大小同比于 学混合算法效果显著，误差在所有同类算法中最低， 其他算法都有很大的优势.与标准粒子群算法以及

·182 智能系统学报 第7卷 混沌粒子群算法相比，改进效果显著.图9为最优搜 [5]XIE Shenli,TANG Min,DONG Jinxiang.An improved ge- 索形成的TSP效果图 netic algorithm for TSP problem[J].Computer Engineering 7×10 and Application,2002,38(8):58-60. [6]SHEN Jihong,LI Yan.Light ray optimization and its pa- rameter analysis[C]//Proceedings of the 2009 International Joint Conference on Computational Science and Optimiza- tion.Kunming,China,2007:918-922. [7]沈继红，李焱.基于正六边形网格的光线寻优算法[C]/中 国运筹学会第十届学术交流会论文集.南京，中国，2010： 89-94. SHEN Jihong,LI Yan.Light ray optimization on hexagonal grid[C]//Proceedings of the 10th ORSC.Nanjing,China, 2010:8994. 图9应用光学混合算法求解CH130最短路径 [8]SHEN Jihong,LI Jialian.The principle analysis of light ray 6210.4220 optimization[C]//2010 Second International Conference on Fig.9 The shortest path 6 210.422 0 of CH130 using Computational Intelligence and Natural Computing.Wuhan, the algorithm in this paper China,2010:154-157. 4结束语 [9]SHI Y,EBERHART R C.A modified particle swarm opti- mizer[C]//Proceedings of the Congress on Evolutionary 本文提出了一种结合光学寻优算法、混沌思想 Computation.Anchorage,USA,1998:69-73. 的混合粒子群算法，通过光学寻优思想形成最优初 [10]ZHANG Guoping,WANG Zhengou,YUAN Guolin.A 值，利用加入混沌的粒子群算法成功解决了TSP问 chaotic search method for a class of combinatorial optimi- 题，该算法迭代次数少、收敛速度快，对比于其他智 zation problems[J].Systems Engineering Theory Prac- 能优化算法具有明显的优势，并用实验表明加入光 ice,2001,21(5):102-105. 学寻优思想的搜索方式大大减少了算法的迭代次 [11]梁艳春，吴春国.群智能优化算法理论与应用[M].北 数，并在一定程度上提高了算法的精度，为高效率解 京：科学出版社，2009：17-21. 决大规模TSP问题提供了新的思路 [12]郑大中.线性系统理论[M].北京：清华大学出版社， 2009:213-251. 参考文献： [13]ANDRIES P E.计算智能导论[M].北京：清华大学出 版社，2010：111-123 [1]KENNEDY J,EBERHART R.A discrete binary version of 作者简介： the particle swarm algorithm[Cl//Proceedings of the World 沈继红，男，1966年生，教授，博士 Multiconference on Systemic,Cyberetics and Informatics. 生导师，黑龙江省工业与应用数学学会 Piscataway,USA:IEEE Service Center,1997:4104-4109. 副理事长，黑龙江省教学名师.主要研 [2]CLERC M.Discrete particle swarm optimization[C]//New 究方向为系统优化与建模.完成科研课 Optimization Techniques in Engineering.Berlin:Spinger- 题12项，获得省级科研和教学奖5项. Verlag,2004:204219. 1996年获霍英东青年教师三等奖，主持 [3]高尚，韩斌，吴小俊，等.求解旅行商问题的混合粒子群 的《数学建模》课程获得黑龙江省精品课程，曾获得美国数 优化算法[J].控制与决策，2004,19(11)：1286-1289. 学建模竞赛一等奖8项，全国大学生数学建模竞赛一等奖1 GAO Shang,HAN Bin,WU Xiaojun,et al.Solving trave- 项，全国研究生数学建模竞赛一等奖1项.发表学术论文 ling salesman problem by hybrid particle swarm optimization 107篇. algorithm[J].Control and Decision,2004,19(11):1286- 王侃，男，1986年生，博士研究生， 1289. 主要研究方向为智能优化算法以及复 [4]HENDLASS T.Preserving diversity in particle swarm opti- 杂系统建模与仿真， mization[J].Lecture Notes in Artificial Intelligence,2003 (2718):155-199