多目标优化问题和遗传算法学习

名词：

Nondominated sorting 非支配排序
Nonelitism approach 非精英机制方法
selection operator 选择算子
multicriterion decision-making methods 多重判据决策方法

基本概念：

（2）pareto（帕累托）最优解的相关概念

1）Paerot支配关系：

2）Pareto最优解定义：

多目标优化问题与单目标优化问题有很大差异。

当只有一个目标函数时,人们寻找最好的解,这个解优于其他所有解,通常是全局最大或最小,即全局最优解。

而当存在多个目标时,由于目标之间存在冲突无法比较,所以很难找到一个解使得所有的目标函数同时最优,也就是说,一个解可能对于某个目标函数是最好的,但对于其他的目标函数却不是最好的,甚至是最差的。

因此,对于多目标优化问题,通常存在一个解集,这些解之间就全体目标函数而言是无法比较优劣的,其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解(nondominated soluitons)或Pareto最优解(Pareto optimal Soluitons),定义如下：

NSGAII算法：

（1）NSGAII算法的基本流程

首先,随机产生规模为N的初始种群,非支配排序后通过遗传算法的选择、交叉、变异三个基本操作得到第一代子代种群;

其次,从第二代开始,将父代种群与子代种群合并,进行快速非支配排序,同时对每个非支配层中的个体进行拥挤度计算,根据非支配关系以及个体的拥挤度选取合适的个体组成新的父代种群;

最后,通过遗传算法的基本操作产生新的子代种群:依此类推,直到满足程序结束的条件。相应的程序流程图如下图所示：

算法思想：

A. 快速非支配排序方法

B. 保留多样性

NSGA-II提出了拥挤比较方法替换了共享函数法。

1）密度估计：根据每一目标函数计算该点两侧的两个点的平均距离，该值作为以最近邻居作为顶点的长方体周长的估计（作为拥挤系数）。如下图，第i个解的拥挤系数为他周围长方体的长度（虚线表示）。计算拥挤系数需要对每一目标函数进行排序。

C. 主程序

先按照非支配面进行排序，然后对每个支配面里的拥挤算子进行排序，找出前N个点，主要思想如上述B里的第二点。

仿真：

（1）测试函数

（2）评估指标

所有目标函数都是求最小化（convex 凸的，nonconvex 非凸的）
1）评估解收敛性，用deb提出的Convergence Metric（收敛性指标）

（3）仿真流程：

参考文献

[1] K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” in IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, April 2002, doi: 10.1109/4235.996017.
[2]公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学 ,2009(2):271-289.

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33949 人正在系统学习中