MoHPBGA: Multiobjective Hierarchical Population Balanced Genetic Algorithm using MapReduce

Abstract

Use of heuristic methods is common to find the solutions to the optimization problems for scientific and real time. Problems such as Travelling Salesman (TSP) require more accurate solution which is tried by various optimization methods. Research in this direction shows the use of Genetic algorithms (GA) as promising candidate and is preferred over other optimization methods. Firstly due to the use of large population and secondly large number of iterations GA tends to be more accurate but inefficient with respect to computation time. Variants of GA are formulated and experimented so as to take care of execution time. We present the review of approaches used to formulation of GA solutions mainly parallel GA (PGA), distributed GA (DGA) and hierarchical parallel GA (HPGA). Further this paper proposes Multi objective Hierarchical Population Balanced Genetic Algorithm (MoHPBGA) as the improved candidate which uses map reduce framework for efficient use of population mapping and synchronization of tasks.

References

• Bart Ian Rylander, “Computational Complexity and the Genetic Algorithm”, Doctoral Dissertation, University of Idaho Moscow, ID, USA @2001, ISBN: 0-493-33514-5.
• Chao Jin, Christian Vecchiola and Rajkumar Buyya, “MRPGA: An Extension of MapReduce for Parallelizing Genetic Algorithms”, in Proceedings of the 4th IEEE International Conference on e-Science 2008.
• D. Abramson and j. Abela, “A parallel Genetic Algorithm for Solving the School Timetabling Problem”, in Proceedings of the 15th Australian Computer Science Conference, Hobart, Feb 1992, pp 1-11.
• D. Lim, Y. Ong, Y. Jin, B. Sendhoff, and B. Lee, “Efficient Hierarchical Parallel Genetic Algorithms using Grid Computing”, in Proceedings of the Future Generation Computer System, 23(4):658–670, 2007.
• De Toro, F.; Ortega, J.; Fernandez, J.; Diaz, A.; “PSFGA: A Parallel Genetic algorithm for Multiobjective Optimization”, in Proceedings of the 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 2002.
• Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T., “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation 6(2) : 182-197, 2002.
• E.Alba and J.M.Troya, “A Survey of Parallel Distributed Genetic Algorithms”, Complexity 4(4), 31-52, 1999. John Wiley and Sons, Inc.
• E.Cant´u-Paz, “Efficient and Accurate Parallel Genetic Algorithms”, Kluwer Academic Publishers, Norwell, MA, USA, 2000, ISBN: 978-0-7923-7221-9.
• Erick Cant`u-Paz, “A Survey of Parallel Genetic Algorithms”, Calculateurs Paralleles, Reseaux et Systems Repartis, 10(2):141-171, 1998.
• Erick Cant`u-Paz, David E. Goldberg, “Are Multiple Runs of Genetic Algorithms Better than One?”, in Proceedings of the 2003 International Conference on Genetic and Evolutionary Computation (GECCO ’03).
• F.Herrera, M. Lozano, M. Lozano, “Hierarchical Distributed Genetic Algorithms”, Technical Report #DECSAI-97-01-03, Dept. Of Computer Science and Artificial Intelligence, University of Granada, Spain, 1997.
• Fonseca, C.M. and Fleming, P.J, “Multiobjective Genetic Algorithms”, in IEE Colloquium on Genetic Algorithms for Control Systems Engineering (Digest No. 1993/130), 1993.
• Gautam Roy, et al, “A Distributed Pool Architecture for Genetic Algorithms”, in Proceedings of the 2009 IEEE Conference on Evolutionary Computation (CEC 2009).
• Gong, Y., Fukunaga, A, “Distributed Island-Model Genetic Algorithms Using Heterogeneous Parameter Settings”, in Proceedings of the IEEE Congress on Evolutionary Computation (CEC), 2011.
• Horn, J., Nafpliotis, N., and Goldberg, D.E, “A Niched Pareto Genetic Algorithm for Multiobjective Optimization”, in Proceedings of the 1st IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, 1994.
• J. Dean and S. Ghemawat. “MapReduce: Simplified Data Processing on Large Clusters”, in Proceedings of the 6th Conference on Symposium on Systems Design and Implementation,OSDI ’04.
• J. Suh and D. Van Gucht, “Distributed Genetic Algorithms”, Tech. Report 225, Computer Science Department, Indiana University, Bloomington, 1987.
• Kelly Easton, Nemhauser George L., and Trick Michael A, “The Traveling Tournament Problem Description and Benchmarks”, in Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, CP’01.
• Knowles, J.D. and Corne, D.W., “Approximating the nondominated front using the Pareto archived evolution strategy”, Evolutionary Computation, 8(2):149-172, 2006.
• Lu, H. and Yen, G.G., “Rank-density-based multiobjective genetic algorithm and benchmark test function study”, IEEE Transactions on Evolutionary Computation, 7(4):325-343, 2003.
• M.Sefrioui,K.Srinivas and J.Periaux, “Aerodyanmic Shape Optimization using a Hierarchical Genetic Algorithm”, European Conference on Computational Methods in Applied Science and Engineering (ECCOMAS 2000).
• Muhammad Ali Ismail, “Parallel Genetic Algorithms (pgas): master slave paradigm approach using mpi”, E-Tech 2004.
• Murata, T. and Ishibuchi, H, “MOGA: multi-objective genetic algorithms”, in Proceedings of the 1995 IEEE International Conference on Evolutionary Computation, Perth.
• Petr Pospichal, Jiri Jaros, and Josef Schwarz, “Parallel Genetic Algorithm on the CUDA Architecture”, in Proceedings of the Applications of Evolutionary Computation, 6024 : 442-451, 2010.
• Ranieri Baraglia, Raffaele Perego, “Parallel Genetic Algorithms for Hypercube Machines”, in Proceedings of the 3rd international conference on vector and parallel processing VECPAR’98.
• Sarker, R., Liang, K.-H., and Newton, C., “A new multiobjective evolutionary algorithm”, European Journal of Operational Research 140(1):12-23, 2002.
• Schaffer, J.D, “Multiple Objective optimization with vector evaluated genetic algorithms”, in Proceedings of the International Conference on Genetic Algorithm and their applications. 1985.
• Srinivas, N. and Deb, K., “Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms”, Journal of Evolutionary Computation, 2(3): 221-248, 1994.
• T. Hiroyasu, M. Kaneko, K. Hatanaka, “A parallel genetic algorithm with distributed environment scheme”, in Proceedings of the 1999 IEEE International conference on Systems, Man, and Cybernetics (SMC '99).
• Verma, A. Llora, X. Goldberg, D.E. Campbell, R.H, “Scaling Genetic Algorithms Using MapReduce”, in Proceedings of the 9th International Conference on Intelligent Systems Design and Applications, ISDA '09.
• Wang, L.; Maciejewski, A.A.; Siegel, H.J.; Roychowdhury, V.P, “A comparative study of five parallel genetic algorithms using the traveling salesman problem”, in Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, 1998.
• Zdenek Konfrst, “Parallel Genetic Algorithms: Advances, Computing Trends, Applications and Perspectives”, in Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04).
• Zitzler, E. and Thiele, L., “Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach”, IEEE Transactions on Evolutionary Computation, 3(4):257-271, 1999.

Index Terms

Keywords