On the definition of dynamic permutation problems under landscape rotation.

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

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.

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

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2019 Genetic and evolutionary computation conference companion (GECCO 2019)
• 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)
• Peer Reviewed: Peer Reviewed
• Pages: 1518-1526
• ISBN: 9781450367486
• DOI: https://doi.org/10.1145/3319619.3326840
• Keywords: Dynamic optimization problem; Flow shop scheduling problem; Permutation problem; Benchmark generator; Evolutionary computation
• Public URL: https://rgu-repository.worktribe.com/output/325317
• Contract Date: Aug 22, 2019