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

doi:10.11896/jsjkx.200400027

摘要/Abstract

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

关键词: SAT求解, 多目标优化, 基于搜索的软件工程, 软件仓库, 软件升级问题

Abstract: 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.

Key words: Multi-objective optimization, SAT solving, Search-based software engineering, Software repository, Software upgradeability problem

中图分类号:

TP311

赵松辉, 任志磊, 江贺. 软件升级问题的多目标优化方法[J]. 计算机科学, 2020, 47(6): 16-23. https://doi.org/10.11896/jsjkx.200400027

ZHAO Song-hui, REN Zhi-lei, JIANG He. Multi-objective Optimization Methods for Software Upgradeability Problem[J]. Computer Science, 2020, 47(6): 16-23. https://doi.org/10.11896/jsjkx.200400027

参考文献

[1]Debian -The Universal Operating System [EB/OL].(2020-03-26)[2020-03-26].https://www.d ebian.org.
[2]IGNATIEV A,JANOTA M,MARQUES-SILVA J.Towards efficient optimization in package management systems[C]//Proceedings of the 36th International Conference on Software Engineering.2014:745-755.
[3]REN Z,JIANG H,XUAN J,et al.Analyzing Inter-objective Relationships:A Case Study of Software Upgradability[C]//International Conference on Parallel Problem Solving from Nature.Cham:Springer,2016:442-452.
[4]TUCKER C,SHUFFELTON D,JHALA R,et al.Opium:Optimal package install/uninstall manager[C]//29th International Conference on Software Engineering (ICSE’07).IEEE,2007:178-188.
[5]ROBERTO D C.How to manage your software upgrades:tales from the Mancoosi frontline[EB/OL].(2010-04-19)[2020-03-26].http://www.dicosmo.org/MyOpinions/index.php?post/2010/04/19/101-how-to-manage-your-software-upgrades-tales-from-the-mancoosi-frontline.
[6]MANCINELLI F,BOENDER J,DI COSMO R,et al.Managing the complexity of large free and open source package-based software distributions[C]//Twenty-First IEEE/ACM International Conference on Automated Software Engineering (ASE’06).IEEE,2006:199-208.
[7]ARGELICH J,MANYA F.Partial Max-SAT solvers with clause learning[C]//International Conference on Theory and Applications of Satisfiability Testing.Berlin:Springer,2007:28-40.
[8]ARGELICH J,LYNCE I,MARQUES-SILVA J.On solving Boolean multilevel optimization problem-s[C]//Twenty-First International Joint Conference on Artificial Intelligence.2009.
[9]LE BERRE D,RAPICAULT P.Dependency mana-gement for the eclipse ecosystem:eclipse p2,metadata and resolution[C]//Proceedings of the 1st international workshop on Open component eco-systems.2009:21-30.
[10]TREZENTOS P,LYNCE I,OLIVEIRA A L.Apt-pbo:solving the software dependency problem using pseudo-boolean optimization[C]//Proceedings of the IEEE/ACM international conference on Automated software engineering.2010:427-436.
[11]RALF T,STEFANO Z.Common Upgradeability Description Format (CUDF) 2.0[EB/OL].(2009-11-24)[2020-03-26].http://www.mancoosi.org/reports /tr3.pdf.
[12]MICHEL C,RUEHER M.Handling software upgradeability problems with MILP solvers[J].Electronic Proceedings in Theoretical Computer Science,2010,29(1):1-10.
[13]GEBSER M,KAMINSKI R,SCHAUB T.aspcud:A linux package configuration tool based on answer set programming[J].Electronic Proceedings in Theoretical Computer Science,2011,65(2):12-25.
[14]ARGELICH J,BERRE D L,LYNCE I,et al.Solving Linux upgradeability problems using boolean optimization[J].Electronic Proceedings in Theoretical Computer Science,2010,29(2):11-22.
[15]JANOTA M,LYNCE I,MANQUINHO V,et al.PackUp:Tools for package upgradability solving[J].Journal on Satisfiability,Boolean Modeling and Computation,2012,8(1/2):89-94.
[16]HARMAN M.The current state and future of search based software engineering[C]//Future of Software Engineering (FOSE’07).IEEE,2007:342-357.
[17]DURILLO J J,ZHANG Y Y,ALBA E,et al.A study of the multi-objective next release problem[C]//2009 1st InternationalSymposium on Search Based Software Engineering.IEEE,2009:49-58.
[18]WALCOTT K R,SOFFA M L,KAPFHAMMER G M,et al.Timeaware test suite prioritization[C]//Proceedings of the 2006 international symposium on Software testing and analysis.2006:1-12.
[19]SARRO F,PETROZZIELLO A,HARMAN M.Multi-objective software effort estimation[C]//2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE).IEEE,2016:619-630.
[20]HENARD C,PAPADAKIS M,HARMAN M,et al.Combining multi-objective search and constraint solving for configuring large software product lines[C]//2015 IEEE/ACM 37th IEEE International Conference on Software Engineering.IEEE,2015,1:517-528.
[21]DUTRA R,LAEUFER K,BACHRACH J,et al.Efficient sampling of SAT solutions for testing[C]//2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE).IEEE,2018:549-559.
[22]MANCOOSI project.International Solver Competition 2012 [EB/OL].[2020-03-26].http://ww w.mancoosi.org/misc-2012/index.html.
[23]DURILLO J J,NEBRO A J.jMetal:A Java framework for multi-objective optimization[J].Advances in Engineering Software,2011,42(10):760-771.
[24]JIANG S J,WANG L S,XUE M,et al.Test Case Generation Based on Combination of Schema Using Particle Swarm Optimization[J].Journal of Software,2016,27(4):785-801.
[25]BAO X A,BAO C,JIN Y T,et al.Com-binatorial Test Case Generation Method Based on Simplified Particle Swarm Optimization with Dynamic Adjustment[J].Computer Science,2018,45(11):199-200.
[26]XUAN J F,REN Z L,WANG Z Y,et al.Progress on approaches to automatic program repair[J].Journal of Software,2016,27(4):771-784.
[27]ZHOU M Q,JIANG G H.New Spectrum-based Fault Localization Method Combining Hitting Set and Genetic Algorithm[J].Computer Science,2018,45(9):207-212.
[28]LU H,ZHANG L,YUE T.Differential IBEA for non-conformity resolution in interactive CPS production line configuration[J].Journal of Software,2016,27(4):901-915.
[29]XIANG Y,ZHOU Y R,CAI S W.Integrating Preference in Many-objective Optimal Software Product Selection Algorithm[J].Journal of Software,2020,31(2):282-301.
[30]MENG F C,CHU D H,LI K Q,et al.Solving SaaS components optimization placement problem with hybrid genetic and simulated annealing algorithm[J].Journal of Software,2016,27(4):916-932.
[31]ZHENG Y J,ZHANG B,XUE J Y.Selection of key software components for formal development using water wave optimization[J].Journal of Software,2016,27(4):933-942.
[32]SAYYAD A S,MENZIES T,AMMAR H.On the value of user preferences in search-based software engineering:a case study in software product lines[C]//2013 35th International Conference on Software Engineering (ICSE).IEEE,2013:492-501.
[33]ZITZLER E,THIELE L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.
[34]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multi objective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

相关文章 15

[1]	孙刚, 伍江江, 陈浩, 李军, 徐仕远. 一种基于切比雪夫距离的隐式偏好多目标进化算法 Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance 计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[2]	李浩东, 胡洁, 范勤勤. 基于并行分区搜索的多模态多目标优化及其应用 Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application 计算机科学, 2022, 49(5): 212-220. https://doi.org/10.11896/jsjkx.210300019
[3]	彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027
[4]	王珂, 曲桦, 赵季红. 多域SFC部署中基于强化学习的多目标优化方法 Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment 计算机科学, 2021, 48(12): 324-330. https://doi.org/10.11896/jsjkx.201100159
[5]	崔国楠, 王立松, 康介祥, 高忠杰, 王辉, 尹伟. 结合多目标优化算法的模糊聚类有效性指标及应用 Fuzzy Clustering Validity Index Combined with Multi-objective Optimization Algorithm and Its Application 计算机科学, 2021, 48(10): 197-203. https://doi.org/10.11896/jsjkx.200900061
[6]	朱汉卿, 马武彬, 周浩浩, 吴亚辉, 黄宏斌. 基于改进多目标进化算法的微服务用户请求分配策略 Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms 计算机科学, 2021, 48(10): 343-350. https://doi.org/10.11896/jsjkx.201100009
[7]	张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法 Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery 计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082
[8]	郑友莲, 雷德明, 郑巧仙. 求解高维多目标调度的新型人工蜂群算法 Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling 计算机科学, 2020, 47(7): 186-191. https://doi.org/10.11896/jsjkx.190600089
[9]	夏春艳, 王兴亚, 张岩. 基于多目标优化的测试用例优先级排序方法 Test Case Prioritization Based on Multi-objective Optimization 计算机科学, 2020, 47(6): 38-43. https://doi.org/10.11896/jsjkx.191100113
[10]	孙敏, 陈中雄, 叶侨楠. 云环境下基于HEDSM的工作流调度策略 Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment 计算机科学, 2020, 47(6): 252-259. https://doi.org/10.11896/jsjkx.190400047
[11]	王绪亮, 聂铁铮, 唐欣然, 黄菊, 李迪, 闫铭森, 刘畅. 流式数据处理的动态自适应缓存策略研究 Study on Dynamic Adaptive Caching Strategy for Streaming Data Processing 计算机科学, 2020, 47(11): 122-127. https://doi.org/10.11896/jsjkx.190800093
[12]	董明刚,刘宝,敬超. 模糊自适应排序变异多目标差分进化算法 Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation 计算机科学, 2019, 46(7): 224-232. https://doi.org/10.11896/j.issn.1002-137X.2019.07.034
[13]	张璐婕, 刘畅, 张龙, 郭阳. 一种基于SAT求解器的组合电路重汇聚现象分析方法 Reconvergence Phenomena Analysis Method in Combinational Circuits Based on SAT Solver 计算机科学, 2019, 46(4): 309-314. https://doi.org/10.11896/j.issn.1002-137X.2019.04.048
[14]	汪晨欣, 杨家海, 庄奕, 罗念龙. 未来网络试验设施的节点资源调度算法 Node Resource Scheduling for Future Network Experimentation Facility 计算机科学, 2019, 46(12): 95-100. https://doi.org/10.11896/jsjkx.190400106
[15]	赵云涛, 谌竟成, 李维刚. 融合自适应差分进化机制的多目标灰狼优化算法 Multi-objective Grey Wolf Optimization Hybrid Adaptive Differential Evolution Mechanism 计算机科学, 2019, 46(11A): 83-88.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed