MOGA对种群中每一个个体的排序数是基于Pareto最优的概念对当前群体中优于该个体解的其他个体数目进行统计,并采用一种基于排序数的适应度赋值方式。另外,该算法采用自适应的小生境技术与受限杂交技术来提高种群多样性,防止解群的过早收敛。
MOGA采用的是基于排序的适应度赋值机制,排序方法是将群体中的每个成员与群体中支配该个体的所有其他个体的数目相关联。Pareto前端上所有个体的排序级别确定为1级,其余成员则将优于该个体的成员数目赋予为排序级别。MOGA的适应度计算方法同时考虑群体成员的级别和群体的平均适应度数值,其赋值过程是:先将群体进行个体级别排序,然后根据预先设定的函数对最高级别至最低级别的个体进行插值,最后让具有相同级别的个体拥有平均的适应度值。这种方法可以保证群体中相同级别的成员具有相等的分布频率,以适当的选择压力维持一个整体稳定的群体适应度。
另外,MOGA采用适应度共享方式,称之为拥挤操作算子和小生境操作算子,其中的重要参数是σshareо σshare是指小生境数目,必须小心设置,因为它对进化结果比较敏感。Fonseca和Fleming采用小生境方法是在表现型空间实施的,目的在于获得Pareto前端均匀分布的解点。
MOGA还采用约束配对方法,Goldberg最早提出采用约束配对是为了避免位于某一局部区域内成员的过度竞争。另外,决策者的目标和意图也可以嵌入到适应度函数中。由于决策者最终是从Pareto前端选择一个子集作为最后优化方案,因而预先确定Pareto前端的最感兴趣区域对解决优化问题很有价值。这种附加的偏好信息以问题领域信息形式出现,作为局部搜索操作算子插入到MOGA的算法过程中。一般来说,决策者偏好的信息可以采用效用函数来实现。效用函数的另一个作用是可以辅助决策者从最终的Pareto前端解点选择出自己认为满意的最佳方案。
MOGA采用格雷编码对染色体个体进行编码,使用两点置换交叉。在进化过程中所有找到的非劣解点存储在一个档案里。该档案可以用来确定如何在下一代中使用σshare值,并与MOGA的运行过程一起迭代更新,即将非劣解点不断地写入到该档案集合中,直至算法运行到满足停止准则为止。
MOGA的主要不足在于如果小生境数目信息是基于目标函数的,那么两个具有相同目标函数向量的不同个体无法在同一代种群中存在,这显然是人们不希望看到的,因为这样的两个解方案有可能恰恰就是决策者想要得到的结果。这种方法的优点是效率较高,而且易于实现。值得一提的是,Fonseca和Fleming从理论上解决了小生境大小规模的计算确定问题,在实际应用中意义和价值较大,本书后文将对此作进一步的深入介绍。
……
展开