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

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

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

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

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

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