Automatic design of specialized algorithms for the binary knapsack problem

Created by W.Langdon from gp-bibliography.bib Revision:1.7615

@Article{ACEVEDO:2020:ESA,

• author = "Nicolas Acevedo and Carlos Rey and Carlos Contreras-Bolton and Victor Parada",
• title = "Automatic design of specialized algorithms for the binary knapsack problem",
• journal = "Expert Systems with Applications",
• volume = "141",
• pages = "112908",
• year = "2020",
• ISSN = "0957-4174",
• DOI = "doi:10.1016/j.eswa.2019.112908",
• URL = "http://www.sciencedirect.com/science/article/pii/S0957417419306268",
• keywords = "genetic algorithms, genetic programming, Automatic generation of algorithms, Binary knapsack problem, Hyperheuristic, Generative design of algorithms",
• abstract = "Not all problem instances of a difficult combinatorial optimization problem have the same degree of difficulty for a given algorithm. Surprisingly, apparently similar problem instances may require notably different computational efforts to be solved. Few studies have explored the case that the algorithm that solves a combinatorial optimization problem is automatically designed. In consequence, the generation of the best algorithms may produce specialized algorithms according to the problem instances used during the constructive step. Following a constructive process based on genetic programming that combines heuristic components with an exact method, new algorithms for the binary knapsack problem are produced. We found that most of the automatically designed algorithms have better performance when solving instances of the same type used during construction, although the algorithms also perform well with other types of similar instances. The rest of the algorithms are partially specialized. We also found that the exact method that only solves a small knapsack problem has a key role in such results. When the algorithms are produced without considering such a method, the errors are higher. We observed this fact when the algorithms were constructed with a combination of instances from different types. These results suggest that the better the pre-classification of the instances of an optimization problem, the more specific and more efficient are the algorithms produced by the automatic generation of algorithms. Consequently, the method described in this article accelerates the search for efficient methods for NP-hard optimization problems",

}

Genetic Programming entries for Nicolas Acevedo Carlos Rey Carlos Contreras-Bolton Victor Parada

Citations