Worst-case execution time test generation for solutions of the knapsack problem using a genetic algorithm

Maxim Buzdalov*, Anatoly Shalyto

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

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.

Original languageEnglish
Title of host publicationBio-Inspired Computing - Theories and Applications
EditorsLinqiang Pan, Tao Song, Gheorghe Păun, Mario J. Pérez-Jiménez
PublisherSpringer Nature
Pages1-10
Number of pages10
ISBN (Electronic)978-3-662-45049-9
ISBN (Print)978-3-662-45048-2
DOIs
Publication statusPublished - 2014
Externally publishedYes

Publication series

NameCommunications in Computer and Information Science
Volume472
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Keywords

  • Genetic algorithms
  • Knapsack problem
  • Test generation
  • Worst-case execution time

Fingerprint

Dive into the research topics of 'Worst-case execution time test generation for solutions of the knapsack problem using a genetic algorithm'. Together they form a unique fingerprint.

Cite this