Automatic design of specialized algorithms for the binary knapsack problem
Created by W.Langdon from
gp-bibliography.bib Revision:1.7975
- @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",
-
year = "2020",
-
volume = "141",
-
pages = "112908",
-
keywords = "genetic algorithms, genetic programming, Automatic
generation of algorithms, Binary knapsack problem,
Hyperheuristic, Generative design of algorithms",
-
ISSN = "0957-4174",
-
URL = "http://www.sciencedirect.com/science/article/pii/S0957417419306268",
-
DOI = "doi:10.1016/j.eswa.2019.112908",
-
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