BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Wojnarowski Józef, Zawiślak Stanisław, Kozik Szymon, Frej Grzegorz
Tytuł
K-Partitioning of Graph by Means of Evolutionary Algorithm
K-podział grafu za pomocą algorytmu ewolucyjnego
Źródło
Badania Operacyjne i Decyzje, 2003, nr 3, s. 91-107, bibliogr. 17 poz.
Operations Research and Decisions
Słowa kluczowe
Algorytmy, Grafy, Programowanie genetyczne
Algorithms, Graphs, Genetic programming
Uwagi
streszcz., summ.
Abstrakt
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.

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.
Dostępne w
Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka Szkoły Głównej Handlowej
Biblioteka Główna Uniwersytetu Ekonomicznego w Katowicach
Biblioteka Główna Uniwersytetu Ekonomicznego w Poznaniu
Biblioteka Główna Uniwersytetu Ekonomicznego we Wrocławiu
Bibliografia
Pokaż
  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.
Cytowane przez
Pokaż
ISSN
1230-1868
Język
eng
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu