The dynamic knapsack problem revisited: A new benchmark problem for dynamic combinatorial optimisation

Philipp ROHLFSHAGEN, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

21 Citations (Scopus)

Abstract

In this paper we propose a new benchmark problem for dynamic combinatorial optimisation. Unlike most previous benchmarks, we focus primarily on the underlying dynamics of the problem and consider the distances between successive global optima only as an emergent property of those dynamics. The benchmark problem is based upon a class of difficult instances of the 0/1-knapsack problem that are generated using a small set of real-valued parameters. These parameters are subsequently varied over time by some set of difference equations: It is possible to model approximately different types of transitions by controlling the shape and degree of interactions between the trajectories of the parameters. We conduct a set of experiments to highlight some of the intrinsic properties of this benchmark problem and find it not only to be challenging but also more representative of real-world scenarios than previous benchmarks in the field. The attributes of this benchmark also highlight some important properties of dynamic optimisation problems in general that may be used to advance our understanding of the relationship between the underlying dynamics of a problem and their manifestation in the search space over time. ©Springer-Verlag Berlin Heidelberg 2009.
Original languageEnglish
Title of host publicationApplications of Evolutionary Computing : EvoWorkshops 2009: EvoCOMNET, EvoENVIRONMENT, EvoFIN, EvoGAMES, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, EvoNUM, EvoSTOC, EvoTRANSLOG,Tübingen, Germany, April 15-17, 2009, Proceedings
EditorsMario GIACOBINI, Anthony BRABAZON, Stefano CAGNONI, Gianni A. CARO, Anikó EKÁRT, Anna Isabel ESPARCIA-ALCÁZAR, Muddassar FAROOQ, Andreas FINK, Penousal MACHADO
PublisherSpringer Berlin Heidelberg
Pages745-754
Number of pages10
ISBN (Electronic)9783642011290
ISBN (Print)9783642011283
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event2009 Workshops on Applications of Evolutionary Computation, EvoWorkshops 2009 - Tübingen, Germany
Duration: 15 Apr 200917 Apr 2009

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin, Heidelberg
Volume5484
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2009 Workshops on Applications of Evolutionary Computation, EvoWorkshops 2009
Country/TerritoryGermany
CityTübingen
Period15/04/0917/04/09

Keywords

  • Global Optimum
  • Evolutionary Computation
  • Knapsack Problem
  • Benchmark Problem
  • Combinatorial Optimisation Problem

Fingerprint

Dive into the research topics of 'The dynamic knapsack problem revisited: A new benchmark problem for dynamic combinatorial optimisation'. Together they form a unique fingerprint.

Cite this