一种改进的多目标优化算法
ｗ ｈ ｅ ｒ ｅ ： ｘ ＝ （ ｘ ， ｘ ， …， ｘ ） ∈Ｘ １ ２ ｎ ｙ ＝ （ ｙ ， ｙ ， …， ｙ ） ∈Ｙ １ ２ ｋ
（ ３ ） （ ４ ）
ｘ 是自变量向量， ｙ 是目标向量； Ｘ是自变量空间； Ｙ是目 其中： （ ｘ ）≤ ０确 定 可 行 解。 多 目 标 优 化 问 题 标空 间， 约束 ｇ ｍ ａ ｘ （ ｆ （ Ｘ ） ） 中的相关定义如下： 定义 １ Ｐ ａ ｒ ｅ ｔ ｏ 支配。对于任意的自变量向量 Ｘ ， Ｘ ： ∈Ｘ １ ２ （ Ｘ ）＜ ｆ （ Ｘ ） ， 称Ｘ ａ ｒ ｅ ｔ ｏ 支配 Ｘ ， 记为 Ｘ ； 当且仅当 ｆ Ｘ ｉ １ ｉ ２ ２Ｐ １ ２ １ 当且仅当 ｆ （ Ｘ ） （ Ｘ ） ， 称Ｘ ａ ｒ ｅ ｔ ｏ 弱支配 Ｘ ， 记为 Ｘ ≤ｆ ｉ １ ｉ ２ ２Ｐ １ ２ Ｘ （ ｉ ＝ １ ， ２ ， …， ｍ ） 。 １ 定义 ２ Ｐ ａ ｒ ｅ ｔ ｏ 最优解。对于一个自变量向量 Ｘ ∈ Ｘ ， 若
·４ ４ ６ｇ （ ｘ ）＝ （ ｇ （ ｘ ） ， ｇ （ ｘ ） ， …， ｇ ｘ ） ） ≤０ １ ２ ｍ（
计 算 机 应 用 研 究
（ ２ ）
第２ ９卷
参数 λ １和 λ ２ 分别代表参与产生新个体的父代个体。λ １和 λ ２ 分别为
（ （ ｐ ｐ ）－ （ ｐ ｐ ） ） ／ ２ λ Δ １＝ １＋ ２ ２－ １ （ （ ｐ ｐ ）－ （ ｐ ｐ ） ） ／ ２ λ Δ ２＝ １＋ ２ １－ ２ （ ９ ） （ １ ０ ）
［ ６ ］ 后来又出现了处理约束问题的优化算法（ Ｍ Ｏ Ｃ Ｐ Ｓ Ｏ ） 可以将
ｐ ｓ ｉ ｌ ｏ ｎ 支配概念的 ｅ ｐ 约束问题转换为多目标优化问题， 基于 ｅ
７ ］ ｓ ｉ ｌ ｏ ｎ Ｍ Ｏ Ｅ Ａ算法 ［ 可以防止解丢失的问题， 在这些优化算法
中多数都有额外参数的设置问题， 需要人工参与运算， 自适应 性不太理想。基于此， 提出了一种中心均值重组自适应多目标 优化算法（ Ｉ Ｍ Ｏ Ｏ Ａ ） ， 在算法中改进模拟交叉算子， 沿用 Ｎ Ｓ Ｇ Ａ Ⅱ算法所采用的拥挤距离对个体进行排序。通过实例测试和 Ｎ Ｓ Ｇ Ａ 该算法能有效解决了实参多目标 Ⅱ算法进行比较表明， 优化问题， 且在解的收敛性、 分布性以及算法的自适应程度均 表现较好。
的Ｓ Ｐ Ｅ Ａ ２算法。这两种算法是目前比较常见的多目标算法， 它们的优点较多， 但缺点也较明显。Ｎ Ｓ Ｇ Ａ Ⅱ 的优点是全局搜 索性能良好， 解集具有良好的分布性， 在算法中使用拥挤距离 排序不会使算法陷入到局部最优； 缺点是在高维问题中， 解集 的多样性不理想， 而且在算法后期选择解的保留时很容易造成
第２ ９卷第 １ ２期 ２ ０ １ ２ 年１ ２月
计 算 机 应 用 研 究 Ａ ｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎＲ ｅ ｓ ｅ ａ ｒ ｃ ｈｏ ｆ Ｃ ｏ ｍ ｐ ｕ ｔ ｅ ｒ ｓ
Ｖ ｏ ｌ ． ２ ９Ｎ ｏ ． １ ２ Ｄ ｅ ｃ ． ２ ０ １ ２
一种改进的多目标优化算法
樊纪山１，王经卓１，熊盛武２
（ １ ． Ｓ ｈ ｏ ｏ ｌ ｏ ｆ Ｅ ｌ ｅ ｃ ｔ ｒ ｏ ｎ ｉ ｃ Ｅ ｎ ｇ ｉ ｎ ｅ ｅ ｒ ｉ ｎ ｇ ，Ｈ ｕ ａ ｉ ｈ ａ ｉ Ｉ ｎ ｓ ｔ ｉ ｔ ｕ ｔ ｅ ｏ ｆ Ｔ ｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ ，Ｌ ｉ ａ ｎ ｙ ｕ ｎ ｇ ａ ｎ ｇＪ ｉ ａ ｎ ｇ ｓ ｕ２ ２ ２ ０ ０ ５ ，Ｃ ｈ ｉ ｎ ａ ；２ ． Ｓ ｃ ｈ ｏ ｏ ｌ ｏ ｆ Ｃ ｏ ｍ ｐ ｕ ｔ ｅ ｒ ，Ｗ ｕ ｈ ａ ｎ Ｕ ｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙｏ ｆ Ｔ ｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ ，Ｗ ｕ ｈ ａ ｎ４ ３ ０ ０ ７ ０ ，Ｃ ｈ ｉ ｎ ａ ）
收稿日期：２ ０ １ ２ ０ ６ ０ ６ ；修回日期：２ ０ １ ２ ０ ７ １ ９ 基金项目：国家自然科学基金资助项目（ ６ １ １ ７ ４ ０ １ ３ ， ６ ０ ５ ７ ２ ０ １ ５ ） 作者简介： 樊纪山（ １ ９ ７ ５ ） ， 男， 山东临沂人， 讲师， 硕士， 主要研究方向为机器学习、 演化计算（ ｆ ｊ ｓ ｓ ｚ ｗ ２ ０ ０ ５ ＠１ ２ ６ ． ｃ ｏ ｍ ） ； 王经卓（ １ ９ ７ ３ ） ， 男， 教 授， 博士， 主要研究方向为检测与控制； 熊盛武（ １ ９ ６ ６ ） ， 男， 教授， 博士， 主要研究方向为机器学习、 智能计算．
（ １ ． 淮海工学院 电子工程学院，江苏 连云港 ２ ２ ２ ０ ０ ５ ；２ ． 武汉理工大学 计算机学院，武汉 ４ ３ ０ ０ ７ ０ ） 摘 要：为了提高非劣解向 Ｐ ａ ｒ ｅ ｔ ｏ 最优面收敛的速度以及解的多样性， 设计了一种新的杂交算子并改进了 Ｎ Ｓ Ｇ Ａ 采用中心均值重组算子策略增强算法全局快速搜索能力， 以获得最佳的 Ｐ ａ ｒ ｅ ｔ ｏ 近似 Ⅱ算法。在此算法中， Ｓ Ｇ Ａ 解， 同时，改进 Ｎ Ⅱ快速非支配排序和拥挤机制将父代与子代的双种群进行截短，确保最优解不会丢失并 保证解的多样性。数据实验表明， 该算法能在解的收敛性、 分布性以及自适应程度上均表现较好。 关键词：多目标优化；中心均值重组；自适应交叉；Ｐ ａ ｒ ｅ ｔ ｏ 最优 中图分类号：Ｔ Ｐ １ ８ ３ 文献标志码：Ａ 文章编号：１ ０ ０ １ ３ ６ ９ ５ （ ２ ０ １ ２ ） １ ２ ４ ４ ６ ３ ０ ３ ： １ ０ ． ３ ９ ６ ９ ／ ｊ ． ｉ ｓ ｓ ｎ ． １ ０ ０ １ ３ ６ ９ ５ ． ２ ０ １ ２ ． １ ２ ． ０ １ ４ ｄ ｏ ｉ
Ａ ｂ ｓ ｔ ｒ ａ ｃ ｔ ：Ｔ ｈ ｉ ｓ ｐ ａ ｐ ｅ ｒ ｐ ｒ ｏ ｐ ｏ ｓ ｅ ｄａｎ ｏ ｖ ｅ ｌ ｍ ｕ ｌ ｔ ｉ ｏ ｂ ｊ ｅ ｃ ｔ ｉ ｖ ｅｅ ｖ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ａ ｒ ｙａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｂ ａ ｓ ｅ ｄｏ ｎａｎ ｏ ｖ ｅ ｌ ｃ ｒ ｏ ｓ ｓ ｏ ｖ ｅ ｒ ｏ ｐ ｅ ｒ ａ ｔ ｉ ｏ ｎａ ｎ ｄｉ ｍ ｉ ｎｏ ｒ ｄ ｅ ｒ ｔ ｏ ｈ ｅ ｉ ｇ ｈ ｔ ｅ ｎｆ ｕ ｒ ｔ ｈ ｅ ｒ ｒ ａ ｔ ｅ ｏ ｆ ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ ｏ ｆ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ｓ ｔ ｏ Ｐ ａ ｒ ｅ ｔ ｏ ｏ ｐ ｔ ｉ ｍ ａ ｌ ｆ ｒ ｏ ｎ ｔ ａ ｎ ｄｅ ｎ ｓ ｕ ｒ ｅ ｔ ｈ ｅ ｄ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ｏ ｆ ｐ ｒ ｏ ｖ ｅ ｓ Ｎ Ｓ Ｇ Ａ Ⅱ， ｏ ｐ ｔ ｉ ｍ ａ ｌ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ． Ｉ ｎｔ ｈ ｅａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ， ｔ ｈ ｅ ｃ ｒ ｏ ｓ ｓ ｏ ｖ ｅ ｒ ｏ ｐ ｅ ｒ ａ ｔ ｏ ｒ ｐ ａ ｒ ａ ｍ ｅ ｔ ｅ ｒ ｗ ａ ｓ ａ ｄ ａ ｐ ｔ ｉ ｖ ｅ ｆ ｏ ｒ ｅ ｎ ｈ ａ ｎ ｃ ｉ ｎ ｇ ｔ ｈ ｅａ ｂ ｉ ｌ ｉ ｔ ｙｏ ｆ ｇ ｌ ｏ ｂ ａ ｌ ｆ ａ ｓ ｔ ｓ ｅ ａ ｒ ｃ ｈ ｔ ｏ ａ ｃ ｈ ｉ ｅ ｖ ｅ ｂ ｅ ｔ ｔ ｅ ｒ Ｐ ａ ｒ ｅ ｔ ｏａ ｐ ｐ ｒ ｏ ｘ ｉ ｍ ａ ｔ ｅ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ｓ ． Ｍ ｏ ｒ ｅ ｏ ｖ ｅ ｒ ， ｉ ｔ ｉ ｍ ｐ ｒ ｏ ｖ ｅ ｄｆ ａ ｓ ｔ ｒ ａ ｎ ｋ ｉ ｎ ｇｍ ｅ ｃ ｈ ａ ｎ ｉ ｓ ｍ ｓ ａ ｎ ｄｃ ｒ ｏ ｗ ｉ ｎ ｇｄ ｉ ｓ ｔ ａ ｎ ｃ ｅｓ ｏ ｒ ｔ ｉ ｎ ｇｏ ｆ Ｎ Ｓ Ｇ Ａ ｒ ｕ ｎ ｃ ａ ｔ ｅ ｓ ｔ ｈ ｅ ｐ ｏ ｐ ｕ ｌ ａ ｔ ｉ ｏ ｎｓ ｅ ｔ ｆ ｏ ｒ ｍ ｅ ｄｂ ｙ ｔ ｈ ｅ ｐ ａ ｒ ｅ ｎ ｔ ｓ ａ ｎ ｄｔ ｈ ｅ ｎ ｅ ｗｐ ｏ ｉ ｎ ｔ ｓ ， ｉ ｎｏ ｒ ｄ ｅ ｒ ｔ ｏ ｅ ｎ ｓ ｕ ｒ ｅ ｔ ｈ ｅ ｏ ｐ ｔ ｉ ｍ ａ ｌ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎｎ ｏ ｔ ｂ ｅ Ⅱｔ ｌ ｏ ｓ ｔ ａ ｎ ｄｔ ｏｅ ｎ ｓ ｕ ｒ ｅ ｔ ｈ ｅｄ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ｏ ｆ ｏ ｐ ｔ ｉ ｍ ａ ｌ ｓ ｏ ｌ ｕ ｔ ｉ ｏ ｎ ． Ｔ ｈ ｅ ｅ ｘ ｐ ｅ ｒ ｉ ｍ ｅ ｎ ｔ ａ ｌ ｒ ｅ ｓ ｕ ｌ ｔ ｓ ｓ ｈ ｏ ｗｔ ｈ ａ ｔ ｔ ｈ ｅｐ ｒ ｏ ｐ ｏ ｓ ｅ ｄａ ｐ ｐ ｒ ｏ ａ ｃ ｈｉ ｓ ａ ｂ ｌ ｅｔ ｏｅ ｆ ｆ ｅ ｃ ， ｄ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ａ ｎ ｄ ｔ ｈ ｅ ｄ ｅ ｇ ｒ ｅ ｅ ｏ ｆ ｔ ｉ ｖ ｅ ｌ ｙｓ ｏ ｌ ｖ ｅｔ ｈ ｅ ｒ ｅ ａ ｌ ｐ ａ ｒ ａ ｍ ｅ ｔ ｅ ｒ ｍ ｕ ｌ ｔ ｉ ｏ ｂ ｊ ｅ ｃ ｔ ｉ ｖ ｅ ｐ ｒ ｏ ｂ ｌ ｅ ｍ ｓ ａ ｎ ｄ ｈ ａ ｓ ｂ ｅ ｔ ｔ ｅ ｒ ｐ ｅ ｒ ｆ ｏ ｒ ｍ ａ ｎ ｃ ｅ ｏ ｎ ｃ ｏ ｎ ｖ ｅ ｒ ｇ ｅ ｎ ｃ ｅ ｃ ｏ ｎ ｔ ｒ ｏ ｌ ｌ ｉ ｎ ｇｓ ｅ ｌ ｆ ａ ｄ ａ ｐ ｔ ｉ ｖ ｅ ． Ｋ ｅ ｙｗ ｏ ｒ ｄ ｓ ：ｍ ｕ ｌ ｔ ｉ ｏ ｂ ｊ ｅ ｃ ｔ ｉ ｖ ｅ ｏ ｐ ｔ ｉ ｍ ｉ ｚ ａ ｔ ｉ ｏ ｎ ；ｍ ｅ ａ ｎ ｃ ｅ ｎ ｔ ｒ ｉ ｃｒ ｅ ｃ ｏ ｍ ｂ ｉ ｎ ａ ｔ ｉ ｏ ｎ ；ｓ ｅ ｌ ｆ ａ ｄ ａ ｐ ｔ ｉ ｖ ｅ ｃ ｒ ｏ ｓ ｓ ｏ ｖ ｅ ｒ ；Ｐ ａ ｒ ｅ ｔ ｏ ｏ ｐ ｔ ｉ ｍ ａ ｌ
３ ］ 精英解的丢失 ［ 。Ｓ Ｐ Ｅ Ａ ２的优点在于可以取得一个分布度较
多目标优化问题
一个通常的多目标优化问题（ Ｍ Ｏ Ｐ ） 包含 ｎ个自变量的集 合、 ｋ 个目标函数的集合、 ｍ 个约束限制的集合和目标函数及 约束都是自变量的函数。以最大化问题为例， Ｍ Ｏ Ｐ表示为
ｍ ａ ｘ ｉ ｍ ｉ ｚ ｅ ： ｙ ＝ ｆ （ ｘ ）＝ （ ｆ （ ｘ ） ，ｆ （ ｘ ） ， …，ｆ （ ｘ ） ） １ ２ ｋ （ １ ）
