W artykule podjęto problematykę wyznaczania tras kompletacji oraz przedstawiono znane i analizowane w literaturze podejścia do tego zagadnienia. Szczególną uwagę poświęcono heurystycznym sposobom generowania ścieżek kompletacyjnych. W tym celu przedstawiono jedenaście różnych metod heurystycznych i metaheurystycznych (algorytmy mrówkowe) mogących służyć do sekwencjonowania miejsc pobrań. Dodatkowo zaproponowano wykorzystanie algorytmu A* do wyznaczania najkrót szych ścieżek pomiędzy tymi miejscami. Przedstawione metody zostały ze sobą porównane i ocenione na podstawie wyników uzyskanych z przeprowadzonych badań.
EN
The paper deals with a problem of routing order pickers and presents known and analyzed in literature approaches. Main attention was paid to heuristics of order pickers routing. Eleven own heuristics and metaheuristics (ant algorithms) used for sequencing pick locations was proposed and investigated. Provided heuristics use the A - star algorithm to determine the shortest paths between pick locations. Presented methods were compared and evaluated according to results of research.
Ant Colony Optimization (ACO) is a stochastic search method that mimics the social behavior of real ant colonies, managing to establish the shortest route to the feeding sources and back. Such algorithms have been developed to arrive at near-optimal solutions to large-scale optimization problems, for which traditional mathematical techniques may fail. In this paper, the semi-random start procedure is applied. A new kind of evaluation of start nodes of the ants is developed and several starting strategies are prepared and combined. The idea of semi-random start is related to a better management of the ants. This new technique is tested on the Multiple Knapsack Problem (MKP). A Comparison among the strategies applied is presented in terms of quality of the results. A comparison is also carried out between the new evaluation and the existing one. Based on this comparative analysis, the performance of the algorithm is discussed. The study presents the idea that should be beneficial to both practitioners and researchers involved in solving optimization problems.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Paper presents suggestion of using ant algorithms for designing optimal order picking system variants. It discusses principles of operation and possibility of using ant algorithms for research problems. It presents how to map the order picking system structure to allow implementation of ant algorithms and shows a simplified algorithm for designing optimal order picking system variants with their use.
PL
W artykule przedstawiono propozycję wykorzystania algorytmów mrówkowych do kształtowania optymalnych wariantów systemu komisjonowania. Omówiono zasady działania i możliwości wykorzystania algorytmów mrówkowych do problemów badawczych. Zaprezentowano sposób odwzorowania struktury systemu komisjonowania na potrzeby implementacji algorytmów mrówkowych oraz przedstawiono uproszczony algorytm kształtowania optymalnych wariantów systemu komisjonowania z ich wykorzystaniem.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The clustering problem is one of the main problems which can be encountered in a data analysis. This problem can be modelled by means of a graph; finding clusters means finding cliques in the graph. Often there is a need to find clusters (cliques) in a graph in different ways and to construct a list of clusters. This paper describes two such ways, these can be stated as the cluster minimum covering problem and the vertex cluster minimum partitioning problem. This paper describes new ant algorithms which were used in order to make a list of clusters in both presented problems, and also discusses the results of their comparison.
PL
Problem klasteryzacji jest jednym z często spotykanych problemów w analizie danych. Problem klasteryzacji może być zamodelowany przy pomocy grafów i znajdowanie klasterów sprowadza się wówczas do znajdowania klik w grafach. W tym artykule opisano dwa sposoby wyznaczania klasterów, czyli klik w grafach, takich jak: problem pokrycia klastrami (klikami) grafu oraz problem wierzchołkowego podziału grafu na klastry (kliki) oraz także przedstawiono dwa nowe algorytmy bazujące na zachowaniu mrówek służące do wyznaczania klastrów (klik) dla obu problemów, a także dokonano porównania ich ze znanymi algorytmami rozwiązującymi te problemy.
W artykule przedstawiono rozwiązanie kwadratowego problemu przydziału, który należy do AP-trudnych problemów optymalizacji dyskretnej, za pomocą algorytmów stadnych. Zastosowano trzy algorytmy: algorytmy mrówkowe, algorytmy optymalizacji rojem cząstek i algorytmy pszczele. Przedstawiono wyniki badań dla wybranych instancji testowych z biblioteki QAPLIB.
EN
This paper presents three swarm algorithms: ant algorithms, particle swarm optimization and bee algorithms, used for solution of quadratic assignment problem, which is a NP-hard optimization problem. The results of experiments performed for selected test problems of quadratic assignment problems from QAPLIB library have been also presented.
6
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
7
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
8
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W artykule przybliżono teorię algorytmów mrówkowych będących odmianą algorytmów stadnych, zaliczanych do metod obliczeniowych z zakresu sztucznej inteligencji. Ponadto przedstawiono metodę optymalizacji wartości zmiennych systemowych w zadaniu, jakim jest tranzyt mocy (energii) w systemach połączonych z zastosowaniem algorytmów mrówkowych.
EN
The paper introduces ant algorithms theory which are a type of swarm algorithms, an artificial intelligence calculation method. In addition, an application of ant algorithms in optimisation of system variables in power (energy) transit in connected systems has been presented .
This paper presents the results of a comparative study of network routing approaches. Recent advances in the field suggest that swarm intelligence may offer a robust, high quality solution. The overall aim of the study was to develop a framework to facilitate the empirical evaluation of a swarm intelligence routing approach compared to a conventional static and dynamic routing approach. This paper presents a framework for the simulation of computer networks, collection of performance statistics, generation and reuse of network topologies and traffic patterns.
10
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
This work introduces ANB (Ant Algorithm for Non-Bifurcated Flows), a novel approach to capacitated static optimization of flows in connection-oriented computer networks. The problem considered arises naturally from several optimization problems that have recently received significant attention. The proposed ANB is an ant algorithm motivated by recent works on the application of the ant algorithm to solving various problems related to computer networks. However, few works concern the use of ant algorithms in the assignment of static flows in connection-oriented networks. We analyze the major characteristics of the ANB and try to explain its performance. We report results of many experiments over various networks.
Genetic and ant algorithms apply stochastic searching, parallel investigation as well as autocatalitic process (or stigmergy) to solve optimization problems. This paper concentrates on the Traveling Salesman Problem (TSP) solved by genetic and ant algorithms. We consider the sets of parameters and operators which influence the acting of these algorithms. Two algorithmic structures emphasizing the selection problem are discussed. We describe the TSP experiments performed for 50 cities. The aim of the comparison is the conclusion that the evolution, which is exploited in genetic algorithms, can improve the performance of ant algorithms.
PL
Artykuł porównuje możliwości algorytmów genetycznych i mrówkowych na przykładzie problemu komiwojażera. Rozważono szereg parametrów mających wpływ na funkcjonowanie wymienionych typów algorytmów. Problem komiwojażera był rozważany dla sieci 50 miast. Celem porównania jest pokazanie, że ewolucja, która jest podstawą funkcjonowania algorytmów genetycznych, zastosowana do algorytmów mrówkowych może zwiększyć ich wydajność.
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ć.