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.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The maximum clique problem is a very well-known NP-complete problem and for such a problem, meta-heuristic algorithms have been developed which ant algorithms belongs to. There are many algorithms including ant algorithms that have been elaborated for this problem. In this paper, a new dynamic function of selecting with a new improvement procedure in order to get a larger size of clique for the ant algorithm is presented and this search for the maximum clique in graph is compared to the best ant algorithms that are already known.
PL
Problem kliki maksymalnej przynależy do klasy problemów NP-zupełnych i dla takich problemów opracowuje się obecnie algorytmy metaheurystyczne, do których zaliczają się algorytmy mrówkowe. W niniejszym artykule prezentowany jest algorytm mrówkowy z dynamiczną funkcją wyboru wierzchołków włączanych do tworzonej kliki przez każdą mrówkę wraz z procedurą poprawy wymiaru otrzymanej kliki poprzez wymianę wierzchołków, a otrzymany algorytm został porównany z innymi już dotychczas opublikowanymi.
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
W artykule przedstawiono propozycję rozwiązania problemu szeregowania zadań TSP (ang. Task Scheduling Problem) określonego za pomocą skierowanego grafu w warunkach ograniczonych zasobów za pomocą algorytmów mrówkowych ACS (ang. Ant Colony System). Zaprojektowano i wykonano własne oprogramowanie w środowisku RAD C++ Turbo Explorer. Oprogramowanie posłużyło do przeprowadzenia wielu badań pozwalających na dobór parametrów ACS w celu rozwiązania problemu TSP. Wyniki wskazują, że zastosowanie ACS stanowi korzystną alternatywę dla używanych algorytmów suboptymalnych typu wielomianowego, jak algorytm Hu lub LPT.
EN
In this paper is presented proposal of solving the task scheduling problem (TSP) given by directed graph, under limited resources condition using the ant colony system (ACS). The own software in C++ Turbo Explorer rapid application development environment was designed and developed. The software was used to carry out series of simulations, what allowed to choose the best parameters of the ACS in solving of the TSP problem. The results indicate, that using of the ACS is an advantageous option to commonly used suboptimal polynomial algorithms, like Hu or LPT.
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
This paper presents a general design procedure for microstrip-like interconnect lines with or without ground plane apertures. For this purpose, we first revisit the empirical closed-form characteristic impedance expression, which considers the effect of the ground plane aperture. After the definition of an appropriate objective function, we apply the Particle Swarm Optimization method in order to calculate the optimized parameters of microstrip-like interconnect lines in the synthesis problem.
PL
Artykuł prezentuje zasady projektowania połączeń typu microstrip. Do tego celu zrewidowano empiryczne wyrażenie opisujące charakterystykę impedancji, przy uwzględnieniu efektu uziemienia apertury. Po zdefiniowaniu odpowiedniej funkcji celu wykorzystano optymalizację metodą algorytmu mrówkowego. Przedstawiono przykład obliczania optymalnych parametrów.
7
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
Tematem niniejszego artykułu jest planowanie tras przejazdu. Autorzy prezentują ujęcie planowania tras przejazdu między kolejnymi punktami odbioru, jako typowe zadanie optymalizacyjne, znane pod nazwą Problemu Komiwojażera lub Problem Chińskiego Listonosza. W pierwszej części artykułu autorzy prezentują teoretyczne ujęcie tematu optymalizacji tras. W drugiej części autorzy przedstawiają możliwość rozwiązanie przedstawionego problemu przy użyciu dwóch technik: techniki z obszaru inteligencji obliczeniowej, a mianowicie Algorytmu Grafowego, oraz drugiej techniki – Algorytmu Mrówkowego, techniki zaczerpniętej z obszaru Sztucznej Inteligencji.
EN
The planning the routs of ride is the subject of present article. The authors present the formulation of planning between next points of receipt, as typical task the routs of ride the optimization, well-known under name of the Travelling Salesman Problem or the Chinese Postman's Problem. The theoretical formulation of subject of optimization routs in first part of the author's article presents. In second part authors represent possibility solution introduced problem near use two technician: the technique from area of computational intelligence, and namely the Graph Algorithm, as well as second technique - ladled from area of Artificial Intelligence the Ant Algorithm, technique.
9
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
This paper uses an ant colony meta-heuristic optimization method to solve the multi-stage expansion problem for multi-state series-parallel systems. The study horizon is divided into several periods. At each period the demand distribution is forecasted in the form of a cumulative demand curve. A multiple-choice of additional components among a list of available product can be chosen and included into any subsystem component at any stage to improve the system performance. The components are characterized by their cost, performance (capacity) and availability. The objective is to minimize the whole investment-costs over the study period while satisfying availability or performance constraints. A universal generating function technique is applied to evaluate system availability. The ant colony approach is required to identify the optimal combination of adding components with different parameters to be allocated in parallel at each stage.
PL
W artykule omówiono metodę optymalizacji wykorzystującą algorytmy mrówkowe. Rozwiązywano problem wielopoziomowej rozbudowy szeregowo-równoległego system zasilania. Horyzont czasowy analizy został podzielony na mniejsze okresy. W każdym okresie potrzeby są prognozowane w postaci kumulacyjnej krzywej potrzeb. Różny wybór dodatkowych składowych systemu był możliwy na każdym etapie analizy. Te składowe były charakteryzowane przez koszt, możliwości i parametry. Celem była minimalizacja całkowitych kosztów inwestycji przy wymuszonych parametrach. Algorytm mrówkowy został wykorzystany do optymalizacji systemu na każdym etapie dodawania nowego elementu.
Identyfikacja układów liniowych MISO z opóźnionymi wejściami, ze względu na wielomodalność przestrzeni rozwiązań, może prowadzić do uzyskania tylko minimum lokalnego i błędnego modelu. Skutecznym narzędziem optymalizacji globalnej są metody sztucznej inteligencji. W pracy zaproponowano zastosowanie algorytmów mrówkowych do identyfikacji opóźnień w układach liniowych MISO. Wykorzystano przy tym klasyczny algorytm gradientowy do określania jakości otrzymanych modeli. Efektywność zaproponowanej metody została porównana z wybranymi metodami klasycznymi z wykorzystaniem badań symulacyjnych.
EN
The identification of time delays of linear systems is one of important tasks. If the system is MISO, the solution space is multi-modal and identification algorithms can find only the local optimum. One of the possibility of identification is the use of the Ant Colony Optimization methods to identify time delays. The nonlinear least-squares method is applied to find the residual parameters and quality function. The simulation results are presented in the paper.
11
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 .
Pozyskiwanie wiedzy diagnostycznej metodami uczenia maszynowego na podstawie danych z eksperymentów i obserwacji diagnostycznych, wymaga wstępnego przetworzenia tych danych. Przetwarzanie to obejmuje między innymi selekcję podzbioru cech spośród licznego zbioru cech. W breferacie przedstawiono wyniki badań dotyczących wyboru cech istotnych z uwagi na możliwość oceny stanu lub oceny rodzaju powstałej niesprawności diagnozowanego obiektu. Do selekcji cech zastosowano metodę z wykorzystaniem algorytmu uczenia maszynowego oraz algorytmu mrówkowego.
EN
Data used in a knowledge acquisition process should be preprocessed. One of the preprocessing stage is selection of attributes, called also selection of information. In the paper there are presented results of a research concerning diagnosis of a technical object - rotation machine. In the research the selection of attributes was earned out using the ant colony optimization approach combined with the wrapper approach.
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ść.
Problem dostawy jest przykładem złożonej optymalizacji kombinatorycznej i należy do grupy problemów NP -zupełnych. Rodzina algorytmów mrówkowych dokonale sobie radzi ze złożonymi problemami tej grupy. Podjęto próbę zaadoptowania algorytmów mrówkowych do rozwiązywania problemu dostawy. W niniejszej pracy przedstawiono wyniki działania wybranych modyfikacji algorymów mrówkowych do rozwiązywania problemu dostawy dla zbiorów danych wejściowych o różnych rozmiarach.
EN
The delivery problem is an example of a complex combinatorial optimization which belongs to the NP-complete group. The family of an algorithms is suitable for solving the problem of this group. We have tried to adopt some an algorithms to the delivery problem. In this paper we present the results of some an algorithms for soloving the delivery problem for the sets of various sizes.
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ć.