Efficacy of Different Strategies in Graph Coloring with Parallel Genetic Algorithms

Authors

  • Fardin Esmaeeli Sangari Sama technical and vocational training college, Islamic Azad University, Urmia branch, Urmia, Iran
  • Mehrdad Nabahat Sama technical and vocational training college, Islamic Azad University, Urmia branch, Urmia, Iran

Keywords:

Graph Coloring Problem, Migration Model, Migration Strategy, Parallel Genetic Algorithm

Abstract

In this paper a new parallel genetic algorithm is proposed to observe efficacy of different strategies for k-graph coloring problem. In the algorithm we have applied a coarse-grained model of parallelism, along with two new algorithms for crossover and mutation are represented: FCX and Fmm. these algorithms compared with CEX�s First Fit and Transposi-tion mutation operators. In our experiments, we observed that different strategies what role have in finding solutions. In computer simulations of PGA we used DIMACS benchmark.

References

Erick Cantu-Paz David E. Goldberg, “Efficient parallel genetic algorithms: theory and practice”, J. Computer Methods in Ap-plied Mechanic and Engineering. 186, 2000, pp.221-238

Zbigniew Kokosinski, Marcin Kolodziej, Krzysztof Kwarciany, “Parallel Genetic Algorithm for Graph Coloring Problem”, ICCS 2004, LNCS 3036, pp. 215–222

Saeed Amizadeh, Farzad Rastegar, Caro Lucas, “Incorporating Heuristics In Evolutionary Optimization”, J. Intelligent Infor-mation Technology Computing, Vol.1, No.2, 2006, pp. 259-270

Zbigniew Kokosinski, Krzysztof Kwarciany, Marcin Kolodziej, “Efficient Graph Coloring With Parallel Genetic Algorithms”, J. Computing and Informatics, Vol. 24, 2005, pp. 1001-1025

Z.G. Wang, Y.S. Wong, M. Rahman, "Development of a parallel optimization method based on genetic simulated annealing algo-rithm", J. Parallel Computing, Vol. 31 ,2005, pp. 839–857

Erick Cantu-Paz, "Migration Policies, takeover Times in parallel genetic algorithms", Department of computer science and Illinois Genetic Algorithm Laboratory, 1999

http://mat.gsia.cmu.edu/COLOR/instances.html

ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/

http://mat.gsia.cmu.edu/COLORING03/

Downloads

Published

2014-05-31

How to Cite

[1]
F. E. Sangari and M. Nabahat, “Efficacy of Different Strategies in Graph Coloring with Parallel Genetic Algorithms”, Int. J. Comp. Sci. Eng., vol. 2, no. 5, pp. 138–141, May 2014.

Issue

Vol. 2 No. 5 (2014): IJCSE May Edition

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.