论文部分内容阅读
高维多目标优化问题广泛存在于实际应用之中。在这类问题中,往往需同时考虑不止3个优化目标。研究高维多目标优化问题的有效解法是当前演化多目标研究领域的热点及难点问题之一。高维多目标优化存在众多难点,如个体密度估计不准确、收敛性和多样性的矛盾加剧、搜索方向难以自适应Pareto前沿（PF）的形状、重组算子表现乏力等。针对这些难点,本文提出了若干简单有效的新高维多目标优化算法,并在大量测试问题上验证与比较新算法与其它主流算法的性能。此外,为促进高维多目标优化算法的实际应用,以软件产品线上最优软件产品选择为实际应用场景,采用新提出的算法框架,结合可满足性（Satisfiability,SAT）求解器,快速且有效地求解高维多目标最优软件产品选择问题。本文遵循从算法设计、到实验仿真、再到实际应用的研究路线,实现算法设计与实际应用的有机结合,形成体系化研究成果,具体包含以下几个方面:1.提出基于夹角的VaEA算法。在算法中,运用夹角估计个体密度。在此基础上,采用“最大夹角优先”准则提升解集的多样性。为平衡收敛性和多样性,设计了“较差剔除”准则,即多样性满足一定条件时,允许替换种群中收敛性较差的个体。在大量具有高达15个目标的测试问题上,比较VaEA与其它主流算法的性能。实验结果表明,在平衡收敛性和多样性方面,VaEA表现优异。此外,在两个PF不规则的实际问题上,VaEA最终解的多样性优于其它对比算法,充分说明运用夹角估计个体密度的有效性。值得一提的是,VaEA具有无需事先指定权向量、控制参数少和时间复杂度不高等优点。2.提出运用标量投影从历史解选择领导者的MaPSO算法。在设计（高维）多目标粒子群优化算法时,领导者的选择策略至关重要。在MaPSO算法中,运用标量投影从粒子各自的历史解中选择领导者。对每个粒子,算法为其保留一定数量的历史解。在目标空间中,历史解记录了粒子的潜在搜索方向。粒子的领导者定义为沿着从天底点到当前粒子位置的方向上,标量投影最大的历史解。沿着上述方向,如此定义的领导者最靠近真实PF。在环境选择时,MaPSO算法运用了分阶段优化的思想,即首先强调收敛性,然后逐步过渡到多样性。运用大量测试问题进行仿真实验,结果表明MaPSO算法较其它主流算法有较大优势。此外,新领导者选择策略的有效性也通过实验予以充分验证。3.提出基于分解的高维多目标人工蜂群算法MOABC/D。该算法是基于分解的算法框架（即MOEA/D）与人工蜂群（ABC）算法的混合算法。在MOABC/D中,高维多目标优化问题被转化为一系列单目标子问题,并由改进的ABC算法同时优化。在一组权向量的辅助下,MOEA/D框架可有效保持解的多样性,而ABC算法收敛性速度快,可快速求解单目标优化问题。因此,二者的混合算法可较好地平衡收敛性和多样性。此外,新算法并非同等对待所有子问题,而是综合运用观察蜂和侦察蜂,根据子问题的难易程度动态地分配计算资源。在具有高达50个目标的13个测试问题上,比较MOABC/D与其它5个主流算法的性能表现。实验结果表明,无论最终解集的质量还是算法效率,与其它算法相比,MOABC/D表现相当甚至更优。相关实验结果还表明,观察蜂和侦察蜂的确有助于提升算法性能。4.提出求解高维多目标最优软件产品选择问题的SATVaEA算法。在软件产品线中,特征模型简洁地表示了所有可能软件产品的信息。最优软件产品选择即从所有软件产品中选择满足某个（些）特定优化目标的最优产品,其中高维多目标最优软件产品选择问题不仅搜索空间大,而且往往带约束。本文提出的SATVaEA有机结合VaEA算法框架与两种不同类型的SAT求解器,为解决高维多目标最优软件产品选择问题提供了行之有效的新方法。在SATVaEA中,采用两个SAT求解器增强VaEA的搜索能力。第一个是随机局部搜索（Stochastic local search,SLS）SAT求解器,目的在于快速修复不可行解;第二个是冲突驱动的子句学习（Conflict-driven clause learning,CDCL）SAT 求解器,目的在于产生多样化的软件产品。为评估SATVaEA,选择最高特征数达62,482的21个特征模型（其中2个模型具有真实特征属性）进行仿真实验。结果表明,在几乎所有特征模型上,SATVaEA均可成功返回100%的有效软件产品。此外,SATVaEA运行速度快,对具有超过10,000个特征的模型,SATVaEA仅需运行几分钟即可搜索到大比例的有效产品。考虑算法的效果和效率,SATVaEA较其它主流算法有明显优势。5.进一步讨论与研究高维多目标最优软件产品选择算法。首先,探讨不同SAT求解器对SATVaEA算法性能的影响。事实上,SATVaEA的局部搜索使用的是快速WalkSAT。选择基于概率的ProbSAT求解器进行对比实验,发现ProbSAT有助于改善最终解集的质量（尤其是多样性）和加快算法搜索到大比例有效产品的收敛速度。其次,提出了集成用户偏好信息的高维多目标软件产品选择算法PreEA。该算法采用成就标量化函数（Achievement scalarizing function,ASF）集成用户偏好,运用与SATVaEA算法相同的SAT求解器增强算法的搜索能力。事实上,SATVaEA以先搜索再选择的后验方式处理用户偏好。与此不同,PreEA将用户偏好集成于优化过程,每次运行仅返回（尽量）满足用户偏好的唯一解。实验结果表明,PreEA可有效处理用户偏好,且SAT求解器是PreEA算法表现优异的关键因素。综上所述,本文针对高维多目标优化问题的算法设计及实际应用展开一系列研究。一方面,本文提出的算法丰富了当前有关高维多目标优化的研究成果。另一方面,本文的研究为软件工程师有效和高效配置软件产品线提供了新思路和新方法。总的来说,本课题的研究成果对演化多目标和软件产品线工程研究领域均具有较大的现实意义和参考价值。