第１９卷第１期 兰，ｋｌ，ｌＩ业高等专科学校学报 Ｊｏｕｒｎａｌ ｏｆ Ｌａｎｚｈｏｕ Ｐｏｌｙｔｅｃｈｎｉｃ Ｃｏｌｌｅｇｅ Ｖｏ１．１９ Ｎｏ．１ ２０１２年２月 Ｆｅｂ．２０１２ 文章编号：１００９—２２６９（２０１２）０１—００３５—０３ 基于单纯形和粒子群优化的搜索算法 甘建强 ，阮 佶 ，李 晶 （１．甘肃建筑职业技术学院基础科学部，甘肃２．兰州交通大学自动化与电气工程学院，甘肃兰州兰州７３００５０； ７３００７０） 摘要：在综合分析单纯形算法与粒子群算法优缺点的基础上，将单纯形算法与粒子群算法相结合， 提出了一种单纯形，粒子群混合算法，有效地避免了原有两种算法的缺陷，提高了对目标函数的搜 索效率与质量，并用试验函数验证了算法的可行性． 关键词：单纯形法；粒子群法；搜索算法 中图分类号：Ｏ２１１．６７ 文献标志码：Ａ 本文介绍了一种基于将单纯形和粒子群混合 进行求解的算法，无需求导，在此基础上利用验证 １）以随机的方式，初始化族群中每一个粒子 的初始速度及初始位置． 函数进行了寻优验证，表明了这种算法的可行性． ２）依据目标函数计算其适合度（Ｆｉｔｎｅｓｓ），来 评估粒子的优略． ３）检查每个粒子的适合度，若比Ｇｂｅｓｔ适合 度好，则以粒子目前的位置取代Ｇｂｅｓｔ． ４）依据式（１）和式（２）更新每一个粒子的速 度与位置． ＝ ＋ｃ１×ｒａｎｄ（）×（Ｐ 一 ）＋ｃ２× １粒子群算法 粒子群最优化算法最早由Ｋｅｎｎｅｄｙ ａｎｄ Ｅｂｅｒ— ｈａｒｔ（１９９５）所提出，为一种具有群体智慧（Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｃｅ）且属于多点搜索的优化算法，源自生 物行为观察学家对鸟群捕食及逃避天敌所演化出 的社会行为研究 。Ｊ，例如鸟群根据找寻离食物最 近的鸟的周围区域及根据自身飞行经验随机搜寻 食物所在位置，以增加觅食成功的机率． 在此仿生物技术的优化算法中，其每个候选解 （Ｃａｎｄｉｄａｔｅ Ｓｏｌｕｔｉｏｎ）即代表一个粒子（Ｐａｒｔｉｃｌｅ），而 每个粒子皆有属于自身的个人最佳经验记忆值 ｒａｎｄ（）×（Ｐ 一 ）， ＝ ＋ ． （１） （２） Ｖｉ为第ｉ个粒子的速度，Ｖｉ会受到 的限制， 以防止粒子过分移动，而超出搜寻的空间；ｃ 、Ｃ 为 学习因子或加速常数；ｒａｎｄ（）为介于０到１之间的 随机数；ｐ 为第ｉ个粒子的ｐｂｅｓｔ；ｐ 为ｇｂｅｓｔ； 为第 ｉ个粒子目前所在的位置． （Ｐｂｅｓｔ），这个记忆值记录个体到目前为止所看过 最好答案的经验，整个粒子群也有一个群体最佳经 验记忆值（Ｇｂｅｓｔ），Ｇｂｅｓｔ则是记录到目前为止整个 演算法所搜寻到最佳的答案经验，而每个粒子都会 ５）检查所预设的任何终止条件，若判断为否， 则转至步骤２），判断为是，则转至步骤６）． ６）结束，输出最优解或最近似解． 受到自我认知及生物群体约束，因此粒子群中的粒 子个体并非完全独立演化，而是受其自身及群体记 忆的影响，这是粒子群最佳化能达到全区最佳化的 关键所在．其调用步骤如下： 收稿日期：２０１１—１１－０８ 作者简介：甘建强（１９７２一），男，江西抚州人，副教授 ２单纯形算法 单纯形算法是应用规则或不规则的几何图形， 计算每个几何体的顶点的函数值，根据函数值大小 ・３６・ 兰州工业高等专科学校学报 第１９卷 和分布来判断目标函数的变化趋势，其后遵循赋予 算法的既定规则来寻优的方法．一个单纯形表示一 个几何体在ｎ维情况下是由１７，＋１个点组成，这些 点可以相互连接成线段，也可以是多边形面或多面 体．二维空间中的单纯形即为三角形．而三维空间 中的单纯形是一个四面体． 单纯形法搜索算法的基本思想是：例如，在非 线性目标函数中有ｔ个待估参数，按照既定规则选 取ｔ＋１组近似值，构成初始单纯形，比较这ｔ＋１组 数，剔除和目标解最远的值，然后按照换点规则换 人一组新的搜索解，用新的搜索值与其余的ｔ组构 成一个新的单纯形，如此反复计算比较去除最差 解，获取近似解，直至目标函数值达到给定的精度 并且逼近极小值为止，这时与目标函数最小值相对 应的那组参数近似解即为目标函数的最优解． 单纯形算法的优点是能够直接快速地搜索到 目标值，而且对大型或复杂的函数求极值，不会出 现收敛不稳定的情况．但单纯形法也有很大的一个 缺陷是对于目标函数有多个局部极小值时，收敛结 果会随着初值的选取而得到不同的结果，因而容易 陷入局部极值． ３单纯形一粒子群算法的实现 针对单纯形算法和粒子群算法的优缺点，考虑 将两种算法的优点合理的结合起来，这种算法的基 本思想是首先利用单纯形算法得到目标函数的局 部最优解，再利用粒子群算法的突跳性搜索（不容 易陷入局部极值）得到新的初始解，使它能跳出局 部极小点，同时结合范围搜索算法使单纯形算法能 不会跳过全局最优解陷入下个局部极值 ．以下 是混合算法的搜索步骤． １）给定随机初始解，确定初值的种群适应度 来判断算法的收敛条件是否满足，若是则结束搜索 并输出结果，否则进行下一步骤． ２）由当前状态，在ｇ／，维单纯形上附加随机扰 动生产ｎ个新状态与原状态构成有ｎ＋１个顶点的 凸多面体． ３）利用单纯形法进行ｔ步搜索后终止，将当 前的最优解作为粒子群算法的初值，训练活动因子 和加速常数来获取适应度从而产生新状态，以一定 概率接收新状态． ４）判断粒子群算法的学习因子是否稳定，若 是，可按照粒子群规则定义步长和加速常数，如没 有稳定，则转步骤２）． ４算法分析 利用３种优化算法对此函数进行寻优，比较３ 种算法的优略． ４．１ 优化函数１ ，Ｙ）＝ ＋Ｙ 一０．３×ＣＯＳ（３＂ｒｒｘ）＋０．３× ＣＯＳ（４，ｔｒｙ）＋０．３， ，Ｙ∈［一１，１］． （３） 函数最优解为一０．１８４ ８，局部极值点与最小 值的差值较大，较容易找到最优解（如图３所示）． 利用三种算法的优化结果如表１所示． 图１ 函数（３）图像 表１ ３种算法结果和消耗时间比较 初值 堡鱼篁堡 最优解耗时／ｓ 从表１的结果可以看出，单纯形方法反而较粒 子群算法和混合算法的效率更好，这主要是由于原 函数不存在局部极值点的情况，越简单的算法效率 越好． 下面对存在多个局部极值点的函数进行优化． ４．２优化函数２ ５ ｌ厂（ ， ）＝｛∑ｉｃｏｓ［（ｉ＋１） ＋ ］）× 第１期 ５ 甘建强：基于单纯形和粒子群优化的搜索算法 ・３７・ ｛∑ｉｃ。ｓ［（ ＋１）ｙ＋Ⅲ， ，Ｙ∈［一１０，１０］・ ＝１ ５ 结语 单纯形．粒子群混合算法将两者的优点有机的 结合起来，既具有较好的搜索效率，又可以收敛至 全局最优解，计算实例验证了该混合算法具有全局 寻优的能力．但是，混合算法的改进还有很多的办 法，哪种办法能达到更有效的搜索效率还需继续探 索．同时，对更为复杂的函数的寻优效果还需在长 （４） 该优化函数有ｌ８个全局最小值，最优解为 一１８６．７３，同时还有７６０个局部最小值，函数图像 如图２，利用三种算法的优化结果如表２所示． ４Ｏ０ ｔｅｒｓ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｃｈａｏｓ ａｌｇｏｒｉｔｈｍ ｌ Ｊ Ｊ．Ｊｏｕｒｎａｌ ｏｆ 图２函数（４）图像 Ｅｌｅｃｔｒ０ｎｉｃ ＭｅａｓｕｒｅＪｎｅｎｔ ａｎｄ Ｉｎｓｔｒｕｍｅｎｔ２００７，２１（４）： ，表２ ３种算法结果和消耗时间比较 ５９＿６２． 初信 望丝 ＿二 垫王壁 ■ 堡盒篁鳖 一［３］Ｄｕａｎ Ｑ，Ｇｕｐｔａ Ｖ Ｋ，ＫＳｏｒｏｏｓｈｉａ Ｓ．Ａ ｓｈｕｆｆｌｅｄ ｃｏｍ一 ＝蕊 ｐｌｅｘ ｅｖｏｌｕｔｉｏｎ ａｐｐｒｏａｃｈ ｆｏｒ ｅｆｆｅｃｔｉｖｅ ａｎｄ ｅｆｉｆｃｉｅｎｔ ｏｐｔｉ一 ｍｉｚａｔｉｏｎ［Ｊ］．Ｏｐｔｉｍｉｚａｔｉｏｎ Ｔｈｅｏｒｙ Ａｐｐｌｉｃａｔｉｏｎ，１９９３，７６ （一２，９）一８９．７３ ５．５６—１８７．１３ ２．６６—１８６．５４ １．１３ １ １ ： ： ：！ ： ： 墅：： ：！ ：！！ ：兰 ：！！ （３）：５０１－５２１． 由表２可以看出单纯形法容易受初值的影响 而陷入局部最优解，粒子群算法虽然可以获取最优 解，但是消耗时间较长，但利用粒子群算法和单纯 形结合的混合算法可以高效的获得全局最优解．从 算法实验中可以看出，单独的单纯形和粒子群算法Ｅ４］ Ｋｅｎｎｅｄｙ Ｊ，Ｅｂｅｒｈａｒｔ Ｒ．Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｐｒｏｃｅｅｄ一 ｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｃｅ ｏｎ Ｎｅｔｗｏｒｋｓ ［Ｍ］・Ｐｅｒｔｈ，Ａｕｓｔｒａｌｉａ １９９５：１９４２—１９４５・ ［ ］Ｋ。彻ｅｄＹ Ｊ，Ｗ Ｍ－ｓｐｅａｒｓ 砒 ｈｉ“ｇ ａ１ｇｏｒｉｍ ｔｏ Ｐｒｏｂ‘ ｌｅｍｓ：Ａｎ Ｅ Ｐ。ｒｉｍｅｎ ａ１ Ｔｅｓｔ ｏｆ ｔｈｅ Ｐ ｎｉｃ ｅ ｓｗ Ａ ．ｎｄ 要搜索更多的点，所以需要消耗更多的时间．尤其当 函数更复杂时，收敛更慢，而混合算法因为增加了跳 转函数而减少了很多不必要的搜索时间，比较快速 的找到目标函数的最优解，大大缩短了计算时间，这 一ｏ ｎｔｈ ｅ Ｍｕｌｔｉｍｏｄ ａｌ Ｐｒｏｂ ｌｅｍ 。ｆｈＩＥＥＥＩ ｃ。ｅｎｃｅ。 Ｅ ｖｏｌｕ ｔｉ。 ａｒｙ ｃ吣 ｔａｔｉ。 ．１９９８：３３２－３４８． ［６］杨晓华，陆桂华，郦建强．混合加速遗传算法在流域 ．模型参数优化中的应用［Ｊ］水科学进展，２００２，１３ （３）：３４０．３４４． 点在更为复杂的函数中将表现的更加明显． Ｔｈｅ Ｓｅａｒｃｈ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍｓ ａｎｄ Ｓｉｍｐｌｅｘ Ｍｅｔｈｏｄ ＧＡＮ Ｊｉａｎ—ｑｉａｎｇ ，ＲＵＡＮ Ｊｉｅ ，ＬＩ Ｊｉｎｇ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｂａｓｉｃ Ｓｃｉｅｎｃｅ，Ｇａｎｓｕ Ｃｏｎｓｔｒｕｃｔｉｏｎ Ｖｏｃａｔｉｏｎａｌ Ｔｅｃｈｎｉｃａｌ Ｃｏｌｌｅｇｅ，Ｌａｎｚｈｏｕ ７３００５０，Ｃｈｉｎａ； ２．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ａｕｔｏｍａｔｉｏｎ ａｎｄ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｌａｎｚｈｏｕ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ ７３００７０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ａｄｖａｎｔａｇｅｓ ａｎｄ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅ ｓｉｍｐｌｅｘ ａｌｇｏｒｉｔｈｍ ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ａｌｇｏｒｉｔｈｍ ｉｓ ｃｏｍｐｒｅ— ｈｅｎｓｉｖｅｌｙ ａｎａｌｙｚｅｄ．Ａ ｓｉｍｐｌｅｘ ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｅｆｆｅｃｔｉｖｅｌｙ ａｖｏｉｄ ｔｈｅ ｏｒｉｇｉｎａｌ ｄｅｆｅｃｔｓ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ａｎｄ ｉｍｐｒｏｖｅ ｔｈｅ ｑｕａｌｉｔｙ ａｎｄ ｅｆｉｃｉｅｎｃｙ ｏｆ ｓｅａｒｃｈ ａｌｇｏｒｆｉｔｈｍ．Ｔｈｅ ｆｅａｓｉｂｉｌｉｔｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｗａｓ ｖｅｒｉｆｉｅｄ ｗｉｔｈ ｔｅｓｔｓ． Ｋｅｙ ｗｏｒｄ：ｓｉｍｐｌｅｘ ａｌｇｏｒｉｔｈｍ；ｐａｒｔｉｃｌｅ ｓｗａｒｍ ａｌｇｏｒｉｔｈｍ；ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ