多目标进化优化（小结-基于《多目标进化优化》）_多目标进化优化 郑金华pdf

前言

本博文是基于：科学出版社，郑金华，邹娟 所著的 《多目标进化优化》 进行一个小总结。谈谈对多目标的理解，以及帮助想要阅读这本书的同学，做一个模板解读，这样看书的时候有一个大概的了解。对多目标思想有个概述，尽可能降低阅读门槛，毕竟大家都是玩程序的侧重点重在coding，重在思路，具体的理论深入应该是在writing的时候，或者算法优化的时候，咱们先把这个架子搭起来再说。这里先申明，一定要把本文看完，因为有些概念为了前期便于理解我做了一些“错误”的说明，后面才有“纠正”。

前面在春节前我写了一个关于 遗传算法的博文 遗传算法小讲解，那么接下来我们的EA（本质上也是GA的升级版）进行一个说明。

首先我们要搞清楚什么是多目标，什么是单目标，什么是高维度。

高维度：其实就是一个需要把优化的方程有多个参数

单目标：其实就是我们只有一个目标方程，一个目标方程去优化，其他的作为条件约束，类似于我们高中经常做的线性规划，求那个Z=G(x) 的时候，在一个平面内最大。

多目标：就是我们有多个目标方程，但是这些方程存在某种冲突，也和那个高中的线性规划类似，但是我们现在求的不仅仅只是一个Z=G(x) 还有 N=H(x)

并且 Z,N存在某种联系但是 相互冲突。所以这里对于多目标就有了两种思路呗，由于存在某种联系，那么我们就把Z，N 想办法组合在一个变成单目标优化，然后添加一些条件在那个平面内。当然这里只是举个例子，实际上课不见得是平面，可能是立方体，有可能是高维度（N>3个变量）

我们这里重点探讨的不是合并单目标，这个主要是数学上的问题，如何合并，如何合理地合并等等。这里在我们的 多目标进化优化当中 叫做 MOEA/D 人家有个好听的名字基于分解的多目标优化 这个不是我们的重点，而且如果我能这样干，我绝对不一定要选择这种方式去实现单目标，粒子群不好吗，退货不好吗？

所以我们的目标是基于支配的多目标优化

基于支配的多目标

在了解什么是基于支配的多目标之前，我们一定，需要去理解一下我们的GA算法，也就是这段代码。

import numpy as np
import matplotlib.pyplot as plt


Population_Size = 100
Iteration_Number = 200
Cross_Rate = 0.8
Mutation_Rate = 0.003
Dna_Size = 10
X_Range=[0,5]


def F(x):
    '''
    目标函数，需要被优化的函数
    :param x:
    :return:
    '''
    return np.sin(10 * x) * x + np.cos(2 * x) * x

def CrossOver(Parent,PopSpace):
    '''
    交叉DNA，我们直接在种群里面选择一个交配
    然后就生出孩子了
    :param parent:
    :param PopSpace:
    :return:
    '''
    if(np.random.rand()) < Cross_Rate:

        cross_place = np.random.randint(0, 2, size=Dna_Size).astype(np.bool)
        cross_one = np.random.randint(0, Population_Size, size=1) #选择一位男/女士交配
        Parent[cross_place] = PopSpace[cross_one,cross_place]

    return Parent

def Mutate(Child):
    '''
    变异
    :param Child:
    :return:
    '''
    for point in range(Dna_Size):
        if np.random.rand() < Mutation_Rate:
            Child[point] = 1 if Child[point] == 0 else 0
    return Child


def TranslateDNA(PopSpace):
    '''
    把二进制转化为十进制方便计算
    :param PopSpace:
    :return:
    '''
    return PopSpace.dot(2 ** np.arange(Dna_Size)[::-1]) / float(2 ** Dna_Size - 1) * X_Range[1]

def Fitness(pred):
    '''
    这个其实是对我们得到的F(x)进行换算，其实就是选择的时候
    的概率，我们需要处理负数，因为概率不能为负数呀
    pred 这是一个二维矩阵
    :param pred:
    :return:
    '''

    return pred + 1e-3 - np.min(pred)

def Select(PopSpace,Fitness):
    '''
    选择
    :param PopSpace:
    :param Fitness:
    :return:
    '''
    '''
    这里注意的是，我们先按照权重去选择我们的优良个体，所以我们这里选择的时候允许重复的元素出现
    之后我们就可以去掉这些重复的元素，这样才能实现保留良种去除劣种。100--》70（假设有30个重复）
    如果不允许重复的话，那你相当于没有筛选
    '''
    Better_Ones = np.random.choice(np.arange(Population_Size), size=Population_Size, replace=True,
                           p=Fitness / Fitness.sum())
    # np.unique(Better_Ones) #这个是我后面加的

    return PopSpace[Better_Ones]


if __name__ == '__main__':
    PopSpace = np.random.randint(2, size=(Population_Size, Dna_Size))  # initialize the PopSpace DNA

    plt.ion() 
    x = np.linspace(X_Range, 200)

    # plt.plot(x, F(x))
    plt.xticks([0,10])
    plt.yticks([0,10])

    for _ in range(Iteration_Number):
        F_values = F(TranslateDNA(PopSpace))  

        # something about plotting
        if 'sca' in globals():
            sca.remove()
        sca = plt.scatter(TranslateDNA(PopSpace), F_values, s=200, lw=0, c='red', alpha=0.5)
        plt.pause(0.05)

        # GA part (evolution)
        fitness = Fitness(F_values)
        print("Most fitted DNA: ", PopSpace[np.argmax(fitness)])
        PopSpace = Select(PopSpace, fitness)
        PopSpace_copy = PopSpace.copy()
        for parent in PopSpace:

            child = CrossOver(parent, PopSpace_copy)
            child = Mutate(child)

            parent[:] = child

    plt.ioff()
    plt.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

这段代码是关于我们遗传算法的单目标优化，实际上对于多目标进化算法的算法结构，我们只需要大致修改两个方面同时也就是这两个方面的修改衍生出大量的理论还是那句话说起来简单，就像你改个Linux内核重新编译换个UI做新的操作系统一样。（我还记得某学长自己给自己的手机的termianal搞了个apk install）

回到主题，我们聊聊什么是支配，首先明确需求，我们的目标就和我们曾经高中做的线性规划类似（只是更加复杂）我们要求两个目标函数 Z(x),N(x) 两者存在冲突，但是需要让两者组成的系统都变小。

举个例子。

选择合适的点（支配的概念）

看到了，前面的例子了嘛，现在我们看到 X ，两个函数都在下降，按道理是有可能产生我们想要的解的，但是一定是最优解吗？不一定是吧，例如在X里面取得函数值分别为 4,5
但是在X2里面取得（5,3），（黄色线，红色线）这个是有可能的吧，所以我们得选择合适的点，来作为我们的一组解，这个是我们最直观的感受吧。

那么现在请联想到我们前面的遗传算法代码，如果我叫你去优化这个函数，你应该怎么做，代码应该怎么改？

首先要改的是 def F(x)对吧，第二个是什么？显然是求取适应度的函数呀

那么问题来了，这个适应度的函数如何求取？这个就是我们的重点之一了。

显然如果我们想要求取最小值的话，那么假设我们有五个个体去求解，我们初始化后交叉，变异之后，我们计算适应函数，得到5组解分别是（z1,n1）,(z2,n2)…
如何去筛选这个个体？我们现在如何评判那个个体更好？

所以我们引入的一个概念叫做支配 也就是 Pareto （帕雷拖）。

这个支配是这样定义的，如果B（5,4） A（4,3）我们发现B的每一个元素都大，那么我们就说A支配B，当我们要求最小值的时候，那显然B个体是不太好的，所以要降低它的适应度。而刚刚，A（4,5） B（5,3）这种情况，我们发现各有好坏，我们说这个叫非支配关系，那么这两个点我们都是要保留的，同样如果此时A(5,5) 不是所有元素比B差，但是也没有比B好的位置，所有我们管这个关系叫做弱非支配关系，刚刚的叫做强非支配关系。

这样一来通过支配关系，我们就能够对我们的种群进行筛选了。

求取非支配

现在我们已经知道了，我们为什么需要支配关系，它有什么作用，那么现在我们需要了解一下我们该怎么快速判断这些个个体产生的解。

这本书上的话给我们列举了很多方法，我这里就随便说一下。

Deb 非支配排序

这个方法就是暴力求解，按照我们的规则把每一个元素遍历一下。

用排除法构造

把支配的和非支配的分开，然后我们根据这个改变适应度。
例如 A 过来先放到非支配集合，然后B过来比较一下，没有被支配就放进来。有点像是维护一个堆。

庄家法构造

这个其实也是类似的，规则就是把第一个元素去遍历，如果被支配了就把自己干掉，同时干掉被支配的，依次类推，这个复杂度差不多（时间），顶多节省空间。

此外还有很多类似的，我们在重点说明一下 快速排序吧

快速排序（1）

这个方法是直接按照规则去进行快速排序（这里注意的是我们把支配的放在前面）这样第一轮排序之后，左右两边左边的就是被支配的，这样就不太需要考虑那一边了然后再来。但是这里注意一下就是我们只是把被支配的放在前面，不满足的不要动位置。

这里注意的是，我们是对它进行一个排序，也就是说按照支配关系去排序，也就是我可以保证在前面的一段位置是被支配的，或者后面一段，之后我们可以按照需要去选择哪些解，这里的其实更像是按照支配关系进行一个分批次的排序，例如

AＢＣＤＥＦＧＨＩ
假设排序后是
ＢＥＡＤＦＧＨＩ说明　ＢＥ被Ａ支配同时A也被别人支配
第二次
ＢＥＡＦＧＤＨＩ　说明 G 支配 F G 也是一样的道理，只有A不被任何人支配，这样才是非支配的，如果都是相互支配的话，那么就会出现这样类似分批的效果。

快速排序（2）

这个是对快速排序的一个升级版，也就是搞两个，这个规则是指两个方案，就是是我们选取的第一个点是第一个进入快排，当遇到第一个不被支配的点，改变工作模式，两个点进行处理。只要被其中一个支配就换位置，然后进入新的循环。直到完成排序。

那么这些就是我们判断，获得非支配解集的方式，这样一来我们就能够去适当地修改我们的适应值，然后对某些个体进行选择。

支配解集

我们前面提到了很多如何求取我们的非支配解的方法，每一轮循环之后（如果按照我们那个代码结构，多目标有很多结构的，先这样理解）我们按照那个方法，我们是可以得到我们每一轮循环的非支配解，然后去选择个体进化。但是有个问题，回到我们的这张图。

我们发现其实的话我们的那个解集也就是让这个函数变得最小的不一定是在某一个区域的，对于一个很复杂的函数。

在不断地进化过程当中，例如第N轮在左边有一些解，但是在不断进化当中例如2N轮在右边，右边总体上比左边好，所以去右边了这个很正常，但是不排除在左边还有个别点其实也很好，所以我们可以去保留每一轮的解集，然后在再这里解集里面去支配筛选。因为我们的目的是去寻找一个好的点。举个不恰当的例子。我想要寻找好的城市，总体上江西省，比广东省差，但是不排除江西有些城市比广东好是吧（例如我大赣州）

这里有书上有一段伪代码：
P 74

t<-0;Mt <- 空集
while(1){
    t <- t+1;
    Zt <- Gen(t) 每一轮产生的非支配解
    Mt <- reduce({Zt}U{M(t-1)}) 合并每一轮的解（非支配）
}
1
2
3
4
5
6

这样一来我们是不是就能够得到更加全面的一组解了，之后把这组解放在我们的解集里面。

那么这样一来，我们似乎就能够进行最基本的一个多目标优化了。
那么在这里我们就可以说说，我们的一些优化模型了，前面我说过“按照我们的代码结构”
这里的话其实我们有不少套路来解决不同的问题，但是只要你是基于 支配 的多目标优化基本上都是这个套路。例如 NSGA-II

NSGA-II 基于支配的多目标

这个名字很高大上一样，其实就是我们前面说的一个模型之一。首先我们得明白一点这个世界很奇妙，有很多种情况，所以有很多种模型，有很多种理论，但是这些玩意都可以归类。看过我刚刚说的那本书的同学可能发现我的目录是和那个书上的不一样的，我这边是以一个更好理解的部分去进行划分的，书上有个毛病都喜欢一股脑全说了，但是在没看完这本书时很难连成一个体系，当然也能理解本来东西比较多，跳来跳去的话可能不太合适，还有一些专业性的问题。

我这里直接引用书上的说明，然后把结合我前面说的你就明白了，一个最基本的多目标基于支配的是怎么玩的（后面的就是我们的优化，理论证明，实际应用，我这里只负责建立概念体系）

原话：

将进化群体分为若干层，第一层为进化群体的支配个体集合，第二层为在进化群体中去掉第一层个体后所求的的非支配个体，第三层为去掉第一二层的，以此类推。

这里的话，我们先简单地把这个层进行一个这样的理解，每第m轮产生的解的集合
假设我们一个循环100轮，那么我们把每20轮放在那个支配集合里面，那么这个第20轮产生的不为第一层了，以此类推（当然这个只是为了方便理解我先这样说，具体的我们在下面的内容中会具体讲述）。

那么到这里是不是就很明朗了。那么接下来就是我们的优化时刻。

分布优化

现在在总体上，我们发现其实还是有两个大方面可以优化的，第一个自然而然还是对我们当前这一层（你可以循环一次作为1层，也可以循环N次为一层，比较灵活的），求取的这个些非支配的解集进行优化。（当然在每一次循环的过程当中求取非支配解集的优化就不用说了）。

在我们不断优化地过程当中，我们求取的非支配解集，在我们的图像上，可能是这样的。

均匀密集

我们可以发现就是我们的这些点是分布比较均匀的，但是有时候，我们还会得到这样的点。（在原来均匀的图像上，随机加了一下点，假设加上的是非支配点）在我们的解集里面，这里你应该注意到了在当前这一层可能会产生这样的结果，在把每一层的结果合并之后也有可能出现这个结果（不过这个出现在第N轮之后，合并是通过支配合并的，那说明我们可能已经到了一个优解的状态）

在一个区域内我们发现就是这些点都汇聚在一起了，虽然他们都是非支配的，但是显然我们不太需要这些太过密集的点，所以我们得适当地删除一些点（同时降低生成这个点对应的个体的适应度）
那么在这里我们有好几个方法，听得最多的就是

网格优化

这个很简单，就是划分网格，然后查看每一个网格的点的个数，这个我们可以根据坐标来看，遍历每个点的坐标然后对应第几个格子，然后分类，把比较密集的删掉几个，例如规定每个格子不能超过三个点，这个方法适用适在我们每一层的进化上优化，因为每一层我们都是产生相对固定的个体（看你具体的策略，假设我们就是每次保证种群个数不变（允许相同基因的个体产生））

自适应网格优化

这个和前面的一样，就是说我们根据个体数来划分网格，动态处理呗。
这个适用哪一个就不用多说了，得看咱们具体的编码情况。

此外我们还有很多，例如我们根据距离

也就是聚类是吧，这个我就不多介绍了。

不均匀问题

这个怎么说，就是在我们前面处理完之后，我们最后得到的是这样的点

那么显然这样我们也得处理一下，
这里的话定义一个杂乱度的概念。messy，同时还有一个EMST欧式距离最小生成树的概念

这个怎么算呢，假设我们5个点。分布是这样的。

这样一来就解决了我们的问题，行不行，人家书上给的证明还是很流批的。

这个的话在《多目标进化优化》的第五章有说明，咱也不太能看懂，没办法大二老菜鸡了。

更多基于支配的多目标模型

到现在我门应该能看懂我们第六章的绝大多数内容的，没有这本书没关系，在这里我都会说说。
首先这个基于分解的多目标我就不说了，多目标变单目标嘛。

首先上场的就是我们的 Schaffer 和 Fonseca
这个是1985提出的，这里注意一点儿就是，说了那么多，其实也应该注意到了，我们基于支配的最明显的特点就是，我们使用支配来当我们的适应函数，来选择我们的个体。但是比关于这个支配解集如何处理，就需要看到我们具体的算法模型了，例如这个Schaffer.

它是这样的。设有r个目标，N个种群，我们把它分类分r个类，每个类N/r个个体，让r个子群体去进化，然后再合并为一个种群去交叉变异，然后再分开，以此类推。在选择的过程当中使用了支配，但是我们没有去维护一个总的支配解集。所以这个模型不太好，当然后面优化了。

我之所以说这个是因为强调一下这个组合很灵活，然后有不少适用情况。

此外我们还有组合，一开始我就是说过，那就是我们得适当地把多目标进化优化拆分出来
是：多目标+进化优化。我们有多目标的方法，同时有进化算法去优化，也就是一个负责筛选解根据支配关系确定遗传/进化算法当中需要被保留的个体，之后我们这个遗传算法根据这个被保留的个体再去交叉变异等等，生产新的解。所以我们一方面可以优化筛选解的方式，另一方面可以优化生产解的算法，例如，基于微种群的遗传算法实现多目标MGAMOO。

或者甚至使用 多目标 + 粒子群，基于支配适应函数的粒子群 + 多目标。

所以在这里我也得说明一下就是我们对于多目标种群的描述，这里分了两个部分，首先一个种群是我们产生解的用于进化算法或者遗传算法的种群，还有一个自然就是我们生成的解，前面我们说过例如 NSGA-II 是会保留我们每一层的解的，所以20个个体用于进化算法生成解，最后在NSGA-II 当中的非支配解可能又30个那么这一个解就是一个个体，在多目标里面有30个个体（为什么说这个也是个体，因为这个也会被淘汰）

高维度问题

细说 NSGA-II

前面我们的算法在面对低纬度（N<=3）的时候（需要优化方程数）

这里的话，倒是在多目标变单目标上面也有不错的优势了，当然在多维度有需要不太一样的处理，在书上给出来一个模型 NSGA-III （这也是为什么我先说这个模型的原因，当然也因为这个比较符合我一开始的设想）

这个的话，没错又是在我们ＮＳＧＡ－ＩＩ的基础上面优化（挤牙膏）

不过这里有好几个小细节要注意，首先是关于我们层的理解，前面我只是单纯的说了一下，实际上这个要稍微复杂一点，当然这个书上也没有说清楚，那么多模型就20多面就能解释清楚那是不太可能的，所以在过度之前，我们必须先把这个 ＮＳＧＡ－ＩＩ说清楚，不然后面不好说，同时说这个模型的时候，我们又能够把前面的内容完整地串在一起。首先就是我们先前对于层数的定义只是说循环了多少次之后的一个解。实际上在NSGA-II 里面这个层数不是这样的，这个是在每一轮都会进行的操作。具体的其实可以去看到一个示意图

下面是解释：

首先第一个上面的那个是初始化种群产生的解的集合（我们假设数量为N，也就是此时有N个解），下面那个是我们第一次交叉变异之后产生的解的集合，之后我们把这两个合并在一块，然后进行非支配排序（例如前面提到算法），这里我注意到一个分层就是F1，F2这个才是我们一开始提到的NSGA-II的分层…然后我们只选择前面的一部分，选择N个如上图，其中我们发现F3做了切分，那么我们就说F3是临界层分类子集(注意F1到Fn 组成一个集合，也就是说F1，F2没有重复的元素，也就是第二层去掉第一层的）我们再把对应的个体提高适应度然后被选择成为新的种群。

如何分层

说到这里其实你应该很好奇如何分层的了，流程图里面有一个是快速非支配排序。实际上的话，我们需要分类不仅仅只是说需要得到一个非支配的解集，我们还需要划分层次，那这个层次是这样的。
其实这也是为什么Deb会提出暴力求解的方法求支配，因为这个要用，当然也能优化

我们找到第一层其实就是不被其他个体支配的个体在图总 假设 是 ABCDE 那么就是 DE
之后是第二层，第二层就是在D，E 的支配的集合里面去找，也就是

[ A B C ],[B C]

然后去遍历 ，我们发现有两个B，两个C，一个A，此时C对应的支配值减去2，B对应的也是减掉2，此时C的那个值为0，那么C就是第二层的一个点，第三层，也是类似的，找到F2对应的点对应的支配的点去遍历，然后减去支配值。

其实就是第一层是没有被支配的点，这个是最好的点，但是并不是所有的点都有这样的效果，这类的点比较少，第二层是只是被第一层支配的，以此类推第三层是被第一第二层支配的。那么这样分类的话，我们发现我们排序后的总的集合个数是 2N但是我们只要前面N个。之后我们再找到这个点对应的个体进入下一个循环。

距离问题

前面我们费了老大难的问题去分层，然后筛选出了N个个体，接下来进入下一个循环，也就是作为子代，但是，还记得我们前面说的分布问题吗，为了避免最优解的问题我们还要再来一下，不过我们只需要针对 F3，也就是是我们的临界子集的问题。

我们要看看我们要选择哪一些F3的个体去我们下一轮循环。

所以我们得计算一下，计算一下排个序，然后选呗。

公式长这个样子

同样这里注意一下边界问题。

之后就是我们交叉变异等等进入新的循环。

NSGA-III

这个前面的过程其实和ＮＳＧＡ－ＩＩ是类似的，区别在于这个哥们使用了参考点，来选择我们的F3的个体。书上是说
NSGA-III 的临界层选择方法采用参考点方法选择个体。
其实也是为了避免局部优化的问题。

参考点设置方法：Das和Dennis在1998年提出的边界交叉构造权重的方法。

在标准化参考平面上，如果每一维目标被均匀地分割成p份，那么均匀地产生C(m+p-1,p)个参考点。这个m是目标个数，p是你要分成几份

这个其实就是分割空间，分成几份的问题，几个点。

在这个还没完，在超平面是这样的

想办法构造这个点，然后去比较。

自适应标准化

接下来的操作比较复杂，我这里的话找到了一个类似的博文，和书上的内容类似
https://blog.csdn.net/xuxinrk/article/details/82965280
我这里就不叙述了，确实比较复杂。

综述

那么到这里的话大概应该是对多目标有了一个比较明朗的认识，那么其实这里面还是《多目标优化进化》的前七章的主要内容，其实后面的内容是什么偏好MOEA，动态MOEA，性能分析，以及测试函数，案例等等当然还有平台。

后面的内容比较复杂，看理论要看吐了，实话实话我很讨厌看paper，看书，一个是专业化，还有一个就是理论化的问题，不像那些什么官方文档，以实用性为主，告诉你怎么用，那些接口，API，以及一些底层细节。当然吐槽归吐槽，这些东西本来就是数学分支出来的，没有理论就没有这个东西，后面的内容我打算慢慢看，别的不说，先好好回去刷Letcode把NSGA-II 什么的实现一下用java或者python，当然先考虑python，毕竟numpy是真舒服。好了就这么多，天知道一个ssm 都没有卷够的人，怎么会去玩pytorch，玩这个…