Open Access   Article Go Back

Efficacy of Different Strategies in Graph Coloring with Parallel Genetic Algorithms

F.E. Sangari1 , M. Nabahat2

Section:Research Paper, Product Type: Journal Paper
Volume-2 , Issue-5 , Page no. 138-141, May-2014

Online published on May 31, 2014

Copyright © F.E. Sangari, M. Nabahat . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

XML View
PDF Download

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: F.E. Sangari, M. Nabahat, “Efficacy of Different Strategies in Graph Coloring with Parallel Genetic Algorithms,” International Journal of Computer Sciences and Engineering, Vol.2, Issue.5, pp.138-141, 2014.

MLA Style Citation: F.E. Sangari, M. Nabahat "Efficacy of Different Strategies in Graph Coloring with Parallel Genetic Algorithms." International Journal of Computer Sciences and Engineering 2.5 (2014): 138-141.

APA Style Citation: F.E. Sangari, M. Nabahat, (2014). Efficacy of Different Strategies in Graph Coloring with Parallel Genetic Algorithms. International Journal of Computer Sciences and Engineering, 2(5), 138-141.

BibTex Style Citation:
@article{Sangari_2014,
author = {F.E. Sangari, M. Nabahat},
title = {Efficacy of Different Strategies in Graph Coloring with Parallel Genetic Algorithms},
journal = {International Journal of Computer Sciences and Engineering},
issue_date = {5 2014},
volume = {2},
Issue = {5},
month = {5},
year = {2014},
issn = {2347-2693},
pages = {138-141},
url = {https://www.ijcseonline.org/full_paper_view.php?paper_id=175},
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
UR - https://www.ijcseonline.org/full_paper_view.php?paper_id=175
TI - Efficacy of Different Strategies in Graph Coloring with Parallel Genetic Algorithms
T2 - International Journal of Computer Sciences and Engineering
AU - F.E. Sangari, M. Nabahat
PY - 2014
DA - 2014/05/31
PB - IJCSE, Indore, INDIA
SP - 138-141
IS - 5
VL - 2
SN - 2347-2693
ER -

VIEWS PDF XML
3596 3438 downloads 3641 downloads
  
  
           

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.

Key-Words / Index Term

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

References

[1] Erick Cantu-Paz David E. Goldberg, �Efficient parallel genetic algorithms: theory and practice�, J. Computer Methods in Applied Mechanic and Engineering. 186, 2000, pp.221-238
[2] Zbigniew Kokosinski, Marcin Kolodziej, Krzysztof Kwarciany, �Parallel Genetic Algorithm for Graph Coloring Problem�, ICCS 2004, LNCS 3036, pp. 215�222
[3] Saeed Amizadeh, Farzad Rastegar, Caro Lucas, �Incorporating Heuristics In Evolutionary Optimization�, J. Intelligent Information Technology Computing, Vol.1, No.2, 2006, pp. 259-270
[4] Zbigniew Kokosinski, Krzysztof Kwarciany, Marcin Kolodziej, �Efficient Graph Coloring With Parallel Genetic Algorithms�, J. Computing and Informatics, Vol. 24, 2005, pp. 1001-1025
[5] 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
[6] Erick Cantu-Paz, "Migration Policies, takeover Times in parallel genetic algorithms", Department of computer science and Illinois Genetic Algorithm Laboratory, 1999
[7] http://mat.gsia.cmu.edu/COLOR/instances.html
[8] ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/
[9] http://mat.gsia.cmu.edu/COLORING03/