K-Partitioning of Graph by Means of Evolutionary Algorithm

• Autorzy: Józef Wojnarowski , Stanisław Zawiślak , Szymon Kozik , Grzegorz Frej

Warianty tytułu

K-podział grafu za pomocą algorytmu ewolucyjnego

• Języki publikacji: EN

Abstrakty

EN

The problem of graph k-partitioning has been considered in the paper. The various interpretations of this problem have been listed. Besides some heuristic methods described in references, the evolutionary approach was proposed. It is the generalisation of the problem of graph bisection. The plain evolutionary algorithms are not so robust in this case as those for the bisection. New genetic operations have been considered which improve the behaviour of the computer program written on the basis of the algorithm proposed. The results of analysis are given.

Omówiono problem k-podziału grafu podając różne interpretacje tego zagadnienia oraz listę artykułów naukowych z tego zakresu. Oprócz algorytmów heurystycznych, opisanych w wybranych pozycjach literatury, rozważa się także ostatnio zastosowane algorytmy ewolucyjne. Problem podziału grafu G (V, E) polega na podziale zbioru jego wierzchołków na dwa lub więcej rozłącznych podzbiorów. Następnie rozważa się krawędzie łączące wygenerowane (na tych podzbiorach zbioru V) podgrafy grafu G. Problemem jest taki podział zbioru V k podzbiorów (k-podział), aby liczba krawędzi łączących te podzbiory była minimalna. Problem ten ma związek z wieloma innymi zagadnieniami z zakresu matematyki dyskretnej, jak na przykład: dekompozycją zadania optymalizacji, zamianą dowolnej macierzy w macierz blokową, projektowaniem układów elektronicznych tzw. VLSI. Do rozwiązania wielu z tych zagadnień stosowano różne algorytmy heurystyczne. Algorytmy ewolucyjne mają tę zaletę, iż są ogólne i unika się wnikania w szczegóły zadania. Początkowo stosowano je do problemu 2-podziału, a następnie uogólniono na k-podział. Algorytm ewolucyjny w przypadku k-podziału nie działa tak skutecznie jak dla podstawowego problemu. Rozważano pewne zmodyfikowane operacje genetyczne, które poprawiają skuteczność opracowanego algorytmu. Napisano programy komputerowe, które przetestowano na przykładowych grafach. Zamieszczono wybrane wyniki i ich analizę. Rozważano 2-, 3- oraz 6-podział, a wyniki pochodzą z różnych wersji programu. W przypadku 6-podziału nie zawsze znajdowane jest rozwiązanie optymalne. Jest to cecha algorytmów ewolucyjnych - w swej istocie losowego przeszukiwania. Prowadzone są prace nad dalszym ulepszeniem algorytmu i programu.

Słowa kluczowe

EN

Algorithms; Graphs; Genetic programming

PL

Algorytmy; Grafy; Programowanie genetyczne

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2003
• Numer: nr 3
• Strony: 91--107

Twórcy

autor

Józef Wojnarowski

autor

Stanisław Zawiślak

autor

Szymon Kozik

autor

Grzegorz Frej

Bibliografia

• [1] CHMIEL W., KADŁUCZKA P., Special genetic operators for the problem of graph partitioning, Algorytmy Ewolucyjne i Optymalizacja Globalna, Proceedings of 'IV Krajowa Konferencja', Politechnika Warszawska, 37-44, Warszawa 2000.
• [2] ELSNER U., Graph Partitioning. A survey, Preprint SFB393/97-27, TU Chemnitz, 1997.
• [3] FALKNER J., RENDL F., WOLKOWICZ H., A computational study of graph partitioning, Mathematical Programming, Vol. 66, 211-239, 1994.
• [4] GOLDSCHMIDT O., HOCHBAUM D., A polynomial algorithm for the k-cut problem for fixed k, Mathematics and Operations Research, Vol. 19, No. 1, 24-37, 1994.
• [5] HE G., LIU J., ZHAO C, Approximation algorithms for some graph partitioning problems, Journal of Graph Algorithms and Applications, Vol. 4, No. 2, (2000), 1-11.
• [6] JANKOWIAK M., Application of an algorithm to symmetrical TSP, Software 2.0, No. 2, 58-63, 2003.
• [7] KERIGHAM B., LIN S., An efficient heuristic procedure for partitioning graphs, The Bell System Technical Journal, Vol. 29, No. 2, 291-307, 1970.
• [8] KADŁUCZKA P., WALA K., Tabu search and genetic algorithms for the generalised graph partitioning problem. Control and Cybernetics, Vol. 24, No. 4, 459-476, 1995.
• [9] von LASZEWSKI G., Intelligent structural operators for the k-way graph partitioning problem, Proceedings of 4th Inter. Congr. on Genetic Algorithms, 1991.
• [10] LEE J.G., VOGT W.G., MICKLE M.H., Optimal Decomposition of Large-Scale Networks, IEEE Trans. on System, Man and Cybernetics, Vol. SMC-9, No. 7 (1979), 369-375.
• [11] LIN-MING JIN, SHU-PARK CHAN, A genetic approach for network partitioning, Int. J. Computer Math., Vol. 42, 47-60, 1992.
• [12] Discrete Optimisation. Models and methods of graphs colouring (in Polish), Editor M. Kubale, WNT, Warszawa 2002.
• [13] TOULOUSE M., THULASIRAMAN K., GLOVER F., Multi-level Co-operative Search: A new paradigm for combinatorial optimisation and an application to graph partitioning, Editors P. Amestoy et al. Euro-Par '99, 533-542, 1999.
• [14] WOJNAROWSKI J., ZAWIŚLAK S., ZIEMSKA I., Application of graphs in decomposition of optimisation problem (in Polish), Proceedings of Conference „Polioptymalizacja i CAD", Politechnika Koszalińska, Koszalin (1999), 35-36.
• [15] WOJNAROWSKI J., ZAWIŚLAK S., Evolutionary Algorithm Applied for Graph Partitioning (in Polish), [in:] 'Polioptymalizacja i Komputerowe Wspomaganie Projektowania' (ed. W. Tarnowski, T. Kiczkowiak) WNT, Warszawa 2002, 277-284.
• [16] WOJNAROWSKI J., ZAWIŚLAK S., Application of evolutionary algorithms to graph partitioning problem, Book of Abstracts of the Annual Scientific Conference GAMM 2002, Augsburg, Germany, 183, 2002.
• [17] ZAWIŚLAK S., ZIEMSKA I., Graph theoretical approach to decomposition problem in optimal design (in Polish), Politechnika Łódzka, Bielsko-Biała, (1999), 159-161.