Równoległe algorytmy genetyczne w zastosowaniu do problemu kolorowania wierzchołków grafu

• Autorzy: Kwarciany K. , Kokosiński Z.

Warianty tytułu

EN

Parallel genetic algorithm approach to graph coloring problem

• Języki publikacji: PL

Abstrakty

PL

W niniejszej pracy drogą symulacji komputerowej przebadano równoległe algorytmy genetyczne (PGA) w zastosowaniu do problemu kolorowania wierzchołków grafu (GCP). Spośród kilku modeli PGA różniących się sposobem zrównoleglenia obliczeń w algorytmie genetycznym, liczbą procesorów i strukturą ich połączeń, liczbą i rodzajem koewolujących populacji, sposobem wymiany informacji genetycznej pomiędzy populacjami itp. wybrano dwa: zrównoleglenie globalne (model master-slave) oraz statyczne podpopulacje z migracją (model wyspowy). Przeprowadzono analizę symulowanej pracy wybranych równoległych algorytmów genetycznych z nowymi operatorami krzyżowania, wykazując eksperymentalnie ich efektywność. Szczegółowe wnioski sformułowane w tej pracy mogą być pomocne przy projektowaniu nowych równoległych algorytmów genetycznych dla problemu GCP.

EN

In this paper we present results of our experiments with parallel genetic algorithms (PGAs) for graph coloring problem (GCP) that belongs to the class of NP-hard combinatorial optimizations problems. The PGAs' approach is based on co-evolution of a number of populations that exchange genetic information during the evolution process according to a communication pattern. We developed an original computer program PGA_for_GCP, which enables selection of various evolution models its parameters. In computer simulations reported in this paper we used two distinct models, namely the master-slave model and the migration model. In the first model we researched the efficiency of parallel model as a function of the number of slave processors. In the second model we investigated the influence of a migration scheme and a rnigration distance on the quality of the obtained solutions We analyzed also the case of evolution on isolated islands. In our experiments we used DIM. benchmark graphs and two new recombination operators for coloring chromosomes: SPPX (Product Partition Crossover) in which simple set operations and random mechanisms implemented, and CEX (Conflict Elimination Crossover) that is focused on the offspring quality. obtained results are promising and encourage future research focused on PGAs and new genetic operators for graph coloring problems.

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2004
• Tom: T. 5
• Strony: 747--754
• Opis fizyczny: Bibliogr. 22 poz., 3 rys., 2 tab.

Twórcy

autor

Kwarciany K.

• Wydział Inżynierii Elektrycznej i Komputerowej, Politechnika Krakowska

autor

Kokosiński Z.

• Wydział Inżynierii Elektrycznej i Komputerowej, Politechnika Krakowska

• Wydział Inżynierii Elektrycznej i Komputerowej, Politechnika Krakowska

Bibliografia

• [1] Alba E., Tomasini M.: Parallelism and evolutionary algorithms, IEEE Trans. Evol. Computing 6 (2002) No.5, s. 443-462.
• [2] Back T.: Evolutionary Algorithms in Theory and Practice, Oxford University Press (1996)
• [3] Croitoriu C., Luchian H., Gheorghies O., Apetrei A.: A new genetic graph coloring heuristic, Computational Symposium on Graph Coloring and Generalizations COLOR'02, w: Proc. Int. Conf. Constraint Programming CP'02 (2002)
• [4] Dorne R., Hao J. -K.: A new genetic local search algorithm for graph coloring. Int. Conf. Parallel Problem Solving from Nature PPSN'1998, w: Lecture Notes in Computer Science 1498 s. 745- 754., Springer-Verlag 1998.
• [5] Filho G.R., Lorena L.A.N.: Constructive genetic algorithm and column generation: an application to graph coloring, Proc. Asia Pacific Operarions Research Symposium APORS'2000.
• [6] Galinier Philippe, Hao Jin-Kao.: Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization 3, s. 379-397, Kluwer Academic Publishers 1999.
• [7] Garey M. R., Johnson D.S.: Computers and Intractability. A Guide to the Ttheory of NP-Completeness. W.H. Freeman and Co., San Francisco 1979.
• [8] Jensen T.R., Toft B.: Graph Coloring Problems, Wiley Interscience 1995.
• [9] Johnson D.S., Trick M.A.: Cliqu.es, Coloring and Satisfiability: Second DIMA.CS Implementation Challenge, DIMACS Series in Discr. Math. and Theor. Comp. Sc. Vol.26.1996.
• [10] Khuri S., Walters T. Sugono Y.: Grouping genetic algorithm for coloring edges of graph, Proc. 2000 ACM Symposium on Applied Computing (2000) s. 422-427
• [11] Kokosiński Z., Kołodziej M., Kwarciany K.: Parallel genetic algorithm for graph coloring problem, Int. Conference on Computational Science ICCS'2004, Kraków, Poland, w: Lecture Notes in Computer Science, Springer-Verlag 2004 (w druku)
• [12] Kołodziej M.: Algorytmy genetyczne dla problemu kolorowania krawędzi grafu. Praca magisterska, Politechnika Krakowska, Kraków 2003.
• [13] Kubale M.: Introduction to Computational Complexity and Algorithmic Graph Coloring, Gdańsk 1998.
• [14] Kubale M. (red.): Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT Warszawa 2002.
• [15] Kwarciany K.: Równolegle algorytmy genetyczne. Praca magisterska, Politechnika Krakowska, Kraków 2003.
• [16] Lorena L.A.N., Filho G.R.: Constructive genetic algorithm for graph coloring, Proc. Asia Pacific Operarions Research Symposium APORS'1997.
• [17] Nowostawski M., Poli R.: Parallel Genetic Algorithm Taxonomy. Proc. Third Intelligent Conference on Knowledge - based Inteligent Information Engineering Systems KES'99, Adelaide, Australia 1999.
• [18] Szyfelbein D.: Metaheuristyki w kolorowaniu grafów' w: Kubale M. (red.): Optymalizacja dyskretna. Modele i metody kolorowania grafów, s. 26-52, WNT, Warszawa 2002.
• [19] de Werra D.: Heuristics for graph coloring, w: Tinhofer G. et all. (eds.): Computational graph theory, Springer-Verlag (1990) s. 191-208.
• [20] http://mat.gsia.cmu.edu/COLOR/instances.html
• [21] ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/
• [22] http://mat.gsia.cmu.edu/COLORING03/