新的混合智能优化算法及其多目标优化应用

( S ta te K ey L abora tory of Industria l C on trol T echnology, Zh ejiang U niversity, H angzhou Zhejiang 310027 , C hina )
Abstract : A fter ana lyz ing the disadvantages of the slo w er converg ence property and low er accuracy in A rtificia l F ish Sw ar m A lgor ithm (A FSA ), a ne w hybrid inte lligent opti m ization a lgor ithm w as propo sed based on phased opti m ization and variab le para m ete r opti m ization as w ell as so m e relevant rules in tabu search a lgor ithm. In th is a lgo rithm, the opti m iza tion process was d iv ided into two phases, one w as to lock the neighbo rhood o f the opti m al so lution or partia l so lution, the o ther w as to obta in the opti m a l so lution o f h igh -prec ision. Each phase set different para m ete rs and co m bined the tabu search algor ithm to m prove convergence speed and accuracy o f opti i m a l so lutions. T he s i m u la tion resu lts sho w that the proposed algor ithm can greatly i m prove the ability of seek ing the g loba l ex cellent resu lt , convergence speed and accuracy. A s fo r the mu lti objective op ti m ization prob lem, the propo sed a lgo rithm can a lso i m prove the quality o f P areto opti m a l so lutions , en large the d istr ibu tion area o f dec isions and ma in tain d iversity in decision-mak ing . K ey words : A rtific ial F ish-Sw ar m A lgo rithm ( AFSA ); phased opti m ization and var iable para m eter opti m ization; T abu Search ( TS); mu lti objective opti m ization
第 5期ቤተ መጻሕፍቲ ባይዱ
张汉强等 : 新的 混合智能优化算法及其多目标优化应用
1291
2 人工鱼群算法概述
2. 1 人工鱼个体相关定义 人 工鱼个体的状态 X = ( x1 , x2 , ,, xn ), 其中 xi ( i = 1, 2 , ,, n) 为欲 寻 优的 变 量 ; 人工 鱼 当 前食 物 浓度 表 示 为 Y = f ( X ) ; 人工鱼个体之间的距离为 d i, j = + X i - X j + ; 人工鱼每 次移 动 最 大 试 探 次 数 为 trynum ber ; 人工鱼的 感知距离为 visua l ; 人工鱼移动的最大步长为 step; 拥挤度因子为 D 。 2. 2 行为描述 觅食行为 设人 工鱼当前状态为 X i, 在其感 知距离 内随 机选择状态 X j, 求 极小值 问题 中 ( 因为 极小值 与极 大值问 题 类似 , 下面均以极小值问题讨论 ) , 当 Y i > Yj 时 , X i / nex t = X i + R and ( ) # S tep# ( X j - X i ) /d i. j; 否则 , 重新随机选择状态 X j, 判 断 Yi > Yj; 反复尝试 trynum ber次后 , 仍不满足前进条件 , 则随 机移动一步。 聚群行为 设人工 鱼当 前状 态为 X i, 搜索 当前 邻域 内 ( 即 d i, j < visab le) 的伙伴数目 nf 及中心位置 X c, 如果 Yc nf < D Y i, 表明伙伴中心 有食 物较 少且 不太 拥挤 , 则 X i / nex t = X i + R and ( ) # S tep# ( Xc - X i ) /+ X c - X i + ; 否则执行觅食行为。 追尾行 为 设人工鱼当前状态为 X i, 探索当前邻域内伙 伴 中 Yj 为最小的 伙伴 X j, 如果 Yj nf < D Y i, 表明 X j 伙伴的状态 具有较低的食物浓度 并且其 周围 不太 拥挤 , 则 X i / nex t = X i + R and ( ) # S tep# X j - X i /+ X j - X i + ; 否则执行觅食行为。 随机行为 随机 行为是觅食行为的一个缺省行为。 公告板 用以记 录最优人工鱼个体状态及该人工鱼位置 的食物浓度。 2. 3 行为选择 根据所要解决问 题的性质 , 对人 工鱼当 前所处 的环境 进 行评价 , 从而选择一种合适的行为 , 一般按照进步最快原则。 2. 4 参数对算法的影响 trynum ber 越小 , 人工鱼 摆脱 局部 极值 的能 力越 强 , 收 敛 效率高 ; visual 越大 , 越容易发 现全局极值点 ; s tep 越 大初始收 敛速度快 , 后期速度降低 , 而且 精度下降 ; D较 大时 , 觅食 行为 和随机行为 突出 , 有利于全 局搜索 , 提高收 敛速度 , 同样 精度 会降低 ; 人工鱼数目 N 越多 , 收敛速度快 , 但是计算量加大。
算法 [ 6] 中的禁忌规 则、 解禁 规则 和终 止规 则 , 提 出一 种新 的 混合智能优 化算 法 ( H ybr id Inte lligent Opti m ization A lgor ithm, HI OA ), 将此优化算法应用在多目标优化问题中 , 取得了良 好 的效果。
1 多目标优化问题描述
( 浙江大学 工业控制技术国家重点实验室 , 杭州 310027 ) ( hqzhang@ iipc. zju. edu . cn)
摘 要 : 针对人工鱼 群算法后 期收敛速度 较慢 、 解精度不 高的不足 , 按照分 阶段寻优 和变参数寻 优的改进策 略 , 并结合禁忌搜索算法中的相关规则 , 提出 一种新的混合智能优化算法 。 该 算法将寻优 过程分为 锁定最优解 或者局部 解邻域和求得高精度最优解两个阶段 , 每 个阶 段设 置不同 的参 数并结 合禁 忌搜索 算法 以提 高收敛 速度 和最优 解精 度 。 典型函数验证表明 , 该算法收敛速度快 、 精度高 ; 同时 , 对于多 目标优化 问题 , 该 算法可以 提高 P are to 最优 解集质 量 , 扩大决策分布范围 , 维持决策多样性 , 有利于决 策者作出决策 。 关键词 : 人工鱼群算法 ; 分阶段寻优和变参数寻优 ; 禁忌搜索 ; 多目标优化 中图分类号 : T P273+ . 5 文献 标志码 : A
在多目标优化问题中 , 各个目标通常是相互制约的关系 , 对其中一个目标 进行 优化 往往 以其 他 目标 的性 能降 低为 代 价 , 因而 全局最优 值通 过各 目标 平衡 达到 , 其 数学 表达 式 如 下: m in F (X ) = ( f i ( X ) ) T; i = 1, 2, ,, m s. t . S ( X ) = ( sj (X ) ) T \ 0; j = 1, 2, ,, k A[ X[ B 其中 : X = xi ( i = 1, 2, ,, n) 为 n 维 决 策 向 量 ; F ( X ) = ( f i (X ) ) T 为多目标优化函数向量 ; S (X ) = ( sj (X ) ) T 为约 束 条件 , 表 示 sj ( X ) \ 0( j = 1, 2, ,, k ); 边界条件 A [ X [ B 表 示每个决策分量须满足 ai [ xi [ bi ( i = 1, 2 , ,, n)。
第 30 卷第 5 期 2010 年 5 月 文章编号 : 1001- 9081( 2010) 05- 1290- 03
计算机应用 Journal o f Computer A pp lications
V o.l 30 N o . 5 M ay 2010
新的混合智能优化算法及其多目标优化应用
张汉强, 卢建刚, 陈金水
收稿 日期 : 2009 - 11 - 19 ; 修 回 日期 : 2010 - 01 - 13 。 基 金 项 目 : 国 家自 然 科 学 基 金资 助 项 目 ( 60736021 ) ; 国 家 863 计 划 项 目 ( 2006A A 04Z184 ; 2007AA 041406) ; 浙江省科技计划资助项目 ( 2006C11066 ; 2006C 31051 ); 浙江省自然科学基金资助项目 ( Y 4080339) 。 作者简介 : 张汉强 ( 1982- ) , 男 , 浙江义乌人 , 硕士研究生 , 主要研究 方向 : 复杂系 统优化、 计 算机智能 控制 ; 卢建 刚 ( 1968 - ) , 男 , 浙江 杭 州人 , 教授 , 主要研究方向 : 复杂工程系统的建模、 控制与优化 ; 陈金水 ( 1970- ) , 男 , 福建福州人 , 副研究员, 主要研究方向 : 嵌入式系统的 软件 模型与工具。
0 引言
人们根据生物系 统的特征 和一些 物理现 象 , 构 造设计 出 许多仿生优化算法来 解决复 杂的实 际问题 , 例如 模拟退 火算 法 [ 1] 、 粒子群算法 [ 2] 和遗传算法 [ 3] 等。虽然这些 优化算 法具 有某些共同的机制和 原理 , 但由于 不同的 优化算 法表现 出不 同的行为特征和优缺 点 [ 4] , 因而算 法间的 相互促 进与补 足逐 渐成为一种改进算法 特性的自然途径。 人工鱼 群算 法 ( A rtific ia l F ish Schoo l A lgo rithm, AFSA ) 是 李晓磊等人 [ 5] 于 2002 年提出的一种基于模拟鱼群觅食 、 聚群 和追尾行为的仿生型优化算法 。该算法 具有良好的克服局部 极值、 取得全局 极值 的能 力 , 并且 该算 法还 具有 对初 值不 敏 感、 鲁棒性强、 简 单 ( 只 使 用目 标函 数 值 ) 、 易实 现 等 诸多 优 点。但是随着 优化 问题 的不 断复 杂化 , AF SA 在 大规 模复 杂 优化问题的求解和应 用中存 在着不 足 , 主 要表现 为算法 得到 的解精度不 高 , 优化 前期 收敛 速度 快但 后期 收敛 速度 慢等。 针对人工鱼群算法的 这些不 足 , 本 文提出 基于分 阶段寻 优和 变参数寻优 的改 进策 略 , 并结 合禁 忌搜 索 ( T abu Search, TS )
New hybrid intelligent optim ization algorithm and its app lication in multi objective optim ization
ZANG H an -q ia ng , LU Jian -gang, CH EN Jin -shui