Markowski model dyskretnego algorytmu mrówkowego

• Autorzy: Rembelski P.
• Języki publikacji: PL

Abstrakty

PL

Algorytm inspirowany naturą zaproponowany przez M. Doriego został w pracy przedefiniowany jako łańcuch Markowa. Istotą rozwiniętego modelu jest wyznaczenie wszystkich podstawowych obiektów jego działania, wskazanie na skończoność przestrzeni stanów oraz wyprowadzenie wyrażeń na składowe podstawowego operatora, macierzy przekształcenia w pojedyńczym kroku. Jednoczesnie sformułowano warunki zachowania się asymptotycznego, by uzyskać ważną własność punktowej asymptotycznej zbieżności.

EN

Discrete Ant System based on M. Dorigo results on Ant System is introduced and defined as a Markov chain. This probabilistic model is presented in details with finite space characteristic and evolution operator description. Finally the pointwise convergence of Discrete Ant Algorithm is stated and justified.

Słowa kluczowe

PL

algorytm optymalizacyjny; algorytm inspirowany naturą; dyskretny algorytm mrówkowy; feromony; łańcuch Markowa; punktowa zbieżność

EN

optimizing algorithms; nature based algorithms; discrete ant algorithm; pheromone; Markov chains; pointwise convergence

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Matematyka Stosowana : matematyka dla społeczeństwa
• Rocznik: 2011
• Tom: T. 13/54
• Strony: 79--103
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Rembelski P.

• Wydział Informatyki Polsko-Japońska Wyższa Szkoła Technik Komputerowych ul. Koszykowa 86, 02-008 Warszawa,

Bibliografia

• [1] U. Boryczka, Algorytmy optymalizacji mrowiskowej, Wydawnictwo Uniwersytetu Śląskiego, Katowice, 2006.
• [2] P. Cichosz, Systemy uczące się, WNT, Warszawa 2000.
• [3] J. Cytowski, Algorytmy genetyczne: podstawy i zastosowania, Seria: Problemy Współczesnej Nauki - Teoria i Zastosowania, 18, Akademicka OficynaWydawnicza PLJ, Warszawa, 1996.
• [4] M. Dorigo, G. Di Caro, L. M. Gambardella, Ant Algorithms for Discrete Optimization, Technical Report IRIDIA/98-10, Universit Libre de Bruxelles, Belgium, 10, 1999.
• [5] M. Dorigo, V. Maniezzo, A. Colorni, Ant System: optymization by colony of cooperating agents, IEEE Transactions on Systems, Man and Cybernetics, 26, 1996.
• [6] M. Dorigo, L. M. Gambardella, A Study of Some Properties of Ant-Q. Proceedings of Fourth International Conference on Parallel Problem Solving from Nature, PPSNIV, Lecture Notes in Computer Science, str. 656-665, Berlin, 1996. Springer-Verlag.
• [7] M. Dorigo, T. Stｨutzle, A short convergence proof for a class of ACO algorithms, IEEE Transactions on Evolutionary Computation, vol 6, 2002.
• [8] M. Dorigo, T. Stｨutzle, Ant Colony Optimization. The MIT Press, 2004.
• [9] D. E. Goldberg, Algorytmy genetyczne i ich zastosowania, WNT,Warszawa, 1995.
• [10] W. J. Gutjahr, ACO algorithms with guaranteed convergence proof to the optimal solution, Information Processing Letters, vol 82, 2002.
• [11] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.
• [12] R. B. Hollstien, Artificial Genetic Adaptation in Computer Control Systems, Ph.D. Thesis, University of Michigan, 1971.
• [13] P. Kieś, Z. Michalewicz, Podstawy algorytmów genetycznych, Matematyka Stosowana. Matematyka dla Społeczeństwa, 1 (44), 2000, 68-91.
• [14] W. Kosiński, S. Kotowski, 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.
• [15] S. Kotowski, Analysis of Genetic Algorithms by Dynamical System Methods, Analiza algorytmów genetycznych jako układów dynamicznych , in Polish, Ph.D. Thesis, IPPT PAN, Warszawa 2008.
• [16] S. Kotowski, W.Kosiński, Z. Michalewicz, P. Synak, Ł. Brocki, On Classifcation Tools for Genetic Algorithms, Fundamenta Informaticae, 96(4) 2009, 477-491, DOI 10.3233/FI-2009-189.
• [17] A. Lasota, Asymptotyczne własności półgrup operatorów Markowa, Matematyka Stosowana. Matematyka dla Społeczeństwa, 3 (45), 2002, 39-51.
• [18] Z. Michalewicz, Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa, 1996.
• [19] J. E. Rowe, The dynamical system models of the simple genetic algorithm, w Theoretical Aspects of Evolutionary Computing, Leila Kallel, Bart Naudts, Alex Rogers (Eds.), Springer, 2001, 31-57.
• [20] R. Rudnicki, On asymptotic stability and sweeping for Markov operators, Bull. Polish Acad. Sci. Math., 43 (1995), 245-262.
• [21] R. Schaefer, Podstawy genetycznej optymalizacji globalnej, Wydawnictwo Uniwersytetu Jagielońskiego, Krak 2002.
• [22] J. Socała, Asymptotic behaviour of the iterates of nonnegative operators on a Banach lattice, Ann. Polon. Math., 68 (1), (1998), 1-16.
• [23] J. Socała, W. Kosiński, Lower-bound function method in the converegence analysis of genetic algorithms, (in Polish: Zastosowanie metody funkcji dolnej do badania zbieżności algorytmów genetycznych,) Matematyka Stosowana. Matematyka dla Społeczeństwa, PTM, Warszawwa, 8 (49), 2007 , 33-44.
• [24] J. Socała, W. Kosiński, S. Kotowski, O asymptotycznym zachowaniu prostego algorytmu genetycznego, Matematyka Stosowana. Matematyka dla Społeczeństwa, PTM, Warszawa, 6 (47), 2005, 70-86.
• [25] M. D. Vose, Modelling Simple Genetic Algorithms, Evolutionary Computation, 3 (4) 453-472, 1996.
• [26] M. D. Vose, The Simple Genetic Algorithm: Foundation and Theory, MIT Press, Cambridge, MA, 1999.