The paper describes an application of Parallel Simulated Annealing (PSA) for solving one of the most studied NP-hard optimization problems: Graph Coloring Problem (GCP). Synchronous master-slave model with periodic solution update is being used. The paper contains description of the method, recommendations for optimal parameters settings and summary of results obtained during algorithm’s evaluation. A comparison of our novel approach to a PGA metaheuristic proposed in the literature is given. Finally, directions for further work in the subject are suggested.
Operational Program Digital Poland, 2014-2020, Measure 2.3: Digital accessibility and usefulness of public sector information; funds from the European Regional Development Fund and national co-financing from the state budget.
May 10, 2021
Sep 17, 2020
Bartkowiak, Anna (1930– ) Łukasik, Szymon Chwistecki, K. Mrukowicz, M.