本来想找MOPSO多目标粒子群算法的matlab工具箱的，但是还没找到。只是有人看到用Matlab的MOGA工具箱。
 
也挺好的，至少可以直接拿过来做MOP多目标问题的求解。
 
NSGA-II is a very famous multi-objective optimization algorithm. I submitted an example previously and wanted to make this submission useful to others by creating it as a function. Even though this function is very specific to benchmark problems, with a little bit more modification this can be adopted for any multi-objective optimization.
 
The function is nsga_2(pop,gen). The input arguments for the function are population size and number of generations. For customization purposes the user is free to modify the objective function (function of several decision variables) by modifying an m file (evaluate_objective.m). Couple of sample objective functions is already described in the file. The user also has the freedom to define the decision space.
 
For more information on NSGA-II visit Kanpur Genetic Algorithm Laboratory at http://www.iitk.ac.in/kangal/
 
One of the main applications of multi-objective optimization that I am currently working on is tuning PID controllers using MOEA. I am hoping to share that work with everyone soon.
 
Update (January 27, 2009): I am unable to support user's request to modify this program to incorporate constraints in the optimization program since I have no time to delve into this field. Hence effective today (January 27, 2009) I release this program under GPLv3. This means that anyone and everyone can modify this code as and how they wish. Enjoy! But do remember to contribute the code back to the community.
 
Effective July 17, 2009 this code is re-licensed under BSD license to comply with Mathworks policy on submissions to MATLAB central.
 
网址：http://www.mathworks.com/matlabcentral/fileexchange/10429-nsga-ii-a-multi-objective-optimization-algorithm

 
本来想找MOPSO多目标粒子群算法的matlab工具箱的，但是还没找到。只是有人看到用Matlab的MOGA工具箱。
 
也挺好的，至少可以直接拿过来做MOP多目标问题的求解。
 
NSGA-II is a very famous multi-objective optimization algorithm. I submitted an example previously and wanted to make this submission useful to others by creating it as a function. Even though this function is very specific to benchmark problems, with a little bit more modification this can be adopted for any multi-objective optimization.
 
The function is nsga_2(pop,gen). The input arguments for the function are population size and number of generations. For customization purposes the user is free to modify the objective function (function of several decision variables) by modifying an m file (evaluate_objective.m). Couple of sample objective functions is already described in the file. The user also has the freedom to define the decision space.
 
For more information on NSGA-II visit Kanpur Genetic Algorithm Laboratory at http://www.iitk.ac.in/kangal/
 
One of the main applications of multi-objective optimization that I am currently working on is tuning PID controllers using MOEA. I am hoping to share that work with everyone soon.
 
Update (January 27, 2009): I am unable to support user's request to modify this program to incorporate constraints in the optimization program since I have no time to delve into this field. Hence effective today (January 27, 2009) I release this program under GPLv3. This means that anyone and everyone can modify this code as and how they wish. Enjoy! But do remember to contribute the code back to the community.
 
Effective July 17, 2009 this code is re-licensed under BSD license to comply with Mathworks policy on submissions to MATLAB central.
 
网址：http://www.mathworks.com/matlabcentral/fileexchange/10429-nsga-ii-a-multi-objective-optimization-algorithm
 
转载本文请联系原作者获取授权，同时请注明本文来自白途思科学网博客。
 
链接地址：http://blog.sciencenet.cn/blog-234554-309565.html
 
上一篇：博客调整方案
 
下一篇：PSO粒子群优化算法Matlab工具箱

多目标遗传算法NSGA
 
因所读的一篇论文中，为了解决多目标的最优解问题，作者使用了一种称为NSGA-II(Improved Non-dominated Sorting Genetic Algorithm)的遗传算法，花了两天时间了解下，此为何物。其中NSGA以及NSGA-II的原理说明内容大部分取自2008年李莉的硕士论文《基于遗传算法的多目标寻优策略的应用研究》，故将此文定为转载。
 
首先需要了解一种称之为‘dominate’的关系： 
 设一个最大化目标函数为$F(x) = (F_1(x), F_2(x), ..., F_k(x))$, 因为是一个多目标最优的问题，所以这里的目标数量$k \ge 2$。假定$x_0$, $x_1$是解空间$X$中的两个解。如果$\exists i \in [1,k]$使得$F_i(x_0) > F_i(x_1)$成立，并且$\forall i \in [1, k]$时，$F_i(x_0) \ge F_i(x_1)$也成立，那么就称解$x_0$占优(dominate)$x_1$。如果在所有的解空间$X$中找不到其他能占优$x_0$的解，那么我们称解$x_0$是一个efficient solution。该$x_0$在空间中对应的点，称为 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) = (F_1(x), F_2(x), ..., F_m(x))$，种群规模为$n$。 

(1)设$i=1$； 
 (2)对于所有的$j=1，2，…，n$且$j \ne i$，按照以上定义比较个体$x_i$和个体$x_j$之间的支 
 配(dominate)与非支配(non-donimated)关系； 
 (3)如果不存在任何一个个体$x_j$优于$x_i$，则$x_i$标记为非支配个体； 
 (4)令$i=1+1$，转到步骤(2)，直到找到所有的非支配个体。 
 通过上述步骤得到的非支配个体集是种群的第一级非支配层，然后，忽略这些已经 
 标记的非支配个体(即这些个体不再进行下一轮比较)，再遵循步骤(1)一(4)，就会得到第二 
 级非支配层。依此类推，直到整个种群被分层。
共享小生境技术 
 为了在演化过程中保持群体的多样性，NSGA中引入了共享小生境技术。 
 假设第$p$级非支配层上有$n_p$个个体，每个个体的虚拟适应度值为$f_p$。 
 (1)算出同属于一个非支配层的个体$x_i$和个体$x_j$的欧几里得距离： 
 
   $$\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}$$  
 其中$m$目标个数，$F_l^u,F_l^d$分别为$F_l$的上界和下界。 
 (2)共享函数(Sharing Function)是表示两个个体间关系密切程度的函数，两个个体$x_i$和$x_j$间的共享函数$sh(d_{ij})$: 
 
   $$\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*}$$  
 $\sigma_{share}$的值表示了$x_i$与$x_j$群体的相似度。 
 $d_{ij}$表示个体$x_i$与$x_j$间的欧式距离。 
 $\alpha$用于对$sh(d_{ij})$的调整。 
 由此可见： 
 $sh(d_{ij})$越大表明二者关系密切，即相似度高 
 (3)然后我们计算出节点$i$与其他所有节点的累积相似度，称为共享度$c_i$: 
 
   $$\begin{equation}
	c_i = \sum_{j=1}^{n_p}sh(d_{ij}), i = 1,2,...,n_p
\end{equation}$$  
 (4)计算出个体$x_i$的共享适应度值: 
 
   $$\begin{equation}
	f_p^{'}(x_i) = f_p(x_i)/c_i
\end{equation}$$  
 同理我们可以计算出所有个体在小生境条件下的适应度，从而提高了种群在演化时的多样性，因为相似度高的种群，其适应度会得到适当地减小。
 
整体NSGA工作流程如下图所示(至于遗传算法的具体内容，如果以后接触到，再做详细地了解)： 
 

遗传算法
 
        遗传算法在多目标优化问题处理中应用广泛，它的基本特征是通过在代与代之间维持由潜在解组成的种群来实现多向性和全局搜索，通过种群基于遗传的进化，实现潜在解向最终解的演变，这种种群到种群的方法在搜素Pareto解时是很有用的。
 
        遗传算法可以处理所有类型的目标函数和约束，不受制于他们的数学属性，可以在不考虑特定内部工作方式的前提下搜索解，因此在求解复杂问题解上比传统优化算法应用更多，可用性也更广。遗传算法作为启发式算法在处理单目标优化问题表现很好，后来逐渐的被引入多目标优化问题处理，现如今基于遗传算法的改进算法蓬勃发展，所以学习了解遗传算法是有必要的。
 
 
算法介绍
 
1. 算法结构
 
        算法过程如下：
 
         算法整体结构：
 
 
 
2. 结构分析
 
①初始种群的生成
 
       遗传算法是对种群进行操作的，初始种群的选择影响着算法的最终性能，所以初始种群的选择尤关重要。在处理实际问题时，问题的最优解在解空间的分布情况是不清楚的，所以设计初始种群时尽量设计成在解空间均匀分布（想法：参考自然界的进化规律，地球生物演化的起点是简单单细胞生物，是否可以以此参照设计初始种群，如从单个种群开始保持高突变率来演化成多种群，这样计算复杂度肯定高了但是否性能会变好？）。初始种群的个数是种群规模，依据问题复杂性，问题越复杂，目标空间维数越高，种群规模越大，反之亦然。常规的种群生成规则如下：
 
       有先验知识：利用先验知识在决策空间的生成均匀分布的初始种群。
        无先验知识：首先随机生成一定规模的初始种群，然后选取一部分适应度最好的，一小部分最差的，一小部分适中的个体，如此循环，直到种群规模满足要求。
 
②个体编码
 
       编码就是把实际问题变量转化成计算处理的决策空间变量，反之，把决策空间的解转成问题空间的解叫解码。编码的要求有三：
 
       （1）完备性：问题空间的任意解可以单射到决策空间。
        （2）健全性：决策空间的解可单射到问题空间的解。
        （3）非冗余性：问题空间的解和决策空间的解相互满射。
 
       编码的方法有多种，最有效最常用的是实数编码，其基因型空间中的拓扑结构与其表现型空间中的拓扑结构一致，因此很容易借鉴传统优化方法中的技术。根据实数编码，种群$P(t)$可以描述为：
 
       $P(t)=${$x_{t,1},x_{t,2}\cdots x_{t,pop}$}
        $x_{t,j}=${$(x_{t,j,1},x_{t,j,2}\cdots x_{t,j,n})|x_{t,j,1},x_{t,j,2}\cdots x_{t,j,n}\in min+(max-min)rand(1)$
        $j\in 1,2,\cdots ,pop$
 
       $pop$是种群规模，种群中的每个个体$x_{t,j}$由$n$个参数衡量，且这$n$个参数有上下限。$rand(1)$表示0到1随机数。
 
③评估函数设计
 
       评估函数是计算评估个体的适应度，从而决定个体是否参与杂交或繁殖其他操作的。适应度是进化论里的概念，表示的是个体对环境的适应程度，在算法中，就是表示个体解的优劣性。适应度越高，表示个体存活的概率越大，也就是更可能参与繁殖。评估函数的形式取自于具体的优化函数，具体有以下要求：
 
       性质：非负，连续，满射，单点极值。
        简单：尽可能减少计算量
        可拓展性：争对具体问题设计的评估函数可以被其他问题使用。
        有效性：能过区分种群个体的优劣性。
 
       评估实际就是个体做标签，作为给算法进行下步处理的参考依据。评估函数计算得出的适应度是可以调整的，如共享函数，可以用来降低个体的适应度来控制种群的多样性。
 
④繁殖机制
 
       整个繁殖机制包括选择，杂交和变异三部分。
 
       选择：按照一定策略从当代种群中选取一部分个体进行下部操作。如上文所说的，依照适应度，通过诸如轮盘赌，$(\mu +\lambda )$选择，锦标联赛，Pareto支配关系，共享等方式，以生成待繁殖群。选择方式的特征有随机性和确定性两种，前者表现为对当代种群的个体，无论适应值好坏，都有被选择的概率。如轮盘赌，依据适应值比例确定个体的被选概率；后者表现为对当代种群个体的选择是依据适应度而确定的，适应度坏的个体不会被选择。大多选择方式是两者特征的结合，如锦标联赛方式，从随机选择的个体中选取适应度好的。
 
       选择过程在整个繁殖机制的基础，它指明着种群的未来进化方向。也就是说，选择的好坏影响着算法解的收敛性和分布性。各种选择方式都遵循“精英保留”原则，保留有前途的个体，这是保证收敛性的操作，然而这种操作也有可能发生有限解收敛到同一个最优解（在单目标问题中，表现为陷入局部最优）的情况，共享方式就是争对这种情况在选择阶段做出改进的方式。通过共享函数，降低聚集区域个体的适应度，从而提高其他个体的被选概率。选择结果的理想状况应是：选取的个体群尽可能表现最好，尽可能分散，尽可能全域覆盖。
 
       杂交：通过当代选择个体群（父代）产生下代种群（子代）。仿照生物界的有性生殖（无性繁殖可不可以仿照？区别于变异的单点进化，如父代首先自我变异，然后父子代个点自我交叉。），产生的子代继承了父代的优良基因，在算法上表现为计算之后的点可能会更加地接近理论最优值，也可能会偏离，但不会严重偏离，同时这种偏离也可能会产生另一个Pareto最优解，因此杂交也体现着算法的收敛性和多样性。对不用的编码方式，杂交算子的设计不同，算子的设计也有随机和确定两种特征。这里介绍NSGA-Ⅱ中基于实数编码的随机算子设计方式：算数杂交。
 
       根据凸集理论：如果可行域是凸的，则可行域中两点连线上的点也在可行域中。对于向量$x_1$,$x_2$，它们的加权平均为 ${\lambda }_1$$x_1$+${\lambda }_2$$x_2$，乘子限制为 ${\lambda }_1$+${\lambda }_2=1$。算数杂交定义的两个向量组合是：
 
                                                                                     $x_1^{{}^{\prime }}={\lambda }_1$$x_1$+${\lambda }_2$$x_2$
                                                                                      $x_2^{{}^{\prime }}={\lambda }_1$$x_2$+${\lambda }_2$$x_1$
 
       其中${\lambda }_1$，${\lambda }_2$的设计为
 
                                                                                     ${\lambda }_1=0.5(1+bq)$
                                                                                      ${\lambda }_2=0.5(1-bq)$
 
         $mu=20$是杂交分布指数。
 
       变异：子代个体的随机变化。杂交之后的子代可能会发送陷入同一最优，过早收敛或不成熟收敛的情况，变异算子可以有效解决上述问题。还是以NSGA-Ⅱ中的变异算子为例，对于向量$x$，变异方式为：
 
                                                                                    $x^{{}^{\prime }}=x+\delta$
                                                                          $\delta =|2rand(1{)}^{\frac{1}{mum+1}}-1|$
 
        $mum=20$是变异分布指数。
 
       整个繁殖机制是算法的核心，可以看出机制的设计处处体现了算法的收敛性和多样性，这也是整个算法的核心思想，大多的基于遗传算法的改进也是从这两方面入手的。宏观上来说，繁殖机制是解计算中的搜索阶段，算法设计原则是更快更好更分散的计算出最终解。杂交过程的作用是在编码空间中进行全局搜索，以最快速度找到PF面上各点（单目标中是全局最优），变异过程提供了加快每个PF点的收敛速率的可能（主要还是保证多样性），提高了算法的局部搜素能力。
 
 
3.总结
 
       对于问题解的搜索，有两种行为模式，一种是全局搜素：广泛搜索整个解空间并且向同一最优逃离；令一种是局部搜索：深度搜索最优解并且向局部最优爬山。显然遗传算法是一种结合两种模式的通用搜易方法，因此在多目标优化问题中得到了最为广泛的应用。
 

 
Tips：
 
通过类比，更好理解多目标优化与单目标优化的联系和区别：
 
单目标优化
多目标优化
局部最优
有限解集收敛到同一最优解
全局最优
有限解集分散构成PF面