Algorytm memetyczny do rozwiązywania uogólnionego zagadnienia podziału grafu

• Autorzy: Kadłuczka, P.

Warianty tytułu

EN

Memetic algorithm for generalized graph partitioning problem

• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowano algorytm memetyczny (ang. memetic algorithm - MA) dla uogólnionego zagadnienia podziału grafu (GGP). MA jest heurystyką do rozwiązywania kombinatorycznych problemów optymalizacyjnych, bazującą na populacji, bliską algorytmom genetycznym (GAs). Inspirację zaczerpnięto z pojęcia meme, które określa jednostkę informacji powielającą się samoistnie przy wymianie idei między ludźmi. MA odzwierciedla kulturową ewolucję, w odróżnieniu od biologicznej. Memetyczna ewolucja może występować w kombinacji z algorytmami genetycznymi, strategiami przeszukiwania lokalnego, takimi jak przeszukiwanie lokalnego sąsiedztwa lub symulowane wyżarzanie. Metoda ta okazała się efektywnym podejściem do rozwiązywania różnych problemów optymalizacji kombinatorycznej : TSP, QAP, NK Landscapes i innych. W artykule podjęto próbę zaadaptowania tej metody łącznie z algorytmem genetycznym dla uogólnionego zagadnienia podziału grafu. GGP polega na podziale zbioru wierzchołków nieskierowanego, ważonego grafu na m. rozłącznych podzbiorów, tzw. punktów skupienia, w celu optymalizacji funkcji celu, przy równoczesnym ograniczeniu ich rozmiaru. Zagadnienie to jest z jednej strony NP--trudne, a z drugiej modeluje wiele ważnych praktycznych sytuacji decyzyjnych (np. problemy przechowywania i przetwarzania dużych programów komputerowych w rozproszonych systemach obliczeniowych lub systemach wieloprocesorowych). Na wstępie przedstawiono model matematyczny zagadnienia, będącego uogólnieniem klasycznego zagadnienia podziału grafu (GP). Kolejny rozdział zawiera opis algorytmu memetycznego, użytych mechanizmów włączonych do bazowego algorytmu genetycznego. Następnie przedstawiono wyniki badań komputerowych powyższego algorytmu dla zadań testowych w zestawieniu z wynikami uzyskanymi za pomocą algorytmu genetycznego i hybrydowego oraz wynikające z nich wnioski.

EN

The paper considers the memtic algorithm (MA) for generalized graph partitioning problem (GGP). MAs are population based heuristic for combinatorial optimization problems closely related to genetic algorithms (GAs). They are inspired by the notion of a meme, defined as a unit of information that reproduces itself when people exchange ideas. Thus, memetic algorithms resemble the cultural evolution instead of the biological evolution. Memetic evolution can be combined with GAs, local search approaches as: the neighbour search or simulated annealing. The method was proved to be efficient while solving various combinatorial optimisation problems: TSP, QAP, NK Landscapes and other. This paper presents a new algoritm combining the MA and GA aproaches that is used for solving a generalized graph partitioning problem. GPP consists in partitioning the nodes of a weighted graph into m disjoint subsets of bounded size, such that an objective function connected with the weights of the graph edges is maximized. This a NP-hard problem that models many important practical decision problems (e.g. processing large computer programs in distributed or multiprocesor computing systems). The paper is organized as folows: first section defines the mathematiac model of the problem beinng the generalisation of the classical graph partitioning problem. Next sections describe the memetic algorithm and the mechanisms introduced to basic GA. Final section present the results of computer experiments and compares them with the results obtained by application of genetic and hybrid algorithms.

Słowa kluczowe

PL

algorytm memetyczny; algorytm GLS

EN

memetic algorithm; GLS algorithm

• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2001
• Tom: T. 5, z. 1/2
• Strony: 311-318
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Kadłuczka, P.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie