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

Multi-objective Optimization Methods for Software Upgradeability Problem

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

Open-source Package management as a means of reuse of software artifacts has become extremely popular,most notably in Linux distributions.Software upgradeabilty problem is a significant challenge which package management system must resolve.This problem aims to find the most suitable upgrade scheme that satisfies upgrade requests from users.An upgrade scheme comprises of a sequence of operations,including installing,removing,and/or upgrading packages.In the existing approaches for solving this problem,multiple upgrade requests are handled in aggregate ways.Hence,a potential risk of such approaches is that,the relationships between different upgrade objectives may not be considered properly.This paper introduces a novel approach SATMOEA,which forms software upgradeability problem as a SAT plus multi-objective optimization problem and addresses this problem combining constraint solving and multi-objective search-based optimization algorithms.We evaluate it on real instances provided by MISC(Mancoosi International Solver Competitions)and obtain promising results where we can find some Pareto optimal solutions for a complex instance with myriad constraints in a single run.In comparison with other solvers,it can provide more solutions with better diversity property to satisfy requirements in different scenarios.