Solving Graph Coloring Problem with Parallel Evolutionary Algorithms in a Mesh Model
Zbigniew Kokosiński, Piotr Domagała
DOI: http://dx.doi.org/10.15439/2014F391
Citation: Position Papers of the 2014 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 3, pages 21–28 (2014)
Abstract. In this paper a parallel evolutionary algorithm (PEA) for coloring graph vertices is investigated. In the algorithm we apply a diffusion model of parallelism (DM). Evolutionary computations are performed in a regular mesh with either a constant size global population or a constant subpopulation in a single node. The performance of the PEA-DM is verified by computer experiments on standard DIMACS graph coloring instances. For recombination well known crossover and mutation operators are chosen. Selection mechanisms include standard roulette and tournament. The obtained results are compared with a classical evolutionary algorithm. It is possible to define dimensions of the rectangular mesh and two types of additional local connections: boundary enclosures (cyclic mesh) and diagonal links. The problem of optimal selection of the mesh configuration as well as global population and subpopulation sizes is adressed.