论文部分内容阅读
演化算法作为一种具有群体搜索策略的启发式算法,被越来越多地应用到科学研究、工业制造中。近年来,被用来解决众目标优化问题(many-objective optimization problems)的有效演化算法也越来越多。在本文中,我们提出了两个新的分别用于解决无约束和有约束众目标优化问题的算法。(1)众目标优化问题有很多个可能存在冲突关系的目标,同时优化所有的目标往往面临很多困难,如无法比较解的质量等。我们提出了一个只在选中的部分目标上比较解的算法：在选中的两个目标上进行Pareto部分支配的众目标演化算法PPDSO-MOEA (Pareto partial dominance on two selected objectives many-objective evolutionary algorithm)。本算法设计了一个选择部分目标的方法,在选择父群体时,只使用两个选中的目标计算解之间的支配关系。本算法中选中的两个目标是离最优点Rpoint最远和次远的两个目标。最优点Rpoint中存储的是到目前为止,每个目标上的历史最优值。当有新的解生成时,实时更新Rpoint。每隔一定的演化次数就重新使用选择目标的方法更换两目标组合来优化所有的目标。在无约束的DTLZ2和DTLZ4问题上验证算法的性能。选择算法MOEA/D, SPEA2+SDE, MyODEMR, PPD-MOEA和随机选择目标方法RS02作为对比算法,实验结果表明我们的算法PPDSO-MOEA在多数情况下要优于其他的算法。(2)现实中的很多问题都是有约束的,算法PPDSO-MOEA主要解决的是无约束的问题,为了解决有约束问题,我们对PPDSO-MOEA进行改进,设计一个新的基于部分支配的算法：PPDSO2-MOEA。由于PPDSO2-MOEA针对的是有约束问题,违反约束的解不是可行解,所以当得到的解是不可行解时,需要使用贪心修复策略进行修复。PPDSO2-MOEA中的archive集合中存放的不一定全是非支配解,因为有时可行的非支配解的个数不一定达到要求,就要用非支配解填充。而PPDSO-MOEA中的archive集合中只存放非支配解,并且archive集合大小是动态变化的。从archive中选择父群体时,PPDSO2-MOEA需要计算crowdingdistance并对解进行排序,然后按层逐个选择解。考虑选出的目标之间的冲突性,选择目标的方法除了PPDSO-MOEA中的方法外,在群体性能不能明显改善时,使用一次随机选择目标的方法。在有约束的众目标0/1背包问题上验证算法的性能。算法PPD-MOEA, MOEA/D, UMOEA/D和随机选择目标的方法RSO,被用来比较我们算法的有效性。实验结果显示PPDSO2-MOEA在大多数场景下优于对比的四个算法。