Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: algorytm memetyczny

Sortuj według:

Ogranicz wyniki do:

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

100%

Kadłuczka P.

2001

tom T. 5, z. 1/2

311-318

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.

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.

Równoległy heurystyczny algorytm dla rozwiązywania problemu trasowania pojazdów z oknami czasowymi

75%

Nalepa J. , Czech Z.

2012

tom Vol. 33, nr 1

91-106

W niniejszej pracy został przedstawiony równoległy heurystyczny algorytm dla rozwiązywania problemu trasowania pojazdów z oknami czasowymi. W pierwszej fazie jest minimalizowany rozmiar floty, a w drugiej fazie całkowita przebyta odległość. Celem pracy jest porównanie jakości rozwiązań otrzymanych za pomocą algorytmu sekwencyjnego oraz równoległego w pierwszej fazie. Przeanalizowany został wpływ zróżnicowania populacji i generowania rozwiązań potomnych na jakość rozwiązań wraz z przyspieszeniami dla algorytmu memetycznego drugiej fazy. Jakość rozwiązań jest oceniana na podstawie najlepszych obecnie znanych wyników dla problemów testowych Gehringa i Hombergera.

The following article presents a parallel heuristic algorithm to solve the vehicle routing problem with time windows (VRPTW). The fleet size is minimized in the first phase and the traveled distance in the second one. The objective is to compare the accuracy of solutions obtained by the sequential and the parallel heuristics in the first phase. The influence of the population diversification and child generation on the accuracy is analyzed together with the speedups for the memetic algorithm in the second phase. The accuracy of solutions is defined as their proximity to the best known solutions of Gehring and Homberger’s benchmarking tests.