大意了啊，优化这一块上学的时候根本没有学。最近在做一些多目标优化的问题，到头来直接用了算法（似乎是因为用到的这几个算法和优化本身的基础理论并没有特别大的关联，而是有自己的一套更细一点的理论），总之在这里稍微整理一下。

多目标优化导论

多目标优化（Multi-objective optimization，缩写就是MOO~虽然是相当复杂的一个东西但有着蛮可爱的一个名字），也可以叫Pareto优化，以意大利经济学家Vilfredo Pareto命名。

优化问题

数学上的优化问题，通常就是要求最小（或者最大，取最小的负值）化一个目标函数，定义如下：

min⁡x∈Af(x)\min_{x \in A} f(x)

其中f(x)f(x)就是目标函数，xx是待优化的参数，可以是多个/向量，AA是对xx的边界限定，可以是不等式约束或等式约束。上面式子的值即为最优的目标值，而最优目标的参数可以用经常见到的arg⁡min⁡x∈Af(x)\arg \min_{x \in A} f(x)来表示。

对于优化而言，还有一个凸与非凸的问题。对于凸的问题，局部最优解就是全局最优解。非凸问题可能存在多个局部最优解，需要一些特殊方法防止陷入局部最优的次优解，得到全局最优。

优化当中最常用、最经典的方法就是梯度下降（Gradient descent），其定义为：

xk+1=xk−α∇f(xk)x_{k+1} = x_k - \alpha \nabla f(x_k)

其中xkx_k是当前参数，∇f(xk)\nabla f(x_k)即当前参数的目标函数的梯度，也就是下降的方向。α\alpha是学习率/步长，控制着每一步沿着梯度下降的方向走多少。在实际优化的过程中通常会使用可变而自适应的学习率，过大的学习率会导致震荡甚至发散（但有时或许也可以用于跳过次优解），而过小的学习率会导致收敛缓慢。

梯度下降通常用于无约束的优化问题，因为梯度方向可能导致参数到达约束限制的不可到达的区域，但可以用一些投影之类的方法保留在约束区域。

多目标优化问题

多目标优化问题，即是同时有多个目标函数的优化问题：

min⁡x∈A(f1(x),f2(x),…,fk(x)),k≥2\min_{x \in A}\big (f_1(x), f_2(x), \dots , f_k(x) \big ), \quad k \geq 2

多目标优化问题可能不止一个同时满足多个优化目标的解，这些解被称为Pareto最优解或非支配解，解集称为Pareto前沿/边界。Pareto 最优解是指在多目标优化问题中，无法在不恶化其他目标的情况下改善某一个目标的解，也就是不被周围的解支配。

在Pareto前沿中，所有目标最优的值构成的点是理想点，最差的值构成的点是Nadir点，这两个点通常都无法得到，但它们限定了Pareto前沿的区域，并且可以通过

fi′(x)=fi(x)−zidealznadir−zidealf_i'(x) = \frac{f_i(x) - z^{\text{ideal}}}{z^{\text{nadir}} - z^{\text{ideal}}}

来对目标函数进行归一化，并计算前沿上每个点到理想点的距离，距离最近的往往是一个比较折中的解。

为了解决多目标优化问题，通常有优化前（A priori）和优化后（A posteriori）的两种处理方法。优化前通常都是将多目标问题简化为单目标问题，大多数情况下，机器学习中的损失函数其实就是用加权和（ Weighted sum）将多目标优化精简到了一个损失函数，依赖这个损失函数进行优化就可以了。

优化后的处理一般会用进化算法来同时寻找多个Pareto解，或者直接上深度学习，去学习到Pareto前沿。

进化算法

顺带一提

模拟退火法

在说进化算法（Evolutionary algorithm, EA）之前先提一嘴模拟退火法（Simulated annealing, SA），这个应该都有听说过。

模拟退火法就是在模拟金属退火的过程。算法一开始随机选择一个解，然后每一步取探索周围的新解，如果新解更优则接受，如果更差则以一定概率接受。一开始温度很高，接受的概率更大，可以探索更多区域避免陷入局部最优。随着温度降低，算法最终收敛到一个更接近全局最优的解。

SA1
模拟退火法解决旅行商问题
SA2
3D旅行商问题

粒子群优化

粒子群优化（Particle swarm optimization, PSO）灵感来自鸟群/鱼群的协同搜索行为。其本质就是，在搜索空间内初始化一堆粒子，每个粒子都知道自己目前最好的位置和周围几个邻居（或者是整个群体）最好的位置，你的比我的好我就去你那里，然后按照自己的惯性去随机一个速度来移动。

粒子群优化本身也有很多参数需要调整才能得到比较好的效果，另外虽然本身并不需要梯度，但梯度或许也可以在引导每个粒子移动时起到一定的作用。总之关键就是要在探索（Exploration）和利用（Exploitation）之间取得平衡。

PSO

所以说？

这两种算法，再加上进化算法都算作元启发式算法 （metaheuristics），是人工智能和优化领域的经典方法。模拟退火和进化算法都能在没有梯度的情况下通过随机的方法去探索周围的解，这也让它们很适合来做一些离散的问题，比如组合选择、路径规划或调度。粒子群优化因为有惯性速度模型的原因对于离散问题可能不太行，但同样也是并不需要空间的梯度。

除此之外，因为优化模型本身也有参数需要优化，甚至还衍生出来了一种元优化（Meta-optimization）的概念， 就是用优化算法去优化优化算法。套娃虽好，我觉得还是自适应比较合适。

回到主题

进化算法的基本定义如下：

  1. 初始化种群
  2. 评估，如果达成目标则终止
  3. 适者生存
  4. 选择优秀个体产生子代
  5. 子代进行变异
  6. 返回2继续迭代

根据具体的实现还大概分成几类，但我也没太看明白区分的规则究竟是什么，在此就不讲了。

NSGA-II/III

非支配排序遗传算法（Nondominated sorting genetic algorithm, NSGA），本质并不麻烦。首先它是一个遗传算法（Genetic algorithm, GA），会在上面提到的进化算法的第四步当中，选择个体进行杂交来产生子代。非支配排序的部分是在生存和选择的部分，优先选择更不被支配的个体，并且在Pareto前沿上定义一个拥挤距离，使得到的解分布更加均匀。

NSGA-II是用于双目标优化，对于更多目标优化用到NSGA-III，基本就是II的方法加上参考方向。参考方向是在优化前定义的将多个目标组合的方法，具体形式就是在多个目标组成的空间的一组向量。这一组向量通常通过Das-Dennis方法来生成，特点是在单位单纯形（unit simplex）上均匀、系统地生成参考点从而作为参考方向。单位单纯形的概念有点难理解（指在nn维空间中，单位单纯形是由n+1n+1个仿射无关点的凸包构成的几何体），在一维就是一条线段，二维是三角形，三维是四面体。NSGA-III会优先选择代表更少的参考方向上的个体，并且以垂直参考方向的距离来使解更均匀。

在基础的算法之外，还有一些小的魔改版本。R-NSGA-II/III，R是指基于参考点（Reference point based），会在排序时考虑人为选择的参考点，可以得到更接近参考点的Pareto前沿。U-NSGA-III，U是指Unified，是通过在杂交部分给子代的家长更多压力来加快收敛。

SPEA2

强化Pareto进化算法二代（Strength Pareto evolutionary algorithm 2），没错这个2是第二代而不是用于双目标优化（虽然它就是用于双目标优化）。SPEA2是NSGA-II的改进版本，一方面拥挤距离改为使用密度全局考虑，另一方面对于Pareto前沿在进化的个体外部保存，避免优秀解在进化过程中消失。

SPEA2的计算复杂度更高一些，但收敛速度更快，解集分布也更均匀。

MOEA/D

其实上面的几个算法都算作MOEA，也就是多目标优化进化算法（Multi-objective evolutionary algorithm），不过还有一个非常基础的MOEA/D，D是指基于分解（based on Decomposition），它是将多目标优化问题分解为一系列单目标优化问题，每个子问题通过和邻域的其他问题协作来保证多目标优化。MOEA/D同样需要参考方向，并且优化效果非常依赖参考方向。

pymoo

需要实际去做多目标优化的话也不必自己重新实现算法，已经有了一个python库专门来做多目标优化的内容，即pymoo。不仅包含了用于优化和多目标优化的众多算法，而且还附带了示例的问题以及方便的可视化操作，甚至还能输出优化过程的视频。

对于多目标优化而言，使用只要下面这样即可.

首先是定义问题，比如我的优化是要最大化a的同时最小化b：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from pymoo.core.problem import ElementwiseProblem

class MyProblem(ElementwiseProblem):
    def __init__(self):
        super().__init__(n_var=2,                   # 两个变量 x,y
                         n_obj=2,                   # 两个目标
                         n_constr=0,                # 没有约束
                         xl=np.array([xmin, ymin]), # 变量范围最小值
                         xu=np.array([xmax, ymax])) # 变量范围最大值
     
    def _evaluate(self, x, out, *args, **kwargs):
        a, b = get_value(x) # 自己定义的从x,y计算a,b的函数
        
        f1 = -a             # 最大化 a
        f2 = b              # 最小化 b
        
        out["F"] = [f1, f2]

然后是优化算法的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# NSGA-II
from pymoo.algorithms.moo.nsga2 import NSGA2
algorithm = NSGA2(pop_size=100) # pop_size是每一代的个体数，一般50~200
# SPEA2
from pymoo.algorithms.moo.spea2 import SPEA2
algorithm = SPEA2(pop_size=100)

# 更多目标优化还需要定义参考方向
from pymoo.util.ref_dirs import get_reference_directions
ref_dirs = get_reference_directions("das-dennis", 2, n_points=50) # 可以用das-dennis或uniform, 2是代表目标数, n_points是生成的方向数量

# NSGA-III
from pymoo.algorithms.moo.nsga3 import NSGA3
algorithm = NSGA3(pop_size=100, ref_dirs=ref_dirs)

# MOEA/D
from pymoo.algorithms.moo.moead import MOEAD
algorithm = MOEAD(ref_dirs,
                  n_neighbors=15,           # 控制邻域大小, 通常5~20
                  prob_neighbor_mating=0.7) # 控制父代选择来自邻居还是全局, 通常0.7~0.9

然后就可以开始优化：

1
2
3
4
5
6
7
from pymoo.optimize import minimize

res = minimize(MyProblem(),
               algorithm,
               termination=('n_gen', 200),
               seed=1,
               verbose=True)

其中termination是指优化的终止条件，可以像这样用n_gen代表优化的代的数量，也可以用n_eval代表运算的次数，time代表优化的时间，x_tol代表输入空间的容差，f_tol代表目标空间的容差。也可以用

1
2
3
4
5
6
7
from pymoo.termination.collection import TerminationCollection
from pymoo.termination import get_termination

termination = TerminationCollection(
    get_termination("n_gen", 200),     
    get_termination("time", "00:05:00")
)

这种方式来组合终止的条件。

seed就是随机种，可以填一样的值来复现优化过程。verbose是在优化过程中是否打印一些指标。