Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Hybrid algorithm with long term frequently memory
Języki publikacji
Abstrakty
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.
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
Strony
59--70
Opis fizyczny
Bibliogr. 13 poz., rys., tab.
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGH1-0032-0003
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.