Approximate backbone based multilevel algorithm for next release problem

The next release problem (NRP) aims to effectively select software requirements in order to acquire maximum customer profits. As an NP-hard problem in software requirement engineering, NRP lacks efficient approximate algorithms for large scale instances. The backbone is a new tool for tackling large scale NP-hard problems in recent years. In this paper, we employ the backbone to design high performance approximate algorithms for large scale NRP instances. Firstly we show that it is NP-hard to obtain the backbone of NRP. Then, we illustrate by fitness landscape analysis that the backbone can be well approximated by the shared common parts of local optimal solutions. Therefore, we propose an approximate backbone based multilevel algorithm (ABMA) to solve large scale NRP instances. This algorithm iteratively explores the search spaces by multilevel reductions and refinements. Experimental results demonstrate that ABMA outperforms existing algorithms on large instances in terms of solution quality and running time.

• Publication year

  2010

• Venue

  Annual Conference on Genetic and Evolutionary Computation

• Publication date

  2010-07-07

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/1830483.1830730arXiv 1704.04773
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Search-Based Software Engineering

  2015cited by this paper
• Software project planning for robustness and completion time in the presence of uncertainty using multi objective search based software engineering

  2009cited by this paper
• Search based data sensitivity analysis applied to requirement engineering

  2009cited by this paper
• “Fairness Analysis” in Requirements Assignments

  2008cited by this paper
• Backbone analysis and algorithm design for the quadratic assignment problem

  2008cited by this paper
• The Current State and Future of Search Based Software Engineering

  2007cited by this paper
• Bi-objective release planning for evolving software systems

  2007cited by this paper
• The multi-objective next release problem

  2007cited by this paper
• Eclipse

  2006cited by this paper
• Search Based Approaches to Component Selection and Prioritization for the Next Release Problem

  2006cited by this paper
• The art and science of software release planning

  2005cited by this paper
• The Backbone of the Travelling Salesperson

  2005influential reference
• A multiple hill climbing approach to software module clustering

  2003cited by this paper
• Backbone Guided Local Search for Maximum Satisfiability

  2003influential reference
• A Multilevel Approach to the Travelling Salesman Problem

  2002cited by this paper
• The next release problem

  2001influential reference
• A backbone-search heuristic for efficient solving of hard 3-SAT formulae

  2001cited by this paper
• How to Solve It: Modern Heuristics

  2000cited by this paper
• Fitness landscape analysis and memetic algorithms for the quadratic assignment problem

  2000cited by this paper
• Convergence of an annealing algorithm

  1986cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper

• Fuzzy Branch and Bound Optimization Technique for Solving Multi-objective Next-Release Problem

  2024cites this paper
• Software Requirements Selection with Incomplete Linguistic Preference Relations

  2021cites this paper
• Genetic configuration sampling: learning a sampling strategy for fault detection of configurable systems

  2018cites this paper
• An Empirical Study of Meta- and Hyper-Heuristic Search for Multi-Objective Release Planning

  2018cites this paper
• Supporting Many-Objective Software Requirements Decision: An Exploratory Study on the Next Release Problem

  2018cites this paper
• Developer recommendation on bug commenting: a ranking approach for the developer crowd

  2017cites this paper
• MICHAC: Defect Prediction via Feature Selection Based on Maximal Information Coefficient with Hierarchical Agglomerative Clustering

  2016cites this paper
• Progress on Approaches to Automatic Program Repair

  2016cites this paper
• Feature based problem hardness understanding for requirements engineering

  2016cites this paper
• Software requirements selection and prioritization using SBSE approaches: A systematic review and mapping of the literature

  2015cites this paper
• Hill Climbing and simulated annealing in large scale next release problem

  2013cites this paper
• An Empirical Validation of the Complexity of Code Changes and Bugs in Predicting the Release Time of Open Source Software

  2013cites this paper
• A Systematic Review of Software Requirements Selection and Prioritization Using SBSE Approaches

  2013cites this paper
• Solving the Large Scale Next Release Problem with a Backbone-Based Multilevel Algorithm

  2012cites this paper
• Complexity Analysis for the NRP Backbone

  2011cites this paper
• A Hybrid ACO algorithm for the Next Release Problem

  2010cites this paper