专栏首页智能算法外部存档指导的多目标进化算法简略版

外部存档指导的多目标进化算法简略版

正值毕业季,小编这里简洁明了地讲述一下自己毕业设计相关的算法。

当初之所以跟着导师学习进化算法,首先很有意思的一点是,进化算法是一种种群类算法,设计算法思路的时候感觉就像在玩策略游戏,讲求如何排兵布阵。

通俗地讲,进化算法是一种模拟生物进化策略的仿生学算法,基本的算法流程无非就是:初始化种群,交叉变异,评价选择,更新种群。

这样如此循环,当达到最优或最大迭代值时即停止进化过程。看到这里,或许聪明的同学应该明白进化算法的两个关键点:

1. 如何产生新的子代

2. 如何保留优秀的子代

如果以上四个步骤,每一种都涉及一些小的技巧策略,求解起来会有很大不同。

初始化种群的过程,涉及种群中个体的编码,随机化或启发式,会对进化效率起到不一样的效果。

交叉变异的过程,是产生新的子代的关键步骤:如常见的差分(DE)进化算法、粒子群(PSO)算法对于这个步骤的涉及可谓用心独到(后面会对这些算法有具体的文章,记得保持关注~)简单的说,就是要涉及一种扰动,去影响个体之间的关系,加强个体之间的多样性与趋同性的平衡 。

(在遗传操作中,对于离散问题,局部搜素的方式更为有效)

评价与选择的过程,评价就是涉及到相关的目标函数,说到这一点,先插一段关于标题的多目标支配原则:

最简单的一个例子,现实生活中我们面临的优化问题通常会相互矛盾,当你想买一辆性价比最好的车,其实隐含着两个目标,性能函数与价格函数,所以其实对于不同的人,会去选择一辆价格较低但性能次优的车,或者选择一辆性能优良,价格昂贵的车;所以我们所说的多目标,并不是产生一个最优解,而是一组最优的解集。这种方式更符合实际,无论是机械手臂参数设计还是机电一体化设计,为我们提供多种方案。所以,我们以多目标支配原则的数学表达式说明:

我们在多目标的优化问题中,需要找出支配(dominate)关系而选择保留个体,而非简单的像单目标一样,基于单个优化函数的值去判断,下图也为读者以举例方式说明了支配关系:

看到这里,发现我们的策略游戏的难度增大,会不会激发起学习进化算法的热情呢?别着急,困难还有!

现实生活中,我们的优化问题,不仅仅是多目标,还有在目标空间或自变量空间的约束函数。

所以在选择个体保留的机制中还涉及了不少的策略:如CDP约束支配原则;经典的非支配排序和其中的拥挤距离;不可行解驱动机制;根据大师兄最新的论文中还改进了传统的CDP约束支配原则,在一些问题中,考虑个体与个体之间的夹角关系的ACDP基于角度支配原则等。单纯的精英保留已经不足以解决目前的问题啦!

更新种群,这个步骤或许感觉像与评价选择有些类似,但是如何在种群的角度上去看待也是有策略性的:

如经典的MOEA/D基于分解的多目标进化算法,其核心思路就是通过将多个目标根据不同权重去分解,在目标空间上以发散的射线分散出不同的进化搜索方向(子问题),基于每个子问题都会有一定的搜索资源,在进行交叉变异的时候就会对不同的子问题有所选择,重点在于利用相邻子问题之间的联系,以达到“个体在搜索信息上的互通有无”也就是我们前面所说的个体与个体之间的关系。

而经典的NSGAII在非支配排序上的更新则是通过父代和子代2N个(假设种群规模为N)个体进行非支配排序和拥挤距离的评价后整体更新;也会有很多改进非支配排序的算法,比如改变最后一层排序的标准,引入个体差异扰动,多对种群的多样性在一定情况下有所改进。

那么真正的重点来了:本文的算法精髓在于,通过双种群的机制,以特别的方式将不同策略进行有效结合。先上图:

图1

图2

图3

图4

如图所示,优化的目标函数F1和F2,以及两个种群:工作种群和外部存档指导种群。图1中,在根据moead不同的方向,分散着随机分布的种群个体,其中绿色、紫色、灰色部分为目标空间不规则约束;黑色的点是目标空间的最优解集Pareto前沿;图2中,种群开始向着最优目标进化,图3中根据不同子问题进入外部存档种群的非支配排序NSGAII结果,产生不同的概率,更容易进入外部种群的子问题方向获得更多搜索资源,即最后的图4,通过这两种方式,以概率的方式联系来进行动态的搜素资源分配。

关于算法的两个核心算法,我们会在后续的文章中分享给大家,感兴趣的读者也可以自己找到原始论文资料品读学习。

通过这样的描写,基本可以看出进化算法是很少涉及数学公式的,但是目前的发展趋势是如何加入机器学习理论,让进化算法更加“聪明”地去学习,而不是仅仅依靠随机形式的自然方式。小编也会同大家一起继续学习。

参考文献:An External Archive Guided Multi-objective Evolutionary Algorithm Based on Decomposition for Combinatorial Optimization” Xinye.Cai, Yexing.Li, Zhun.Fan, Qingfu.Zhang . IEEE Transactions on Evolutionary Computation. 2013. 1089-778X

回复数字或算法名称即可查看相关文章:

1. 决策树算法之一C4.5

2. 数据挖掘之Apriori算法

3. 网页排序算法之PageRank

4. 分类算法之朴素贝叶斯分类

5. 遗传算法如何模拟大自然的进化?

6. 没有公式如何看懂EM算法?

7. Python实现KNN算法

8. 基础聚类算法:K-means算法

9. 集成学习算法----Adaboost

10. 分类回归树算法---CART

11. EAG多目标进化算法

本文分享自微信公众号 - 智能算法(AI_Algorithm),作者:智能算法

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

原始发表时间:2016-05-24

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 主宰这个世界的10大算法

    出自linux中文社区 链接:https://linux.cn/article-3125-1.html 什么是算法? 简而言之,任何定义明确的计算步骤都可称为算...

    智能算法
  • 机器学习常见算法分类汇总

    来源: IT经理网 链接:www.ctocio.com/hotnews/15919.html 机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作...

    智能算法
  • 机器人算法专题介绍

    算法 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规...

    智能算法
  • 11位机器学习大牛最爱算法全解

    【新智元导读】“你最喜欢的机器学习算法是什么?”这个问题有些像“你最喜欢的颜色是什么?”说不重要吧,细究起来,颇有深意。本文摘选一些机器学习大牛在 Quora ...

    新智元
  • 主宰这个世界的10大算法,来了解一下

    简而言之,任何定义明确的计算步骤都可称为算法,接受一个或一组值为输入,输出一个或一组值。(来源:homas H. Cormen, Chales E. Leise...

    磐创AI
  • 极客算法训练笔记(一),算法学习方法篇

    付完款那一刻我忍不住吐槽“哇塞,我可真有钱”,一看余额“我去,伤心的人那么多~我变成了其中一个~”(这首歌叫啥来着,好像有点应景)。

    阿甘的码路
  • 同样是罪犯,36岁比19岁危害小,这是算法的逻辑?

    我们可以看到它们在世间发挥作用,我们知道它们正塑造我们周遭的各种事物,但我们大多数人并不知道算法是什么——或者算法如何影响我们。

    用户1737318
  • 从这个角度去理解数据结构与算法更容易

    在互联网、大数据、人工智能火爆的今天,“算法”这个词几乎妇孺皆知,业已成为“高薪”“牛X”的代名词。

    黄泽杰
  • 了解一下“算法”,每个人都要掌握的编程知识

    假设我们有一个难题需要解决,那怎么解决呢?解决的步骤怎样呢?如果有一样东西能把这个解决这个难题的步骤描述出来,那就叫做这个问题的算法。

    讲编程的高老师
  • Java数据结构和算法(一)——简介

      本系列博客我们将学习数据结构和算法,为什么要学习数据结构和算法,这里我举个简单的例子。   编程好比是一辆汽车,而数据结构和算法是汽车内部的变速箱。一个开车...

    IT可乐

扫码关注云+社区

领取腾讯云代金券