CFP last date
20 June 2024
Reseach Article

Genetic Algorithm: Simple to Parallel Implementation using MapReduce

Published on September 2016 by Girdhar Gopal, Rakesh Kumar, Naveen Kumar
Recent Innovations in Computer Science and Information Technology
Foundation of Computer Science USA
RICSIT2016 - Number 2
September 2016
Authors: Girdhar Gopal, Rakesh Kumar, Naveen Kumar
b80e3761-296c-4e1c-9fe1-56d284aef13e

Girdhar Gopal, Rakesh Kumar, Naveen Kumar . Genetic Algorithm: Simple to Parallel Implementation using MapReduce. Recent Innovations in Computer Science and Information Technology. RICSIT2016, 2 (September 2016), 12-15.

@article{
author = { Girdhar Gopal, Rakesh Kumar, Naveen Kumar },
title = { Genetic Algorithm: Simple to Parallel Implementation using MapReduce },
journal = { Recent Innovations in Computer Science and Information Technology },
issue_date = { September 2016 },
volume = { RICSIT2016 },
number = { 2 },
month = { September },
year = { 2016 },
issn = 0975-8887,
pages = { 12-15 },
numpages = 4,
url = { /proceedings/ricsit2016/number2/26190-2026/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 Recent Innovations in Computer Science and Information Technology
%A Girdhar Gopal
%A Rakesh Kumar
%A Naveen Kumar
%T Genetic Algorithm: Simple to Parallel Implementation using MapReduce
%J Recent Innovations in Computer Science and Information Technology
%@ 0975-8887
%V RICSIT2016
%N 2
%P 12-15
%D 2016
%I International Journal of Computer Applications
Abstract

Simple Genetic Algorithms are used to solve optimization problems. Genetic Algorithm also comes with a parallel implementation as Parallel Genetic Algorithm (PGA). PGA can be used to reduce the execution time of SGA and also to solve larger size instances of problems. In this paper, different implementations for PGA have been discussed with their frameworks. In this implementation, all PGA are based on a single SGA framework. These are executed on a parallel machine and tested on some benchmark problem instances of Traveling Salesman problem (TSP) from TSPLIB. TSPLIB is a well known library for data set of benchmark problem instances. A basic framework has been proposed for implementing PGA on today's parallel computers.

References
  1. Holland J. , (1975), Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor.
  2. Rakesh Kumar, Girdhar Gopal, Rajesh Kumar, (2013), "Hybridization in Genetic Algorithms", International Journal of Advanced Research in Computer Science and Software Engineering (IJARCSSE), Vol-3, Issue-4, pp 403-409.
  3. Goldberg D. E. , (1989), Genetic algorithms in search, optimization, and machine learning, Addison Wesley Longman, Inc. , ISBN 0-201- 15767-5.
  4. Rakesh Kumar, Girdhar Gopal, Rajesh Kumar, (2013), "Novel Crossover Operator for Genetic Algorithm for Permutation Problems", International Journal of Soft Computing and Engineering (IJSCE), Vol. 3, Issue-2, pp 252-258.
  5. Moscato P. , Cotta C. , (2003), "A gentle introduction to memetic algorithms", Handbook of Metaheuristics, pp 105-144.
  6. P. Jog, J. Y. Suh, and D-, Van Gucht, "The effects of population size, heuristic crossover and local improvement on a genetic algorithm for the traveling salesman problem," 3rd Int'l Conference on Genetic Algorithms, july 1989, pp. 110-115
  7. Bosworth Jack, Foo Norman, and Zeigler Bernard P. (1972), "Comparison of Genetic Algorithms with Conjugate Gradient Methods". Technical Report 00312-1-T, University of Michigan: Ann Arbor, MI, USA.
  8. Bethke Albert Donally. (1980), "Genetic Algorithms as Function Optimizers". PhD thesis, University of Michigan: Ann Arbor, MI, USA.
  9. Brady R. M. (1985), "Optimization Strategies Gleaned from Biological Evolution. " Nature, 317(6040): 804–806, doi: 10. 1038/317804a0.
  10. Sinha Abhishek and Goldberg D. E. (2003), "A Survey of Hybrid Genetic and Evolutionary Algorithms". IlliGAL Report 2003-2004, Illinois Genetic Algorithms Laboratory (IlliGAL), Department of Computer Science, Department of General Engineering, University of Illinois at Urbana-Champaign: Urbana-Champaign, IL, USA.
  11. Dean J. , Ghemawat S. , "MapReduce: simplified data processing on large clusters", Communications of ACM51 (2008) 107–113.
Index Terms

Computer Science
Information Sciences

Keywords

Optimization Parallel Genetic Algorithm Simple Genetic Algorithm Traveling Salesman Problem