Dynamic combinatorial optimisation problems: An analysis of the subset sum problem


Research output: Journal PublicationsJournal Article (refereed)peer-review

25 Citations (Scopus)


The field of evolutionary computation has traditionally focused on static optimisation problems. Recently, many new approaches have been proposed that adapt traditional evolutionary algorithms to the dynamic domain to deal with the task of tracking high-quality solutions as the search space changes over time. These novel algorithms are subsequently evaluated on a wide range of different optimisation problems, including well-specified benchmark generators. However, due to a lack of theoretical results, as well as a general lack of references to actual real-world scenarios, it is not entirely clear whether these benchmarks capture any of the characteristics found in NP-hard dynamic optimisation problems. In this paper, we extensively analyse the properties of the NP-hard (dynamic) subset sum problem. In particular, we highlight the correlation between the dynamic parameters of the problem and the resulting movement of the global optimum. It is shown by empirical means that the degree to which the global optimum moves in response to the underlying dynamics is correlated only in specific cases. Furthermore, the role of the representation used to encode the problem, as well as the impact of the formulation of the objective function on the dynamics are also discussed. © 2010 Springer-Verlag.
Original languageEnglish
Pages (from-to)1723-1734
Number of pages12
JournalSoft Computing
Issue number9
Early online date24 Jun 2010
Publication statusPublished - Sept 2011
Externally publishedYes

Bibliographical note

This work was supported by EPSRC Grant no. EP/E058884/1 entitled “Evolutionary Algorithms for Dynamic Optimisation Problems: Design, Analysis and Applications”. The authors are grateful for useful discussions with Trung Thanh Nguyen regarding this work.


  • Combinatorial optimisation
  • Dynamic optimisation
  • Evolutionary computation
  • Fitness landscapes
  • Subset sum problem


Dive into the research topics of 'Dynamic combinatorial optimisation problems: An analysis of the subset sum problem'. Together they form a unique fingerprint.

Cite this