软件升级问题多目标优化方法研究

导语：软件升级问题多目标优化方法研究一文来源于网友上传，不代表本站观点，若需要原创文章可咨询客服老师，欢迎参考。

1引言

随着开源思想的流行，越来越多的开发者加入开源软件世界，FOSS（FreeandOpenSourceSoftware）发行版操作系统中的开源软件仓库的规模日益壮大。同时，开源软件仓库中的软件包之间的依赖和冲突关系越来越复杂，这导致了一个严重的问题：当使用系统原生的包管理器安装或升级软件包时，可能会遇到软件包安装或升级后系统变得不稳定或丧失一些功能的情况，甚至可能由于计算上的高复杂度，包管理器无法找到能够满足系统中软件包之间的依赖和冲突的安装方案，而直接提示软件包安装或升级失败。这些状况会影响正常的生产工作，因此有效地解决软件安装或升级问题十分必要。如图1所示，自2001年以来，Debian软件仓库中的软件包数量持续增长，截至2019年12月，软件包数量已超过59000［1］。然而，由于软件包之间的联系，软件包的管理在计算上是非常复杂的。例如，一个软件包可能依赖某些软件包或者与某些软件包冲突，软件包管理工具必须要能够维护好一个描述软件包安装情况的配置方案，该方案须满足每个软件包的依赖项，并且不会造成软件包之间的冲突，搜索这样的配置方案就是软件升级问题。然而，配置方案仅仅满足软件包之间的依赖和冲突是不够的，还需要在这个基础上达到某种最优的要求，软件包升级问题本质上是多目标优化问题。考虑到系统的稳定性，用户可能对不同的升级目标感兴趣，如要求被移除的软件包的数量和版本发生改变的软件包的数量尽可能少；此外，考虑到网络传输数据量，用户可能希望需要下载的软件包的体积尽量小等。即使仅考虑其中一个升级目标，软件升级问题可以简化为带权重的最大可满足（partialweightedMAXSAT）问题［2］，这也是一个NP难问题。不仅如此，越来越庞大的软件包仓库也使得可量测性成为软件升级过程中的巨大挑战。现有的升级问题求解器都是以聚合的方式简单地将多个升级目标加权转化为一个单目标优化问题，再使用单目标优化算法进行求解。这种方式未考虑不同目标之间的关系和冲突，可能存在一定的风险：如果过度重视某一个目标的优化，那么单目标优化算法在其他目标上的表现就会非常糟糕［3］。针对上述问题和挑战，本文首次尝试结合约束求解和多目标演化算法来处理软件升级问题，并提出了一个多目标优化软件升级框架———SATMOEA，其能够同时对多个升级目标进行优化，而不会发生现有的升级问题求解器中“厚此薄彼”的现象。该框架分为实例解析、约束求解、构建多目标优化问题、演化优化4个阶段。实例解析是将软件升级问题实例（CUDF文件）中描述的与用户请求的软件包相关的依赖和冲突关系抽象出来，表示为描述布尔可满足性问题（SAT）的CNF文件；约束求解是使用快速采样技术得到CNF文件的一系列可行解；构建多目标优化问题是定义软件升级问题的各个优化目标函数以及约束条件的计算方法；演化优化阶段则是使用本文改进的多目标演化算法对构建好的多目标优化问题进行迭代优化求解，并最终得到帕累托解集。本文在MISC提供的升级问题标准实例集上进行了实验，结果表明该框架能够在一次运行后即可得到一系列在各个优化目标上均为帕累托最优的升级方案，相比现有的软件升级问题求解器一次只能得到一个升级方案，该框架能够提供给用户更多的可选方案以应对多样的应用场景，并且在一些升级目标上有显著的优势。本文第2节论述了软件升级问题领域现有的相关工作和研究进展；第3节详细阐述了本文提出的多目标优化软件升级框架的流程与细节；第4节介绍了本框架在标准升级问题实例集上的实验及结果；最后总结了本框架的优势与存在的问题，以及未来进一步的研究方向。

2相关工作

2．1软件升级问题求解器。在类UNIX操作系统中有各种用于解决软件包管理问题的自动化工具，如Debian中的apt－get、RedHat中的yum、ma－cOS中的fink等。这些工具基于软件包的依赖和冲突信息来决定如何在已安装其他软件包的系统中安装用户请求安装的新包，并且满足其依赖［4］。然而，由于软件包之间依赖和冲突关系的复杂性，这些工具通常使用某种启发式方法，因此是不完备的求解工具。在有些情况下，尽管某个软件包是可以安装的，但是这些工具却不能成功地找到一个安装方案［5］。早期有些工作采用了基于布尔可满足性问题（BooleanSatisfiability，SAT）的工具来求解复杂的依赖和冲突，并能确保在安装及升级软件包前后，软件包仓库和系统原已安装的软件包的一致性。Mancinelli等［6］将软件包安装问题形式化描述为SAT问题，并首次使用基于SAT的工具为发行编辑提供支持。他们开发的自动化工具能够确保完整性，并且比内置的和手动的工具更加可靠。后来，Argelich等［7］应用最大可满足问题（MaximalSatisfiability，MaxSAT）的思想从用户角度求解软件包安装问题。Tucker等［4］提出了优化的方法，通过使用SAT求解器、伪布尔问题求解器、整数线性规划求解器来达到更好的结果。他们设计出Opium工具用于优化用户提供的一个目标函数。Argelich等［8］从布尔多级优化（BooleanMulti－levelOptimization，BMO）的视角求解软件升级问题，他们提出了两种不同的算法，分别基于MaxSAT和伪布尔优化（Pseudo－BooleanOptimization，PBO）。他们的实验表明，专门用于BMO的算法比最好的MaxSAT和PB求解器效率提高了几个数量级。Daniel等［9］开发了一个基于SAT4J伪布尔求解器的软件包升级工具P2，用于处理E－clipse平台上的插件安装问题。Paulo等［10］将软件安装问题形式化描述为伪布尔优化问题再进行求解。至止，以上求解工具都是采用在不同的软件包管理环境中的不同语言来描述软件升级问题。为了便于评估和比较这些求解工具的性能，MANCOOSI项目人员设计了一种标准的文档格式CUDF（CommonUp－gradabilityDescriptionFormat）来描述软件升级问题［11］。自此，各种CUDF求解器开始出现，它们将CUDF文件描述的升级问题转换为SAT问题、混合整数线性规划（MixedInte－gerLinearProgramming，MILP）问题、伪布尔优化（PBO）问题、ASP（AnswerSetProgramming）问题、最大可满足问题（MaxSAT）等形式，再采用相应的专门算法进行求解。这些求解器包括mccs［12］，aspcud［13］，P2CUDF（P2的新版本）［14］，PackUp［15］和PackUpHyb［3］。本文使用CUDF实例进行实验探究。上述现有的求解器大多是将软件升级问题按照用户的个性化请求转换为某个单目标优化问题，然后以聚合的方式处理多个升级目标。尽管这些求解器能够得到一个某种意义上的最优解，但是这些方法具有明显的局限性：在现有的方法中，多个升级请求以聚合的方式被处理，如加权和（weightedsum）标量化转换方法和字典序组合方法。因此，这些方法存在一个潜在的风险：不同的升级目标之间的关系可能没有被恰当地考虑。2．2基于搜索的技术在软件工程中的应用。软件升级问题在于找到能够满足软件包的依赖关系并避免冲突的软件包安装方案，这是一个NP难问题。使用精确算法求解NP难问题需要指数级别的复杂度，但是每一个NP难问题都可以用一些近似算法来获得可接受的优化解。基于搜索的软件工程倡导应用运筹学领域的优化技术或（元）启发式计算方法来解决软件工程问题［16］，这些技术或方法按照构建的问题模型主要分为单目标优化方法和多目标优化方法。对于本文涉及的多目标优化领域，目前已有许多成功应用的实例，如优化需求搜索以求解NRP（NextReleaseProb－lem）［17］问题、优化测试数据选择和优先级排序［18］、优化软件项目管理［19］，以及用于优化软件产品线中特征选择问题的SATIBEA框架［20］。此外，基于搜索的技术在软件测试数据自动生成［24－25］、程序错误自动修复［26］、软件缺陷定位［27］、软件产品线配置［28－29，32］、云计算构件优化［30－31］等软件工程领域也取得了丰硕的成果。本文从软件升级问题的自然本质出发，此问题实质上是多目标优化问题。我们首次采用多目标演化算法来进行求解，同时优化多个升级目标，而不是以聚合的方式处理这些目标，最后得到一组帕累托最优解提供给用户或服务器管理员，以供他们在不同场景下进行选择。

3多目标优化软件升级框架

针对软件升级问题，本文提出一个多目标优化框架SATMOEA，该框架结合了可满足问题（SAT）的求解和多目标演化算法（MOEA）。框架的结构设计如图2所示。本框架求解一个软件升级问题实例的流程如下：（1）使用CUDF解析器（Parser），将输入的描述一个升级问题实例的CUDF文件解析为相应的描述可满足问题的CNF文件，即把CUDF实例转为CNF实例；同时，生成一个映射文件（Map），描述CNF中的数值编号与CUDF中的软件包之间一对一的映射关系。（2）对于步骤（1）中得到的CNF实例，使用MaxSAT快速采样技术高效地得到一定数量的解，即为升级问题的一部分可行解，然后选取这些解中的部分或全部作为演化算法的初始种群。QuickSampler采样工具实现了MAX－SAT快速采样技术，通过较少次数地调用MaxSAT求解器就能得到大量CNF实例的有效解。（3）建立有约束的多目标最小化问题。其中，约束条件为问题解必须为CNF的可行解。目标有5个，分别为：1）需要移除的软件包的数量；2）版本发生变化的软件包的数量；3）新增的软件包的数量；4）非最新版本的软件包的数量；5）未满足的推荐软件包的数量。（4）选择演化算法并配置演化相关参数（种群大小、演化代数、变异策略及概率、交叉策略及概率、选择策略），然后执行演化算法，得到帕累托最优解集（ParetoFront）。3．1软件升级问题的形式化构建。本文将软件升级问题构建为“可满足问题＋多目标优化问题”的形式，以便使用约束求解算法和多目标演化算法逐步求解软件升级问题。3．1．1构建可满足问题一个典型的CUDF实例文件的结构如图3所示，它能够描述软件仓库中所有软件包的信息（Universe）、当前系统中已安装的软件包的信息（Installed）、用户的请求（Request），以及软件包之间错综复杂的依赖冲突关系［11］。每个软件包的信息由多个字段描述，主要包括软件包名字、版本号、是否已安装、依赖项、冲突项等。关于依赖项和冲突项的说明如下：假设软件包A的依赖项中有软件包B，那么，当安装软件包A时，必须先安装软件包B；当卸载软件包B时，软件包A也将随之被卸载。假设软件包A的冲突项中有软件包B，那么，A和B不能同时存在于同一个系统中，即当安装软件包A时，须保证软件包B未被安装或已被卸载。求解软件升级问题的先决条件是：必须首先解决软件包之间的冲突和依赖问题，在此基础上才能进一步搜索最优的升级方案，即一个软件升级方案一定是满足系统中所有软件包的冲突和依赖的升级方案。基于CUDF的文件结构，本文设计了专门的语法解析器，用于解析CUDF文件，获取其中蕴含的软件包之间的依赖与冲突关系信息；然后将冲突和依赖关系形式化为布尔可满足性问题，也就是SAT问题。因此，CUDF解析器的作用是将CUDF文件转化为描述相应的SAT问题的CNF文件。SAT问题用于判断是否存在一组变量赋值满足给定的布尔表达式，它的定义如下：一个布尔表达式由变量、合取操作符（∧）、析取操作符（∨）、否操作符（）和括号组成，当存在一种对变量的赋值方案，使得布尔表达式的值为真时，称这个布尔表达式可满足。考虑图4所示的升级问题实例，假设从一个CUDF实例中获取到的软件包之间的关系如图4（a）所示，用户的请求是安装软件包a。图4中，实线单箭头表示“与”依赖关系，在图4表示的关系中，软件包b和c均已安装的情况下，软件包a才能被安装；虚线单箭头表示“或”依赖关系，即软件包d和e中安装任意一个之后，才能安装软件包b，软件包c，e，f同理；实线双箭头表示冲突关系，即软件包d和e不能同时安装在一个系统中，只能安装其中一个。可以用式（1）所示的布尔表达式描述软件包a，b，c之间的关系：a∧（a∨b）∧（a∨c）（1）这是一个合取范式，要使合取范式的取值为真，必须使每一个子句的取值为真。当某个变量值为true时，表示安装对应的软件包；否则表示不安装。式（1）中，第1个子句a表示用户请求安装软件包a，即a的取值必须为true；第2个子句a∨b表示当a的取值为true时，b必须为true，才能使子句的取值为真，也就是软件包a依赖软件包b的关系；第3个子句同理。式（2）描述了软件包b依赖软件包d或e的关系以及软件包d与e之间的冲突关系：（b∨d∨e）∧（d∨e）（2）在第1个子句中，当b为true时，须使d或e中至少一个为true，才能使子句为真，这就表示了软件包b与软件包d和e之间的“或”依赖关系。与之同理，可以用式（3）来描述软件包c，e，f之间的关系。在第2个子句中，当变量d和e之间任意一个取值为true时，另一个变量必须为false，才能使子句为真，即两个变量不能同时为true。（c∨e∨f）（3）使用合取符号将式（1）—式（3）连接起来可得到式（4），这样就完整地表达了图4实例中的依赖和冲突关系。a∧（a∨b）∧（a∨c）∧（b∨d∨e）∧（d∨e）∧（c∨e∨f）（4）为了数值化表示这些关系，CUDF解析器首先对所有涉及的软件包进行编号，编号从1开始，即生成软件包与数值编号的一一映射关系，如图4（b）所示的Map文件（Sample．map）。图4（c）所示的CNF文件（Sample．cnf）是由式（4）直接转化得到的。其中，第1行“pcnf66”是问题描述行，表示这是一个CNF文件，并且包含6个变量和6个子句。从第2行开始的每一行都对应式（4）中的一个子句，转化的规则是：使用Map文件定义的软件包的编号替换公式中的字母变量；使用空格替换析取符号（∨）；最后再加上空格和数字0作为结尾，数字0表示子句结束符。CNF文件所描述的SAT问题实例可以通过SAT求解器进行求解。当构建的SAT问题在有限时间内找不到可行的赋值方案时，求解器会将其标记为“UNSATIFIABLE”，即该CUDF实例所描述的用户请求很难被满足；当SAT求解器能够找到一个可行的赋值方案时，会将问题标记为“SAT－ISFIABLE”，并提供一个可行的赋值方案。赋值方案规定了每一个软件包是否被安装，当编号为正数时，表示安装对应的软件包，当编号前面加上了负号变成负数时，表示不安装对应的软件包。另外，赋值方案以“v”为起始标志，以“0”为结束标志。例如，对于图4所示的问题实例，SAT求解器的输出文件如图5所示。根据它提供的赋值方案并对照图4（b）的Map文件，即可得出：需要安装的软件包有a，b，c，d，f，不需要安装的软件包是e。传统的SAT求解器最多只能提供一个可行解，直到2018年Dutra等［21］提出了一个高效的SAT问题求解工具QuickSampler，它一次能够得到大量的可行解。这也是我们在本工作采用多目标演化算法搜索最优的软件升级方案的动机之一，使用QuickSampler工具一次性得到CNF实例的大量可行解恰好可以作为演化算法的初始种群。3．1．2构建多目标优化问题对于多目标优化问题的构建，本文选择MISC提出的5个优化准则作为最小化目标，分别是：1）需移除的软件包数量（Remove），对应目标函数为R（X）；2）版本发生改变的软件包数量（Change），对应目标函数为C（X）；3）新增的软件包数量（New），对应目标函数为N（X）；4）不是位于最新版本的软件包数量（Notdate），对应目标函数为Nd（X）；5）未满足推荐软件包的数量（Unsatisfied－recommend），对应目标函数为Us（X）。本文将约束条件设置为：必须满足CNF实例中的每一个子句，即赋值方案须保证真值为假的析取范式的数量为0。我们用长度为n（表示CNF实例涉及到的软件包数量）的二进制串来表示一个解，第i位上的取值即表示编号为i的软件包是否需要安装：0代表不需安装，1代表需要安装。例如，图5所示的一个可行解可以转化为二进制串“111101”。在演化算法中，优化函数的每一个解X表示一个个体，若干个体组成一个种群，我们称之为代；选择种群中的部分个体，让它们随机配对交叉或随机变异，产生新的个体，即构成新一代种群，这就是生物进化的思想。我们用Xpk表示演化第p代中的第k个解，它是一个特殊的n维向量，每一位只能取值1或0，表示某个软件包是否需要安装，我们称之为二进制向量。该解对应的上述5个目标函数值分别定义为：1）R（Xpk），表示解决方案Xpk导致的原来系统中需要移除的软件包的数量；2）C（Xpk），表示解决方案Xpk使原来系统发生版本变更的软件包的数量；3）N（Xpk），表示解决方案Xpk使原来系统新增软件包的数量；4）Nd（Xpk），表示解决方案Xpk中不是位于最新版本的软件包的数量；5）Us（Xpk），表示解决方案Xpk中软件包的推荐项未被满足的数量。这些函数值可以根据Xpk定义的软件包的安装方案与CUDF实例中描述的软件包的安装情况以及软件包的版本信息、推荐安装列表对比计算得出。另外，我们用Violate（Xpk）表示违背子句的数量，即Xpk定义的赋值方案使得CNF实例中结果为假的子句（析取范式）的数量。例如，对于图4所示的实例来说，当Xpk＝（1，0，1，0，1，0）时，它对应的CNF赋值方案是“1－23－45－6”，CNF中的违背子句有且仅有“－120”，原因是“－120”规定的是赋值方案中须包含－1或2，而Xpk对应的赋值方案中既不包含－1，也不包含2。此时，Violate（Xpk）＝1。综上所述，软件升级问题可以构建为如下形式的包含5个优化目标和1个约束条件的多目标最小化问题。minF（X）＝（R（X），C（X），N（X），Nd（X），Us（X））Ts．t．Violate（X）＝0，X是一个二进制向量3．2演化及中间解修正算法。当多目标优化问题模型构建完成后，我们使用多目标演化算法进行求解。演化算法的输入是初始种群，因此首先需要确定初始种群。初始种群可以完全随机化，即随机产生若干个体构成初始种群，这些个体的每一位都是随机的0或1，不能保证满足多目标优化问题的约束条件；借助QuickSam－pler工具，能够一次性得到CNF实例的若干个可行解，于是我们还可以将这些可行解全部作为初始种群中的个体。确定初始种群之后，正式进入演化过程。与生物进化论相似，选择、交叉、变异是演化算法中的3种常用操作。选择是指从种群中选出适应度较好的个体，用于进行交叉操作从而产生新一代个体，不同的选择算法计算适应度的方法有所不同。交叉是指将两个父代个体的基因局部进行交换，产生两个新的子代个体，在本问题中，我们用二进制向量表示问题的解就可以很方便地进行单点或多点交叉操作。个体的基因有一定的概率发生变异，我们采用位翻转的变异策略，当问题的解的某一位从0变为1或相反时，表示发生了变异。如果父代个体是可行解，当它们完成交叉和变异操作（交叉操作对于解的改变是非常显著的）之后，产生的新解极有可能变成不可行解，而不可行解违背了优化问题的约束条件。因此，将产生的不可行解调整为可行解，是十分必要的。我们在多目标演化算法的基础上，增加了中间解修正操作，以维持解的可行性。中间解修正算法如算法1所示。该算法的基本思想是：先找出不包含在被违背的约束条件中的软件包，固定它们的取值（0或1），具体来讲就是将它们的取值作为约束条件，添加到原来的CNF约束条件之后；然后由SAT求解器计算出其余的软件包的取值。下面考虑这样的一个CNF实例：（p1∨p5）∧（p2∨p3）∧（p2∨p5）当我们得到了它的一个不可行解M的赋值方案（0，0，1，1，0）时可知，该方案违背了CNF定义的两个约束条件（p1∨p5）和（p2∨p5），这两个约束条件涉及p1，p2，p53个软件包，我们将这3个软件包的取值从C中移除，将p3和p4的取值作为约束条件添加到原来的CNF实例中，则新的CNF变为：（p1∨p5）∧（p2∨p3）∧（p2∨p5）∧p3∧p4我们将新的CNF交给SAT求解器进行求解，计算出p1，p2，p5的取值，得到一个新的可行解N＝（1，1，1，1，0）。于是，一个中间解的修正操作就完成了。算法1中间解修正算法输入：一个演化过程的中间解M＝（x1，x2，…，xm），满足Violate（M）＞0；CNF文件Fold中的子句集合C＝（c1，c2，…，cn）输出：修正后的可行解N1．令集合B表示中间解中需要修正的索引集合；2．B←；3．fori←1tondo4．ifci＝falsethen5．将ci包含的索引添加到集合B中；6．endif7．endfor8．fori←1tomdo9．if集合B中不包含xithen10．将子句“xi0”添加到集合C中；11．endif12．endfor13．使用集合C中的子句构造出一个新的CNF文件Fnew；14．调用SAT求解模块对Fnew进行求解，得到可行解N；15．returnN．

4实验与分析

4．1实验设置。本文选择国际软件包安装与升级问题求解器竞赛［22］提供的CUDF标准实例数据集进行实验，其中CUDF实例模拟了真实系统环境中软件包的复杂度。实验按照软件包名称计数，这些实例包含的软件包全集的数量为27710～59094，平均数量为35275．5，与Debian实际的软件包仓库的规模十分接近。因此，本文获得的实验结果可以模拟现实环境中求解器的性能表现。在多目标演化模块中，本文在开源的多目标优化算法框架jMetal［23］提供的基于指示器的演化算法（Indicator－BasedEvolutionaryAlgorithm，IBEA）的基础上，调整了交叉算子和变异算子的实现方式以适配软件升级问题，并且增加了演化中间解的修正操作。演化算法中的一些重要参数设置如表1所列。4．2实验结果与分析。本文主要对以下4个研究问题进行实验分析。RQ1：提高初始种群中可行解的比例对演化算法结果的提升效果如何？RQ2：相比其他高维多目标演化算法，IBEA算法是否具有优势？RQ3：中间解修正会对演化结果造成怎样的影响？RQ4：SATMOEA的性能是否优于其他软件升级问题求解器？4．2．1探究约束求解对演化结果的提升效果对于初始种群，有两种构建策略：1）使用SAT求解器对CNF实例进行求解，得到一个可行解作为初始种群中的一个个体，其余个体随机生成（必定包含大量的不可行解），构成完整的初始种群；2）使用QuickSampler工具，它能快速得到指定数量的可行解，然后使用这些可行解建立初始种群，即初始种群全部为可行解。我们使用以上两种方法构建初始种群，分别执行基于指示器的演化算法：初始种群的大小设为30，迭代4次，统计演化算法终止时得到的帕累托解集中可行解的情况，如表2所列。实验结果表明，初始种群中可行解的数量越多，演化得到的帕累托解集中的可行解的数量就越多。因此，最好是将初始种群全部设为可行解（可以借助QuickSampler工具实现），以便在最后的帕累托解集中得到更多的可行解。4．2．2不同多目标演化算法的对比Sayyad等［32］在软件产品线工程中的特征选择问题的研究中发现，相比其他多目标演化算法（Multi－ObjectiveEvolu－tionaryAlgorithm，MOEA），基于指示器的演化算法（IBEA）表现更好。为了验证IBEA在软件升级问题上是否也具有同样的优势，本文在软件升级问题实例上对比了IBEA，NS－GAII，SPEA2，NSGAIII4种演化算法的表现。选取这几种算法，一方面是参考Sayyad等的研究工作中对比的算法，另一方面是因为它们都支持二进制类型的问题解。在本实验中，设置种群大小为30，迭代次数为10，4种演化算法的演化结果如表3所列。其中，第2－6列数据是不同的演化算法得到的帕累托集在各个目标函数上的值。HV和Spread是衡量多目标演化算法得到的帕累托集的两个重要的质量指标，可以由jMetal演化算法框架方便地计算出来，Size表示帕累托集包含解的数量。HV代表帕累托集构成的前沿面所覆盖的空间的体积（HyperVolume）［33］，这个体积越大，表示帕累托集越接近真实的帕累托前沿面，说明帕累托集的质量越高。Spread代表帕累托集扩展的程度［34］，多目标演化算法希望得到的帕累托集能够在真实的帕累托前沿面上分布得更广泛、更均匀。Spread的计算方式如式（5）所示：其中，N表示帕累托集中包含的点（解）的数量，di表示两个相邻解之间的欧氏距离，d－是di的平均值，df和dl分别是帕累托集中的边界解与极值点（Extremesolution）之间的欧氏距离。当帕累托集中只包含一个解时，Spread的值为1。一个好的帕累托集应该包含各个目标的极值点（df＝dl＝0），并且各个解分布均匀（di－d－趋近于0），此时Spread的值接近于0。因此，Spread的值越小说明帕累托集的分布情况越好。IBEA与其他3种多目标演化算法对比的实验结果如表3所列。该结果显示，IBEA得到的帕累托集中不仅包含更多的解，并且在HV和Spread两个质量指标上均表现出了一定的优势。因此，本文选择IBEA作为优化软件升级问题的多目标演化算法。4．2．3探究中间解修正操作对演化结果的影响为了探究增加中间解修正操作对演化算法结果的影响，本文设置初始种群的大小为50（全部由QuickSampler得到的可行解构成）、迭代次数为10，分别执行无修正操作的演化算法和有修正的操作的演化算法各一轮，然后计算帕累托解集中可行解所占的比例。实验结果如表4所列。其中，无修正操作的演化算法得到的帕累托解集中包含43个解，超过了有修正操作的演化算法得到的帕累托解集；然而，无修正操作的帕累托解集中可行解的数量是0，也就是说，无修正操作的演化算法最终得到的解全部为不可行解，这对软件升级问题的求解是没有意义的。有修正操作的演化算法得到的帕累托解集中全部为可行解，因此中间解修正操作对于演化结果的质量有显著的提升。4．2．4探究SATMOEA框架与其他求解器的性能对比情况为了探究SATMOEA框架求解软件升级问题的性能是否优于现有的其他求解器，本文对比了它们求解同一个CUDF实例得到的解在不同的升级目标上的表现，结果如表5所列。其中，R（X）表示需要移除原来系统中软件包的数量，C（X）表示原来系统中发生版本变更的软件包的数量，N（X）表示新增软件包的数量，Nd（X）表示不是最新版本的软件包的数量，Us（X）表示未满足已安装的软件包中的推荐的数量。前5行数据分别表示由现有的5种不同的求解器得到的升级方案计算出的各个目标函数值，第6－12行数据表示SATMOEA框架得到的帕累托解集中的每一个解对应的各个目标函数值。需要注意的是，对于一个CUDF实例，其他求解器只能得到单一的升级方案，而SATMOEA框架运行一次就能够计算出一组帕累托最优解集，其中包含一系列可行的升级方案，用户可以从中选择不同的升级方案，以应对不同的场景。另外，从表5中加粗的数据可以看出，本框架能够找到不被其他求解器占优的解，即一个或多个目标函数值优于其他求解器相应的目标函数值。因此，当用户希望新增的软件包数量尽可能少时，可以选择SATMOEA框架提供的第1，2，3，6，7个解，对应表5中的第6，7，8，11，12行；而当用户希望位于最新版本的软件包尽可能多时，可以选择SATMOEA框架提供的第5个解，对应表5中的第10行。为了更显著地表现SATMOEA框架的优势，我们将各个优化目标上能达到的最小值单独列出来，如表6所列。其中，第1行表示其他求解器的解综合起来所能达到的各个目标函数的最小值，第2行表示SATMOEA框架演化得到的帕累托解集中的解在各个目标上能够达到的最小值。数据表明，在R（X）目标函数上，SATMOEA框架所能达到的最小值与其他求解器相当，均为0；在C（X），N（X），Nd（X）3个目标函数上，SATMOEA表现出了明显的优势；然而，对于Us（X）目标函数，SATMOEA与其他求解器相比，表现更差。因此，SATMOEA框架不仅在解的数量上明显优于其他求解器，而且在解的质量上也有一定的优势。

为了避免聚合的方式对不同升级目标之间的关系处理不当而引起的风险，本文从多目标优化的角度解决软件升级问题，成功构建了一个结合约束求解和多目标演化优化的软件升级问题求解框架SATMOEA，并在演化算法的基础上增加了中间解修正算法，使帕累托解集中可行解的比例达到了100％；与其他求解器只能提供单一的升级方案相比，该框架能够提供一系列不同的软件升级方案，以应对不同的软件升级场景，为软件升级问题的求解研究提供了一种新的思路。同时，由于演化算法需要对种群中每个个体计算适应度等，一定程度上增加了计算量，这是演化算法先天的缺陷，未来将考虑采用并行化的演化算法对SATMOEA框架进行优化，以提高求解的效率。

作者:赵松辉 任志磊 江贺 单位:大连理工大学软件学院