啊要出分数线了好紧张. 赶紧复习复习以前学的东西_(:з」∠)_

竟然写了大半天, 全都忘光了, 怕不是要凉 (/ﾟДﾟ)/

遗传算法(Genetic Algorithm)

此处使用二进制编码法形成染色体.

种群初始化: 随机将染色体的某些 DNA 置 1, 进行 M 次, 形成 M 个不重复的个体组成第一代种群.

适应度评价: 对每个个体运行适应度评价函数, 区分群体中个体好坏. 并按照一定策略选择出部分适应度高的个体, 作为下一代的父代.

交叉与变异: 对挑选出的父代, 每次随机选择两个染色体, 在一定概率下将两者的某些 DNA 进行交换, 形成两个新的个体, 即为染色体的交叉; 同时上述新产生的个体有一定概率发生染色体变异, 即对染色体的某些位取反. 最后形成新的子代. 遗传算法就是上述步骤的反复.

非支配排序遗传算法(Non-Dominated Sorting Genetic Algorithm, NSGA)

有时候我们的优化目标不止一个, 比如买菜时同时要求菜越新鲜越好, 且单价越便宜越好. 这便是多目标优化问题. 面对此类问题时, 无法用 1 个指标衡量染色体的好坏, 在判断两个染色体孰优孰劣时将会产生困难. NSGA 解决多目标问题和普通 GA 的主要区别就是在选择算子执行之前对个体关系的分层, 而选择算子, 交叉算子, 变异算子没有区别.

Pareto 支配关系

Pareto 最优解给出了多目标问题的判别的方法.

对于最小化多目标问题, n 个目标分量 fi(i=1,...,n) 组成的向量 f―(X―)=(f1(X―),f2(X―),...,fn(X―)), 给定两个决策变量 X―u,X―vU:

• 当且仅当 ∀i∈{1,...,n} 时, 都有 fi(X―u)<fi(X―v), 则 X―u 支配 X―v.
• 当且仅当 ∀i∈{1,...,n} 时, 都有 fi(X―u)⩽fi(X―v), 且至少存在一个 j∈{1,...,n} 使得 fj(X―u)=fj(X―v), 则 X―u 弱支配 X―v.
• 当且仅当 ∃i∈{1,...,n}, 使 fi(X―u)<fi(X―v), 且 ∃j∈{1,...,n}, 使 fj(X―u)>fj(X―v), 则 X―u 和 X―v 互不支配.

若 X―u 为 Pareto 最优解, 则不存在 X―v∈U 支配 X―u.

非支配排序

对于互不支配的染色体, 我们称这些染色体处于同一层. 则所有的染色体可以被划分到若干层. 非支配排序就是将染色体分层的排序算法, 分得的层称为第一级非支配层, 第二级非支配层...... 其中第一级非支配层处于 Pareto 前沿(Pareto Front).

非支配排序步骤如下:

• (1)设 i=1;
• (2)对所有的 j=1,2,...,N(j≠i), 基于适应度函数比较个体 xi, xj 之间的支配关系;
• (3)若不存在任何一个个体 xj 优于 xi, 则标记 xi 为非支配个体;
• (4)令 i=i+1, 转到 (1), 重复直至找到所有非支配个体.

上述步骤将得到第一级非支配层, 过滤第一层所有个体后再次运行非支配排序, 即可得到第二级非支配层.

可以看到每找一层的时间复杂度是 O(MN2) (M 为目标数, N 为种群大小), 最多要找 N 次, 所以一共的时间复杂度到了 O(MN3).

虚拟适应度(略)

为了算法更快地收敛, 虚拟适应度越大(层数越低)的个体应该有更多机会进入下一代. 但同时, 我们期望的 Pareto 最优解集应该是均匀分布的(而不是都挤在一个或几个点附近), 因此还要保证当前非支配层上的个体具有多样性。NSGA 中引入了基于拥挤策略的小生境(NIChe)技术, 对每个个体计算共享适应度.

带精英策略的非支配排序遗传算法(NSGA-II)

NSGA-II 是 NSGA 的改进. NSGA-II 相对于 NSGA, 1. 提出了快速非支配排序算子, 将非支配排序从 O(MN3) 优化到了 O(MN2) (M 为目标数, N 为种群大小); 2. 提出了拥挤距离算子; 3. 提出了精英策略选择算子.

快速支配排序算子

• (1)对种群 P 中的每个个体 p, 计算 p 在种群 P 中支配的个体数 np, 并将这些被 p 支配的个体存入 Sp 中(即每个个体都要两两比较一次, 共比较 N(N−1))2 次, 每次比较要遍历 M 个目标, 时间复杂度 O(MN2));
• (2)layer=1;
• (3)找出所有 np=0 的个体, 保存在数组 Flayer 中;
• (4)对于 Flayer 中的每个个体 p 的支配集 Sp: 遍历 Sp, 对 Sp 中每个个体 l, 执行 nl=nl−1;
• (5)layer=layer+1, 重复(3).

拥挤距离算子

• (1)对每个个体 p 令拥挤距离 dp=0,p=1,2,...,N
• (2)对 M 个目标的每个目标函数 fm:
  • 1)根据目标 fm 的数值大小, 对每个个体排序;
  • 2)对每个个体 p, 计算 dp=dp+(fm(p+1)−fm(p−1)) (其中第一个和最后一个个体拥挤距离设为无穷 d1=dN=∞)

选择时优先选择拥挤距离 d 大的.

精英策略选择算子

即保留父代优良个体直接进入子代, 以防止 Pareto 前沿的解丢失. 具体操作就可以直接把父代子代合并到一起进行非支配排序.