论文部分内容阅读
多目标优化广泛应用于工程实践和科学研究等领域,解决多目标优化问题常用的方法有传统解法和智能算法。遗传算法是智能算法的一种,是基于生物自适应进化的一种仿生算法,其全局搜索和并行搜索能力较强,在单目标和多目标问题的求解方面具有优越的性能。本文基于遗传算法的基本理论,设计了一种改进的非支配排序遗传算法(DNSGA2-PSA)用于多目标问题的求解,并对算法的性能进行了评价。主要研究工作及成果如下:首先,在学习研究多目标优化理论和传统的多目标优化求解算法的基础上,进一步学习了多目标进化算法的基本理论和几种典型的多目标进化算法;着重阐述了多目标进化算法领域中的一种基准算法——带精英保留策略的非支配排序遗传算法(NSGA-Ⅱ)。其次,设计了一种基于支配度矩阵的非支配排序遗传算法求解多目标优化问题。该算法在带精英保留策略的非支配排序遗传算法(NSGA-Ⅱ)的框架上进行了解集多样性和非支配排序方法的改进。通常多目标算法的主要设计目标有收敛性和多样性,NSGA-Ⅱ算法着重考虑收敛性的设计,对多样性有一定的改进,取得了较好的效果。为了进一步提高NSGA-Ⅱ算法的多样性,本文利用划分选择算法(PSA)重新定义个体之间的拥挤度距离来保持种群多样性。划分选择算法可以从任意给定集合中选择出具有多样性的子集,利用算法的这个特点可以从当前种群中筛选出具有多样性的个体进入下一代进化过程,从而得到具有多样性的解集。此外,由于NSGA-II算法采用Pareto支配引导算法收敛到Pareto前沿面,搜索过程包含非支配排序、支配计数等方法,这些方法通常比较耗时,并且时间会随着目标函数维度的增加而增加;因此本文引入了一种新的矢量排序方案——基于支配度矩阵的非支配排序(DDA-NS)来降低整个算法运行时间。本文将PSA和DDA-NS两种改进策略同时嵌入到NSGA-Ⅱ中改进了该算法,文中将改进算法表示为 DNSGA2-PSA。最后,通过数值实验测试了改进算法的性能。本文采用算法执行时间和最终解集的收敛性指标以及在非劣前沿上的均匀分布性指标对算法进行评价。实验结果表明:DNSGA2-PSA算法的运行时间明显小于单独加入PSA的NSGA-Ⅱ算法(NSGA2-PSA),这说明基于支配度矩阵的非支配排序方法可以很大程度减少整个算法的运行时间;改进算法在收敛性指标GD、IGD和多样性指标HV、Spacing上的评价结果明显优于单独使用DDA-NS,PSA加入到NSGA-Ⅱ的算法,并且在高维情形下仍表现出良好的适用性。