多目标遗传算法NSGA

因所读的一篇论文中，为了解决多目标的最优解问题，作者使用了一种称为NSGA-II(Improved Non-dominated Sorting Genetic Algorithm)的遗传算法，花了两天时间了解下，此为何物。其中NSGA以及NSGA-II的原理说明内容大部分取自2008年李莉的硕士论文《基于遗传算法的多目标寻优策略的应用研究》，故将此文定为转载。

首先需要了解一种称之为‘dominate’的关系：
设一个最大化目标函数为 F(x)=(F1(x),F2(x),...,Fk(x)) <script type="math/tex" id="MathJax-Element-1">F(x) = (F_1(x), F_2(x), ..., F_k(x))</script>, 因为是一个多目标最优的问题，所以这里的目标数量 k≥2 <script type="math/tex" id="MathJax-Element-2">k \ge 2</script>。假定 x0 <script type="math/tex" id="MathJax-Element-3">x_0</script>, x1 <script type="math/tex" id="MathJax-Element-4">x_1</script>是解空间 X <script type="math/tex" id="MathJax-Element-5">X</script>中的两个解。如果∃i∈[1,k]<script type="math/tex" id="MathJax-Element-6"> \exists i \in [1,k]</script>使得 Fi(x0)>Fi(x1) <script type="math/tex" id="MathJax-Element-7">F_i(x_0) > F_i(x_1)</script>成立，并且 ∀i∈[1,k] <script type="math/tex" id="MathJax-Element-8">\forall i \in [1, k]</script>时， Fi(x0)≥Fi(x1) <script type="math/tex" id="MathJax-Element-9">F_i(x_0) \ge F_i(x_1)</script>也成立，那么就称解 x0 <script type="math/tex" id="MathJax-Element-10">x_0</script>占优(dominate) x1 <script type="math/tex" id="MathJax-Element-11">x_1</script>。如果在所有的解空间 X <script type="math/tex" id="MathJax-Element-12">X</script>中找不到其他能占优x0<script type="math/tex" id="MathJax-Element-13">x_0</script>的解，那么我们称解 x0 <script type="math/tex" id="MathJax-Element-14">x_0</script>是一个efficient solution。该 x0 <script type="math/tex" id="MathJax-Element-15">x_0</script>在空间中对应的点，称为 non-dominated point。个人感觉efficient solution其实就是一个Pareto最优解，即，不可能在使得至少一个人收益变得更好情况下而保证其他人的收益不变差。
一般而言，在多目标优化的问题里， efficient solution往往不是唯一的，那么所有efficient solutions的集合，我们称为efficient set。相对应地，所有non-dominated points组成的点集，称为Pareto front(帕累托前沿)。

题外话：一般多目标规划问题，其实都可以建模为找Pareto 最优解的问题。

在一个庞大的解空间中找出所有的Pareto解(Pareto front)是一个NP-hard问题，因此一些有意思启发式算法就诞生了，而本文这里所讲的遗传算法(Genetic Algorithm)就是其中之一。

NSGA(Non-dominated Sorting Genetic Algorithm)

NSGA非支配排序遗传算法就是一种以基本遗传算法为基础的多目标寻优策略，因为其在多目标寻优领域的优势，成为人们的研究热点。

下面将简要说明NSGA的原理[[1]]。
NSGA主要由三部分构成，分别为：

• 种群分层
  假定寻找最大化目标函数为 F(x)=(F1(x),F2(x),...,Fm(x)) <script type="math/tex" id="MathJax-Element-16">F(x) = (F_1(x), F_2(x), ..., F_m(x))</script>，种群规模为 n <script type="math/tex" id="MathJax-Element-17">n</script>。
  (1)设i=1<script type="math/tex" id="MathJax-Element-18">i=1</script>；
  (2)对于所有的 j=1，2，…，n <script type="math/tex" id="MathJax-Element-19">j=1，2，…，n</script>且 j≠i <script type="math/tex" id="MathJax-Element-20">j \ne i</script>，按照以上定义比较个体 xi <script type="math/tex" id="MathJax-Element-21">x_i</script>和个体 xj <script type="math/tex" id="MathJax-Element-22">x_j</script>之间的支
  配(dominate)与非支配(non-donimated)关系；
  (3)如果不存在任何一个个体 xj <script type="math/tex" id="MathJax-Element-23">x_j</script>优于 xi <script type="math/tex" id="MathJax-Element-24">x_i</script>，则 xi <script type="math/tex" id="MathJax-Element-25">x_i</script>标记为非支配个体；
  (4)令 i=1+1 <script type="math/tex" id="MathJax-Element-26">i=1+1</script>，转到步骤(2)，直到找到所有的非支配个体。
  通过上述步骤得到的非支配个体集是种群的第一级非支配层，然后，忽略这些已经
  标记的非支配个体(即这些个体不再进行下一轮比较)，再遵循步骤(1)一(4)，就会得到第二
  级非支配层。依此类推，直到整个种群被分层。

• 共享小生境技术
  为了在演化过程中保持群体的多样性，NSGA中引入了共享小生境技术。
  假设第 p <script type="math/tex" id="MathJax-Element-27">p</script>级非支配层上有np<script type="math/tex" id="MathJax-Element-28">n_p</script>个个体，每个个体的虚拟适应度值为 fp <script type="math/tex" id="MathJax-Element-29">f_p</script>。
  (1)算出同属于一个非支配层的个体 xi <script type="math/tex" id="MathJax-Element-30">x_i</script>和个体 xj <script type="math/tex" id="MathJax-Element-31">x_j</script>的欧几里得距离：
  

  dij=∑l=1l=m(Fl(xi)−Fl(xj)Ful−Fdl)2−−−−−−−−−−−−−−−−−⎷
  <script type="math/tex; mode=display" id="MathJax-Element-32">\begin{equation} d_{ij} = \sqrt{\sum_{l=1}^{l=m}(\frac{F_l(x_i)-F_l(x_j)}{F_l^u-F_l^d})^2} \end{equation}</script>
  其中 m <script type="math/tex" id="MathJax-Element-33">m</script>目标个数，Ful,Fdl<script type="math/tex" id="MathJax-Element-34">F_l^u,F_l^d</script>分别为 Fl <script type="math/tex" id="MathJax-Element-35">F_l</script>的上界和下界。
  (2)共享函数(Sharing Function)是表示两个个体间关系密切程度的函数，两个个体 xi <script type="math/tex" id="MathJax-Element-36">x_i</script>和 xj <script type="math/tex" id="MathJax-Element-37">x_j</script>间的共享函数 sh(dij) <script type="math/tex" id="MathJax-Element-38">sh(d_{ij})</script>:
  
  sh(dij)=⎧⎩⎨⎪⎪1−(dijσshare)α0,dij≤σsharedij>σshare
  <script type="math/tex; mode=display" id="MathJax-Element-39">\begin{eqnarray*} sh(d_{ij}) = \left\{ \begin{array}{ll} 1 - (\frac{d_{ij}}{\sigma_{share}})^{\alpha} & , d_{ij} \le \sigma_{share} \\ 0 & d_{ij} > \sigma_{share} \end{array} \right. \end{eqnarray*}</script>
  σshare <script type="math/tex" id="MathJax-Element-40">\sigma_{share}</script>的值表示了 xi <script type="math/tex" id="MathJax-Element-41">x_i</script>与 xj <script type="math/tex" id="MathJax-Element-42">x_j</script>群体的相似度。
  dij <script type="math/tex" id="MathJax-Element-43">d_{ij}</script>表示个体 xi <script type="math/tex" id="MathJax-Element-44">x_i</script>与 xj <script type="math/tex" id="MathJax-Element-45">x_j</script>间的欧式距离。
  α <script type="math/tex" id="MathJax-Element-46">\alpha</script>用于对 sh(dij) <script type="math/tex" id="MathJax-Element-47">sh(d_{ij})</script>的调整。
  由此可见：
  sh(dij) <script type="math/tex" id="MathJax-Element-48">sh(d_{ij})</script>越大表明二者关系密切，即相似度高
  (3)然后我们计算出节点 i <script type="math/tex" id="MathJax-Element-49">i</script>与其他所有节点的累积相似度，称为共享度ci<script type="math/tex" id="MathJax-Element-50">c_i</script>:
  
  ci=∑j=1npsh(dij),i=1,2,...,np
  <script type="math/tex; mode=display" id="MathJax-Element-51">\begin{equation} c_i = \sum_{j=1}^{n_p}sh(d_{ij}), i = 1,2,...,n_p \end{equation}</script>
  (4)计算出个体 xi <script type="math/tex" id="MathJax-Element-52">x_i</script>的共享适应度值:
  
  f′p(xi)=fp(xi)/ci
  <script type="math/tex; mode=display" id="MathJax-Element-53">\begin{equation} f_p^{'}(x_i) = f_p(x_i)/c_i \end{equation}</script>
  同理我们可以计算出所有个体在小生境条件下的适应度，从而提高了种群在演化时的多样性，因为相似度高的种群，其适应度会得到适当地减小。

整体NSGA工作流程如下图所示(至于遗传算法的具体内容，如果以后接触到，再做详细地了解)：