Wyniki wyszukiwania - Biblioteka Nauki

1

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

100%

Kadłuczka P.

|

2001

|

tom T. 5, z. 1/2

311-318

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.

2

Algorytm hybrydowy z długoterminową pamięcią częstotliwościową

63%

Chmiel W. , Kadłuczka P.

|

1999

|

tom T. 3, z. 1

59-70

PL

Artykuł prezentuje rezultaty prac nad algorytmami przybliżonymi realizującymi proces genetyczny poszukiwania, dostarczającymi rozwiązań dla zagadnień, w których zastosowanie metod dokładnych nie jest możliwe, ze względu na liczność przestrzeni rozwiązań. Zaprezentowany w artykule hybrydowy algorytm realizuje oryginalną metodę genetycznego przeszukiwania przestrzeni rozwiązań wykorzystującą "restart" algorytmu - w oparciu o tzw. długoterminową pamięć częstotliwościową. Został on stworzony dla możliwie najszerszej klasy problemów dyskretnych, należących do klasy zagadnień NP-trudnych (kwadratowy problem przypisania, zagadnienie kolorowania grafu, harmo-nogramowania, komiwojażera, podziału grafu oraz wiele innych ważnych zagadnień optymalizacji kombinatorycznej). Zastosowane ogólne metody różnicowania i intensyfikacji procesu poszukiwania rozwiązania pozwalają na lepsze przeszukiwanie przestrzeni rozwiązań, niezależnie od typu rozpatrywanego zagadnienia. Mechanizmy te, dzięki zastosowaniu pamięci długoterminowej, pozwalają zapobiec przedwczesnej zbieżności algorytmu do ekstremów lokalnych. Algorytm został przetestowany dla przykładowych zadań oraz wybranych zagadnień kombinatorycznych.

EN

The paper presents the results of computer investigation of approximate algorithm, performing evolutionary search process for problems computationally intractable with regard to size of solution space. The proposed hybrid algorithm implements a new original method of genetic search of solution space which consist in restarting the search algorithm and the use of long term frequently memory. This algorithm can be adapted to the wide instances of combinatorial optimization problems including the travelling salesman problem, quadratic assignments problem, graph coloring, production scheduling problems. The application of the universal method of diversification and intensification of search process allows the algorithm to search better the solution space, independently of a problem instance. The application of long term frequently memory in the investigated methods allows to avoid the coiwergence to local optima. The algorithm was tested for sample tasks and selected combi-natorial problems.

3

Zastosowanie transformacji permutacji do przestrzeni wektorowej w algorytmach ewolucyjnych

63%

Chmiel W. , Kadłuczka P.

|

2000

|

tom z. 131

37-47

PL

W pracy przedstawiono wyniki badań eksperymentalnych procesu optymalizacji realizowanego za pomocą algorytmu ewolucyjnego dla testowego zagadnienia przydziału z kwadratową funkcją celu. Opierając się na zagadnieniu porównano algorytm ewolucyjny korzystający z metod transformujących zagadnienie permutacyjne do postaci kombinacji z działającymi wyłącznie na permutacjach.

EN

This paper presents results of experimental examination of optimization process realized with the aid of genetic algorithm on the test example of quadratic assignment problem. The investigated genetic algorithm realizes original genetic search process. In this algorithm we introduce technique normally used to optimize objective functions of any kind in Cartesian space where derivatives are not available or impossible to determine.

4

Efektywność algorytmu ewolucyjnego wykorzystującego mechanizm różnicowania

51%

Chmiel W. , Kadłuczka P. , Jędrusik S.

|

2006

|

tom z. 143

33-44

PL

Artykuł prezentuje wyniki prac związanych z implementacją i badaniem efektywności algorytmu ewolucyjnego, wykorzystującego operatory różnicujące. Bazują one na warunkowej wartości oczekiwanej funkcji celu rozwiązań częściowo ustalonych. Badania testowe wykonano dla standardowych zadań testowych kwadratowego zagadnienia przydziału (QAP).

EN

The paper presents our work on implementation and evaluation of evolutionary algorithm using diversification operators. They are based on expected conditional value of objective function for partially fixed solutions. The experiments were performed for standard test problems of quadratic assignment problems (QAP).