Dynamic Combinatorial Optimisation Problems: An Analysis of the Subset Sum Problem

P Rohlfshagen, Xin Yao

Research output: Contribution to journalArticle

18 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)1723-1734
Number of pages12
JournalSoft Computing
Volume15
Issue number9
Early online date25 Jun 2010
DOIs
Publication statusPublished - 1 Sep 2011

Fingerprint

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