Skip to main content

Research Repository

Advanced Search

On the definition of dynamic permutation problems under landscape rotation.

Alza, Joan; Bartlett, Mark; Ceberio, Josu; McCall, John


Joan Alza

Josu Ceberio


Manuel L�pez-Ib��ez


Dynamic optimisation problems (DOPs) are optimisation problems that change over time. Typically, DOPs have been defined as a sequence of static problems, and the dynamism has been inserted into existing static problems using different techniques. In the case of dynamic permutation problems, this process has been usually done by the rotation of the landscape. This technique modifies the encoding of the problem and maintains its structure over time. Commonly, the changes are performed based on the previous state, recreating a concatenated changing problem. However, despite its simplicity, our intuition is that, in general, the landscape rotation may induce severe changes that lead to problems whose resemblance to the previous state is limited, if not null. Therefore, the problem should not be classified as a DOP, but as a sequence of unrelated problems. In order to test this, we consider the flow shop scheduling problem (FSSP) as a case study and the rotation technique that relabels the encoding of the problem according to a permutation. We compare the performance of two versions of the state-of-the-art algorithm for that problem on a wide experimental study: an adaptive version that benefits from the previous knowledge and a restarting version. Conducted experiments confirm our intuition and reveal that, surprisingly, it is preferable to restart the search when the problem changes even for some slight rotations. Consequently, the use of the rotation technique to recreate dynamic permutation problems is revealed in this work.


ALZA, J., BARTLETT, M., CEBERIO, J. and MCCALL, J. 2019. On the definition of dynamic permutation problems under landscape rotation. In López-Ibáñez, M. (ed.) Proceedings of the 2019 Genetic and evolutionary computation conference companion (GECCO 2019), 13-17 July 2019, Prague, Czech Republic. New York: ACM [online], pages 1518-1526. Available from:

Conference Name 2019 Genetic and evolutionary computation conference companion (GECCO 2019)
Conference Location Prague, Czech Republic
Start Date Jul 13, 2019
End Date Jul 17, 2019
Acceptance Date Feb 6, 2019
Online Publication Date Jul 13, 2019
Publication Date Jul 31, 2019
Deposit Date Aug 22, 2019
Publicly Available Date Aug 22, 2019
Publisher Association for Computing Machinery (ACM)
Pages 1518-1526
ISBN 9781450367486
Keywords Dynamic optimization problem; Flow shop scheduling problem; Permutation problem; Benchmark generator; Evolutionary computation
Public URL


You might also like

Downloadable Citations