多目标优化算法——多目标粒子群优化算法(MOPSO)

Handling Multiple Objectives With Particle Swarm Optimization(多目标粒子群优化算法)

一、摘要:

本文提出了一种将帕累托优势引入粒子群优化算法的方法,使该算法能够处理具有多个目标函数的问题。与目前其他将粒子群算法扩展到解决多目标优化问题的建议不同,我们的算法使用二级(即外部)粒子库,这些粒子库稍后被其他粒子用来引导它们自己的飞行。我们还加入了一个特殊的突变算子,丰富了我们算法的探索能力。采用几个测试函数和指标,从进化多目标优化的标准文献中验证了所提出的方法。结果表明,该方法具有很强的竞争性,可以被认为是解决多目标优化问题的可行选择。

二、概念解释

1.支配(Dominance ) : 在多目标优化问题中,如果个体p至少有一个目标比个体q好,而且个体p的所有目标都不比q差;那么称个体p支配个体q

S1支配S2:

在这里插入图片描述

S1和S2互不支配:

在这里插入图片描述

2.序值(Rank): 如果p支配q,那么p的序值比q低;如果p和q互不支配,那么p和q有相同的序值

3.拥挤距离(Crowding Distance): 表示个体之间的拥挤程度,测量相同序值个体之间的距离。

4.帕累托(Pareto)

pareto最优解与pareto最优解集:
如果对于优化问题的一个解A,不存在其他的解可以支配解A,那么解A就是一个pareto最优解。显然pareto最优解不只一个,由这些解组成的集合就称为pareto最优解集。pareto最优解集中所有解的互相之间都是非支配的关系,也就是解集中不存在任何一个解完全优于其他解(要和平共处)。所以,和PSO最后要求出唯一一个最优解不同,MOPSO的目标是求出一个互相之间为非支配关系的解的集合,也就是pareto最优解集。

帕累托最优解也称为非劣解、可容许解或有效解;它们对应的向量称为非支配向量。

下图中:S1、S3、S5、S6、S9之间互不支配,且不被其他解支配,这些解称为Pareto解或非支配解。在下图的多目标优化问题中,如果在整个可行的变量空间中再不能找到解能够支配上述五个解,那么上述五个解称为Pareto最优解,所有的Pareto最优解组成Pareto最优解集

在这里插入图片描述

5.帕累托最优解对应的目标函数值就是帕累托最优前沿,对于两个目标的问题,其Pareto最优前沿通常是条线。而对于多个目标,其Pareto最优前沿通常是一个超曲面

6.外部存档:因为粒子群算法在迭代过程中各个粒子的速度和位置都是不断变化的,适应度(目标函数)也随之变化,所以一般都需要采用一个外部存档将pareto最优解的数据存储下来。

三、算法原理

​ 1.算法流程图
在这里插入图片描述

  1. MOPSO:
  • 根据pareto支配原则,计算得到Archive集(存放当前的非劣解)计算局部最优pbest
  • 计算Archive集中的拥挤度在Archive集选择全局最优gbest
  • 更新粒子的速度和位置,并计算适应值更新Archive集(需注意防止溢出)
  1. PSO和MOPSO的大框架一致,MOPSO只是根据多目标问题改进了PSO中的pbest和gbest的选取方法
  • 速度更新公式:

在这里插入图片描述

  • 位置更新公式:

在这里插入图片描述

​ 当一个决策变量超出其边界时,我们会做两件事:

​ 1)决策变量取其相应边界(下边界或上边界)的值;

​ 2)它的速度乘以**-1**,以便它在相反的方向上搜索。

  • pbest的选取:
    单目标问题中,PSO可以根据适应度直接找出该粒子历史最好的位置
    多目标问题中,MOPSO找出该粒子历史最好的位置(保存于该粒子结构体的一个属性中),(即如果记忆中的位置支配当前位置时,则保留记忆中的位置;否则当前位置取代记忆中的位置;)如果在更新当前粒子的历史最好位置发现当前位置与历史最佳互不支配0.5概率随机选一个

    在这里插入图片描述

  • gbest的选取:
    单目标问题中,PSO可以根据适应度直接找出当前最好的粒子
    多目标问题中,MOPSO根据Pareto找出当前最好的粒子集合,最后找到最不拥挤的那个粒子

    MOPSO中,gbest变成了REP[h],REP[h]是从存储库中获取的值;索引h的选择方式如下:那些包含一个以上粒子的超立方体的适应度值等于:任何数字x>1除以它们包含的粒子数的结果。这旨在降低那些包含更多粒子的超立方体的适应度,它可以被视为一种适应度共享的形式。然后,我们将这些适应度值应用于轮盘赌来选择超立方体,再选择相应粒子。当选中某个超立方体后,我们随机选择超立方体中的一个粒子。

  1. 外部存档

​ 外部存档主要目的是保存搜索过程中发现的非支配向量的历史记录,由两个主要部分组成:存档控制器网格

存档控制器:它的功能是决定一个解是否能被添加到归档集中。决策过程如下:算法的种群每次迭代发现的非支配向量与外部储存库的向量进行比较,这个外部储存库在一开始的时候是空的。如果外部的归档集是空的,则接受当前解(见Fig1,case1)。如果这个新解被外部归档集中的某个个体支配,则新解将自动被移除(见Fig1,case2)。否则如果外部归档集中的个体没有一个支配想进入归档集的解,则这个解将被存储在外部归档集中。如果归档集中存在某些解被新解支配,则这些解将从归档集中移除(见Fig1,case3、4)。最后,如果外部种群达到最大容量,则启动自适应网格程序(见Fig1,case5)。

在这里插入图片描述

网格:为了获得均匀分布的Pareto前沿,我们的方法使用了[21]中提出的自适应网格技术。其基本思想是使用一个外部归档集储存所有非支配解。在归档集中,目标函数空间被分割成几个区域,如Fig2所示。注意,如果外部种群中的个体在当前网格边界外,则必须重新计算网格并且重新定位网格中的每个个体(见Fig3)。

在这里插入图片描述

自适应网格实际上是一个超立方体形成的空间。这个超立方体的维度和目标函数一样多。每个超立方体可以被解释为一个不含任何个体的地理区域。自适应网格技术的主要优点是其计算开销少于小生境技术。唯一的例外是如果网格在每一代都必须更新。此时,自适应网格技术的计算复杂度和小生境技术的计算复杂度相同。自适应网格用于实现解的均匀分布。为了实现这个目标,有必要提供确定的信息(即子网格的数量)。

  1. 突变算子:突变算子通过引入随机扰动,有效避免了粒子群陷入局部最优,提升了算法的全局搜索能力。均匀突变保证了随机性,而非均匀突变则随着迭代次数的增加逐渐减少突变程度,平衡了探索和开发的关系。
四、ZDT问题运行结果
  1. ZDT1

    在这里插入图片描述

  2. ZDT2

    在这里插入图片描述

  3. ZDT3

    在这里插入图片描述

  4. ZDT4

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/479811.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++设计模式——Singleton单例模式

一、单例模式的定义 单例模式,英文全称Singleton Pattern,是一种创建型设计模式,它保证一个类在程序中仅有一个实例,并对外提供一个访问的该类实例的全局接口。 单例模式通常用于需要控制对象资源的开发场景,一个类…

Python学习35天

# 定义父类 class Computer: CPUNone MemoryNone diskNone def __init__(self,CPU,Memory,disk): self.disk disk self.Memory Memory self.CPU CPU def get_details(self): return f"CPU:{self.CPU}\tdisk:{self.disk}\t…

<项目代码>YOLOv8 停车场空位识别<目标检测>

YOLOv8是一种单阶段(one-stage)检测算法,它将目标检测问题转化为一个回归问题,能够在一次前向传播过程中同时完成目标的分类和定位任务。相较于两阶段检测算法(如Faster R-CNN),YOLOv8具有更高的…

mac下Gpt Chrome升级成GptBrowser书签和保存的密码恢复

cd /Users/自己的用户名/Library/Application\ Support/ 目录下有 GPT\ Chrome/ Google/ GptBrowser/ GPT\ Chrome 为原来的chrome浏览器的文件存储目录. GptBrowser 为升级后chrome浏览器存储目录 书签所在的文件 Bookmarks 登录账号Login 相关的文件 拷贝到GptBrow…

GB28181系列二:SIP信令

我的音视频/流媒体开源项目(github) GB28181系列目录 目录 一、SIP报文介绍 二、SIP交互流程: 1、Session Model 2、Pager Model 3、SIP信令交互过程中的3个定义 三、媒体传输(SDP和RTP) 一、SIP报文介绍 这里将会介绍SIP…

ViSTa:一个包含4000多个视频和逐步描述的层次化数据集,用于评估VLMs在不同复杂性任务中的表现。

2024-11-22,由Google DeepMind和MATS机构创建的ViSTa数据集,为评估视觉语言模型(VLMs)在理解基于顺序的任务方面的能力提供了新的视角,这对于强化学习中的成本降低和安全性提升具有重要意义。 数据集地址:…

区块链:波场-TRON链

注意: 1、调试时请将所有的API地址都换成 https://api.trongrid.io 以免报错等问题 https://api.trongrid.io 主网 (Mainnet) 适用于生产环境 https://api.shasta.trongrid.io 测试网 (Shasta) 适用于开发者测试 https://nile.trongrid.io 测试网 (Nile) …

【适配】屏幕拖拽-滑动手感在不同分辨率下的机型适配

接到一个需求是类似下图的3D多房间视角,需要拖拽屏幕 问题 在做这种屏幕拖拽的时候发现,需要拖拽起来有跟手的感觉,会存在不同分辨率机型的适配问题。 即:美术调整好了机型1的手感,能做到手指按下顶层地板上下挪动&…

比特币libsecp256k1中safegcd算法形式化验证完成

1. 引言 比特币和其他链(如 Liquid)的安全性取决于 ECDSA 和 Schnorr 签名等数字签名算法的使用。Bitcoin Core 和 Liquid 都使用名为 libsecp256k1 的 C 库来提供这些数字签名算法,该库以其所运行的椭圆曲线命名。这些算法利用一种称为modu…

『VUE』elementUI dialog的子组件created生命周期不刷新(详细图文注释)

目录 1. 测试代码分析令人迷惑的效果 分析原因解决方法 如何在dialog中反复触发created呢?总结 欢迎关注 『VUE』 专栏,持续更新中 欢迎关注 『VUE』 专栏,持续更新中 主要是在做表单的时候想要有一个编辑表单在dialog弹窗中出现,同时dialog调用的封装的…

深入探讨 Redis 持久化机制:原理、配置与优化策略

文章目录 一、引言二、Redis持久化概述三、RDB(Redis DataBase)持久化1、RDB概念与工作原理2、RDB的配置选项3、RDB优化配置项4、RDB的优势与劣势 三、AOF(Append-Only File)持久化1、AOF概念与工作原理2、AOF的三种写回策略3、Re…

使用爬虫时,如何确保数据的准确性?

在数字化时代,数据的准确性对于决策和分析至关重要。本文将探讨如何在使用Python爬虫时确保数据的准确性,并提供代码示例。 1. 数据清洗 数据清洗是确保数据准确性的首要步骤。在爬取数据后,需要对数据进行清洗,去除重复、无效和…

(计算机网络)期末

计算机网络概述 物理层 信源就是发送方 信宿就是接收方 串行通信--一次只发一个单位的数据(串行输入) 并行通信--一次可以传输多个单位的数据 光纤--利用光的反射进行传输 传输之前,要对信源进行一个编码,收到信息之后要进行一个…

111. UE5 GAS RPG 实现角色技能和场景状态保存到存档

实现角色的技能存档保存和加载 首先,我们在LoadScreenSaveGame.h文件里,增加一个结构体,用于存储技能相关的所有信息 //存储技能的相关信息结构体 USTRUCT(BlueprintType) struct FSavedAbility {GENERATED_BODY()//需要存储的技能UPROPERT…

Js-对象-04-Array

重点关注:Array String JSON BOM DOM Array Array对象时用来定义数组的。常用语法格式有如下2种: 方式1: var 变量名 new Array(元素列表); 例如: var arr new Array(1,2,3,4); //1,2,3,4 是存储在数组中的数据&#xff0…

【Flink-scala】DataStream编程模型之 窗口的划分-时间概念-窗口计算程序

DataStream编程模型之 窗口的划分-时间概念-窗口计算程序 1. 窗口的划分 1.1 窗口分为:基于时间的窗口 和 基于数量的窗口 基于时间的窗口:基于起始时间戳 和终止时间戳来决定窗口的大小 基于数量的窗口:根据固定的数量定义窗口 的大小 这…

Java代码操作Zookeeper(使用 Apache Curator 库)

1. Zookeeper原生客户端库存在的缺点 复杂性高:原生客户端库提供了底层的 API,需要开发者手动处理很多细节,如连接管理、会话管理、异常处理等。这增加了开发的复杂性,容易出错。连接管理繁琐:使用原生客户端库时&…

linux系统下如何将xz及ISO\img等格式压缩包(系统)烧写到优盘(TF卡)

最近用树莓派做了个NAS,效果一般,缺少监控及UI等,详细见这篇文章: https://blog.csdn.net/bugsycrack/article/details/135344782?spm1001.2014.3001.5501 所以下载了专门的基于树莓派的NAS系统直接使用。这篇文章是顺便复习一…

带有悬浮窗功能的Android应用

android api29 gradle 8.9 要求 布局文件 (floating_window_layout.xml): 增加、删除、关闭按钮默认隐藏。使用“开始”按钮来控制这些按钮的显示和隐藏。 服务类 (FloatingWindowService.kt): 实现“开始”按钮的功能,点击时切换增加、删除、关闭按钮的可见性。处…

MD5算法加密笔记

MD5是常见的摘要算法。 摘要算法: 是指把任意⻓度的输⼊消息数据转化为固定⻓度的输出数据的⼀种密码算法. 摘要算法是 不可逆的, 也就是⽆法解密. 通常⽤来检验数据的完整性的重要技术, 即对数据进⾏哈希计算然后⽐ 较摘要值, 判断是否⼀致. 常⻅的摘要算法有: MD5…