A cooperative tabu-search for dynamic optimization problems
A. D. Masegosa, J. R. González, I. J. Garcíadel Amo, D. Pelta and J.L Verdegay
Models of Decision and Optimization research group
Department of Computer Sciences and Artificial Intelligence
University of Granada, Granada, Spain
Recently, there is a growing research interest on the resolution of Dynamic Optimization Problems (DOPs) [1], due to the ability of these models to closely approximate a variety of real-world situations, including trade market prediction, meteorological forecast, robotics motion control, among others. The methods designed to deal with these problems must take into account that both the problem and the solution may evolve in time, and in addition must make allowance for the fact that it is more important to follow the optima as closely as possible than to find their exact position.
Methods already exist to deal with DOPs, but there are not yet clear criteria about which method is better to apply or how to respond to a new dynamic problem. The most commonly used methods have been evolutionary algorithms, but recently, other approaches have been applied and shown to outperform these algorithms in some cases (see e.g. multi-QPSO [1] and Agents [2]).
Most of the methods used are population-based algorithms under the assumption that the use of several solutions helps to avoid local minima and to better detect when a change on the problem occurs. This assumption has gone largely unchallenged and most of the research done in DOPs focuses on the recommended population methods with little attention given to the possibility of employing trajectory-based methods. Another common feature of most of the methods for DOPs is a reliance on some form of cooperative search, which is eminently reasonable in this context.
Taking into account that trajectory-based methods have been rarely considered in DOPs and that certain cooperative forms have exhibited good behaviour, González et al. [3] assessed the merit of creating trajectory methods coupled with a cooperation scheme in this context. Specifically, they proposed a centralized cooperative strategy that consists of a set of tabu searches, with different parameter configurations, that are run in parallel. To control these optimization methods, there exists a coordinator that receives information about their performance and sends orders to them. The coordinator’s behaviour is defined by a control rule base. The tabu search employs an adaptive step size to explore the solution’s neighborhood. To escape from local minima, it allows non-improving moves making use of a tabu list (embodying restrictions that forbid the reversal of recently executed moves) to avoid cycling.
The centralized cooperative strategy was tested on the Moving Peaks Benchmark (scenario 2) [4] and on a dynamic version of three continuous optimization functions (Ackley, Griewank and Rastrigin). In all cases, the element that changes over the time is the objective function. Furthermore, different configurationswere considered for each benchmark,which vary in the severity of the change of the optimums’ position and the number of functions that compose them.To assess the performance of the cooperative tabu searchthis wascomparedversus two state-of-the-art methods: multi-QPSO and Agents. The results obtained disclosed that the cooperative tabu search showed a very robust performance over the different test problems and configurations, being able to improve significantly in terms of Mean Fitness Error [5] both state-of-the-art algorithms in virtually all cases (Mann-Whitney’s U non-parametric test at a significance level of 0.05). Apart from this, the centralized cooperative strategy incorporating tabu searchshowed a faster convergence after the changes of the objective function in the four benchmarks.
References:
[1] T. Blackwell and J. Branke “Multiswarms, exclusion, and anti-convergence in dynamic environments” IEEE Transactions on Evolutionary Computation, 10(4):459-472, 2006.
[2] D. Pelta, C. Cruz, and J. L. Verdegay “Simple control rules in a cooperative system for dynamic optimisation problems” International Journal of General Systems, 38(7):701-717, 2008.
[3] J.R. González, A.D. Masegosa and I.J. García “A cooperative strategy for solving dynamic optimization problems” Memetic Computing, 2010. DOI: 10.1007/s12293-010-0031-x. In press.
[4] J. Branke “Memory enhanced evolutionary algorithms for changing optimization problems”. In IEEE Congress on Evolutionary Computation CEC99, pages 1875-1882. IEEE, 1999.
[5] H. Richter and S. Yang “Learning behavior in abstract memoryschemes for dynamic optimization problems”. Soft Computing – A Fusion of Foundations, Methodologies and Applications, 13(12):1163-1173, 2009.