Now showing 1 - 10 of 12
  • Publication
    A Hybrid Algorithm for Multi-objective Test Case Selection
    Testing is crucial to ensure the quality of software systems – but testing is an expensive process, so test managers try to minimise the set of tests to run to save computing resources and speed up the testing process and analysis. One problem is that there are different perspectives on what is a good test and it is usually not possible to compare these dimensions. This is a perfect example of a multi-objective optimisation problem, which is hard — especially given the scale of the search space here. In this paper, we propose a novel hybrid algorithm to address this problem. Our method is composed of three steps: a greedy algorithm to find quickly some good solutions, a genetic algorithm to increase the search space covered and a local search algorithm to refine the solutions. We demonstrate through a large scale empirical evaluation that our method is more reliable (better whatever the time budget) and more robust (better whatever the number of dimensions considered) – in the scenario with 4 objectives and a default execution time, we are 178% better in hypervolume on average than the state-of-the-art algorithms.
      208
  • Publication
    MILPIBEA: Algorithm for Multi-objective Features Selection in (Evolving) Software Product Lines
    (Springer International Publishing, 2020-04-09) ; ; ;
    Software Product Lines Engineering (SPLE) proposes techniques to model, create and improve groups of related software systems in a systematic way, with different alternatives formally expressed, e.g., as Feature Models. Selecting the 'best' software system(s) turns into a problem of improving the quality of selected subsets of software features (components) from feature models, or as it is widely known, Feature Configuration. When there are different independent dimensions to assess how good a software product is, the problem becomes even more challenging- it is then a multi-objective optimisation problem. Another big issue for software systems is evolution where software components change. This is common in the industry but, as far as we know, there is no algorithm designed to the particular case of multi-objective optimisation of evolving software product lines. In this paper we present MILPIBEA, a novel hybrid algorithm which combines the scalability of a genetic algorithm (IBEA) with the accuracy of a mixed-integer linear programming solver (IBM ILOG CPLEX). We also study the behaviour of our solution (MILPIBEA) in contrast with SATIBEA, a state-of-the-art algorithm in static software product lines. We demonstrate that MILPIBEA outperforms SATIBEA on average, especially for the most challenging problem instances, and that MILPIBEA is the one that continues to improve the quality of the solutions when SATIBEA stagnates (in the evolving context).
      369Scopus© Citations 4
  • Publication
    A Hybrid Algorithm for Multi-objective Test Case Selection
    Testing is crucial to ensure the quality of software systems-but testing is an expensive process, so test managers try to minimise the set of tests to run to save computing resources and speed up the testing process and analysis. One problem is that there are different perspectives on what is a good test and it is usually not possible to compare these dimensions. This is a perfect example of a multi-objective optimisation problem, which is hard-especially given the scale of the search space here. In this paper, we propose a novel hybrid algorithm to address this problem. Our method is composed of three steps: a greedy algorithm to find quickly some good solutions, a genetic algorithm to increase the search space covered and a local search algorithm to refine the solutions. We demonstrate through a large scale empirical evaluation that our method is more reliable (better whatever the time budget) and more robust (better whatever the number of dimensions considered)-in the scenario with 4 objectives and a default execution time, we are 178% better in hypervolume on average than the state-of-the-art algorithms.
      489Scopus© Citations 17
  • Publication
    Exact and Hybrid Solutions for the Multi-objective VM Reassignment Problem
    Machine Reassignment is a challenging problem for constraint programming (CP) and mixed integer linear programming (MILP) approaches, especially given the size of data centres. Hybrid solutions mixing CP and heuristic algorithms, such as, large neighbourhood search (CBLNS), also struggle to address the problem given its size and number of constraints. The multi-objective version of the Machine Reassignment Problem is even more challenging and it seems unlikely for CP, MILP or hybrid solutions to obtain good results in this context. As a result, the first approaches to address this problem have been based on other optimisation methods, including metaheuristics. In this paper we study three things: (i) under which conditions a mixed integer optimisation solver, such as IBM ILOG CPLEX, can be used for the Multi-objective Machine Reassignment Problem; (ii) how much of the search space can a well-known hybrid method such as CBLNS explore; and (iii) can we find a better hybrid approach combining MILP or CBLNS and another recent metaheuristic proposed for the problem (GeNePi). We show that MILP can handle only small or medium scale data centres, and with some relaxations, such as, an optimality tolerance gap and a limited number of directions explored in the search space. CBLNS on the other hand struggles with the problem in general but achieves reasonable performance for large instances of the problem. However, we show that our hybridisation improves both the quality of the set of solutions (CPLEX+GeNePi and CBLNS+GeNePi improve the solutions by +17.8% against CPLEX alone and +615% against CBLNS alone) and number of solutions (8.9 times more solutions than CPLEX alone and 56.76 times more solutions than CBLNS alone), while the processing time of CPLEX+GeNePi and CBLNS+GeNePi increases only by 6% and 16.4% respectively. Overall, the study shows that CPLEX+GeNePi is the best algorithm for small instances (CBLNS+GeNePi only gets 45.2% of CPLEX+GeNePi’s hypervolume) while CBLNS+GeNePi is better than the others on large instances (that CPLEX+GeNePi cannot address).
      602Scopus© Citations 13
  • Publication
    ROThAr: Real-time On-line Traffic Assignment with Load Estimation
    (Institute of Electrical and Electronic Engineers (IEEE), 2013-11-01) ; ;
    More and more drivers use on-board units to help them navigate in the increasing urbanised environment they live and work in. These system (e.g., routing applications on smart phones) are now very often on-line, and use information from the traffic situation (e.g., accidents, congestion) to get the best route. We can now envisage a world where all trips are assigned and updated by such an on-line system, making the best routing decisions based on traffic conditions. The problem is that current systems consider only 'local' elements (e.g., driver preference and current traffic condition) and do not make routing decisions from a global perspective. This can lead to a lot of similar routing assignments that could lead to further traffic congestion. The objective of the next generation on-line navigation systems is then to come up with a 'smart', real-time route assignment, which balances the load between the different road segments and offers the best quality to the drivers. However, every routing decision made has an impact on the traffic conditions (one more vehicle on the road segments selected) and computing the load induced by the trips is a computationally heavy problem. This paper addresses this question of real-time on-line traffic assignment, and shows that under certain conditions it is possible to have (i) an accurate estimation of the load and travel time on every road segment and (ii) an optimised traffic assignment that adapts to divergence and evolutions (e.g., accidents) of the system.
      434Scopus© Citations 9
  • Publication
    Is seeding a good strategy in multi-objective feature selection when feature models evolve?
    Context: When software architects or engineers are given a list of all the features and their interactions (i.e., a Feature Model or FM) together with stakeholders 'preferences' their task is to find a set of potential products to suggest the decision makers. Software Product Lines Engineering (SPLE) consists in optimising those large and highly constrained search spaces according to multiple objectives reflecting the preference of the different stakeholders. SPLE is known to be extremely skill- and labour-intensive and it has been a popular topic of research in the past years.Objective: This paper presents the first thorough description and evaluation of the related problem of evolving software product lines. While change and evolution of software systems is the common case in the industry, to the best of our knowledge this element has been overlooked in the literature. In particular, we evaluate whether seeding previous solutions to genetic algorithms (that work well on the general problem) would help them to find better/faster solutions.Method: We describe in this paper a benchmark of large scale evolving FMs, consisting of 5 popular FMs and their evolutions – synthetically generated following an experimental study of FM evolution. We then study the performance of a state-of-the-art algorithm for multi-objective FM selection (SATIBEA) when seeded with former solutions.Results: Our experiments show that we can improve both the execution time and the quality of SATIBEA by feeding it with previous configurations. In particular, SATIBEA with seeds proves to converge an order of magnitude faster than SATIBEA alone.Conclusion: We show in this paper that evolution of FMs is not a trivial task and that seeding previous solutions can be used as a first step in the optimisation - unless the difference between former and current FMs is high, where seeding has a limited impact.
      450Scopus© Citations 12
  • Publication
    A comparative study of multi-objective machine reassignment algorithms for data centres
    At a high level, data centres are large IT facilities hosting physical machines (servers) that often run a large number of virtual machines (VMs)— but at a lower level, data centres are an intricate collection of interconnected and virtualised computers, connected services, complex service-level agreements. While data centre managers know that reassigning VMs to the servers that would best serve them and also minimise some cost for the company can potentially save a lot of money—the search space is large and constrained, and the decision complicated as they involve different dimensions. This paper consists of a comparative study of heuristics and exact algorithms for the Multi-objective Machine Reassignment problem. Given the common intuition that the problem is too complicated for exact resolutions, all previous works have focused on various (meta)heuristics such as First-Fit, GRASP, NSGA-II or PLS. In this paper, we show that the state-of-art solution to the single objective formulation of the problem (CBLNS) and the classical multi-objective solutions fail to bridge the gap between the number, quality and variety of solutions. Hybrid metaheuristics, on the other hand, have proven to be more effective and efficient to address the problem – but as there has never been any study of an exact resolution, it was difficult to qualify their results. In this paper, we present the most relevant techniques used to address the problem, and we compare them to an exact resolution ( -Constraints). We show that the problem is indeed large and constrained (we ran our algorithm for 30 days on a powerful node of a supercomputer and did not get the final solution for most instances of our problem) but that a metaheuristic (GeNePi) obtains acceptable results: more (+188%) solutions than the exact resolution and a little more than half (52%) the hypervolume (measure of quality of the solution set).
      498Scopus© Citations 7
  • Publication
    Preliminary Study of Multi-objective Features Selection for Evolving Software Product Lines
    When dealing with software-intensive systems, it is often beneficial to consider families of similar systems together. A common task is then to identify the particular product that best fulfils a given set of desired product properties. Software Product Lines Engineering (SPLE) provides techniques to design, implement and evolve families of similar systems in a systematic fashion, with variability choices explicitly represented, e.g., as Feature Models. The problem of picking the 'best' product then becomes a question of optimising the Feature Configuration. When considering multiple properties at the same time, we have to deal with multi-objective optimisation, which is even more challenging. While change and evolution of software systems is the common case, to the best of our knowledge there has been no evaluation of the problem of multi-objective optimisation of evolving Software Product Lines. In this paper we present a benchmark of large scale evolving Feature Models and we study the behaviour of the state-of-the-art algorithm (SATIBEA). In particular, we show that we can improve both the execution time and the quality of SATIBEA by feeding it with the previous configurations: our solution converges nearly 10 times faster and gets an 113% improvement after one generation of genetic algorithm.
      471Scopus© Citations 2
  • Publication
    MILP for the Multi-objective VM Reassignment Problem
    Machine Reassignment is a challenging problem for constraint programming (CP) and mixed integer linear pro- gramming (MILP) approaches, especially given the size of data centres. The multi-objective version of the Machine Reassignment Problem is even more challenging and it seems unlikely for CP or MILP to obtain good results in this context. As a result, the first approaches to address this problem have been based on other optimisation methods, including metaheuristics. In this paper we study under which conditions a mixed integer optimisation solver, such as IBM ILOG CPLEX, can be used for the Multi-objective Machine Reassignment Problem. We show that it is useful only for small or medium scale data centres and with some relaxations, such as an optimality tolerance gap and a limited number of directions explored in the search space. Building on this study, we also investigate a hybrid approach, feeding a metaheuristic with the results of CPLEX, and we show that the gains are important in terms of quality of the set of Pareto solutions (+126.9% against the metaheuristic alone and +17.8% against CPLEX alone) and number of solutions (8.9 times more than CPLEX), while the processing time increases only by 6% in comparison to CPLEX for execution times larger than 100 seconds.
      646Scopus© Citations 13
  • Publication
    VM reassignment in hybrid clouds for large decentralised companies: A multi-objective challenge
    Optimising the data centres of large IT organisations is complex as (i) they are composed of various hosting departments with their own preferences and (ii) reassignment solutions can be evaluated from various independent dimensions. But in reality, the problem is even more challenging as companies can now choose from a pool of cloud services to host some of their workloads. This hybrid search space seems intractable, as each workload placement decision (seen as running in a virtual machine on a server) is required to answer many questions: can we host it internally? In which hosting department? Are the capital allocators of this hosting department ok with this placement? How much does it save us and is it safe? Is there a better option in the Cloud? Etc. In this paper, we define the multi-objective VM reassignment problem for hybrid and decentralised data centres. We also propose H2¿D2, a solution that uses a multi-layer architecture and a metaheuristic algorithm to suggest reassignment solutions that are evaluated by the various hosting departments (according to their preferences). We compare H2¿D2 against state-of-the-art multi-objective algorithms and find that H2¿D2 outperforms them both in terms of quantity (approx 30% more than the second-best algorithm on average) and quality of solutions (19% better than the second-best on average).
      561Scopus© Citations 31