Solving graph coloring problem with parallel evolutionary algorithms in a mesh model / Zbigniew Kokosiński, Piotr Domagała // W: FedCSIS : Position Papers of the 2014 Federated Conference on Computer ... więcej

Solving graph coloring problem with parallel evolutionary algorithms in a mesh model / Zbigniew Kokosiński, Piotr Domagała // W: FedCSIS : Position Papers of the 2014 Federated Conference on Computer Science and Information Systems, September 7-10, 2014, Warsaw, Poland [Dokument elektroniczny] / eds. Maria Ganzha, Leszek Maciaszek, Marcin Paprzycki. – Warszawa : Polskie Towarzystwo Informatyczne, 2014. – (Annals of Computer Science and Information Systems, ISSN 2300-5963 ; 3). – S. 21-28 : rys., tab. – Tryb dostępu: https://fedcsis.org/proceedings/2014/pliks/391.pdf. – Bibliogr. 40 poz., Abstr. – doi: 10.15439/2014F391. – ISBN 978-83-60810-60-6 (Web). – ISBN 978-83-60810-59-0 (USB)

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 ... więcej

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.