Applying extremal optimisation to dynamic optimisation problems

Extremal Optimisation is a recently conceived addition to the range of stochastic solvers. Due to its deliberate lack of convergence behaviour, it can be expected to solve dynamic problems without having to be informed when a change occurs. Moreover, the severity of change does not seriously affect algorithm performance, allowing for unpredictable fluctuations without affecting the outcome. Experimental studies on three example problems confirmed this assumption but also raised some issues concerning the interaction of solver mechanisms with problem intricacies, a phenomenon shared by many algorithm implementations. Many of the problems used as benchmarks had not been solved with EO before. While EO is a very lightweight stochastic process, it is at its most effective when the choice of next move is modelled skilfully according to the problem characteristics. Some insights into effective neighbourhood modelling were revealed during the experimentations. Stochastic algorithms are designed to skilfully and implicitly balance exploration and exploitation. Due to the random elements in these balancing mechanisms, their timing may not be accurate, i.e. a solver may often choose an explorative move in a situation where the greediest choice would be most effective. Often, the problem or problem instance offers cues for a deliberate timing of these features. In the current work, it has been observed that exploiting these cues and timing the actions accordingly – reducing the extent of randomness whenever possible – is highly beneficial to the overall outcome. Consequently, hybridisations of EO with various hill climbing techniques has proved most effective, speeding up the optimisation process even further.