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

• Autorzy: Rembelski P.

Warianty tytułu

EN

Pointwise convergence of discrete ant system algorithm with practical results

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

dyskretny algorytm mrówkowy; DAS; system mrówkowy; algebraiczny model probabilistyczny; łańcuchy Markowa

• Wydawca: Wyższa Szkoła Informatyki i Umiejętności
• Czasopismo: Zeszyty Naukowe Wyższej Szkoły Informatyki
• Rocznik: 2012
• Tom: Vol. 11, Nr 1
• Strony: 122--137
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Rembelski P.

• Polsko-Japońska Wyższa Szkoła Technik Komputerowych Wydział Informatyki,

Bibliografia

• [1] Dorigo M., Optimization, learning and natural algorithms, Ph. D. disseration, 1992.
• [2] Dorigo M., Birattari M. Stutzle T, Ant Colony Optimization, IEEE Computional Intelligence Magazine, XI 2006.
• [3] Dorgio M., Gambardella L. M., Ant Colony System: A cooperative learing approach to the TSP problem, IEEE Transaction on Evolutionary Computation, vol. 1, 1997.
• [4] Dorigo M, Gambardella L. M., Solving symmetric and asymmetic TSPs by ant colonies, IEEE International Conference on Evolutionary Computation, 1996.
• [5] Dorigo M., Maniezzo V., Colorni A., Ant System: optymization by colony of cooperating agents, IEEE Transactions on Systems, Man and Cybernetics, vol. 26, 1996.
• [6] Dorigo M., Stutzle T., A short convergence proof for a class of ACO algorithms, IEEE Transactions on Evolutionary Computation, vol 6, 2002.
• [7] Gutjahr W. J., ACO algorithms with guaranteed convergence proof to the optimal solution, Information Processing Letters, vol 82, 2002.
• [8] Lasota A., Asymptotyczne własności półgrup operatorów Markowa, Matematyka Stosowana. Matematyka dla Społeczeństwa, 3 (45), 2002, 39-51.
• [9] Kosiński W., Kotowski S., Limit Properties of Evolutionary Algorithms, Chapter 1 in: Advances in Evolutionary Algorithms, W. Kosiński (Ed.), IN-TECH 2008, pp. 1-28, ISBN 978-953-7619-11-4.
• [10] Rembelski P., Model teoretyczny algorytmu mrówkowego SAS, Proceedings of the XII International Ph.D. Workshop, OWD 2010 (strony 37-42).
• [11] Rembelski P. Markowowski model dyskretnego algorytmu mrówkowego, Matematyka Stosowana. Matematyka dla Społeczeństwa, PTM, Warszawa, 13 (54), 2011.
• [12] Rudnicki R., On asymptotic stability and sweeping for Markov operators, Bull. Polish Acad. Sci. Math., 43 (1995), 245-262.
• [13] Socała J., Kosiński W., Kotowski S., O asymptotycznym zachowaniu prostego algorytmu genetycznego, Matematyka Stosowana. Matematyka dla Społeczeństwa, PTM, Warszawa, 6 (47), 2005, 70-86.