On the definition of dynamic permutation problems under landscape rotation.
Alza, Joan; Bartlett, Mark; Ceberio, Josu; McCall, John
Doctor Mark Bartlett firstname.lastname@example.org
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|
|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|
|Keywords||Dynamic optimization problem; Flow shop scheduling problem; Permutation problem; Benchmark generator; Evolutionary computation|
ALZA 2019 On the definition
You might also like
Ensemble selection based on classifier prediction confidence.
Introducing the dynamic customer location-allocation problem.
Limitations of benchmark sets and landscape features for algorithm selection and performance prediction.
Multi-label classification via incremental clustering on an evolving data stream.
A holistic metric approach to solving the dynamic location-allocation problem.