Hiperheurystyki w kolorowaniu grafów

• Autorzy: Dąbrowski J. , Obszarski P.

Warianty tytułu

EN

Hyperheuristics in graph coloring

• Języki publikacji: PL

Abstrakty

PL

Hiperheurystyki to jeden z nowych trendów w technice obliczeniowej. Można je zdefiniować jako algorytmy, które wykorzystują zdefiniowany zbiór prostych heurystyk do znalezienia przybliżonego rozwiązania. Celem algorytmu jest znalezienie takiej sekwencji uruchamiania tych prostych operacji, która będzie dawała najlepsze rozwiązanie dla danej instancji problemu lub danej klasy instancji problemu. W pracy zdefiniowano heurystyki dla problemu wierzchołkowego kolorowania grafów oraz przedstawiono algorytm genetyczny, w którym ewolucji podlegają sekwencje ich wyboru przy kolorowaniu zachłannym.

EN

Hyperheuristics are optimization algorithms that use sets of simple heuristic operations that can change the state of a solution. The goal of the algorithm is to find a good sequence of those operations that produces a good solution to the problem. This work presents low-level heuristics for the well known Graph Coloring Problem and a genetic algorithm that evolves sequences of choices for a greedy coloring algorithm.

Słowa kluczowe

PL

hiperheurystyki; opis algorytmu; wierzchołkowe kolorowanie grafów; algorytm genetyczny

EN

hyper-heuristics; low-level heuristics; genetic algorithm

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 13
• Strony: 443--448
• Opis fizyczny: Bibliogr. 5 poz., rys. tab.

Twórcy

autor

Dąbrowski J.

autor

Obszarski P.

• Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska

Bibliografia

• [1] Brelaz, D.: New Methods to Color the Vertices of a Graph, Communications of the ACM 22, s. 251 - 256, 1979.
• [2] Fang, H-L., Ross, P.M. i Corne, D. A Promising Hybrid GA/Heuristic Approach for Open-Shop Scheduling Problems w: Proceedings of ECAI 94: 11th European Conference on Artificial Intelligence, A. Cohn (ed), s. 590-594, John Wiley and Sons Ltd, 1994.
• [3] Kubale, M.: Introduction to Computational Complexity and Algorithmic Graph Coloring, Gdańskie Towarzystwo Naukowe, 1998.
• [4] Burke, E. i in. Hyper-heuristics: an Emerging Direction in Modern Search Technology, rozdział 16 w: Handbook of Metaheuristics, s. 457-474, Kluwer Academic Publishers, 2003.
• [5] ftp://dimacs. rutgers.edu/ pub/ challenge/ graph/benchmarks/ color/