@inbook{5c7aa6be967d4737b0d35d832f65ac41,
title = "Worst-case execution time test generation for solutions of the knapsack problem using a genetic algorithm",
abstract = "Worst-case execution time test generation can be hard if tested programs use complex heuristics. This is especially true in the case of the knapsack problem, which is often called “the easiest NP-complete problem”. For randomly generated test data, the expected running time of some algorithms for this problem is linear. We present an approach for generation of tests against algorithms for the knapsack problem. This approach is based on genetic algorithms. It is evaluated on five algorithms, including one simple branch-and-bound algorithm, two algorithms by David Pisinger and their partial implementations. The results show that the presented approach performs statistically better than generation of random tests belonging to certain classes. Moreover, a class of tests that are especially hard for one of the algorithms was discovered by the genetic algorithm.",
keywords = "Genetic algorithms, Knapsack problem, Test generation, Worst-case execution time",
author = "Maxim Buzdalov and Anatoly Shalyto",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2014.",
year = "2014",
doi = "10.1007/978-3-662-45049-9_1",
language = "English",
isbn = "978-3-662-45048-2",
series = "Communications in Computer and Information Science",
publisher = "Springer Nature",
pages = "1--10",
editor = "Linqiang Pan and Tao Song and Gheorghe P{\u a}un and P{\'e}rez-Jim{\'e}nez, {Mario J.}",
booktitle = "Bio-Inspired Computing - Theories and Applications",
address = "Switzerland",
}