第３９卷第１期 ２０１２年２月 应 用 科 技 Ａｐｐｌｉｅｄ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｖ＿０ｌ＿３９．Ｎｏ．１ Ｆｅｂ．２０１２
ｄｏｉ：１０．３９６９￣．ｉｓｓｎ．１００９＝６７１Ｘ．２０１１１１００４
一种改进的混沌粒子群优化混合算法
钱晓山
１．宜春学院物理科学与工程技术学院，江西宜春，３３６０００ ２．中南大学信息科学与工程学院，湖南长沙，４１００８３
摘要：提出了一种改进的混沌粒子群优化混合算法．该算法利用信息交换机制将两组种群分别用差分进化算法和 粒子群算法进行协同进化，并且将混沌变异操作引入其中，加强算法的局部搜索能力．通过对３个标准函数进行测 试，仿真结果表明该算法与差分进化粒子群优化（ＤＥＰＳＯ）算法相比，全局搜索能力和抗早熟收敛性能大大提高． 关键词：混合算法；差分进化；粒子群优化；协同进化；混沌变异；早熟收敛 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１００９．６７１Ｘ（２０１２）０１．０００５．０４
Ａ ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ｃｈａｏｔｉｃ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ
ＯＩＡＮ Ｘｉａｏｓｈａｎｌ， １ １
１．Ｃｏｌｌｅｇｅ ｏｆ Ｐｈｙｓｉｃａｌ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ，Ｙｉｃｈｕｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｙｉｃｈｕｎ ３３６０００，Ｃｈｉｎａ ２．Ｓｃｈｏｏｌ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｅｎｔｒａｌ Ｓｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ ４１００８３，Ｃｈｉｎａ
Ａｂｓｔｒａｃｔ：Ａ ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ｃｈａｏｔｉｃ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｓ ｐｒｏｐｏｓｅｄ．Ｂａｓｅｄ ｏｎ ｔｈｅ ｉｎｆｏｒｍａｔｉｏｎ ｅｘｃｈａｎｇｅ ｍｅｃｈａｎｉｓｍ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｕｓｅｓ ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ａｌｇｏｒｉｔｈｍ ｔｏ ｍａｋｅ ＣＯ—ｅｖｏｌｕｔｉｏｎ ｆｏｒ ｔｗｏ ｇｒｏｕｐｓ ｏｆ ｐｏｐｕｌａｔｉｏｎｓ，ａｎｄ ｔｈｅ ｃｈａｏｓ ｍｕｔａｔｉｏｎ ｉｓ ｉｎｔｒｏｄｕｃｅｄ ｉｎｔｏ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｔｏ ｅｎｈａｎｃｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｌｏｃａｌ ｓｅａｒｃｈ ｃａｐａｂｉｌｉｔｉｅｓ．Ｕｓｉｎｇ ｔｈｒｅｅ ｓｔａｎｄａｒｄ ｆｕｎｃｔｉｏｎｓ ｔｏ ｔｅｓｔ ｉｔ，ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ，ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ（ＤＥＰＳＯ）ａｌｇｏｒｉｔｈｍ，ｇｌｏｂａｌ ｓｅａｒｃｈ ａｂｉｌｉｔｙ ａｎｄ ｒｅｓｉｓｔａｎｃｅ ｔｏ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ ａｒｅ ｉｎｃｒｅａｓｅｄ ｇｒｅａｔｌｙ． Ｋｅｙｗｏｒｄｓ：ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍ；ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ ｏｐｔｉｍｉｚａｔｉｏｎ；ｐａｒｔｉｃｌｅ ｓｗａｒｍ；ＣＯ—ｅｖｏｌｕｔｉｏｎ；ｃｈａｏｔｉｃ ｖａｒｉａｔｉｏｎ；
ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ
由ＰｒｉｃｅＩｌｌ首先提出的一种基于种群并行随机搜索
的新型进化算法——差分进化算法，对当前种群进行 重组、变异和选择操作产生新一代种群，并逐步使种
群进化，实现全局最优解的搜索，已成功应用于函数
优化、模式识别和工程领域．但是该算法在优化迭代
后期接近最优解时收敛速度缓慢，易陷入局部最优． 粒子群优化算法是基于群体的进化计算技术，其思想
来源于人工生命和演化计算理论，是一种基于种群搜 索策略的全局优化进化算法【２】，具有概念简单、容易
实现等特点，已成功应用于函数优化、图像处理、负 荷预测、工业过程控制等领域【２ 】．虽然它在进化初期
收稿日期：２０１１－Ｉ１一Ｏ２． 基金项目：国家自然科学基金资助项目（６０８７４０６９）；国家８６３计划资 助项目（２００９ＡＡ０４Ｚ１２４，２００９ＡＡ０４Ｚ１３７）． 作者简介：钱晓山（１９８０．），男，博士研究生，主要研究方向：复杂过 程信息处理与优化建模，Ｅ—ｍａｉｌ：ｑｉａｎｘｉａｏｓｈａｎ＠１２６．ｃｏｍ． 收敛速度陕，但在进化后期容易陷入局部极小点、收 敛速度慢［ 引，算法所能达到的精度较差．针对两者的
缺点，笔者在文献［９】的基础上，将混沌变异操作引入
其中，提出了一种混沌差分进化的粒子群优化算法．
该算法利用信息交换机制将两组种群分别用差分进化 算法和粒子群算法进行协同进化［１们，并将具有遍历和
随机特陛的混沌机制引人其中，进一步加强算法的局 部搜索能力．采用３个标准函数进行测试，仿真结果
表明该算法与ＤＥＰＳＯ算法相比，全局搜索能力和收
敛速度有了大大提高．
１混沌粒子群算法及其改进
１．１混沌系统
混沌运动是存在于非线性系统中的一种较为普遍 的现象［¨］
，混沌虽然貌似随机，却隐含着精致的内在 应 用 科 技 第３９卷
结构，具有遍厉陛、随机Ｉ生、规律性［】２］等特点，可以
在足够长的时间内，遍历相空间中所有状态．因而混 沌成为优化搜索且能避免陷入局部极小的一种新颖的
优化技术，具有全局性的优点． 混沌系统动力学模型种类繁多，这里选用一种最 为简单的一维非线性映射模型：
，Ｏ＋１）＝ ，（ ）（１一，（ｆ）），ｔ＝ｌ，２，…；ｌ（ｏ）∈【０，１】．（１） 在优化过程中，利用该映射产生的混沌变量Ｚ（ ） 进行搜索，搜索过程按混沌运动自身的规律进行，其 随机Ｉ生保证了大范围搜索能力，遍历性使算法按系统 自身的规律不重复地遍历所有可能状态，有利于克服
一般随机算法中以分布遍历性搜索带来的局限Ｉ生．
１．２混沌粒子群算法及其改进
粒子群算法采用速度—位置搜索模型，群体中第ｉ 个粒子在Ｄ维解空间的位置为 ＝ ｆ１，Ｘｆ２，…，ｘｉＤ），速度
为 ＝（ １，ｖ ，…， ｆＤ），当前时刻的个体极值记为Ｐｂ ，
全局极值记为Ｇｂ吲．在每次迭代中，粒子跟踪个体极 值、全局极值和自己前一时刻的状态来调整当前时刻
的位置和速度，迭代公式如下： （七＋１）＝ （ｋ）＋Ｃ （ 。 一 （ ））＋ Ｃ２ ：（ 一 （后））； （２）
（七＋１）＝ （七）＋ （｜ｊ｝＋１）． （３）
式中： ｝）、Ｖ（ｋ＋１）、 、坝斛１）分别是粒子当前时
刻、下一时刻的速度和位置；这里只１、 ２、ｃ１、Ｃ２、
是影响粒子群优化（ＰＳＯ）算法收敛的重要参数，然 而 ｌ是【０，１］之间的随机数，不具备遍历特眭，这里引
入具有遍历特陛的混沌机制，改进ＰＳＯ的全局收敛 性，尺ｌ、 ２选择如下：
Ｒ（尼＋１）＝４Ｒｉ（后）（１一Ｒｉ（尼））． （４） 式中：Ｒｉ（尼）∈（０，１），ｉ：１，２． Ｃ１、Ｃ２是学习因子，通常取为２；Ｗ是权重因子，
为加快收敛速度，其值应随算法迭代的进行而减小，一 般定义为
Ｗ＝ ＋（％一Ｄ）（ 一 ）／ ．（５） 式中： 、 分别为最大、最小权重因子 为当
前迭代次数， 为总的迭代数．
另外，为了提高ＰＳＯ算法的收敛速度和收敛精 度，提高解的质量，降低早熟收敛的比率，引入末位 淘汰机制，其基本思想为：每次进行适应值计算后，
选择适应值最小的微粒淘汰，再重新生成一个新的微
粒，这样一直有新的微粒持续不断地补充到群体中来， 保持种群的多样性． ２混沌差分进化算法
２．１差分进化算法
差分进化算法是一种连续空间全局优化启发式算
法．它与标准遗传算法相同的是包含选择、交叉和变 异３个操作，与标准遗传算法不同的是它采用由变异到
交叉，再到选择的操作顺序． ＤＥ／ｒａｎｄ／ｌ／策略㈣是应用差分进化算法来解
决问题的首选方法，在文中数值试验中即采用了这个
版本，对于一个最小化问￣ｍｉｎＦ（ｘ），ＤＥ从包含 个候
选解的初始种群 开始，卢Ｉ，２，…， ，式中堤种群数， ｆ为当前代．在变异操作中，任一随机ｌ， ｒ矢量根据式
（６）所产生，其中，．１，ｒ２，ｒ３∈｛１，２，…， 是随
机数，ＦＥ［０，２］为加权因子．
ｖｊｔ＝ ｔｌ＋Ｆ、，ｔ２＋ ３）． （６）
在杂交操作中，新种群 由随机矢量 和目标矢量
共同产生．
． １ ，ｉｆ ｒａｎｄｂ（ｊ） ＣＲ ｏｒ Ｊ＝ｒａｎｄｒ（ｉ）；，叶、 ａｌｌ， 一、＼，／ ” ｌ ，ｉｆ ｒａｎｄｂ（ｊ） ＣＲ ａｎｄ Ｊ≠ｒａｎｄｒ（ｉ）．
式中： ∈［１捌，ｒａｎｄｂ（ｊ）∈【０，１］是同一随机数发生器
的射个值，ＣＲ∈［０，１］是变异概率，ｒａｎｄｂ（ｊ）∈ ［１，
２，…，Ｄ】是随机选择指数，它确保Ｘｉｒ能从 ｒ中得到至
少一个参数．选择操作中采用贪婪策略．
“：』 ’，ｉｆ （ ’）≤ （ ）； （８） ’ Ｉ
， ｅｌｓｅ．
式中 （ ）代表适应度函数．
２．２混沌差分进化算法
混沌差分进化（ｃｈａｏｓ ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ，ＣＤＥ）
算法中混沌搜索的基本原理是在每一代中用ＤＥ搜索 到最佳个体 。 在 的附近再进行七次混沌搜索，
得到ｋ个个体，在ｋ个个体中找出适应度值最佳的个
体 ｓｔ．若 ’ｂ。 适应度值比 好，则用坂ｂｅｓ 的 适应度值取代‰的适应度值，并将 ｌｂ。 随机取代
种群中的某个个体后返回；若溉ｂ。 适应度值比 鳅
差，则直接返回．在‰附近进行混沌搜索，即
ｘｋ＝ｘｂｅｓｔ＋ａＹｋ． （９） 式中：Ｙ 是式（９）的解， 为调节因子．由式（９）
可知，当初值Ｙ１为（０，１）时，式（９）的解全为正解．
引入调节因子 可使 朝正、反２个方向变化， 取
值如下：
第１期 钱晓山：一种改进的混沌粒子群优化混合算法
ｆ １， 一 ｉｆ ０．５：
ｅｌｓｅ． （１０、 ／・ ＝∑ｉ ・ （１１）
式中 为（０，１）中一个均匀分布的随机数．
３ 混沌差分进化的粒子群混合算法
３．１ 混合算法的收敛性分析 文献［１４］详细地分析了粒子群算法的粒子运动轨 迹收敛性，文献［１５】对进一步分析了引入混沌机制的 粒子群优化算法粒子速度对算法收敛ｌ生的影响且给出 了证明．关于差分进化算法的收敛性和证明详见文献 ［１ ６］，差分进化算法采用贪婪搜索策略进行选择操作， 收敛速度较快容易陷人局部最优，文中将混沌机制引
入的差分进化算法在保证算法收敛的前提下，虽然减 缓了收敛速度但增加了算法的遍历性和随机陛，使得 算法跳出局部最优从而达到全局最优．因此对于两种 群的协同进化混合算法也收敛．
３．２混合算法步骤
利用信息交换机制，将２个改进的算法融合进行
协同进化，构成新的混沌差分进化粒子群算法
（ＣＤＥＰＳＯ），具体步骤如下： １）基本参数初始化设置，包括：群体规模 、
最大迭代次数 、求解精度 、最大陨性权重ｗｍ
最小惯性权重 控制因子 、加速因子Ｃｌ和Ｃ２、 缩放因子Ｆ、变异概率ＣＲ．
２）将群体等分成２个种群 ＤＥ和尸ｃＰｓｏ，且２
个种群初始化的位置分别位于不同区域．
３）设置迭代计数器ｔ＝０． ４）根据式（２卜（５）对ＰＣＰｓｏ群体中所有个体进
行速度、位置更新．
５）根据式（６）一（１０）对 ＤＥ群体中所有个体 执行变异、杂交和选择操作．
６）选出ＰＣＤＥ群体中最佳个体Ｇ ｂＣ哪ＤＥ．
７）选出尸ｃＰｓｏ群体中最佳个体ＧｂｅＣＰＳ。． ８）比较 ＣＤ。 Ｅ、（￣ｂＣＰＳ。的优劣，选择最佳个体作为
ＰＣＤＥ和尸ＣＰｓｏ下一代进化依据．
４实验仿真及分析
下面将通过３个典型函数优化问题（求解最小值） 来测试文中算法的性能，同时与文献［１］的算法进行比
较． １）Ｓｐｈｅｒｅ函数： 全局最优点： ＝０，ｆ１（ ）＝０，一１００ １００．
２）Ｒｏｓｅｎｂｒｏｃｋ函数：
ｆ２（ ＝ １００× ＋ －ｇ） ＋ 一Ｄ ），一３０＜ｘ￣≤３ｏ．（１２） ｉ＝１ 其最优状态和最优值为
ｍｉｎｆ（ｘ ）＝ｆ（１，１，…，１）＝０
３）Ｒａｓｔｒｉｇｒｉｎ函数：
∽＝∑（＃一ｌＯｃｏｓ（２￣）＋１０），一５．１２＜ｘ￣ ５．１２．（１３） ｉ＝１ 其最优状态和最优值为
ｒｒｆｉｎｆ（ｘ ）＝厂（０，０＇…，０）＝０．
仿真分析实验使用主频２．８ＧＨｚ、内存１ ＧＢ的
计算机，采用Ｍａｔｌａｂ ７．０程序．实验在３０维空间中进
行，每种算法运行５Ｏ次．对于所有实验，ＣＤＥＰＳＯ和
ＤＥＰＳＯ算法的实验参数设置参考文献【９］．其中
＝０．９，ｗｍｉｎ＝Ｏ．４，Ｃ１＝ ＝０．２，ＣＲ＝Ｏ．８，Ｆ＝０．５．两种 算法的种群规模均设为５０，迭代上限为１ ５００次．上 述３个函数的实验结果如表１以及图ｌ～３所示．
表１测试结果分析
趔
’茛
闭
蜊
图１ Ｓｐｈｅｒ
ｅ函数寻优过程比较