http://www.paper.edu.cn 混沌粒子群混合优化算法 王大均，李华平，高兴宝，赵云川 四川蜀渝石油建筑安装工程有限责任公司，四川成都（610017） 摘 要：粒子群优化算法（PSO）具有收敛速度快但易陷入局部最优点的特点，因此本文将 在结合混沌运动的遍历性、伪随机性和对初值的敏感性等特点的基础上，对粒子群优化算法 进行了改进，提出了一种基于混沌思想的粒子群优化算法（CPSO），该算法保持了群体多样 性，增强了 PSO 算法的全局寻优能力，提高了算法的计算精度，改善了收敛性和鲁棒性， 很大程度上避免了算法停滞现象的发生，是一种有效的优化搜索算法。 关键词：混合优化算法；混沌优化算法；粒子群优化算法 1. 引言 粒子群算法 PSO(Particle Swarm Optimization) 是 Kennedy J 与 Eberhart R 于 1995 年借鉴 鸟群和鱼群捕食过程的社会行为提出的[1]。该算法具有程序简单、控制参数少、寻优结果与 初值无关、且具有一定的并行性等特点，因此从开始研究到现在短短的十年时间里，表现出 强大的优化功能，被广泛应用到函数优化、神经网络训练、人工智能、模糊系统控制等领域。 PSO 作为一种更高效的并行搜索算法，非常适于对复杂环境中的优化问题的求解，成为目 前进化计算研究的一个热点。但是标准的粒子群算法表现出强烈的“趋同性”，对于单调函数、 严格凸函数或单峰函数，能在初始时很快向最优解靠拢，但在最优解附近收敛较慢，对于多 峰函数更易出现早熟现象以及运算量较大等缺点。 混沌学的诞生是 20 世纪人类科学史上继相对论和量子理论之后的第三次革命，混沌是 指在确定性系统中出现的随机状态，为非线性系统的一种演变现象，它不是由随机性外因引 起，而由确定性规则导致的对初始条件非常敏感的无固定周期的长期行为[2]。混沌运动能在 一定范围内按其自身不重复地遍历所有状态，初始值条件极其微弱的变化会引起系统行为巨 大变化。因此，本文将在对标准粒子群算法改进的基础上，将混沌思想引入到粒子群算法中， 避免了易陷入局部最优值的缺点，大大改善了粒子群算法的优化性能。 2. 粒子群优化算法的改进 2.1 标准粒子群优化算法 假设搜索空间是 D 维的，搜索空间有 m 个微粒，每个微粒的位置表示一个潜在的解， 微粒群中第 i 个微粒的位置用 → X i = ( x , x i 2 , i 1 , x )iD L 表示，第 i 个微粒的速度表示为 → V i → P i = = i ( v ( p ( v , 1 L , 2 i , v , p i 2 , i 1 , L 。 第 i 个 微 粒 经 历 过 的 最 好 位 置 ( 有 最 好 适 应 度 ) 记 为 )iD )iD ，称为个体极值 bestp 。整个微粒群迄今为止搜索到的最好位置记为 )gD ，称为全局极值 bestg 。对于每一个微粒，其第 d 维( )Dd ≤ ≤1 p , ， , p = → P p g 根据如下等式变化： L p , g 2 g 1 -1- 

t id − x t id ) + ( prc 22 t gd − x t id ) http://www.paper.edu.cn （1） v t 1 ⎧ + id ⎪⎪ x t 1 + ⎨ id ⎪ i = ⎪ ⎩ t = ω x t = id ,2,1 L ( v prc t + id 11 v t 1 + + id dm , ; = ,2,1 , D L 式中： ω——惯性因子； 1c 、 2c ——学习因子； 1r 、 2r ——[0,1]之间的均匀分布随机 数。 ，则微粒只有社会经验,收敛速度可能较快，但容易陷入局部最优点。如果 学习因子 1c 、 2c 是用来调整微粒的自身经验与社会经验在其运动中的权重。如果 1 =c 0 ,则 微粒没有群体共享信息，只有自身经验，因此一个规模为 m 的群体就因为个体间没有交互 而变成了 m 个单微粒的运行，一般很难得到最优解。 2 =c 0 2.2 改进的粒子群优化算法 为了平衡算法的全局搜索能力和局部搜索能力对惯性因子进行了改进，在标准粒子群优 化算法中，惯性权重ω是用来控制历史速度对当前速度的影响程度，平衡 PSO 算法的全局 搜索能力和局部搜索能力的。若ω较大，则微粒有能力扩展搜索空间，全局搜索能力强。 0=ω 时,微粒没有记忆性，根 若ω较小，主要是在当前解的附近搜索,局部搜索能力强；当 据式(1)，它将飞向个体最优位置和全局最优位置的加权中心，而处于全局最优位置的微粒 将保持静止。从寻优的整个过程来看，前期主要是扩展搜索空间，需要较大的ω；后期主 要是在最优解附近精细搜索，需要较小的ω；所以本文将ω从最大惯性权重到最小惯性权 重之间线性减小。 t ωω = max − ωω − max iter max min t （2） max iter ——最大迭代步数。 maxω ——最大惯性因子， minω ——最小惯性因子。 当微粒的飞行速度 maxV 较大时，有利于全局搜索，但有可能飞过最优解；当微粒的飞 行速度 maxV 较小时，微粒可在特定区域内精细搜索，但容易陷入局部最优，因此，必须对 微粒的飞行的最大速度进行限制。 V max V −< （3） V = max V −= v t id v 若 若 > max t id v ⎧ ⎪ ⎨ v ⎪⎩ t id t id max maxV 是常数，由用户设定,它决定了微粒在解空间中的搜索精度。 3. 基于混沌理论的改进粒子群混合优化算法 尽管改进的粒子群优化算法比标准的粒子群优化算法有了很大的改进，但是由于初始化 粒子的随机性，某些粒子的位置及其 bestp 接近群体的 bestg 时，这些粒子会因为它以前的速 度和惯性因子不为零而远离最佳位置而导致算法不收敛，当速度越来越小，接近于零时，种 群多样性就慢慢消失，粒子出现惰性，随着迭代过程的进行，其它粒子将很快聚集到这些惰 性粒子附近并停止移动，粒子出现停滞现象，导致算法的早熟，影响了算法的收敛性。为了 避免早熟，提高算法的适应性，使粒子群能构跳出这种停滞状态，本文将混沌思想引入到粒 子群算法中，在演化的过程中，当某些粒子群出现停滞现象时，通过某个特定格式迭代产生 -2- 

http://www.paper.edu.cn 混沌序列，然后通过载波的方式将混沌变量的值域放大到优化变量取值范围，进行进一步的 迭代，使算法收敛到全局最优点。 假设寻优问题的目标函数为： ,2,1 = L （4） ( )xfmin [ ] )i ba , i xn ; i ( i ∈ , 则基于混沌思想的粒子群优化算法（CPSO）的迭代过程为： S．1：给定算法的最大进化步数 max iter ，学习因子 1c 和 2c ，惯性因子的范围 maxω 和 minω ， 微粒的最大速度 maxV 。 S．2：随机产生 m 个微粒的初始位置 0 idx ，并将初始速度设为 vid 0 = U ( − 1,1 V ) max ，其中 )1,1−U ( 为均匀分布的随机数。 S．3：计算每个粒子的适应度 if ，并将粒子群的当前位置设为 bestp ，将适应度最优的 位置的粒子设为 bestg 。 S．4：判断算法是否满足收敛准则？若满足，则执行 S．9；否则，继续下一步。 δ<∆ if S．5：采用 if∆ 判定每个粒子是否停滞，如果在迭代中连续 cN 次满足条件 （其中 cN 为设定的常数，δ为设定的常数阀值），则执行以下步骤，否则跳转至 S．7。 f =∆ i f i − f P best f i （5） ( ) S．6：产生一个 D 维随机初始向量 y 0 dn , [ y = 1,0 y , L 2,0 , , y ,0 D ]′ ， , ∈dny ( )1,0 ，且各分 量间有微小差异，并根据 Logistic 方程 )dn ( 1− =′ y µ dn , y y ,1 + d n , 0 ≤ µ （6） ≤ 4 开始混沌序列，然后通过载波方式，根据 )1 ( y 2 , dn =′ R di , − + x y di , dn , （7） 将混沌迭代变量 dny , 的取值“放大”到一个以粒子当前位置 dix , 为中心，以 diR , 为混沌搜索半 ，如果是不动点，可加一小扰动 Cr ，C 为一较大 径的区域上（其中 { }75.0,5.0,25.0 , ∉dny 的正数）。然后跳转到 S．8。 S．7：根据式（1）更新粒子群的速度和位置。 S．8：若新粒子的适应度由于 bestp 的适应度，则将其设为 bestp ，然后在 bestp 与前一个 bestg 中选择适应度最优的个体设为 bestg 。 S．9：返回 S．4 执行。 S．10：输出结果，结束程序。其算法的迭代步骤如下： 4. 算法实例分析 这里主要通过对下面函数的分析来进一步分析算法的收敛性能。 max ts 0.. ⎧ ⎨ ⎩ ( ) xf x ≤≤ x += 9 *10 sin( x *7)5 + cos( x )4 （8） -3- 

2 max =ω iter ； 算法的初始化参数如下：学习 1 =c ；最大最小 2 =c 、 2 因子 5 ； 1 − 1.0=r ； 最 大 约 束 速 度 为 惯 性 因 子 为 4.0 min =ω V 1 max = 20=N 最大进化代数为 ；函数的维数维 max = 粒 子 的 规 模 数 为 1=D ； 25 ；混 3=µ ； 沌 优 化 参 数 为 ： = eδ 10=C 。 通过 Matlab 软件编程，运用基于 混沌理论的改进标准粒子群优化 算法，其结果如图 2 所示，从图中 我们可以清楚地看出，当迭代到第 5 步时算法就已经基本收敛于最 后得到的最优位置：X =7.8562， 此 时 得 到 的 函 数 最 大 值 为 ： max 度是及其迅速的，从中我们不难发 ( ) =xf 。其收敛速 .24 8553 现，作为一种新的优化算法，混沌 粒子群算法具有其它算法无法比 拟的优越性。 5. 结论 PSO 算法是一种新型的演化计 算方法，其算法简单，参数较少， 优 化 性 能 较 好 。 本 文 在 对 标 准 的 PSO 算法的改进的基础上，将混沌 理论引进粒子群算法中，利用混沌 的伪随机性、对初始值的敏感性和 遍历性来引导粒子搜索，提高种群 的多样性和粒子搜索的遍历性，使 因速度降低而失去搜索能力的粒子 继续获得搜索能力。并通过 Matlab 软件编程，将迭代过程以交互式界 面形式给出，算法的计算结果表明， 其优化性能得到了大大的改善，是 一种非常有效的优化算法。 http://www.paper.edu.cn 开 始 9.0 、 初始化参数： max iter ， 1c 、 2c ， maxω 、 minω ， maxV 随机产生 idv ， 0 idx 0 计算 if ，确定 bestp ， bestg 输出结果 是 计算 1+t idv ， idx 1+t 收敛？ ∆ if δ< 否 是 进行混沌迭代计算 更新 bestp ， bestg 图 1 混沌粒子群算法迭代步骤 图 2 混沌粒子群混合优化算法寻优性能 -4- 

http://www.paper.edu.cn 参考文献 [1] Kennedy J, Eberhart R 1995Proc.IEEE Int.Conf.Neu.Net.(Perth: IEEE) p1942 [2] 格莱克,张淑誉译.混沌:开创新科学[M].上海:上海译文出版社,1990. [3] Shi Y,Eberhart R.A modified particle swarm Optimization[C]. In: Proceedings of the IEEE Conference on Evolutionary Computation, Scoul, Korea, 2001:101~106 [4] Clerc M, Kennedy J. The Particle Swarm Explosion, Stability, and Convergence in a Multidimensional Complex Space. IEEE Trans. On Evolutionary Computation, 2002, 6(1) ：58 [5] 戴冬雪，王祁，阮永顺，王晓超. 基于混沌思想的粒子群优化算法及其应用. 华中科技大学学报（自然 科学版），2005，33（10）：53~56 [6] 郑鹏，郭鹃，杨为民. 一种嵌入局部混沌搜索的混合微粒群优化算法. 计算机仿真，2006，23（2）： 161~164 Hybrid Particle Swam with Chaos Optimization Algorithm Wang Dajun, Li Huaping, Gao Xingbao, Zhao Yunchuan Sichuan ShuYu petroieum Construction and Installation engineering CO.LTD, Chengdu, Sichuan, China (610017) Abstract Particle swam optimization algorithm (PSO) had quickly convergence but easily trapped into the local optimum. So this article will from the base of the chaos of enumeration, random and sensitivity for initial values, give a new better algorithm which based on the chaos of the particle swam optimization (CPSO), was presented through the improvement of particle swam optimization algorithm. This algorithm maintained the colony multiplicity, reinforced the PSO algorithm of global optimization, advanced computational precision, and improved the convergence property and robustness. Avoided algorithm stagnancy happed in more degree, so this algorithm was a availability of optimization. Keywords: Hybrid optimization algorithm; Chaos optimization algorithm; Particle swam optimization algorithm -5-