第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