A Review on Gravitational Search Algorithm and its Applications to Data Clustering & Classification

Full Text (PDF, 822KB), PP.79-93

Views: 0 Downloads: 0

Author(s)

Yugal kumar 1,* G. Sahoo 2

1. Dept. of Information Technology, Birla Institute of Technology, Mesra, Ranchi, Jhrakhand, India

2. Department of Information Technology, Birla Institute of Technology, Mesra, Ranchi, Jhrakhand, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2014.06.09

Received: 14 Aug. 2013 / Revised: 20 Nov. 2013 / Accepted: 17 Jan. 2014 / Published: 8 May 2014

Index Terms

Classification, Clustering, Gravitational Search Algorithm, Optimization, Nature Inspired Algorithm

Abstract

Natural phenomenon’s and swarms behavior are the warm area of research among the researchers. A large number of algorithms have been developed on the account of natural phenomenon’s and swarms behavior. These algorithms have been implemented on the various computational problems for the sake of solutions and provided significant results than conventional methods but there is no such algorithm which can be applied for all of the computational problems. In 2009, a new algorithm was developed on the behalf of theory of gravity and was named gravitational search algorithm (GSA) for continuous optimization problems. In short span of time, GSA algorithm gain popularity among researchers and has been applied to large number of problems such as clustering, classification, parameter identification etc. This paper presents the compendious survey on the GSA algorithm and its applications as well as enlightens the applicability of GSA in data clustering & classification.

Cite This Paper

Yugal kumar, G. Sahoo, "A Review on Gravitational Search Algorithm and its Applications to Data Clustering & Classification", International Journal of Intelligent Systems and Applications(IJISA), vol.6, no.6, pp.79-93, 2014. DOI:10.5815/ijisa.2014.06.09

Reference

[1]W. Du, B. Li,”Multi-strategy ensemble particle swarm optimization for dynamic optimization”, Information Sciences, 2008, 178, pp 3096–3109.

[2]X. Yao, Y. Liu, G. Lin,”Evolutionary programming made faster”, IEEE Transactions on Evolutionary Computation, 1999, 3 pp 82–102.

[3]Y. Liu, Z. Yi, H. Wu, M. Ye, K. Chen, “A tabu search approach for the minimum sum-of-squares clustering problem”, Information Sciences, 2008, 178, 2680–2704.

[4]X. Tan, B. Bhanu, “Fingerprint matching by genetic algorithms”, Pattern Recognition, 2006, 39, 465–477.

[5]T.H. Kim, I. Maruta, T. Sugie,”Robust PID controller tuning based on the constrained particle swarm optimization”, Automatica, 2008, 44, 1104–1110.

[6]Z. Baojiang, L. Shiyong,”Ant colony optimization algorithm and its application to neuro-fuzzy controller design”, Journal of Systems Engineering and Electronics 18, 603–610.

[7]O. Cordon, S. Damas, J. Santamarı,”A fast and accurate approach for 3D image registration using the scatter search evolutionary algorithm, Pattern Recognition Letters, 2006, 27 ,pp 1191–1200.

[8]H. Nezamabadi-pour, S. Saryazdi, E. Rashedi,” Edge detection using ant algorithms”, Soft Computing, 2006, 10, pp 623- 628.

[9]JY Wu,”MIMO CMAC neural network classifier for solving classification problems”, Applied Soft Computing, 2011, 11 (2), pp 2326–2333

[10]Kalinlia A, Karabogab N, “Artificial immune algorithm for IIR filter design”, Engineering Applications of Artificial Intelligence, 2005, 18, 919–929.

[11]D. Karaboga, C. Ozturk (2011) A novel clustering approach: artificial bee colony (ABC) algorithm. Applied Soft Computing 11 (1), pp 652–657.

[12]Kirkpatrick S, Gelatt CD and Vecchi P,”Optimization by simulated annealing”, Science, 1983, 220, 671-680.

[13]Mitra D, Romeo F and Vincentelli, A.S., “Convergence and Finite-Time Behavior of Simulated Annealing Advances in Applied Probability”, 1986. 

[14]Janson S & Middendorf M, “A hierarchical particle swarm optimizer for dynamic optimization problems”, In: Proceedings of the application of evolutionary computing, 2004, volume 3005. pp 513–524.

[15]Kennedy J & Eberhart R, “Particle swarm optimization”, In: Proceeding of IEEE int’l. Conf. on neural networks, 1995, Vol. IV, pp. 1942–1948.

[16]Silva A, Neves A, Costa E,”Chasing the swarm: a predator pray approach to function optimization”, In: Proceeding of the international conference on soft computing MENDEL, 2002. 

[17]Y.L. Lin, W.D. Chang, J.G. Hsieh,”A particle swarm optimization approach to nonlinear rational filter modeling, Expert Systems with Applications, 2008, 34, pp 1194–1199.

[18]Holland JH, “Adaptation in natural and artificial systems”, University of Michigan Press, 1975.

[19]Boeringer D-W, Werner DH, “Particle swarm optimization versus genetic algorithm for phased array synthesis”, IEEE Trans Antennas Propag., 2004, 52(3):771–779.

[20]Dorigo M,“Optimization, learning and natural algorithms”, PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992.

[21]Dorigo M and Gambardella LM, “Ant colony for the traveling salesman problem”, Bio systems, 1997, 43, pp. 73-81. 

[22]Costa, D. and Hertz, A. (1997) Ants can color graphs. J. Operate Res. Soc., 48, pp. 295-305.

[23]Di Caro G. and Dorigo M. (1998) Two ant colony algorithms for best-effort quality of service routing. In: Unpublished at ANTS'98-From Ant Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization.

[24]Merkle D & Middendorf M.Modelling,” ACO: Composed permutation problems”, In: Ant algorithms Proceedings of ANTS 2002—Third international workshop. Lecture Notes in Comput Sci, 2002, vol, 2463., pp. 149–62.

[25]Gutjahr WJ, “A graph-based ant system and its convergence Future Generat. Comput. Syst., 2000, 16(9):873–88.

[26]Gutjahr WJ, “ACO algorithms with guaranteed convergence to the optimal solution”, Information Process Letters, 2002, 82(3), 145–53.

[27]Karaboga D, Basturk B,”A powerful and efficient algorithm for numerical function optimization:artificial bee colony (abc) algorithm”, J Glob Optim. 2007b, 39:459–471.

[28]Karaboga D & Basturk B,”A comparative study of artificial bee colony algorithm”, Applied Mathematics and Computation, 2009, 214:108–32.

[29]Akay B, Karaboga D , “A modified artificial bee colony algorithm for real-parameter optimization” Inf Sci., 2010 doi:10 .1016/j.ins.2010.07.015.

[30]Basturk B, Karaboga D, “An artificial bee colony (abc) algorithm for numeric function optimization’, In: IEEE swarm intelligence symposium 2006, Indianapolis, IN, USA.

[31]Mezura-Montes E, Damian-Araoz M, Cetina-Domingez O ,” Smart flight and dynamic tolerances in the artificial bee colony for constrained optimization”, In: 2010 IEEE congress on evolutionary computation (CEC), 2010, pp 1–8.

[32]Eduardo Gerhardt and Herbert Martins Gomes, “Artificial Bee Colony (ABC) Algorithm for Engineering Optimization”, Problems In: Proceeding of 3rd International Conference on Engineering Optimization Rio de Janeiro, Brazil, 2012.

[33]Zhu GP & Kwong S,”Gbest-guided artificial bee colony algorithm for numerical function optimization”, Applied Mathematics and Computation 2010, doi: 10.1016/j.amc.2010 .08.049.

[34]Osman K. Erol and Ibrahim Eksin,”A new optimization method: Big Bang–Big Crunch”, Advances in Engineering Software, 2006, 37, pp. 106–111.

[35]Hesheng Tang, Jin Zhou, Songtao Xue and Liyu Xie, ”Big Bang-Big Crunch optimization for parameter estimation in structural systems”, Mechanical Systems and Signal Processing, 2010, 24, pp 2888–2897.

[36]M.H. Afshar and I. Motaei,”CONSTRAINED BIG BANG-BIG CRUNCH ALGORITHM FOR OPTIMAL SOLUTION OF LARGE SCALE RESERVOIR OPERATION PROBLEM”, Int. J. Optim. Civil Eng., 2011, 2, pp 357-375.

[37]Hatamlou A, Abdullah S and Othman Z , “Gravitational Search Algorithm with Heuristic Search for Clustering Problems”, In proceeding of 3rd IEEE on Data Mining and Optimization (DMO), 2011, pp. no. 190 – 193, 28-29 June 2011, Selangor, Malaysia.

[38]Rashedi E, Nezamabadi-pour H, Saryazdi S,” GSA: a gravitational search algorithm”, Information Science, 2009, 179, 2232–2248.

[39]Holliday D, Resnick R and Walker J, “Fundamentals of physics”, John Wiley and Sons, 1993.

[40]Schutz B.,” Gravity from the Ground Up”, Cambridge University Press, 2000.

[41]Rashedi E, Nezamabadi-pour H, Saryazdi S ,”BGSA: binary gravitational search algorithm”, Nat Comput, 2010, 9, pp 727–745.

[42]Hamid Reza Hassanzadeh and Modjtaba Rouhani, “A MULTI OBJECTIVE GRAVITATIONAL SEARCH ALGORITHM”, In: Proceeding of Second International Conference on Computational Intelligence, Communication Systems and Networks, 2010, pp. 7 – 12. 

[43]S. Sarafrazi, H. Nezamabadi-pour and S. Saryazdi, ”Disruption: A new operator in gravitational search algorithm. Scientia Iranica D, 2011, 18 (3), pp. 539–548.

[44]M. Soleimanpour-moghadam, H. Nezamabadi-pour, M. M. Farsangi ,”A quantum behaved gravitational search algorithm”, In: proceeding of Int. Conf. Computational Intelligence and Software Engineering, Wuhan, China, 2011.

[45]Radu-Emil Precup, Radu-Codruţ David, Emil M. Petriu , Stefan Preitl and Mircea-Bogdan Rădac,”Gravitational Search Algorithm in Fuzzy Control Systems Tuning”, In: Proceeding of 18th IFAC World Congress, 2011, pp. no. 13624-13629, Milano (Italy).

[46]Nihan Kazak and Alpaslan Duysak,”Modified Gravitational Search Algorithm”, In: Proceeding of IEEE International Symposium on Innovations in Intelligent Systems and Applications (INISTA), 2012, pp. 1- 4, Turkey.

[47]Mohadeseh Soleimanpour moghadam & Hossein Nezamabadi pour, “An improved quantum behaved gravitational search algorithm”, In: proceeding of 20th Iranian Conference on Electrical Engineering, (ICEE2012), 2012, pp. no. 711 – 715.

[48]Nanji H. R., Mina Sohrabi and Esmat Rashedi,”A High-Speed, Performance-Optimization Algorithm Based on a Gravitational Approach”, Journal of Computing in Science & Engineering, 2012, volume 14, Issue: 5 pp. 56 – 62.

[49]Xiangtao Li, Jianan Wang, Junping Zhou and Minghao Yin,”An Effective GSA Based Memetic Algorithm for Permutation Flow Shop Scheduling. In: proceeding of IEEE congress on Evolutionary Computation, 2010, pp. no. 1-6.

[50]Seyedali Mirjalili and Siti Zaiton Mohd Hashim,” A new hybrid PSOGSA algorithm for function optimization”, In: Proceeding of International conference on computer and information application (ICCIA), 2010, pp. no. 374- 377.

[51]Chatterjee A, Mahanti G. K. and Pathak N, (2010),” COMPARATIVE PERFORMANCE OF GRAVITATIONAL SEARCH ALGORITHM AND MODIFIED PARTICLE SWARM OPTIMIZATION ALGORITHM FOR SYNTHESIS OF THINNED SCANNED CONCENTRIC RING ARRAY ANTENNA”, Progress In Electromagnetic Research B, Vol. 25, 331-348.

[52]Radu-Emil Precup, Radu-Codruţ David, Emil M. Petriu , Stefan Preitl and Adrian Sebastian Paul,”Gravitational Search Algorithm-Based Tuning of Fuzzy Control Systems with a Reduced Parametric Sensitivity”, Advances in Intelligent and Soft Computing, 2011, Volume 96, pp. 141-150.

[53]Jianhua Xiao, Fan Qi, and Yongkai Li, “Gravitational Chaotic Search Algorithm for Partners Selection with Due Date Constraint in Virtual Enterprise”, In: Proceeding of Fourth International Workshop on Advanced Computational Intelligence, 2011, pp. 138 – 142.

[54]J. P. Papa, A. Pagnin, S. A. Schellini, A. Spadotto, R. C. Guido, M. Pont, G. Chiachia and A. X. Falcaoi,”FEATURE SELECTION THROUGH GRAVITATIONAL SEARCH ALGORITHM”, In: Proceeding of IEEE international conference Acoustics, Speech and Signal Processing (ICASSP), 2011, pp. 2052 – 2055.

[55]M. Ghalambaz, A.R. Noghrehabadi, M.A. Behrang, E. Assareh, A. Ghanbarzadeh, N.Hedayat,”A Hybrid Neural Network and Gravitational Search Algorithm (HNNGSA) Method to Solve well known Wessinger's Equation”, World Academy of Science, Engineering and Technology, 2011, issue 49, pp. no. 803 – 807.

[56]Chaoshun Li and Jianzhong Zhou , “Parameters identification of hydraulic turbine governing system using improved gravitational search algorithm”, Energy Conversion and Management, 2011, Volume 52, Issue 1, pp. 374–381.

[57]Jianhua Xiao and Zhen Cheng,”DNA Sequences Optimization Based on Gravitational Search Algorithm for Reliable DNA computing In: proceeding of IEEE Sixth International Conference on Bio-Inspired Computing: Theories and Applications, 2011, pp. 103 – 107.

[58]Esmat Rashedi, Hossien Nezamabadi-pour and Saeid Saryazdi,”Filter modeling using gravitational search algorithm Engineering applications of Artificial Intelligence, 2011, volume 24(1), pp 117-122.

[59][59] Serhat DUMAN, Aysen Basa ARSOY and Nuran YÖRÜKEREN ,”Solution of Economic Dispatch Problem using Gravitational Search Algorithm”, In: Proceeding of 7th international conference of electrical and electronics engineering, 2011, pp. 54 – 59, Turckey.

[60]Chaoshun Li, Jianzhong Zhou, Jian Xiao and Han Xiao (2012)Parameters identification of chaotic system by chaotic gravitational search algorithm. Chaos, Solitons & Fractals, Volume 45, Issue 4, Pages 539–547, 2012.

[61]Radu-Emil Precup, Radu-Codruţ David, Emil M. Petriu , Stefan Preitl and Mircea-Bogdan Radac,”Novel Adaptive Gravitational Search Algorithm for Fuzzy Controlled Servo Systems”, IEEE Transcation on Industrial Informatics, 2012, volume 8, no. 4, pp 791 -800.

[62]Lucian Ovidiu Fedorovici, Radu-Emil Precup, Florin Dragan, Radu-Codrut David and Constantin Purcaru ,”Embedding Gravitational Search Algorithms in Convolutional Neural Networks for OCR Applications In: Proceeding of 7th IEEE International Symposium on Applied Computational intelligence and Informatics, 2012, pp. 125 – 130.

[63]S. Duman, Y. So nmez, U. Gu venc and N. Yo ru keren, “Optimal reactive power dispatch using a gravitational search algorithm”, IET Gener. Transm. Distrib., 2012, Vol. 6 (6), pp. 563–576.

[64]Serhat Duman, Ugur Guvenc, Yusuf Sonmez and Nuran Yorukeren,”Optimal power flow using gravitational search algorithm”, Energy Conversion and Management, 2012, volume 59, pp 86–95.

[65]Asrulibrahim A, Mohamed and Shareef H, ”Application of quantum-inspired binary gravitational search algorithm for optimal power quality monitor placement. In: proceedings of the 11th WSEAS international conference on Artificial Intelligence, Knowledge Engineering and Database,”, 2012, pp. no. 27- 32.

[66]Hossein Askari and Seyed-Hamid Zahiri, “Decision function estimation using intelligent gravitational search algorithm”, Int. J. Mach. Learn. & Cyber, 2012, 3, pp. 163–172.

[67]Mohammad Khajehzadeh, Mohd RaihanTaha, Ahmed El-Shafie and MahdiyehEslami, “A modified gravitational search algorithm for slope stability analysis”, Engineering Applications of Artificial Intelligence (article in press)

[68]Hamed Sadeghi, Najmeh Eghbal and Reyhaneh Kardehi Moghaddam, “Application Gravitational Search Algorithm in Identification of Switched Linear Systems”, In: Proceeding of IEEE Third International Conference on Intelligent Systems Modeling and Simulation, 2012, pp. 89 – 95. 

[69]LI Pei & Duan HaiBin,”Path planning of unmanned aerial vehicle based on improved gravitational search algorithm”, Science China published by Springer, 2012, Vol.55 No.10: 2712–2719.

[70]M. Mahdavi (2008) Novel meta-heuristic algorithms for clustering web documents. Applied Mathematics and Computation, 208, 201 (1–2), pp 441–451.

[71]R. Gil-Garcia, A. Pons-Porrata,”Dynamic hierarchical algorithms for document clustering, Pattern Recognition Letters, 2010, 31 (6), pp 469–477.

[72]Tan P N, Steinbach M & Kumar, “Introduction to data mining, Boston: Addison Wesley, 2005, pp. 487–559.

[73]Tjhi W C & Chen L H,”A heuristic-based fuzzy co-clustering algorithm for categorization of high-dimensional data”, Fuzzy Sets and Systems, 2008, 159(4), pp 371–389.

[74]P. Jin, Y.L. Zhu, K.Y. Hu,”A clustering algorithm for data mining based on swarm intelligence”, in: Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, ICMLC, 2007.

[75]Zhang B, Hsu M & Dayal U,”K-harmonic means – a data clustering algorithm”, Technical Report HPL-1999-124, Hewlett-Packard Laboratories.

[76]P.S. Shelokar, V.K. Jayaraman, B.D. Kulkarni, “An ant colony approach for clustering”, Analytica Chimica Acta, 2004, 509 (2),pp 187–195.

[77]Zhou H & Liu YH,”Accurate integration of multi-view range images using k-means clustering. Pattern Recognition, 2008, 41(1), pp 152–175.

[78]Hatamlou A, Pour HN and Abdullah S, ” Application of gravitational search algorithm on data clustering In: published in proceeding of 6th international workshop on Rough Set and Knowledge technology (RSKT-11), 2011, pp. no. 337-346.

[79]Hatamlou A, Abdullah S and Pour HN, “ A combined approach for clustering based on K-means and gravitational search algorithms”, Swarm and Evolutionary Computation, 2012, 6, pp 47–52.

[80]Minghao Yin, Yanmei Hu, Fengqin Yang, Xiangtao Li and Wenxiang Gu,”A novel hybrid K-harmonic means and gravitational search algorithm approach for clustering”, Expert Systems with Applications, 2011, 38, 9319–9324.

[81]M.W. Kurzynski, “The optimal strategy of a tree classifier”, Pattern Recognition, 1983, 16, pp 81–87.

[82]F. Seifi, M.R. Kangavari, H. Ahmadi, E. Lotfi, S. Imaniyan, S. Lagzian, “Optimizing twins decision tree classification using genetic algorithms”, In: 7th IEEE International Conference on Cybernetic Intelligent Systems, 2008, pp. 1–6.

[83]P. Knagenhjelm, P. Brauer,”Classification of vowels in continuous speech using MLP and a hybrid network”, Speech Communication,1990, 9 (1) pp 31–34.

[84]Rana S, Jasola S and Kumar R A review on particle swarm optimization algorithms and their applications to data clustering Artif Intell Rev, 201,1 35, 211–222.

[85]Soroor Sarafrazi and Hossein Nezamabadi-pour, “Facing the classification of binary problems with a GSA-SVM hybrid system”, Mathematical and Computer Modeling, 2013, vol. 57, issue 1, pp. 270–278. 

[86]Bahrololoum A, Pour HN, Bahrololoum H and Saeed M, “A prototype classifier based on gravitational search algorithm”, Applied Soft Computing , 2012, 12, 819–825.

[87]Soroor Sarafrazi, Hossein Nezamabadi-pour and Mojgan Barahman,”A GSA-SVM HYBRID SYSTEM FOR CLASSIFICATION OF BINARY PROBLEMS”, In: Proceedings of the Fourth Global Conference on Power Control and Optimization, 2011, pp. 198-203.