Abstract

In this study a new Bat Algorithm (BA) based on multi-swarm technique called the Multi-Swarm Bat Algorithm (MSBA) is proposed to address the problem of premature convergence phenomenon. The problem happens when search process converges to non-optimal solution due to the loss of diversity during the evolution process. MSBA was designed with improved ability in exploring new solutions, which was essential in reducing premature convergence. The exploration ability was improved by having a number of sub-swarms watching over the best local optima. In MSBA, when the quality of best local optima does not improve after a pre-defined number of iterations, the population is split equally into several smaller sub-swarms, with one of them remains close to the current best local optima for further exploitation while the other sub-swarms continue to explore for new local optima. The proposed algorithm has been applied in feature selection problem and the results were compared against eight algorithms, which are Ant Colony Optimization (ACO), Genetic Algorithm (GA), Tabu Search (TS), Scatter Search (SS), Great Deluge Algorithm (GDA) and stander BA. The results showed that the MSBA is much more effective that it is able to find new best solutions at times when the rest of other algorithms are not able to.

Keywords:

Bat algorithm , bio-inspired algorithms , data mining , feature selection , multi-swarm , optimization,

References

1. Abdullah, S. and N. Jaddi, 2010. Great Deluge Algorithm for Rough Set Attribute Reduction. In: Zhang, Y., A. Cuzzocrea, J. Ma, K.I. Chung, T. Arslan and X. Song, (Eds.), Database Theory and Application, Bio-science and Bio-technology. Springer, Berlin, Heidelberg, ISBN: 3642176224, pp: 310.
   CrossRef    
2. Blackwell, T. and J. Branke, 2004. Multi-swarm Optimization in Dynamic Environments. In: Raidl, G., S. Cagnoni, J. Branke, D. Corne, R. Drechsler et al. (Eds.), Applications of Evolutionary Computing. Springer, Berlin, Heidelberg.
   CrossRef    
3. Brits, R., A.P. Engelbrecht and F. Van Den Bergh, 2007. Locating multiple optima using particle swarm optimization. Appl. Math. Comput., 189: 1859-1883.
   CrossRef    
4. Choubey, N.S. and M.U. Kharat, 2013. Hybrid system for handling premature convergence in GA - Case of grammar induction. Appl. Soft Comput., 13: 2923-2931.
   CrossRef    
5. Corcoran, A.L. and R.L. Wainwright, 1994. A parallel island model genetic algorithm for the multiprocessor scheduling problem. Proceeding of the ACM Symposium on Applied Computing. Phoenix, Arizona, USA.
   CrossRef    
6. Dorigo, M. and C. Blum, 2005. Ant colony optimization theory: A survey. Theor. Comput. Sci., 344: 243-278.
   CrossRef    
7. Hedar, A.R., J. Wang and M. Fukushima, 2008. Tabu search for attribute reduction in rough set theory. Soft Comput. Fusion Found. Methodol. Appl., 12: 909-918.
   CrossRef    
8. Jensen, R. and Q. Shen, 2003. Finding rough set reducts with ant colony optimization. Proceeding of the UK Workshop on Computational Intelligence, pp: 15-22.
   
9. Jensen, R. and Q. Shen, 2004. Semantics-preserving dimensionality reduction: Rough and fuzzy-rough-based approaches. IEEE T. Knowl. Data En., 16: 1457-1471.
   CrossRef    
10. Jue, W., A.R. Hedar, Z. Guihuan and W. Shouyang, 2009. Scatter search for rough set attribute reduction. Proceeding of the International Joint Conference on Computational Sciences and Optimization, pp: 531-535, April 24-26.
    
11. Levine, D., 1996. A parallel genetic algorithm for the set partitioning problem. In: Osman, I. and J. Kelly (Eds.), Meta-heuristics: Theory and Applications. Kluwer Academic Publishers, Boston, MA, USA, pp: 23-35.
    CrossRef    PMid:8557344 PMCid:PMC173722    
12. Liang, J. and P. Suganthan, 2006. Dynamic multi-swarm particle swarm optimizer with a novel constraint-handling mechanism. Proceeding of IEEE Congress on Evolutionary Computation (CEC, 2006), pp: 9-16.
    CrossRef    
13. Lilliefors, H.W., 1967. On the kolmogorov-smirnov test for normality with mean and variance unknown. J. Am. Stat. Assoc., 62: 399-402.
    CrossRef    
14. Lin, J.H., C.W. Chou, C.H. Yang and H.L. Tsai, 2012. A chaotic levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems. J. Comput. Inform. Technol., 2(2): 56-63.
    
15. Liu, J., X. Ren and H. Ma, 2012. Adaptive swarm optimization for locating and tracking multiple targets. Appl. Soft Comput., 12: 3656-3670.
    CrossRef    
16. Liu, Y., G. Wang, H. Chen, H. Dong, X. Zhu and S. Wang, 2011. An improved particle swarm optimization for feature selection. J. Bionic Eng., 8: 191-200.
    CrossRef    
17. Mallipeddi, R., P.N. Suganthan, Q.K. Pan and M.F. Tasgetiren, 2011. Differential evolution algorithm with ensemble of parameters and mutation strategies. Appl. Soft Comput., 11: 1679-1696.
    CrossRef    
18. Marinakis, Y. and M. Marinaki, 2010. A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem. Comput. Oper. Res., 37: 432-442.
    CrossRef    
19. Muhlenbein, H., 1991. Evolution in Time and Space-the Parallel Genetic Algorithm. In: Foundations of Genetic Algorithms. Morgan Kaufmann Publishers Inc., San Farncisco, USA, pp: 316-337.
    CrossRef    
20. Niu, B., Y. Zhu and X. He, 2005. Multi-population Cooperative Particle Swarm Optimization. In: Capcarrère, M., A. Freitas, P. Bentley, C. Johnson and J. Timmis, (Eds.), Advances in Artificial Life. Springer, Berlin, Heidelberg.
    CrossRef    
21. Parsopoulos, K.E. and M.N. Vrahatis, 2002. Particle swarm optimization method in multiobjective problems. Proceeding of the ACM Symposium on Applied Computing. ACM, Madrid, Spain.
    CrossRef    
22. Pereira, C.M.N.A. and C.M.F. Lapa, 2003. Parallel island genetic algorithm applied to a nuclear power plant auxiliary feedwater system surveillance tests policy optimization. Ann. Nucl. Energy, 30: 1665-1675.
    CrossRef    
23. Rafael, B., M. Affenzeller and S. Wagner, 2013. Application of an Island Model Genetic Algorithm for a Multi-track Music Segmentation Problem. In: Machado, P., J. Mcdermott and A. Carballal, (Eds.), Evolutionary and Biologically Inspired Music, Sound, Art and Design. Springer, Berlin, Heidelberg.
    CrossRef    
24. Taha, A.M. and A.Y.C. Tang, 2013. Bat algorithm for rough set attribute reduction. J. Theor. Appl. Inform. Technol., 51(1).
    
25. Taha, A.M., A. Mustapha and S.D. Chen, 2013. Naive bayes-guided bat algorithm for feature selection. Sci. World J., 2013: 1-9, Article ID 325973.
    
26. Wang, W., Y. Wang and X. Wang, 2013a. Bat Algorithm with Recollection. In: Huang, D.S., K.H. Jo, Y.Q. Zhou and K. Han, (Eds.), Intelligent Computing Theories and Technology. Springer, Berlin, Heidelberg.
    CrossRef    
27. Wang, X., W. Wang and Y. Wang, 2013b. An Adaptive Bat Algorithm. In: Huang, D.S., K.H. Jo, Y.Q. Zhou and K. Han, (Eds.), Intelligent Computing Theories and Technology. Springer, Berlin, Heidelberg.
    CrossRef    
28. Xie, J., Y. Zhou, and H. Chen, 2013. A novel bat algorithm based on differential operator and lévy flights trajectory. Comput. Intell. Neurosci., 2013(2013): 13, Article ID 453812.
    
29. Zhao, S.Z., J.J. Liang, P.N. Suganthan and M.F. Tasgetiren, 2008. Dynamic multi-swarm particle swarm optimizer with local search for Large Scale Global Optimization. Proceeding of the IEEE World Congress on Computational Intelligence, Evolutionary Computation. Hong Kong, pp: 3845-3852, June 1-6.
    CrossRef    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.