An ensemble of intelligent water drop algorithms and its application to optimization problems

详细信息    查看全文

• 作者：Basem O. Alijla^a ; ^b ; Li-Pei Wong^a ; Chee Peng Lim^c ; ^{cplim123@yahoo.com" class="auth_mail" title="E-mail the corresponding author} ; ^{chee.lim@deakin.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Ahamad Tajudin Khader^a ; Mohammed Azmi Al-Betar^d
• 关键词：Intelligent water drops ; Optimization ; Swarm intelligence ; Exploitation ; Exploration
• 刊名：Information Sciences
• 出版年：2015
• 出版时间：20 December 2015
• 年：2015
• 卷：325
• 期：Complete
• 页码：175-189
• 全文大小：536 K

文摘

The Intelligent Water Drop (IWD) algorithm is a recent stochastic swarm-based method that is useful for solving combinatorial and function optimization problems. In this paper, we propose an IWD ensemble known as the Master-River, Multiple-Creek IWD (MRMC-IWD) model, which serves as an extension of the modified IWD algorithm. The MRMC-IWD model aims to improve the exploration capability of the modified IWD algorithm. It comprises a master river which cooperates with multiple independent creeks to undertake optimization problems based on the divide-and-conquer strategy. A technique to decompose the original problem into a number of sub-problems is first devised. Each sub-problem is then assigned to a creek, while the overall solution is handled by the master river. To empower the exploitation capability, a hybrid MRMC-IWD model is introduced. It integrates the iterative improvement local search method with the MRMC-IWD model to allow a local search to be conducted, therefore enhancing the quality of solutions provided by the master river. To evaluate the effectiveness of the proposed models, a series of experiments pertaining to two combinatorial problems, i.e., the travelling salesman problem (TSP) and rough set feature subset selection (RSFS), are conducted. The results indicate that the MRMC-IWD model can satisfactorily solve optimization problems using the divide-and-conquer strategy. By incorporating a local search method, the resulting hybrid MRMC-IWD model not only is able to balance exploration and exploitation, but also to enable convergence towards the optimal solutions, by employing a local search method. In all seven selected TSPLIB problems, the hybrid MRMC-IWD model achieves good results, with an average deviation of 0.021% from the best known optimal tour lengths. Compared with other state-of-the-art methods, the hybrid MRMC-IWD model produces the best results (i.e. the shortest and uniform reducts of 20 runs) for all13 selected RSFS problems.