基于遗传算法的多目标优化算法优化方案

带精英策略的快速非支配排序遗传算法（NSGA－Ⅱ）是一种基于遗传算法的多目标优化算法，是目前应用最为广泛的算法之一［167，168］。在NSGA－Ⅱ的基础上，提出INSGA－Ⅱ算法，该算法采用最优前端个体系数表示最优前端中的个体在种群中所占的比例，即最优前端个体数＝min｛最优前端个体系数*种群大小，前端中现存的个体数目｝。最优前端个体系数的引入用来限制第一前端保留的个体数目，当最优前端个体数确定后，通过锦标选择将该前端中的个体数目修剪至保留的个体数目。

INSGA－Ⅱ的运算步骤如下。

（1）随机产生一个由确定长度的特征字符串组成的初始种群，非支配排序后通过遗传算法的选择、交叉和变异3个基本操作得到第一代子种群。

（2）从第二代开始，将父代种群与子代种群合并，进行非支配排序，同时计算每个前端中的拥挤距离。

（3）通过序值和拥挤距离在两倍于种群大小的个体中选择出个数等于种群大小的个体组成新的父代种群。

（4）通过遗传算法基本操作产生新的子代种群。以此类推，直到满足停止条件。

相应的算法流程如图5－8所示，其中GEN为当前代数。

图5-8　INSGA-Ⅱ算法流程图

5.3.3.1　序值计算

在多目标优化问题中，如果个体p至少有一个目标比个体q的好，而且个体p的所有目标都不比个体q的差，那么称个体p支配个体q。如果p支配q，则p的序值比q低；如果p和q互不支配，则p和q具有相同的序值。序值为1的个体属于第一前端，以此类推。

5.3.3.2　非支配排序

非支配排序的作用是对父、子种群合并后的种群中的个体进行排序。排序过程中，序值从1开始，依次加1，在每一轮排序中，依次将种群中未被排序的个体p与其余未被排序的个体q进行比较。若个体q没有支配个体p，则个体p被赋予当前序值；反之，个体p参与下一轮的排序。通过排序，种群中的所有个体被分到了不同的前端，如图5－9所示。(www.xing528.com)

图5-9　非支配排序图

5.3.3.3　拥挤距离计算

拥挤距离计算即计算某一前端内每个个体与其相邻个体的距离。其计算步骤为：对于前端两头的两个个体，给定一个无限大的数；其余个体的拥挤距离为与其相邻的两个个体在每个目标上的距离差之和。计算拥挤距离的目的是使求得的解均匀地分布在Pareto曲面上，其计算模型如下：

式中：Cd［1］，Cd［n］为前端两头个体的拥挤距离；Cd［p］为个体p的拥挤距离；fm为第m个目标函数。

图5－10所示为双目标函数个体拥挤距离示意图，个体p的拥挤距离为两部分折线长度之和。从图中可以看出，某个体的拥挤距离越大，表示该个体与相邻个体的目标函数值差别越大，多样性越好，在接下来的种群修剪中就越不会被裁剪掉。

5.3.3.4　锦标赛选择

与GA不同，INSGA－Ⅱ的选择只使用基于序值和拥挤距离的锦标赛选择。对于两个个体，当序值不同时，序值小的个体将被选中而不论其拥挤距离如何；当序值相同时，拥挤距离大的个体将被选择。

INSGA－Ⅱ算法的形象描述如图5－11所示。与基本遗传算法相比，INSGA－Ⅱ具有如下特点：采用了快速非支配排序法，降低了算法的计算复杂度；提出了序值、前端、拥挤距离等概念，其中拥挤距离在非支配排序后的选择中作为胜出标准，使准Pareto域中的个体能扩展到整个Pareto域并均匀分布，保证了物种的多样性；引入精英策略，扩大采样空间；将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保证父代中的优良个体不被遗失，迅速提高种群水平。

图5-10　拥挤距离

图5-11　INSGA-Ⅱ示意图