啊要出分数线了好紧张. 赶紧复习复习以前学的东西_(:з」∠)_
竟然写了大半天, 全都忘光了, 怕不是要凉 (/ﾟДﾟ)/
遗传算法(Genetic Algorithm)
此处使用二进制编码法形成染色体.
种群初始化: 随机将染色体的某些 DNA 置 1, 进行 M 次, 形成 M 个不重复的个体组成第一代种群.
适应度评价: 对每个个体运行适应度评价函数, 区分群体中个体好坏. 并按照一定策略选择出部分适应度高的个体, 作为下一代的父代.
交叉与变异: 对挑选出的父代, 每次随机选择两个染色体, 在一定概率下将两者的某些 DNA 进行交换, 形成两个新的个体, 即为染色体的交叉; 同时上述新产生的个体有一定概率发生染色体变异, 即对染色体的某些位取反. 最后形成新的子代. 遗传算法就是上述步骤的反复.
非支配排序遗传算法(Non-Dominated Sorting Genetic Algorithm, NSGA)
有时候我们的优化目标不止一个, 比如买菜时同时要求菜越新鲜越好, 且单价越便宜越好. 这便是多目标优化问题. 面对此类问题时, 无法用 1 个指标衡量染色体的好坏, 在判断两个染色体孰优孰劣时将会产生困难. NSGA 解决多目标问题和普通 GA 的主要区别就是在选择算子执行之前对个体关系的分层, 而选择算子, 交叉算子, 变异算子没有区别.
Pareto 支配关系
Pareto 最优解给出了多目标问题的判别的方法.
对于最小化多目标问题, n 个目标分量 \(f_i\) \((i=1,...,n)\) 组成的向量 \(\overline{f}(\overline{X})=(f_1(\overline{X}), f_2(\overline{X}), ..., f_n(\overline{X}))\), 给定两个决策变量 \(\overline{X}_u, \overline{X}_v \ U\):
- 当且仅当 \(\forall i \in \{1, ..., n\}\) 时, 都有 \(f_i(\overline{X}_u) < f_i(\overline{X}_v)\), 则 \(\overline{X}_u\) 支配 \(\overline{X}_v\).
- 当且仅当 \(\forall i \in \{1, ..., n\}\) 时, 都有 \(f_i(\overline{X}_u) \leqslant f_i(\overline{X}_v)\), 且至少存在一个 \(j \in \{1, ..., n\}\) 使得 \(f_j(\overline{X}_u) = f_j(\overline{X}_v)\), 则 \(\overline{X}_u\) 弱支配 \(\overline{X}_v\).
- 当且仅当 \(\exists i \in \{1, ..., n\}\), 使 \(f_i(\overline{X}_u) < f_i(\overline{X}_v)\), 且 \(\exists j \in \{1, ..., n\}\), 使 \(f_j(\overline{X}_u) > f_j(\overline{X}_v)\), 则 \(\overline{X}_u\) 和 \(\overline{X}_v\) 互不支配.
若 \(\overline{X}_u\) 为 Pareto 最优解, 则不存在 \(\overline{X}_v \in U\) 支配 \(\overline{X}_u\).
非支配排序
对于互不支配的染色体, 我们称这些染色体处于同一层. 则所有的染色体可以被划分到若干层. 非支配排序就是将染色体分层的排序算法, 分得的层称为第一级非支配层, 第二级非支配层...... 其中第一级非支配层处于 Pareto 前沿(Pareto Front).
非支配排序步骤如下:
- (1)设 \(i = 1\);
- (2)对所有的 \(j = 1, 2, ..., N (j \ne i)\), 基于适应度函数比较个体 \(x_i\), \(x_j\) 之间的支配关系;
- (3)若不存在任何一个个体 \(x_j\) 优于 \(x_i\), 则标记 \(x_i\) 为非支配个体;
- (4)令 \(i = i + 1\), 转到 (1), 重复直至找到所有非支配个体.
上述步骤将得到第一级非支配层, 过滤第一层所有个体后再次运行非支配排序, 即可得到第二级非支配层.
可以看到每找一层的时间复杂度是 \(O(MN^2)\) (\(M\) 为目标数, \(N\) 为种群大小), 最多要找 \(N\) 次, 所以一共的时间复杂度到了 \(O(MN^3)\).
虚拟适应度(略)
为了算法更快地收敛, 虚拟适应度越大(层数越低)的个体应该有更多机会进入下一代. 但同时, 我们期望的 Pareto 最优解集应该是均匀分布的(而不是都挤在一个或几个点附近), 因此还要保证当前非支配层上的个体具有多样性。NSGA 中引入了基于拥挤策略的小生境(NIChe)技术, 对每个个体计算共享适应度.
带精英策略的非支配排序遗传算法(NSGA-II)
NSGA-II 是 NSGA 的改进. NSGA-II 相对于 NSGA, 1. 提出了快速非支配排序算子, 将非支配排序从 \(O(MN^3)\) 优化到了 \(O(MN^2)\) (\(M\) 为目标数, \(N\) 为种群大小); 2. 提出了拥挤距离算子; 3. 提出了精英策略选择算子.
NSGA-II 流程图快速支配排序算子
- (1)对种群 \(P\) 中的每个个体 \(p\), 计算 \(p\) 在种群 \(P\) 中支配的个体数 \(n_p\), 并将这些被 \(p\) 支配的个体存入 \(S_p\) 中(即每个个体都要两两比较一次, 共比较 \(\frac{N(N-1))}{2}\) 次, 每次比较要遍历 \(M\) 个目标, 时间复杂度 \(O(MN^2)\));
- (2)\(layer = 1\);
- (3)找出所有 \(n_p = 0\) 的个体, 保存在数组 \(F_{layer}\) 中;
- (4)对于 \(F_{layer}\) 中的每个个体 \(p\) 的支配集 \(S_p\): 遍历 \(S_p\), 对 \(S_p\) 中每个个体 \(l\), 执行 \(n_l = n_l - 1\);
- (5)\(layer = layer + 1\), 重复(3).
拥挤距离算子
- (1)对每个个体 \(p\) 令拥挤距离 \(d_p = 0, p = 1, 2, ..., N\)
- (2)对 \(M\) 个目标的每个目标函数 \(f_m\):
- 1)根据目标 \(f_m\) 的数值大小, 对每个个体排序;
- 2)对每个个体 \(p\), 计算 \(d_p = d_p + (f_m(p+1) - f_m(p-1))\) (其中第一个和最后一个个体拥挤距离设为无穷 \(d_1 = d_N = \infty\))
选择时优先选择拥挤距离 \(d\) 大的.