Algorytm mrówkowy w optymalizacji dyskretnych problemów nieliniowych

• Autorzy: Krenich S.

Warianty tytułu

EN

Ant colony based algorithm for discrete and nonlinear optimization

• Języki publikacji: PL

Abstrakty

PL

Artykuł prezentuje zastosowanie algorytmu mrówkowego w optymalizacji problemów o dyskretnym i nieliniowym charakterze. Algorytm mrówkowy zaliczany jest do grupy algorytmów rojowych, które są inspirowane zachowaniem stad lub rojów zwierząt, ptaków czy owadów podczas poszukiwania pożywienia czy przemieszczania się. Algorytmy te stosowane są głównie do rozwiązywania problemów opisanych za pomocą grafów i sieci. W niniejszej pracy przedstawiono modyfikację klasycznego algorytmu mrówkowego i jego przystosowanie do rozwiązywania zadań optymalizacji jednokryterialnej konstrukcji z ograniczeniami, które nie są modelowane jako grafy z wyraźnie zaznaczonymi węzłami i krawędziami przejść o określonym ściśle koszcie lub wartości drogi. Wprowadzono modyfikację w wyznaczaniu prawdopodobieństwa wyboru tzw. krawędzi przejścia oraz w obliczaniu wartości feromonu na tych krawędziach. Wartości te zależą nie tylko od liczby przejść sztucznych mrówek, ale także dodatkowo od dynamicznie ustalanej wartości pozostawianego przez mrówki feromonu. Eksperymenty przeprowadzono na dwóch przykładach dyskretnej optymalizacji sprzęgła wielopłytkowego oraz układu koncentrycznych sprężyn poddanych zmiennemu obciążeniu z wykorzystaniem zmodyfikowanego algorytmu mrówkowego oraz dodatkowo w celu porównania z wykorzystaniem algorytmu ewolucyjnego i losowego. Wyniki wskazują, iż algorytm mrówkowy może być efektywnym narzędziem w programowaniu dyskretnym.

EN

The paper presents an approach to design optimization for discrete and nonlinear problems using ant colony based algorithm. This algorithm belongs to the group of swarm algorithms inspired by behavior of birds, animals and bugs during their life or movement. Generally it is used for solving tasks which are modeled as grid or network problems. In the work a modification of the classical ant colony algorithm and its adaptation for problems that are not modeled as a network task with marked nodes and edges is described. New dependencies for dynamic calculating of pheromone on the edges and for probability of their choosing are introduced. Experiments were carried out for two examples of discrete optimization. The first one deals with the coupling system and the second one solves the set of concentric springs. Additionally, in order to compare generated optimal solutions, an evolutionary algorithm and a random search method are used. The obtained results indicate that the ant colony based algorithm can be an effective tool for discrete programming.

Słowa kluczowe

PL

algorytm mrówkowy; problem nieliniowy; programowanie dyskretne

EN

ant colony; nonlinear optimization; discrete programming

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2014
• Tom: nr 6
• Strony: 6032--6040
• Opis fizyczny: Bibliogr. 14 poz., rys., tab., pełny tekst na CD3

Twórcy

autor

Krenich S.

• Instytut Technologii Maszyn i Automatyzacji Produkcji, Wydział Mechaniczny, Politechnika Krakowska, Al. Jana Pawła II 37, 31 -864 Kraków. Tel. [phone], fax [phone]

Bibliografia

• 1. Bonabeau E., Dorigo M. et Theraulaz G., Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2, 1999.
• 2. Dorigo M., Di Caro G., Gambardella L. M., Ant Algorithms for Discrete Optimization. Artificial Life, 5 (2): 137–172, 1999.
• 3. Dorigo M., Stützle T., Ant Colony Optimization, MIT Press. ISBN 0-262-04219-3, 2004
• 4. Dorigo, M., Optimization, Learning and Natural Algorithms, Rozprawa doktorska (PhD thesis), Politecnico di Milano, Włochy, 1992.
• 5. Krenich S. and Osyczka A.: Optimal Design of Multiple Clutch Brakes Using a Multistage Evolutionary Method. IUTAM Symposium on Evolutionary Methods in Mechanics, Kluwer Academic Publishers, Dordrecht/Boston/London, 2004, pp. 219-228.
• 6. Krenich S.: Optymalna alokacja obiektów z wykorzystaniem algorytmów ewolucyjnych. Logistyka 3/2011, s.1365-1375.
• 7. Krenich S. Równoległe algorytmy ewolucyjne w optymalizacji konstrukcji. Logistyka 3/2014, str. 3306-3313.
• 8. Malec M. Morawski M. Wpływ parametrów sterowania na siłę ciągu podwodnego robota mobilnego z napędem falowym dla różnych wariantów płetwy ogonowej. Elektronika, konstrukcje technologie, zastosowania, Nr 12/2013, s. 99-102,
• 9. Małopolski W., Optymalizacja wykorzystania automatycznie sterowanego robota mobilnego w systemie transportowym za pomocą symulacji komputerowej, Logistyka, 2014, Nr 3, 4162-4169.
• 10. Małopolski W., Cost Optimization in Manufacturing System with Unidirectional AGVs, Applied Mechanics and Materials Vol. 555 (2014) pp. 822-828.
• 11. Osyczka A., Krenich S., Krzystek J. (2002): Spring Design Automation Using Evolutionary Algorithms. Zeszyty Naukowe Politechniki Koszalinskiej, Koszalin, Nr 31, str. 121-128.
• 12. Osyczka A., Krenich S.: Evolutionary Algorithms for Global Optimization, Chapter in: J. Pinter (Ed.) Global Optimization - Selected Case Studies, Kluwer Academic Publishers, 2007.
• 13. Osyczka A.: Evolutionary Algorithms for Single and Multicriteria Design Optimization. Springer-Verlag Physica, Berlin Heilderberg 2001.
• 14. Szymak P., Malec M., Morawski M., Conception of Research on Bionic Underwater Vehicle with Undulating Propulsion, Solid State Phenomena,Vol. 180, Trans Tech Publications Inc., 2012, str.160-167.