Skip to main content

Research Repository

See what's under the surface

Advanced Search

On the definition of dynamic permutation problems under landscape rotation.

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

Authors

Joan Alza

Josu Ceberio

John McCall



Contributors

Manuel López-Ibáñez
Editor

Abstract

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.

Start Date Jul 13, 2019
Publication Date Jul 13, 2019
Publisher Association for Computing Machinery
ISBN 9781450367486
Institution Citation 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: https://doi.org/10.1145/3319619.3326840
DOI https://doi.org/10.1145/3319619.3326840
Keywords Dynamic optimization problem; Flow shop scheduling problem; Permutation problem; Benchmark generator; Evolutionary computation

Files





You might also like



Downloadable Citations

;