专栏首页人工智能与演化计算成长与进阶IGD反转世代距离-多目标优化评价指标概念及实现

IGD反转世代距离-多目标优化评价指标概念及实现

IGD反转世代距离-多目标优化评价指标概念及实现

参考资料 多目标进化优化[1]-郑金华老师,邹娟老师著 实验室人手一本人人必看的宝藏图书!

  • IGD(Inverted Generational Distance)是常用的可以同时评价算法收敛性和多样性的指标,中文名反转世代距离。

从GD到IGD

  • 先被提出的用于评价多目标算法收敛性的指标是GD(Generational Distance),用来表示
PF_{known}

PF_{true}

之间的间隔距离,计算式被定义为:

GD=\frac{(\sum^{n}_{i=1}d^p_i)^{1/p}}{n}

其中n表示

PF_{known}

中点的个数,p表示目标维数,

d_{i}

表示目标空间中得到的 每个点

PF_{known}

距离

PF_{true}

参考点(类似于答案)的最近欧式距离的平均值 。若此值为0,则表示

PF_{known} == PF_{true}

.

  • 欧式距离的平面版本初中我们就学过^ _ ^
  • 举个[1]中二维目标的例子

计算可得:

d_1=\sqrt[2]{(2.5-2)^2+(9-8)^2}
d_1=\sqrt[2]{(3-3)^2+(6-6)^2}
d_1=\sqrt[2]{(5-4)^2+(4-4)^2}
  • 因此,
PF_{known}

PF_{true}

之间的间隔距离为

GD=\sqrt[2]{1.118^2+0^2+1^2}/3=0.5
  • 值得一提的是,某种意义上可以这样认为:GD是从自己得到的每个点指向最近的真实前沿上的点的欧式距离的平均

IGD

  • 可以发现,GD的方式只能够评价算法的收敛性 。为了同时评价算法的 收敛性和多样性 ,IGD被提出了。区别在于 IGD是从真实帕累托前沿上的参考点射向算法的得到的解,即是从
PF_{true}

射向

PF_{known}

,因此被称为 反向世代距离

  • 思路是:从真实帕累托前沿上均匀取点,对于 真实前沿上的每个点找到已知帕累托前沿上距离最近的点 ,将这些点之间距离相加并取平均。和GD略微不同的是没有开方的操作!只用取平均就行,分母是从真实前沿上取点的个数。
IGD=\frac{\sum^{n}_{i=1}|d_i|}{n}

其中n表示

PF_{true}

中点的个数,

d_{i}

表示目标空间中 真实前沿的每个点距已知前沿的最近欧式距离 。此值越小,意味着算法的综合性能越好。

关于IGD的解释

  • 由于两点间的距离是可逆的,A->B的距离和B->A的距离相等,那么真实前沿上点到已知前沿的最小值必定包含了,已知前沿到真实前沿的最小值(IGD),假设真实前沿上的点比已知前沿的点多这种观点是错的,因为边是有向的,从一个顶点出发只能连接一另一端的点,而不能同时连接两个终点。GD和IGD并不是从所有边集合中挑选出其中距离最短的边,而是从指定顶点出发的距离最短的有向边!
  • 例如,显然A-D和A-B是最短的两条边。计算GD时,遍历PFknown,会选择A->D,然后到B,B会选择B->D。计算IGD时,遍历PFtrue,C会选C->A,即使A->D更短,但是对于C而言并不会考虑A的感受,D会选择D->B,即时D->A也很短,但是D只能做出最好的选择,很明显D->B比D->A更好。而为了避免同一个点指向两个端点,即取最小的距离,使用循环的方法。在找到最近点后就会跳过该点进入下一个点的查找最近距离的步骤
  • 也直接引用郑金华老师书[1]中的例子进行介绍。
  • 为什么选择从PFtrue出发放出射线呢?还是因为PFtrue是分布均匀的答案,从PFtrue出发才能让一个PFknown不仅仅是 靠向PFtrue还要分布均匀因此PF true中采样点的数目十分重要,采样点越多,分布越均匀结果才越精确可靠

IGD实现

matlab

IGD = 0;% 初始化IGD为0
for i = 1:51 % 遍历PFtrue中的所有电
    % data中保存的是真实PF
    % data(i,1)表示第i行的第1列数
    % 得到一个单元格中数值是data(i,)形状是(pop2,1)的长条状列向量
    c1 = data(i,1)*ones(pop2,1);% 第一个目标的目标值
    c2 = data(i,2)*ones(pop2,1);% 第二个目标的目标值
    %对于一个参考点,使用所有实际点在两个目标上对应项相减后分别在两个目标上平方
    % sum(,2)按行相加
    % min 取最小的距离开方
    IGD = IGD + sqrt(min(sum((T2_data-[c1 c2]).^2,2)));
end
% 对PFtrue上所有点取平均
store(2,generation)=IGD/51;  

本文分享自微信公众号 - DrawSky(wustcsken),作者:CloudXu

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [吴恩达机器学习笔记]12支持向量机6SVM总结

    用以解决 SVM 最优化问题的软件很复杂,且已经有研究者做了很多年数值优化。因此强烈建议使用高优化软件库中的一个,而不是尝试自己落实一些框架。有许多好的软件库,...

    DrawSky
  • 一起来学演化计算-matlab基本函数randn,rand, orth

    DrawSky
  • [吴恩达机器学习笔记]15非监督学习异常检测7-8使用多元高斯分布进行异常检测

    (每个样本都可以表示为一个 1 _ n 的向量)每个特征的平均值(对应特征求平均)

    DrawSky
  • 迪杰斯特拉(dijkstra)c语言实现方法

    迪杰斯特拉(dijkstra)是用来实现查找一个点到其它点最短路径的一种方法。通过查找从起点到最短距离的点,然后将该点放入到集合中,代表以及找到起点到这一点的最...

    诸葛青云
  • 快速获取一个网站的所有资源,图片,扒站,仿站必备工具

    网络爬行(也称为网络抓取)在当今的许多领域得到广泛应用。它的目标是从任何网站获取新的或更新的数据并存储数据以便于访问。Web爬虫工具越来越为人所知,因为Web爬...

    叉叉敌
  • 空间研究领域的 10大NASA机器人,也许你一个都不知道

    文 / R. Colin Johnson 谁家空间机器人最有名?还看美国国家航天航空局(NASA)!一直以来,NASA及其喷气推进实验室(JPL)开发了一系列空...

    机器人网
  • selenium元素定位

    muntainyang
  • 机器学习(四)通过递归的矩阵向量空间预测组合语义摘要简介方法结果结论

    Semantic Compositionality Through Recursive Matrix-Vector Spaces 摘要 单字矢量空间模型已经在学...

    致Great
  • 具有EC2自动训练的无服务器TensorFlow工作流程

    机器学习训练工作通常是时间和资源密集型的,因此将这一过程整合到实时自动化工作流程中可能会面临挑战。

    代码医生工作室
  • Spring 源码第六弹!松哥和大家聊聊容器的始祖 DefaultListableBeanFactory

    当 ClassPathResource 将文件以 IO 流的方式输出后,接下来就是构造 XmlBeanFactory ,XmlBeanFactory 功能有限,...

    江南一点雨

扫码关注云+社区

领取腾讯云代金券