Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Worst-Case Execution Time Test Generation for Solutions of the Knapsack Problem Using a Genetic Algorithm
verfasst von : Maxim Buzdalov, Anatoly Shalyto
Erschienen in: Bio-Inspired Computing - Theories and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.