Memetic algorithms based on local search chains for large scale continuous optimisation problems: MA-SSW-Chains

摘要

Nowadays, large scale optimisation problems arise as a very interesting field of research, because they appear in many real-world problems (bio-computing, data mining, etc.). Thus, scalability becomes an essential requirement for modern optimisation algorithms. In a previous work, we presented memetic algorithms based on local search chains. Local search chain concerns the idea that, at one stage, the local search operator may continue the operation of a previous invocation, starting from the final configuration reached by this one. Using this technique, it was presented a memetic algorithm, MA-CMA-Chains, using the CMA-ES algorithm as its local search component. This proposal obtained very good results for continuous optimisation problems, in particular with medium-size (with up to dimension 50). Unfortunately, CMA-ES scalability is restricted by several costly operations, thus MA-CMA-Chains could not be successfully applied to large scale problems. In this article we study the scalability of memetic algorithms based on local search chains, creating memetic algorithms with different local search methods and comparing them, considering both the error values and the processing cost. We also propose a variation of Solis Wets method, that we call Subgrouping Solis Wets algorithm. This local search method explores, at each step of the algorithm, only a random subset of the variables. This subset changes after a certain number of evaluations. Finally, we propose a new memetic algorithm based on local search chains for high dimensionality, MA-SSW-Chains, using the Subgrouping Solis Wets’ algorithm as its local search method. This algorithm is compared with MA-CMA-Chains and different reference algorithms, and it is shown that the proposal is fairly scalable and it is statistically very competitive for high-dimensional problems.