收 稿日期 : 2007-04-02; 修回 日期 : 2007-06-28 基 金项 目: 甘 肃省科 技攻 关 项目 ( GS044-A52- 001-24) ; 甘 肃省 自 然科 学 基金 资 助项 目
( 3ZS042-B25-012)
作 者简介 : 李 恒杰 ( 1981-) , 男, 陕西 户县人 , 博 士研 究生, 主要 研究 方向为 学习 控制、多 目标 优 化( lihj915@ 163. com) ; 郝 晓 弘( 1960- ) 男, 甘 肃
泾川人 , 教 授, 博导 , 主 要研 究方向 为学习 控制 、电 机控制 技术 等; 张磊 ( 1982-) , 女, 山西太 原人 , 硕 士研究 生, 主要 研究 方向为 学习控 制.
基 于 Pareto 的 快 速 多 目 标 克 隆 选 择 算 法
*
李恒杰, 郝晓弘, 张 磊
( 兰州 理工 大学 电 气工 程与 信息工 程学 院, 兰 州 730050)
摘 要: 基 于免 疫系 统中 克隆 选择 原理, 提 出了 一种多 目标 克 隆 选择 算 法 MCSA。 该方 法 只 对部 分 当 前所 得 到
的 Pareto 最优 解进 行进 化操 作, 所求 得的 Pareto 最优 解 保留 在 一 个 不 断 更 新 的外 部 记 忆 库 中, 并选 用 一 种 简 单
的多 样性保 存机 制来 保证 其具 有 良 好 的 分 布 特 征。 实 验 结 果 表 明 , 该 方 法 能 够 很 快 地 收 敛 到 Pareto 最 优 前 沿
面, 同时 较好 地保 持解的 多样 性和 分布 的均 匀性 。对于 公认 的多 目标 benchmark 问 题, MCSA 在解 集 分 布的 均 匀
性、多样 性与 解的 精确 性及 算法 收敛速 度等 方面 均优 于 SPEA、NSGA-II 等算 法。
关键 词: 克 隆选 择原 理; Pareto 最优 解; 多 目标 优化
中图 分类 号: TP301 文 献标 志码: A 文 章编 号: 1001-3695( 2008) 05-1368-04
Fast Pareto-based multi-objective clonal selection algorithm
LI Heng-jie, HAO Xiao-hong, ZHANG Lei
( School of Electrical Engineering & Information Engineering, Lanzhou University of Technology, Lanzhou 730050, China)
Abstract: A multi-objective clonal selection algorithm( MCSA) was proposed based on the clonal selection principle in the
immune system. Only some Pareto optimal solutions were selected for further evolutionaryoperation in the algorithm. The Pare-
to optimal solutions were reserved in an external memory set which was renewed in each generation, and a simple mechanism
was used to maintain good spread of solutions. It isshown by experimental results thatthe method can reachthe Pareto optimal
front very quickly and retain the better diversity of the solutions. The proposed MCSA is superior to other algorithms such as
SPEA, NSGA-II etc. in terms of the precision, the quantity, the distribution uniformity, the diversity of solutionsand the con-
vergence rate of algorithmin solving one kind of typical benchmark problems.
Key words: clonal selection principle; Pareto optimal solutions; multi-objective optimization
最优化处理是在可能的解 中搜索 对于某 些目标 来说是 最
优解的问题, 这种问题在过去的五十年中已经得到了深入的研
究。若仅考虑一个优化目标, 即 单目标 优化问 题; 如 果存在 的
目标超过一个并 需要 同时 处理, 就 成 为多 目标 优 化问 题
[ 1, 2]
。
多目标优化问题中各目标之间通过决策变量相互制约, 对其中
的一个目标优化必须以其他目标作为代价, 而且各目标的物理
意义往往又不一致, 因此很难评价多目标问题解的优劣性。与
单目标优化问题的本质区别在于, 多目标优化问题的解不是惟
一的, 而是存在一个最优解集合, 集合中元 素称为 Pareto 最优
解或非 支 配 解 ( non-dominated solutions)
[ 3]
。所 谓 Pareto 最 优
解, 就是不存在比其中至少一个目标好而其他目标不劣的更好
的解, 也就是不可能通过优化其中部分目标而使其他目标不至
劣化。因此, Pareto 最优解集中的元素就所有 目标而 言是彼 此
不可比较的。
在过去的二十年中, 进化算法作为多目标优化问题的新求
解方法受到了相当程度的关 注, 这就诞 生了多 目标进 化算法。
Fonseca和 Fleming对这 一主 题 进行 了 综 述
[ 4]
, 他 们将 进 化 多
目标优化算法分为明确加权法、基于种群的非 Pareto 方法 和基
于 Pareto 的方法三类。其 中基 于 Pareto 的进 化算 法是 一条 求
解多目标问题非劣最 优解的 有效途 径。在基 于 Pareto 的方 法
中最具代表性的两 类是解 排序遗 传算 法 NSGA( non-dominated
sorting genetic algorithm) 和 基 于浓 度 的 Pareto 进 化算 法 SPEA
( strength pareto evolutionary algorithm) 。 Zitzler 和 Thiele 于
1999 年提出了 SPEA
[ 5]
, 它的运行效率比较低, 但由于 SPEA 采
用聚类方法 维 持解 群 体 的分 布 性, 其解 集 的 分 布 性 比 NSGA
好。Zitzler等人于 2001 年又对 SPEA 进行了改进, 提出了运 行
效率相对较高的 SPEA2
[ 6]
。Srinivas 和 Deb基于个体的多层次
分类提出了 NSGA
[ 7]
。NSGA 通过计算个体之间的聚集距离 来
保持群体的 分布 性, 运行 效 率 比 SPEA 高, 但 分 布 性差 一 些。
最近, Deb 等人通过引进快速非劣解排序和新的 多样性保存 方
法提出了第二代 NSGA, 简称 NSGA-Ⅱ
[ 8]
。总的来说, NSGA-Ⅱ
的运行效率比 SPEA2 好, 其解集的分布性也不比 SPEA2 差, 是
目前研究者们比较认同的一种好算法。
上面提到 的 多 目标 进 化 算 法 基 本 上 都是 基 于 遗 传 算 法
( GA) 来求解多目标优化问题。本文借鉴免疫系统中的克隆选
择原理, 将成功地应用于单目标优化问题的克隆选择算法扩展
到多目标优化问题中, 设计出了一种新的基于 Pareto 的多目 标
优化算法。
1 克隆选择原理
在自然界中, 免疫功能是指机体对外部感染具有抵抗能力
第 25 卷 第 5 期
2008 年 5 月
计 算 机 应 用 研 究
Application Research of Computers
Vol. 25 No. 5
May 2008