The use of genetic algorithm to solve the problem of graph vertex coloring

W niniejszej pracy zostało poruszone zagadnienie grafów i ich kolorowania w kontekście wykorzystania algorytmu genetycznego i algorytmu sekwencyjnego SL.W ramach pracy zaimplementowane zostały w języku Python algorytmy SL i genetyczny rozwiązujące problem kolorowania grafu. Przeprowadzone badania i otrzymane na ich podstawie wyniki umożliwiły porównanie obu algorytmów i wyostrzenie ich słabych i mocnych stron. Główny wniosek to brak jednoznacznego faworyta w kwestii ogólnego działania. Otóż ani algorytm genetyczny ani algorytm sekwencyjny SL nie spełniają w pełni stawianych im wymogów. Pierwszy z nich wykazuje natomiast pewien potencjał, który daje nadzieję udoskonalenia jego pracy, w związku z czym przejawia pewną przewagę względem drugiego badanego algorytmu.

The issue of graphs and their coloring in the context of using the genetic algorithm and the sequential algorithm SL is discussed in this monography. As part of the thesis, application solving graph coloring problem using python was implemented. The research and the results obtained based on it made it possible to compare both algorithms and sharpen their strengths and weaknesses. The main conclusion is the lack of a clear favorite.Neither the genetic algorithm nor the sequential algorithm SL fully meet the requirements set for them. The first of them, however, shows some potential that gives hope for improving his work, and therefore has a certain advantage over the second algorithm under study.