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

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.