Algorytm genetyczny do rozwiązywania uogólnionego, wielokryterialnego zagadnienia podziału grafu.

Kadłuczka, P.

Artykuł - szczegóły

Tytuł artykułu

Algorytm genetyczny do rozwiązywania uogólnionego, wielokryterialnego zagadnienia podziału grafu.

Autorzy

Kadłuczka P.

Identyfikatory

Warianty tytułu

Genetic algorithm for generalized multicriterial, graph partitioning problem.

Konferencja

XI Krajowa Konferencja Automatyzacji Dyskretnych Procesów Przemysłowych, Zakopane 24-27.09.1998

Języki publikacji

Abstrakty

W artykule zaprezentowano algorytm genetyczny dla uogólnionego, wielokryterialnego zagadnienia podziału grafu (GGP). Plega ono na podziale zbioru wierzchołków nieskierowanego, ważonego grafu na m rozłącznych zbiorów, tzw. punktów skupienia, w celu optymalizacji funkcji celu, przy równoczesnej optymalizacji ich rozmiaru. W algorytmie zastosowano specjalną formalizację Pareto. Rozwiązania są odwzorowywane w przestrzeni 2D Euklidesa, gdzie pierwszą współrzędną obszaru jest rozmiar największego punktu skupienia (suma wag węzłów), a drugą współrzędną wartość funkcji celu (całkowita suma wag krawędzi należących do punktów skupienia). W artykule przedstawiono model matematyczny zagadnienia, opis zastosowanego algorytmu genetycznego, wyniki badań komputerowych dla standardowych zadań tekstowych oraz wynikające z nich wnioski.

A genetic algorithm for the generalized multicriterial graph partitioning problem (GGP) is presented. The GGP problem consists in partitioning the set of nodes of an undirected weighted graph into m disjoint subsets of bounded size (called clusters), such that the objective function is maximized whereas the size of clusters is minimized. In the presented approach the specific formalization of Pareto set was applied. The solutions are projected into to two dimensional Euclidean space where the first coordinate is the maximal cluster size (the sum of weights of nodes), the second is the value objective function (the sum of edge weights in a cluster). The paper presents the mathematical formalization of the problem, applied genetics algorithm and the results of computer experiments for the standard test cases.

Słowa kluczowe

algorytm genetyczny grafy GGP Generalized Graph Partitioning

Wydawca

Wydawnictwo Politechniki Śląskiej

Czasopismo

Zeszyty Naukowe. Automatyka / Politechnika Śląska

Rocznik

1998

Tom

z. 125

Strony

145--153

Opis fizyczny

Bibliogr. 16 poz.

Twórcy

autor

Kadłuczka P.

Akademia Górniczo-Hutnicza, Kraków

Bibliografia

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BSL2-0002-0017