当前位置：文档之家 › 基于Pareto熵的多目标粒子群优化算法_胡旺

基于Pareto熵的多目标粒子群优化算法_胡旺

  • 格式：pdf
  • 大小：1.68 MB
  • 文档页数：26

Corresponding author: HU Wang, E-mail: scuhuwang@ Abstract : Due to its concise formation, fast convergence, and flexible parameters, particle swarm optimization (PSO) with the ability to
gain multiple solutions at a run and to approximate the Pareto front of those non-convex or discontinuous multiobjective optimization problems (MOPs) is considered to be one of the most promising techniques for MOPs. However, several challenges, such as maintaining the archive, selecting the global and personal best solutions, and balancing the exploration and exploitation, occur when extending PSO from single-objective optimization problems to MOPs. In this paper, the distribution entropy and its difference of an approximate Pareto front in a new objective space, named parallel cell coordinate system (PCCS), are proposed to assess the diversity and evolutionary status of the population. The feedback information from evolutionary environment is served in the evolutionary strategies to balance the convergence and diversity of an approximate Pareto front. Meanwhile, the new concepts, such as cell dominance and individual density based on cell distance in the PCCS, are introduced to evaluate the individual environmental fitness which is the metric using in updating the archive and selecting the global best solutions. The experimental results illustrate that the proposed algorithm in this paper
软件学报 ISSN 1000-9825, CODEN RUXUEW Journal of Software,2014,25(5):10251050 [doi: 10.13328/ki.jos.004496] ©中国科学院软件研究所版权所有 .
E-mail: jos@ Tel/Fax: +86-10-62562563
1
预备知识
1.1 多目标优化问题 对于最小化无约束连续多目标优化问题 (在优化计算领域 ,最大化问题与最小化问题是一组对偶问题 .在无 特别说明的情况下 ,本文所指最优化均为最小化问题),可以定义如下: min F(x)=[f1(x),f2(x),…,fM(x)]T for all x D, 其中 ,x=[x1,x2,…,xD] S,D 为决策变量个数,S 是 D 维决策空间 .一组目标函数 f1,f2,…,fM 将决策空间映射到目标 空间 ,S M,M 为目标个数 , 是 M 维目标空间 . 下面给出与本文使用了 Pareto 最优的相关定义. 定义 1(Pareto 占优 ). 对于任意两个向量 u,v ,称 u 占优 v,或称 v 被 u 占优 ,记作 uv,当且仅当 i=1,2,…,m, ui≤ vij=1,2,…,m, uj<vj. 定义 2(Pareto 最优解). 一个解 x* 被称为 Pareto 最优解或非占优解,当且仅当 x :xx*. 定义 3(Pareto 最优解集和 Pareto 前端 ). 所有 Pareto 最优解的集合 PS={x*|x :xx*}称为 Pareto 最优 解集 .所有 Pareto 最优解对应目标函数值所形成的区域 PF={F(x*)|x*PS}称为 Pareto 前端 ,或 Pareto 均衡面 .
significantly outperforms the other eight peer competitors in terms of IGD on 12 test instances chosen from the ZDT and DTLZ test suites. Key words: multiobjective optimization problem (MOP); particle swarm optimization (PSO); parallel cell coordinate system (PCCS); Pareto entropy; adaptive parameter

基金项目 : 中央高校基本科研业务费专项资金(2672013ZYGX2013J078) 收稿时间 : 2013-04-19; 修改时间 : 2013-06-18; 定稿时间 : 2013-09-09
1026
Journal of Software 软件学报 Vol.25, No.5, May 2014
大多数工程和科学问题都可以归结为多目标优化问题(multiobjective optimization problem,简称 MOP),其 求解方法一直都是学术界和工程界共同关注的焦点 . 多目标优化问题通常存在多个彼此冲突的目标 ,其优化结 果为 Pareto 最优解集 . 与数学规划方法相比 , 进化算法因一次运行可得到多个解 , 且能逼近非凸或不连续的 Pareto 最优前端 ,从而被认为是更适合求解多目标优化问题的智能方法 . 粒子群优化算法(particle swarm optimization,简称 PSO)[1]是由 Kennedy 和 Eberhart 在 1995 年提出的仿生 算法 ,它是受到飞鸟集群活动规律的启发,根据社会学和心理学而建立的群体智能模型 .粒子群优化算法是一种 具有形式简洁、收敛快速和参数调节机制灵活等优点的进化算法 ,并且已经成功应用于单目标优化问题 ,被认 为是求解多目标优化问题最具潜力的方法之一 . 但当粒子群优化算法从单目标问题扩展到多目标问题而形成 多目标粒子群优化(multiple objective particle swarm optimization,简称 MOPSO)时 ,新的技术问题随之出现.多目 标优化问题的 Pareto 最优解集特征和粒子群优化算法的快速收敛特征,使得多目标粒子群优化算法面临以下 技术挑战 :① 维护存储 Pareto 最优解集的档案,使算法最终输出的 Pareto 前端能够兼顾收敛性和多样性 ,这是第 二代进化多目标算法的共性问题;② 从群体和个体的 Pareto 最优解集中分别选举全局最优解(gBest)和个体最 优 解 (pBest), 使 这 两 个 最 优 解 引 导 粒 子 尽 最 大 可 能 地 发 现 高 质 量 的 新 解 ;③ 平 衡 进 化 过 程 中 的 开 采 (exploration)和开发 (exploitation),使得种群既保持快速收敛的优点 ,但又尽可能地避免陷入局部 Pareto 前端或 者收敛到单一解.后面两个挑战是多目标粒子群优化算法区别于其他多目标进化算法的特有问题. 本文将根据多目标优化问题和粒子群优化算法的特征 ,采用近似 Pareto 前端的分布熵及其变化来估计种 群进化状态 ,并依据这些进化过程反馈信息设计具有动态平衡开采和开发能力的进化策略 ,形成基于 Pareto 熵 的多目标粒子群优化算法. 为了内容相对独立以及统一本文术语和符号 ,本文第 1 节简要介绍多目标优化问题和粒子群优化算法的 基本概念 .第 2 节综述与本文内容相关的多目标粒子群优化算法的研究现状和存在的问题 .第 3 节阐述 Pareto 熵的计算方法以及基于 Pareto 熵的种群进化状态检测方法.第 4 节描述本文算法的主要进化策略和完整的算法 流程 .第 5 节分析对比实验结果.最后 ,在第 6 节中给出全文结论 .
通讯作者 : 胡旺 , E-mail: scuhuwang@
摘 要:
粒子群优化算法因形式简洁、收敛快速和参数调节机制灵活等优点,同时一次运行可得到多个解,且能逼
近非凸或不连续的 Pareto 最优前端,因而被认为是求解多目标优化问题最具潜力的方法之一.但当粒子群优化算法 从单目标问题扩展到多目标问题时,Pareto 最优解集的存储与维护、 全局和个体最优解的选择以及开发与开采的平 衡等问题亦随之出现.通过目标空间变换方法,采用 Pareto 前端在被称为平行格坐标系统的新目标空间中的分布熵 及差熵评估种群的多样性及进化状态,并以此为反馈信息来设计进化策略,使得算法能够兼顾近似 Pareto 前端的收 敛性和多样性.同时,引入格占优和格距离密度的概念来评估 Pareto 最优解的个体环境适应度,以此建立外部档案更 新方法和全局最优解选择机制,最终形成了基于 Pareto 熵的多目标粒子群优化算法.实验结果表明:在 IGD 性能指标 上,与另外 8 种对等算法相比,该算法在由 ZDT 和 DTLZ 系列组成的 12 个多目标测试问题集中表现出了显著的性 能优势. 关键词: 多目标优化问题;粒子群优化;平行格坐标系统;Pareto 熵;自适应参数 中图法分类号 : TP301

合集下载

一种改进的基于pareto解的多目标粒子群算法

一种改进的基于pareto解的多目标粒子群算法

第２卷 第５ ７ 期
文章编号 ：０ ６— ３ ８ ２ １ ） ５— ０ ６— ４ １０ ９ ４ （０ ０ ０ ０ ９ ０
计
算
机
仿
真
２０ 月 ０ 年５ １
一
种 改进 的基 于 ｐ ｒｔ 的 多 目标 粒 子 群算 法 ａｅｏ解
李 纬， 张兴 华
（ 南京工业大学 自动化学 院， 江苏 南京 ２ ００ ） １０ ９
摘要 ： 研究一种改进的多 目 标粒子群优化算法 ， 算法采用精英归档策 略， 利用粒 子的个体最 优定位 ， 通过 Ｐ ｒ ｏ ａ ｔ 支配关系更 ｅ 新全体粒子最优位置 ， 由档案库 中动态提供。根据 Ｐ ｒ ｏ ａ ｔ支配关系来更新粒子 的个体最优位置。使 用非劣解 目标 的密度距 ｅ 离度量非劣解前端的均匀性 ， 通过删除密度距离小 的非劣解提高非劣解前端的均匀性 。从归档 中根据粒子的密度距离大小 依 照概率选取作为粒子的全局最优位置 ， 以保持解 的多样性。标 准函数 的仿真实验结 果表明 ， 所提算法能够 获得 大量且较
ｆｏ ｔ ｒｎ．
ＫＥ Ｗ ＯＲ Ｙ ＤＳ：ａ ｉｅｓａｍ； ｌ —ｏｊｃｖ ｖｌ ｉ ａｙａ ｏｉ ｍ； ｐｉａ； ｙａ ｉ ｃ ｗ ｉｇ Ｐｒｃ ｗ ｒ Ｍｕ ｉ ｂｅｔ ｅｅｏ ｔ ｎｒ ｌ ｒｈ Ｏ ｔ ｌ Ｄ ｎ ｃ ｒ ｄｎ ｔｌ ｔ ｉ ｕｏ ｇ ｔ ｍ ｍ ｏ
Байду номын сангаас
１ 引 言
粒子群优化算法是由 Ｋ ｎ ｅｙ和 Ｅ ｅｈｒ提出的一种进 ｅ ｎｄ ｂｒａｔ
ｃ ｉｅ ｔ ｔ ｇ ｓｕ ｅ ｈｖ ｄ ｓ ａ ｅ ｙ ｉ ｓ ｄ，ｇｏ ａ ｅ ｔｐ ｓｔ ｎ ｉ ｒ ｖｄ ｄ ｂ ｏ —ｄ ｍｉ ａｅ ｏ ｕｉ ｎ ｎ ｔ ｅ ａ ｃ ｉｅ ａ ｄ ｉ ｄｖ ｄ ａ ｒ ｌｂ ｌｂ ｓ ｏ ｉ ｏ ｓ ｐ ｏ ｉｅ ｙ ｎ ｎ ｉ ｏ ｎ ｔｄ ｓ ｌ ｔ ｓ ｉ ｈ ｒ ｈ ｖ ｎ ｎ ｉｉ ｕ ｏ ｌ
求解多目标优化问题基于相对熵的pareto解演化算法

求解多目标优化问题基于相对熵的pareto解演化算法

求解多目标优化问题基于相对熵的Pareto 解演化算法!陈昌巨武秀文（武汉理工大学，武汉430070）摘要提出了一种求解多目标优化问题的基于相对熵的Pareto 解演化算法，首先分析了多目标优化中各目标间的补偿模式和非补偿模式，以及它们对应的Pareto 解演化算法和经典加权求和算法。

指出实际问题中，并不存在完全的补偿模式或完全的非补偿模式，往往是需要补偿，但要避免目标间极端不均衡解的产生。

故需在Pareto 解演化算法基础上引入目标间均衡性的评价。

然后利用相对熵作为均衡性的评价指标，在MOGA 算法的基础上引入相对熵，形成了EPEA 算法。

算法避免了各目标间极端不均衡解的产生，为方便寻找偏好解提供了途径。

数值实验证实了算法的有效性。

关键词多目标优化；Pareto 解演化算法；均衡性；相对熵中图法分类号TP 301.6过去10年中，对多目标优化问题的兴趣显著地增长，且涌现出了许多求解多目标优化问题的演化算法（MOEAS ，evolutionary algorithmS form multiobjectiveoptimization problemS ）［1］。

演化算法可以在一次种群演化中得到多个解，故非常适合于多目标优化问题［2］。

因此，许多MOEAS 被提了出来，旨在找到非劣解集。

Pareto 排序和适应值共享模型成为了MOEAS 的标准。

MOEAS 一次可得到一个非劣解的集合。

问题是如何从得到的多个解中选出所需要的解呢？一般对MOEAS 可任意从非劣解集中选出一个偏好解。

一些旨在从非劣解集中找到偏好解的区域的技术已经被提了出来［1］。

其中之一是guided domination ap-proch 。

它利用事先要求的矩阵a =（a ij ），其中a ij 是损失第i 个目标函数一个单位所换得的第j 个目标函数单位的数量，故需要更多的信息。

本研究提出了一种针对多目标优化问题的基于相对熵的Pareto 解演化算法（EPEA ，entropy-baSedpareto evolutionary algorithm ）。

基于Pareto熵的多目标粒子群优化算法_胡旺

基于Pareto熵的多目标粒子群优化算法_胡旺


通讯作者 : 胡旺 , E-mail: scuhuwang@
摘 要:
粒子群优化算法因形式简洁、收敛快速和参数调节机制灵活等优点,同时一次运行可得到多个解,且能逼
近非凸或不连续的 Pareto 最优前端,因而被认为是求解多目标优化问题最具潜力的方法之一.但当粒子群优化算法 从单目标问题扩展到多目标问题时,Pareto 最优解集的存储与维护、 全局和个体最优解的选择以及开发与开采的平 衡等问题亦随之出现.通过目标空间变换方法,采用 Pareto 前端在被称为平行格坐标系统的新目标空间中的分布熵 及差熵评估种群的多样性及进化状态,并以此为反馈信息来设计进化策略,使得算法能够兼顾近似 Pareto 前端的收 敛性和多样性.同时,引入格占优和格距离密度的概念来评估 Pareto 最优解的个体环境适应度,以此建立外部档案更 新方法和全局最优解选择机制,最终形成了基于 Pareto 熵的多目标粒子群优化算法.实验结果表明:在 IGD 性能指标 上,与另外 8 种对等算法相比,该算法在由 ZDT 和 DTLZ 系列组成的 12 个多目标测试问题集中表现出了显著的性 能优势. 关键词: 多目标优化问题;粒子群优化;平行格坐标系统;Pareto 熵;自适应参数 中图法分类号 : TP301
大多数工程和科学问题都可以归结为多目标优化问题(multiobjective optimization problem,简称 MOP),其 求解方法一直都是学术界和工程界共同关注的焦点 . 多目标优化问题通常存在多个彼此冲突的目标 ,其优化结 果为 Pareto 最优解集 . 与数学规划方法相比 , 进化算法因一次运行可得到多个解 , 且能逼近非凸或不连续的 Pareto 最优前端 ,从而被认为是更适合求解多目标优化问题的智能方法 . 粒子群优化算法(particle swarm optimization,简称 PSO)[1]是由 Kennedy 和 Eberhart 在 1995 年提出的仿生 算法 ,它是受到飞鸟集群活动规律的启发,根据社会学和心理学而建立的群体智能模型 .粒子群优化算法是一种 具有形式简洁、收敛快速和参数调节机制灵活等优点的进化算法 ,并且已经成功应用于单目标优化问题 ,被认 为是求解多目标优化问题最具潜力的方法之一 . 但当粒子群优化算法从单目标问题扩展到多目标问题而形成 多目标粒子群优化(multiple objective particle swarm optimization,简称 MOPSO)时 ,新的技术问题随之出现.多目 标优化问题的 Pareto 最优解集特征和粒子群优化算法的快速收敛特征,使得多目标粒子群优化算法面临以下 技术挑战 :① 维护存储 Pareto 最优解集的档案,使算法最终输出的 Pareto 前端能够兼顾收敛性和多样性 ,这是第 二代进化多目标算法的共性问题;② 从群体和个体的 Pareto 最优解集中分别选举全局最优解(gBest)和个体最 优 解 (pBest), 使 这 两 个 最 优 解 引 导 粒 子 尽 最 大 可 能 地 发 现 高 质 量 的 新 解 ;③ 平 衡 进 化 过 程 中 的 开 采 (exploration)和开发 (exploitation),使得种群既保持快速收敛的优点 ,但又尽可能地避免陷入局部 Pareto 前端或 者收敛到单一解.后面两个挑战是多目标粒子群优化算法区别于其他多目标进化算法的特有问题. 本文将根据多目标优化问题和粒子群优化算法的特征 ,采用近似 Pareto 前端的分布熵及其变化来估计种 群进化状态 ,并依据这些进化过程反馈信息设计具有动态平衡开采和开发能力的进化策略 ,形成基于 Pareto 熵 的多目标粒子群优化算法. 为了内容相对独立以及统一本文术语和符号 ,本文第 1 节简要介绍多目标优化问题和粒子群优化算法的 基本概念 .第 2 节综述与本文内容相关的多目标粒子群优化算法的研究现状和存在的问题 .第 3 节阐述 Pareto 熵的计算方法以及基于 Pareto 熵的种群进化状态检测方法.第 4 节描述本文算法的主要进化策略和完整的算法 流程 .第 5 节分析对比实验结果.最后 ,在第 6 节中给出全文结论 .
基于粒子群算法求解多目标优化问题

基于粒子群算法求解多目标优化问题

基于粒子群算法求解多目标优化问题一、本文概述随着科技的快速发展和问题的日益复杂化，多目标优化问题在多个领域，如工程设计、经济管理、环境保护等，都显得愈发重要。

传统的优化方法在处理这类问题时，往往难以兼顾多个目标之间的冲突和矛盾，难以求得全局最优解。

因此，寻找一种能够高效处理多目标优化问题的方法，已成为当前研究的热点和难点。

粒子群算法（Particle Swarm Optimization, PSO）作为一种群体智能优化算法，具有收敛速度快、全局搜索能力强等优点，已经在多个领域得到了广泛应用。

近年来，粒子群算法在多目标优化问题上的应用也取得了显著的成果。

本文旨在探讨基于粒子群算法求解多目标优化问题的原理、方法及其应用，为相关领域的研究提供参考和借鉴。

本文首先介绍多目标优化问题的基本概念和特性，分析传统优化方法在处理这类问题时的局限性。

然后，详细阐述粒子群算法的基本原理和流程，以及如何将粒子群算法应用于多目标优化问题。

接着，通过实例分析和实验验证，展示基于粒子群算法的多目标优化方法在实际问题中的应用效果，并分析其优缺点。

对基于粒子群算法的多目标优化方法的发展趋势和前景进行展望，为未来的研究提供方向和建议。

二、多目标优化问题概述多目标优化问题（Multi-Objective Optimization Problem, MOP）是一类广泛存在于工程实践、科学研究以及社会经济等各个领域中的复杂问题。

与单目标优化问题只寻求一个最优解不同，多目标优化问题涉及多个相互冲突的目标，这些目标通常难以同时达到最优。

因此，多目标优化问题的解不再是单一的最优解，而是一组在各个目标之间达到某种平衡的最优解的集合，称为Pareto最优解集。

多目标优化问题的数学模型通常可以描述为：在给定的决策空间内，寻找一组决策变量，使得多个目标函数同时达到最优。

这些目标函数可能是相互矛盾的，例如，在产品设计中，可能同时追求成本最低、性能最优和可靠性最高等多个目标，而这些目标往往难以同时达到最优。