Wyniki wyszukiwania - BazTech

1

Systemy mrówkowe w zastosowaniu do rozwiązania problemu problemu komiwojażera

Modrzejewski M.

Studia i Materiały Informatyki Stosowanej

|

2009

|

nr 1

65-76

PL

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.

EN

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

2

A document clustering method based on ant algorithms

Machnik Ł.

TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

|

2007

|

Vol. 11, No 1-2

87-102

EN

Ant Algorithms, particularly the Ant Colony Optimization (ACO) metaheuristic, are universal, flexible and scalable because they are based on multi-agent cooperation. The increased demand for effective methods of managing large collections of documents is a sufficient stimulus to place the research on new applications of ant-based systems in the area of text document processing. The author presents an implementation of such a technique in the area of document clustering. Details of the ACO document clustering method and results of experiments are presented.

3

Some aspects of ant systems for the TSP

Boryczka M.

Fundamenta Informaticae

|

1998

|

Vol. 35, nr 1-4

197-209

EN

We describe the ant systems and the application of the generative policies improving the performance of the ant systems in the context of the Travelling salesman Problem. The generative policies are derived from the studies carried out in Germany and USA in the sixties. We study the leader (superman) and elite strategies, which have been chosen because of their analogy to the world of real ants. First, we describe three ant algorithms and we introduce a formal description of the ant system. Then we discuss the reflection of the evolutionary computing in the ant systems.