Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (6): 16-23.doi: 10.11896/jsjkx.200400027

• Intelligent Software Engineering • Previous Articles     Next Articles

Multi-objective Optimization Methods for Software Upgradeability Problem

ZHAO Song-hui, REN Zhi-lei, JIANG He   

  1. School of Software,Dalian University of Technology,Dalian,Liaoning 116600,China
  • Received:2020-03-07 Online:2020-06-15 Published:2020-06-10
  • About author:ZHAO Song-hui,born in 1995,postgra-duate,is a student member of China Computer Federation.His main research interests include multi-objective optimization and search-based software engineering.
    REN Zhi-lei,born in 1984,Ph.D,asso-ciate professor,is a member of China Computer Federation.His main research interests include evolutionary computation,automatic algorithm configuration,data mining,and data analysis in software engineering.

PDF (PC)

1119

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

CLC Number: 

  • TP311
[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.
[1] SUN Gang, WU Jiang-jiang, CHEN Hao, LI Jun, XU Shi-yuan. Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance [J]. Computer Science, 2022, 49(6): 297-304.
[2] LI Hao-dong, HU Jie, FAN Qin-qin. Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application [J]. Computer Science, 2022, 49(5): 212-220.
[3] PENG Dong-yang, WANG Rui, HU Gu-yu, ZU Jia-chen, WANG Tian-feng. Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos [J]. Computer Science, 2022, 49(4): 312-320.
[4] GUAN Zheng, DENG Yang-lin, NIE Ren-can. Non-negative Matrix Factorization Based on Spectral Reconstruction Constraint for Hyperspectral and Panchromatic Image Fusion [J]. Computer Science, 2021, 48(9): 153-159.
[5] WANG Ke, QU Hua, ZHAO Ji-hong. Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment [J]. Computer Science, 2021, 48(12): 324-330.
[6] CUI Guo-nan, WANG Li-song, KANG Jie-xiang, GAO Zhong-jie, WANG Hui, YIN Wei. Fuzzy Clustering Validity Index Combined with Multi-objective Optimization Algorithm and Its Application [J]. Computer Science, 2021, 48(10): 197-203.
[7] ZHU Han-qing, MA Wu-bin, ZHOU Hao-hao, WU Ya-hui, HUANG Hong-bin. Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms [J]. Computer Science, 2021, 48(10): 343-350.
[8] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[9] ZHENG You-lian, LEI De-ming, ZHENG Qiao-xian. Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling [J]. Computer Science, 2020, 47(7): 186-191.
[10] SUN Min, CHEN Zhong-xiong, YE Qiao-nan. Workflow Scheduling Strategy Based on HEDSM Under Cloud Environment [J]. Computer Science, 2020, 47(6): 252-259.
[11] XIA Chun-yan, WANG Xing-ya, ZHANG Yan. Test Case Prioritization Based on Multi-objective Optimization [J]. Computer Science, 2020, 47(6): 38-43.
[12] WANG Xu-liang, NIE Tie-zheng, TANG Xin-ran, HUANG Ju, LI Di, YAN Ming-sen, LIU Chang. Study on Dynamic Adaptive Caching Strategy for Streaming Data Processing [J]. Computer Science, 2020, 47(11): 122-127.
[13] DONG Ming-gang,LIU Bao,JING Chao. Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation [J]. Computer Science, 2019, 46(7): 224-232.
[14] WANG Chen-xin, YANG Jia-hai, ZHUANG Yi, LUO Nian-long. Node Resource Scheduling for Future Network Experimentation Facility [J]. Computer Science, 2019, 46(12): 95-100.
[15] ZHAO Yun-tao, CHEN Jing-cheng, LI Wei-gang. Multi-objective Grey Wolf Optimization Hybrid Adaptive Differential Evolution Mechanism [J]. Computer Science, 2019, 46(11A): 83-88.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.