论文部分内容阅读
在现实中有许多多目标优化问题(Multi-objective optimization problems,MOPs)。这些问题被广泛应用到工程优化与设计、数据挖掘、运筹学、生物医学等领域。由于多目标优化问题的各目标之间是相互冲突和排斥的,因此不存在最好的唯一解,而是一个最优解集(Pareto最优解集)。多目标进化算法(Multi-objective evolutionary algorithms,MOEAs)是一类有效地求解多目标优化问题的方法,目前其已经变成了一个研究热点。追求所求解集的多样性和收敛性是多目标进化算法的两个主要目标。为了同时实现这两个目标,针对复杂多目标优化问题和高维多目标优化问题(Many-objective optimization problems),分别设计了几个基于分解的多目标进化算法。本文的主要创新成果分为如下四个方面:第一,为了提高进化算法的搜索效率和维持解的多样性,将机器学习技术(learning automata)应用到定量正交设计(quantization orthogonal crossover)来提高搜索效率,并且设计了一个新的基于分解的适应度函数来维持解的多样性和引导解的搜索。在此基础上,提出了一个基于分解的正交多目标进化算法((OELA)。分别对具有复杂Pareto最优解集(Parto optimal solutions,PS)和具有很多局部最优解的多目标优化问题进行了测试,实验结果表明,对具有复杂PS的多目标优化问题,设计的算法的性能优于MOEA/D、NNIA和NSGAII,能找到收敛性更好并且分布均匀宽广的Pareto最优解集;对于具有很多局部最优解的多目标优化问题,OELA比MOEA/D、NNIA和NSGAII更快的收敛到Pareto最优解集。第二,为了能更好地维持解的多样性,设计了一个基于目标空间分解的进化算法。首先,将一个多目标优化问题的目标空间通过一组方向向量分成若干个子目标空间;然后,让每一个子空间有一个解,即使这个解是被支配解,这样就可以很好地维持解的多样性。另外,让支配解有更大的选择概率来产生下一代,这样可以让每个解都尽可能地收敛到PS。算法测试了6个这类多目标优化问题,数值实验结果表明,设计的算法比MOEA/D、NNIA和NSGAII更擅长维持解的多样性,并且能收敛到PS。第三,对高维多目标优化问题,随着目标个数的增加,种群中非支配解的比例会急剧增加,而多目标进化算法常依靠种群中的非支配解来指引搜索,这会导致多目标进化算法的收敛能力急剧下降。为了提高收敛能力和维持解的多样性,设计了一个新的收缩非支配区域的方法。它是通过修改目标函数值来使新的目标向量集中在一个小的区域并且收缩解的非支配区域,然后用Pareto占优对新的目标向量进行排序。这个收缩非支配区域的方法能很好的平衡收敛性和多样性。最后通过数值实验验证,与当前两个排序方法进行比较,表明新的排序方法能提高解的收敛性并能很好地保持解的多样性。第四,对于高维多目标优化问题,实现解集的多样性和收敛性更加困难。为了达到这两个目标,设计了一个基于分解和收缩方法的进化算法(UREA/D)。这个算法用均匀设计产生权重向量,权重向量的个数不会随着目标个数的增加而呈非线性增长,这样种群的规模可以不随目标数的增加而急剧增加,且可灵活设置。为了提高算法的收敛性,使用了一个子种群策略来加强局部搜索,并且利用收缩非支配区域的方法来对每个子种群进行排序。数值实验测试了目标个数是5到25的多目标测试问题,与现存的算法NSGAII-CE、MOEA/D和HypE比较,实验结果表明,UREA/D能找到收敛性和多样性都更好的解集。