基于自适应ε支配多目标遗传算法的研究

摘要

现实世界中存在着许多多目标优化问题（MOP），传统的规划算法不能很好求解这些问题。而多目标遗传算法(MOGA)擅长于求解高度复杂的多目标优化问题且通过一次运行可以搜索到一组Pareto折衷解。因此引起许多研究者的兴趣，提出了不少多目标遗传算法，如：SPEA2、NSGAII、PESAII等。这些算法要么耗费大量时间以获得良好的分布度，要么速度很快但分布度较差。例如，虽然SPEA2的解分布度比NSGAII好，但它需要更多的时间。 Deb等提出的基于ε支配的ε-MOGA，该算法利用ε参数将整个Pareto最优面分成若干个超立方体，然后利用ε支配使得在每个超立方体中至多有一个非支配个体，从而来保持解集的分布度。由于该算法不需要截断算法，因此在一定条件下能在时间效率和分布度之间取得很好折衷，但是该算法需要根据Pareto最优面及用户期望得到的非支配个体的数量来设定ε参数，而由于许多实际问题无法知道它的Pareto最优面，因而无法合理地设定ε参数。针对上述问题，在结合其他算法的优点上，本文提出一种基于自适应ε支配的多目标遗传算法（AEMOGA），该算法不需要在算法初始时人为设定ε参数。采用庄家法则来构造非支配集，用改进的SPEA2的截断算子作为截断算子。同时文章中提出了更新ε参数的方法及改进的SPEA2的截断算子。最后通过与当前几种经典的MOGA实验比较，验证了本文提出的算法在时间效率、分布度、收敛度等方面都有不错的表现。