Posts

前言

在多目标优化问题中，基于帕累托支配关系的最优解集（即帕累托前沿，PF）很可能不是有限的集合；多数情况下可能是高维空间中某一区域。因此，优化算法的目标就是在有限时间里得到一个能够表现出PF的形状、且分布良好的解集。这也是为什么收敛性和多样性在演化多目标优化算法中是两大重要指标。经典的基于支配关系的算法框架（如NSGA-II等）依靠适应值来维护解集的多样性，避免边缘解的丢失以及解过于密集的现象。而MOEA/D的提出，将分解的思想重新带入了演化多目标优化的领域来。

在遗传算法中，如何从亲代中产生好的子代个体是至关重要的问题。本文将收录一些经典的、但理解起来略有难度的交叉和变异算子（Crossover and mutation operators），并简要叙述一下其背后的原理。

本文中各种算子的中文名称均为个人直译结果，不代表学术界公认译名（本来也基本没有……）。

最近在学习并尝试实现演化多目标优化的相关算法，希望我能通过这篇博客把算法了解得更加透彻orz

基础篇

帕累托支配

在多目标优化领域，一般来说，决策变量和目标都是由多个元素组成的，而不同目标之间往往难以比较。如果将决策/目标视作一个向量$\mathbf{x}$，我们用帕累托支配（Pareto dominance）来刻画向量间的关系。对于两个$n$维向量$\mathbf{x}^{(1)} = (x^{(1)}_1, \dots, x^{(1)}_n)^T, \mathbf{x}^{(2)} = (x^{(2)}_1, \dots, x^{(2)}_n)^T$，我们称$\mathbf{x}^{(1)}$支配$\mathbf{x}^{(2)}$（记作$\mathbf{x}^{(1)} \prec \mathbf{x}^{(2)}$）当且仅当$\forall 1 \leq i \leq n,\ x^{(1)}_i \leq x^{(2)}_i$，且$\exists 1 \leq i \leq n,\ x^{(1)}_i < x^{(2)}_i$。

没事瞎水博客系列……

在日常处理矩阵的时候，有时我们希望在不更改矩阵的前提下获知其每一行/列的字典序“名次”（rank）。MATLAB/NumPy分别提供了sortrows/argsort方法来获得一个“索引向量”（index vector），表示排序后的矩阵的每一行/列对应原矩阵的行/列号。只需对索引向量再做一次排序，便可得到对应的”名次向量“（rank vector）。对应MATLAB代码大致如下：

[~, index] = sortrows(matrix);
[~, rank] = sort(index);

为了深入理解这个操作背后的原理，我参考了StackExchange上的这篇回答。从他的证明过程中我发现了一个关键：排序前后两个矩阵的关系可以用排列/置换（permutation）来刻画。下面我将站在线性代数的视角来系统化解释一下“名次向量”背后的原理。

龟速补上欠下的账ing……

写完发现读着好晦涩，但数学不就是这样的吗🌚

基本概念/符号表示

为了方便下文叙述，现做如下规定/定义：

$G = (V, E)$是有向、无平行边的图，每条边边权为正，其中有一个源点（source）$s$和汇点（sink）$t$满足：没有一条边以$t$为起点，或以$s$为终点。

对某边$e \in E$，记该边边权为$c(e)$。