Zbieżność punktowa dyskretnego algorytmu mrówkowego : wyniki praktyczne

W artykule prezentujemy Dyskretny Algorytm Mrówkowy (DAS), będący modyfikacją klasycznego systemu mrówkowego sformułowanego przez M. Dorigo. Przedstawiamy kolejno definicję problemu optymalizacyjnego oraz podajemy szczegółowy opis składowych reguł działania metody DAS. Następnie wprowadzamy pojęcie algebraicznego modelu probabilistycznego dla opisu procesu ewolucji rozważanej heurystyki w ujęciu łańcuchów Markowa. Finalnym rezultatem pracy jest ustalenie zbieżności punktowej dyskretnego algorytmu mrówkowego oraz prezentacja wstępnych wyników praktycznych.

---

Discrete Ant System (DAS) algorithm, a modification of classical Ant System algorithm formulated by M. Dorigo, is presented. Definition of optimization problem and a detailed description of component rules of DAS method are given. Then a probabilistic algebraic model of DAS heuristic describing its evolution in terms of Markov chains is presented. The final outcome about a pointwise convergence of Discrete Ant System algorithm is established. In addition, preliminary practical results are introduced on the effectiveness of the DAS algorithm applied to the selected NP-complete problem.