Multi-Objective Evolutionary Methods Of Software Upgradeability Problem

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 thesis proposes a novel framework,SATMOEA,to address software upgradeability problems combining constraint solving and multi-objective search-based optimization.The framework integrates software upgrade problem instance parsing,constraint solving and multiobjective evolutionary algorithms to solve software upgradeability problems from the perspective of multi-objective optimization.This thesis designed and developed a CUDF parser to implement the module of software upgrade problem instance parsing.The parser can encode a CUDF document into a CNF document describing the constraint satisfaction problem.Constraint solving is a process of using a quick sampling technology to solve the CNF document obtained after instance parsing,and it can provide a large number of feasible solutions.The framework SATMOEA takes these feasible solutions as the initial population and performs evolution process to search for Pareto sets;This thesis proposes a correction algorithm to correct intermediate solutions losing feasibility due to evolution operators and integrate it into SATMOEA framework.This correction algorithm greatly increasing the proportion of feasible solutions in the evolution results.Furthermore,in order to improve the quality of evolved Pareto solution set,this thesis employs a novel operation strategy that adjust the ratio of fixed packages installed in old system.This thesis evaluated the framework SATMOEA on real instances provided by MISC(Mancoosi International Solver Competitions)and obtained promising results where it 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.