Genetic Algorithm Using MapReduce - A Critical Review

Palak Sachar*, Vikas Khullar**
* PG Scholar, Department of Computer Science and Engineering, CT Group of Institutions, Jalandhar, Punjab, India.
** Assistant Professor, Department of Computer Science and Engineering, CT Group of Institutions, Jalandhar, Punjab, India.
Periodicity:August - October'2015
DOI : https://doi.org/10.26634/jcc.2.4.4907

Abstract

Now-a-days, to achieve an optimized solution for hard problems is a big challenge. Scientists are putting their best efforts to introduce a best algorithm to optimize the problem to a great extent. Genetic Algorithm is one of the stepping stones in the challenge and is an evolutionary algorithm inspired by Darwin's theory of evolution. Using this algorithm, with MapReduce, makes it efficient and user friendly. Users can build more scalable applications with MapReduce, since it provides a better abstraction to the genetic algorithm in lesser time. To parallelize the process of any project, MapReduce plays a vital role on Hadoop platform. The platform may vary from Hadoop to cloud which affect the performance significantly. Parallelizing of a genetic algorithm is convenient with the help of MapReduce. The major objective of the study is to know the behavior of Genetic Algorithm under the paradigm of Hadoop MapReduce. The various applications show different trends influenced by this platform. Also literature review strongly depicts the advantages of Hadoop MapReduce platform over other platforms. Moreover, the difference between various paradigms of Parallelisation is given in the paper to make decisions regarding its implementation of future work.

Keywords

Genetic Algorithm (GA), MapReduce, Hadoop.

How to Cite this Article?

Sachar, P., and Khullar, V. (2015). Genetic Algorithm Using MapReduce-A Critical Review. i-manager's Journal on Cloud Computing, 2(4), 35-42. https://doi.org/10.26634/jcc.2.4.4907

References

[1]. K. Gallagher and M. Sambridge, (1994). “Genetic algorithms: a powerful tool for large-scale on linear optimization problems”. Comput. Geosci., Vol. 20, No. 78, pp.1229–1236.
[2]. P. Frnti, J. Kivijrvi, T. Kaukoranta, and O. Nevalainen, (1997). “Genetic algorithms for large scale clustering problems”. Comput.J, Vol. 40, pp. 547–554.
[3]. K. Sastry, D. E. Goldberg, and X. Llora, (2007). “Towards Billionbit Optimization Via a Parallel Estimation of distribution algorithm”. In GECCO '07: Proceedings of the th 9 Annual Conference on Genetic and Evolutionary Computation, pp. 577–584, New York, NY, USA, ACM.
[4]. Verma, A., Llorà, X., Goldberg, D. E., and Campbell, R. H., (2009). “Scaling Genetic Algorithms Using MapReduce”. In: 9th International Conference on Intelligent Systems Design and Applications, pp. 13-18. IEEE, New York.
[5]. Chao Jin and Rajkumar Buyya, (2008). “MRPGA: An Extension of Map Reduce for Parallelizing Genetic Algorithm”. IEEE international Conference on Escience, pp. 214-221.
[6]. Zhou C., (2010). “Fast Parallelization of Differential th Evolution Algorithm Using MapReduce”. In: 12 Annual Conference on Genetic and Evolutionary Computation, pp. 1113-1114, ACM, New York .
[7]. Filomena Ferrucci, (2015). "A Parallel Genetic Algorithm Framework Based on Map Reduce.” ACM New York, NY, USA, pp. 13-17.
[8]. Nivranshu Hans, Sana Mahajan, and SN Omkar, (2015). “Big Data Clustering Using Genetic Algorithm On Hadoop Mapreduce”. International Journal of Scientific & Technology Research, Vol. 4, No. 4.
[9]. Doina Logofatu, and Daniel Stamate, (2014). “Scalable Distributed Genetic Algorithm for Data Ordering Problem with Inversion Using MapReduce”. AIAI 2014, pp. 325-334.
[10]. Filomena Ferrucci, M-Tahar Kechadi, (2013). “A Framework for Genetic Algorithms Based on Hadoop”. arixiv, Cornell University USA, Vol. 30.
[11]. Iza'in Nurfateha Ruzan, and Suriayati Chuprat, (2012). “A Hybrid Algorithm Using Genetic Algorithmhadoop Mapreduce Optimization for Energy Efficiency in Cloud Computing Platform”. International Journal of Science and Research (IJSR).
[12]. Dino Keco, and Abdulhamit Subasi, (2012). “Parallelization of Genetic Algorithm using Hadoop Map/reduce”, Southeast Europe Journal of Soft Computing, Vol.1, No. 2, pp. 56-59.
[13]. Atanas Radenski, (2012). “Distributed Simulating Annealing with Map Reduce”, European Conference on Applications of Evolutionary Computation, pp. 466-476, Spinger, Berlin.
[ 1 4 ] . Periasamy Vivekanandan, and Raju Nedunchezhian, (2011). “Mining Data Stream with the concept drifts using genetic algorithm”. Artificial Intelligence Review, Vol. 36, No.3, pp. 163-178.
[15]. Di-Wei Huang and Jimmy Lin, (2010). “Scaling population of a genetic algorithm for Job Shop scheduling Problem using map reduce”. 2nd IEEE International Conference on Cloud Computing Technology and Science, pp. 780-785,USA.
[16]. Bioplanet.com. What is Bioinformatics? Retrieved from http://www. bioplanet.com/what-is-bioinformatics/
[17]. Abhishek Verma and Roy H. Campbell, (2010). “Scaling ECGA Model Building via Data-Intensive Computing”. IEEE Congress on Evolutionary Computation (CEC), Barcelona, Spain.
[18]. Youssef M. Essa, Gamal Attiya and Ayman El-Sayed, (2013). “Mobile Agent based New Framework for Improving Big Data Analysis”. 2013 International Conference on Cloud Computing and Big Data.
[19]. Saurabh Arora and Inderveer Chana, (2014). “A Survey of Clustering Techniques for Big Data Analysis”. 5th International Conference- Confluence The Next Generation Information Technology Summit (Confluence).
[20]. Shankar Ganesh Manikandan and Siddarth Ravi, (2014). “Big Data Analysis using Apache Hadoop”. 2014 International Conference on IT Convergence and Security (ICITCS 2014), Beijing, China, pp. 345-348.
[21]. Xiafai Huang, Hui Zhou, Wei Wu, (2015). “Hadoop Job Scheduling Based on Mixed Ant-genetic Algorithm”. Cyber-Enabled Distributed Computing and knowledge Discovery, September 2015, pp. 226-229, IEEE.
[22]. Yildrim, Hallac, I.R. Aydin.G and Tatar Y, (2015). “Running Genetic Algorithm on hadoop for solving high  dimensional optimization problems”. 9th International Conference (AICT), pp. 12-16, IEEE.
[23]. Pan and Ren-Hao, (2015). "Design of an NGS MicroRNA predictor using multilayer hierarchal MapReduce Framework”. Data Science and Advanced Analytics (DSAA), 2015, IEEE International Conference, pp. 1-8, France.
[24]. Milos Ivanovic, Visnja Simic, Boban Stojanovic, Ana Kaplarevic and Branko Marovic, (2014). “Elastic Grid Resources Provisioning with WoBinGo: A parallel framework for genetic algorithm based optimization”. Future Generation Computer Systems, Vol. 42, No. 2015, pp. 44-54.
[25]. Chengyu Hu, Jing Zhao, Xuesong Yan, Deze Zeng and Song Guo, (2015). “A MapReduce based Parallel Niche Genetic Algorithm for Containment Source Identification in Water Distributed Network”. Ad Hoc Networks, pp. 1-11.
[26]. Mashan A. Alshammari and El-Sayed M.El-alfy, (2015). “MapReduce Implementation for Minimum Reduct using Parallel Genetic Algorithm”. 6th International Conference on Information and Communication System , IEEE.
[27]. Andrea L. Halweg-Edward, William C Grau, James D Winkler, Andrew D. Garast and Rayan T. Gill, (2015). “The emergence commodity-scale genetic manipulation”. Chemical Biology, pp. 150-155.
[28]. David Camacho, (2015). “Bio-inspired Clustering: Basic Features and Future Trends in the Era of Big Data”. 2nd international Conference on Cybernetics (CYBCONF 2015), IEEE, Poland.
[29]. Yue-Jiao Gong, Wei-Neng chen, Zhi-Hui Zhan, Jun Zhang, Yun Li and Qingfu Zhang, (2015). “Distributed evolutionary Algorithm and their models: A Survey of State-of-the-art”. Applied Soft Computing, Vol. 34, pp. 286-300.
[30]. D.L. Gonzalez, and F.F. de Vega, (2007). “On the Intrinsic Fault-Tolerance Nature of Parallel Genetic Programming”. In : EUROMICRO International Conference on Parallel, Distributed and Network-Based Processing, pp. 450–458.
[31]. F. Herrera, and M. Lozano, (2000). “Gradual Distributed Real-Coded Genetic Algorithms”. IEEE Trans. Evol. Comput. Vol. 4, No. 1, pp. 43–63.
[32]. N. Melab, and E.-G. Talbi, (2010). “GPU-based Island Model for Evolutionary Algorithms”. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO), pp. 1089–1096.
[33]. J.J. Merelo-Guervos, A. Mora, J.A. Cruz, A.I. Esparcia-Alcazar, C. Cotta, (2012). “Scaling in Distributed Evolutionary Algorithms with Persistent Population”. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1–8.
[34]. L.d.P. Veronese, and R.A. Krohling, (2010). “Differential Evolution Algorithm on the GPU with C-CUDA”. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1–7.
[35]. S.M. Said, and M. Nakamura, (2012). “Parallel enhanced hybrid evolutionary algorithm for continuous function optimization”. In: International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, pp. 125–131.
[36]. B. Wu, G. Wu, and M. Yang, (2012). “A MapReduce Based Ant Colony Optimization Approach to Combinatorial Optimization Problems”. In: International Conference on Natural Computation (ICNC), pp. 728–732.
[37]. B. Yu, Z. Yang, X. Sun, B. Yao, Q. Zeng, and E. Jeppesen, (2011). “Parallel Genetic Algorithm in Bus Route Headway Optimization”. Appl.Soft Comput. Vol. 11, No. 8, pp. 5081–5091.
[38]. W. Yu,W. Zhang, (2006). “Study on function Optimization Based on Master-Slave Structure Genetic Algorithm”. In: International Conference on Signal Processing, Vol. 3, pp. 1–4.
[39]. J. Zhao, W. Wang, W. Pedrycz, and X. Tian, (2012). “Online Parameter Optimization-based Prediction for Converter Gas System by Parallel Strategies”. IEEE Trans. Control Syst. Technol. Vol. 20, No. 3, pp. 835–845.
[40]. C. Zhou, (2010). “Fast parallelization of differential Evolution Algorithm using MapReduce”. In: Proceedings th of the 12 Annual Conference on Genetic and Evolutionary Computation (GECCO), pp. 1113–1114.
[41]. W. Zhao, S. Alam, and H.A. Abbass, (2014). “MOCCA-II: A Multi-objective Co-operative Evolutionary Algorithm”. Appl. Soft Comput. Vol. 23, pp. 407–416.
[42]. W. Zhu, (2011). “Nonlinear Optimization with a Massively Parallel Evolution Strategy Pattern Search Algorithm on Graphics Hardware”. Appl. Soft Comput. Vol. 11, No. 2, pp. 770–1781.
[43]. X. Llora, A. Verma, R.H. Campbell, and D.E. Goldberg, (2010). “When Huge is Routine: Scaling Genetic Algorithms and Estimation of Distribution Algorithms Via Data Intensive Computing”. In: Parallel and Distributed Computational Intelligence, Springer, Berlin, Heidelberg, pp. 11–41.
[44]. J.J. Durillo, and A.J. Nebro, (2011). “JMetal: a Java Framework for Multi-objective Optimization”. Adv. Eng. Softw. Vol. 42, No. 10, pp. 760–771.
[45]. J. Ekanayake, S. Pallickara, and G. Fox, (2008). “MapReduce for Data Intensive Scientific Analyses”. eScience, 2008. eScience '08. IEEE Fourth International Conference, pp. 277–284.
[46]. T. Xia, (2008). “Large-scale sms messages mining based on map-reduce”. Computational Intelligence and Design, 2008, ISCID '08 International Symposium, Vol. 1, pp. 7–12.
[47]. H.-c. Yang, A. Dasdan, R.-L. Hsiao, and D. S. Parker, (2007). “Map-reduce-merge: simplified relational data processing on large clusters”. In SIGMOD '07: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, pp. 1029–1040, New York, NY, USA, ACM.
[48]. Fei Teng, and Doga Tuncay, "Genetic Algorithm using MapReduce runtimes". Proposal Document on salsahpc.indiana.edu.
[49]. Sukhmani Goraya, and Vikas Khullar, (2015). “Map- Reduce Synchronized and Comparative Queue Capacity Scheduler in Hadoop for Extensive Data”. IOSR Journals (IOSR Journal of Computer Engineering), pp. 64- 75.
[50]. Vikas Khullar and Sukhmani Goraya, (2015). “Enhancing Dynamic Capacity Scheduler for Data Intensive Jobs”. International Journal of Computer Applications, Vol. 121, No. 12, pp. 21-24.
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
USD EUR INR USD-ROW
Pdf 35 35 200 20
Online 35 35 200 15
Pdf & Online 35 35 400 25

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.