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

作     者：赵松辉 任志磊 江贺 ZHAO Song-hui;REN Zhi-lei;JIANG He

作者机构：大连理工大学软件学院辽宁大连116600 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2020年第47卷第6期

页      面：16-23页

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：软件升级问题 多目标优化 SAT求解 基于搜索的软件工程 软件仓库 

摘      要：近年来,开源软件包管理成为软件产品重用的一种普遍方式,尤其是在Linux发行版操作系统领域。其中,软件升级问题是软件包管理工具必须要解决的关键挑战之一。软件升级问题旨在按照某种优化准则找出能够满足用户升级请求的最合适的升级方案。优化准则由几个不同方向的优化目标组成,因此软件升级问题本质上是一个多目标优化问题。现有的解决软件升级问题的方法均是将多个优化目标聚合成为单个目标的形式再进行处理。这些方法都可能没有恰当地考虑不同的优化目标之间的关系,因此会存在潜在的风险。针对这种风险,文中提出了一个多目标演化框架——SATMOEA(Combining Constraints Solving and Multi-objective Evolutionary Algorithms),将软件升级问题构建为可满足问题+多目标优化问题的形式,并集成了约束求解和多目标优化算法,来对软件升级问题进行求解。基于MISC竞赛提供的升级问题标准实例集进行实验,结果表明对于有着大量约束条件的复杂问题实例,多目标演化框架在一次运行中即可有效地计算出各个优化目标均达到帕累托最优的解决方案,相比现有的升级问题求解器提供的升级方案更加多样,并且在一些优化目标上更具优势,可以满足用户在不同场景下的需求。