Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Ant systems applied to solve the Travelling Salesman Problem
Języki publikacji
Abstrakty
Artykuł porusza dwa zagadnienia. Pierwsze określane jest jako problem komiwojażera popularnie nazywanego TSP (z ang. Traveling Salesman Problem), oraz systemy mrówkowe (z ang. Ant Systems) jako przedstawiciel nowatorskiego podejścia do rozwiązywania problemów optymalizacyjnych z grupy NP-trudnych. Problem TSP jest zagadnieniem optymalizacyjnym polegającym na znalezieniu drogi o najmniejszym koszcie dla wyznaczonej przez komiwojażera trasy. Systemy mrówkowe są to algorytmy wzorujące się na świece przyrody, a konkretniej na sposobie organizacji kolonii mrówek w poszukiwaniu najkrótszej drogi z mrowiska do pokarmu i z powrotem. Artykuł ma za zadanie zapoznać czytelnika z dwoma zakreślonymi powyżej zagadnieniami, zaprezentować zastosowanie systemów mrówkowych do rozwiązania TSP, zbadać efektywność algorytmów mrówkowych oraz algorytmów klasycznych w poszukiwaniu optimum dla określonych problemów TSP oraz przedstawić otrzymane wyniki wraz z wnioskami końcowymi. Dodatkową częścią artykułu są kierunki dalszych badań, jakie są podejmowane przez naukowców, przy wykorzystaniu filozofii systemów mrówkowych.
The paper discusses two problems. The first one is known as the Travelling Salesman Problem (TSP), whereas the second one is defined as the Ant Systems being the representative of innovative attitude to solving optimization problems belonging to the NPhard group. The TSP problem is an optimizing issue that consists in finding the lowest cost travelling way for the route specified by the n travelling salesman. The ant systems are algorithms pattered after the nature, more specifically, after the way an ant colony is organized is order to find the shortest way from the anthill to food and back. The aim of the paper is to familiarize readers with the above two problems, to present application of ant systems to solve the TSP, to examine efficiency of ant algorithms and classical algorithms when searching for the optimum for specific TSP problems as well as to present obtained results together with final conclusions. As an additional part of this paper, the author presented further directions of research undertaken by scientists using philosophy of ant systems
Słowa kluczowe
Czasopismo
Rocznik
Tom
Strony
65--76
Opis fizyczny
Bibliogr. 7 poz., rys., tab., wykr.
Twórcy
autor
- Uniwersytet Kazimierza Wielkiego, Instytut Techniki, II rok MU Edukacja Techniczno-Informatyczna, ul.Chodkiewicza 30, 85-064 Bydgoszcz, prophetnes@wp.pl
Bibliografia
- 1. MICHALEWICZ, Z., FOGEL, D.B., Jak to rozwiązać, czyli nowoczesna heurystyka, Warszawa, Wydawnictwo Naukowo-Techniczne Warszawa, 2006, s. 226,
- 2. BIGGS, N. L., LLOYD, E. K., WILSON, R. J., Graph Theory 1736-1936, [online], Oxford, Oxford University Press, 1998
- 3. HELSGANN, K., NGASSA, J-L., KIERKEGAARD, J., ACO and TSP, Roskilde University, may 2007
- 4. MILLER, P., Swarm Theory, [online], National Geographic Staff, lipiec 2007, http://ngm.nationalgeographic.com/2007/07/swarms/mille r-text.
- 5. DORIGO, M., STÜTZLE, T., Ant Colony Optimization, London, The MIT Press Cambridge Massachusetts Institute of Technology, 2004, p. 69
- 6. DORIGO, M., GAMBARDELLA, M.l., Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1997, p. 53-66,
- 7. PALMER, J., Smart future for swarm robots, Technology Reporter, BBC News, August 2008
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BWMA-0016-0018
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ć.