Virtual Savant as a generic learning approach applied to the basic independent Next Release Problem

摘要

This article presents how Virtual Savant (VS) can be used to automatically learn, from an exact algorithm, how to solve the basic independent Next Release Problem in a quick and accurate way. This variant of the Next Release Problem (NRP) is in essence a 0/1 Knapsack Problem and VS is applied to solve the underlying optimization problem. VS is a generic problem-solving approach based on machine learning and heuristics, that works by mimicking how a reference program produces solutions to problem instances. Essentially, VS learns how to generate solutions to a given problem from a reference algorithm and a training set of instances, and it is able to efficiently solve new problem instances by using the acquired knowledge. In this paper, an exact optimizer is used as a reference algorithm. Hence, we are using VS to learn from optimal solutions, which helps to reduce the approximation error inherent to the learning process. We compare five versions of VS (differing in the heuristics they implement) on a large benchmark, composed of problems with different sizes and difficulties. For the best VS configuration, which also has the lowest computational complexity, computed solutions differ less than 1% from the optima in the worst case. Therefore, VS succeeds in learning how to solve the problem under study, and it does so in a highly efficient way, exempting the programmer from having a deep knowledge of the problem domain or highly specialized parallel programming skills. (C) 2021 Elsevier B.V. All rights reserved.