Wirtualne laboratoria optymalizacji heurystycznej : wykorzystanie algorytmów mrówkowych

• Autorzy: Szewczak M. , Trojanowski K.
• Języki publikacji: PL

Abstrakty

PL

W życiu codziennym spotykamy się z różnego rodzaju problemami heurystycznymi. Do ich rozwiązania możemy stosować istniejące już deterministyczne metody optymalizacji. Istnieje jednak wiele zdarzeń kombinatorystycznych o niezwykle wysokiej złożoności obliczeniowej, dla których deterministyczne metody rozwiązania nie są do zaakceptowania, ponieważ ich złożoność i koszt obliczeniowy przekracza możliwości obliczeniowe najszybszych nawet komputerów. Wtedy dla inżyniera, pragnącego w rozsądnym czasie znaleźć rozwiązanie jeżeli nie optymalne, to przynajmniej suboptymalne, odpowiednim narzędziem stają się metody heurystyczne. Szukanie rozwiązania za ich pomocą sprowadza się do wygenerowania i zastosowania zbioru reguł kierujących procesem przeszukiwania przestrzeni rozwiązań. Istnieje kilka różnych paradygmatów pozwalających na generowanie szeregu algorytmów heurystycznych. Paradygmaty te nazywane są metaheurystykami, ponieważ nie definiują konkretnych algorytmów ale opisują ogólne podejścia. W ramach takiego podejścia istnieje możliwość szerokiego wariantowania poszczególnych reguł, co w rezultacie prowadzi do różnych algorytmów należących jednak do wspólnej rodziny (zob. np. [13]). [...]

Słowa kluczowe

PL

metoda heurystyczna; metaheurystyki; algorytm mrówkowy; algorytm heurystyczny

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2003
• Tom: Vol. 2(2)
• Strony: 87--100
• Opis fizyczny: Bibliogr. 13 poz., rys., tab., wykr.

Twórcy

autor

Szewczak M.

• Akademia Podlaska, Siedlce

autor

Trojanowski K.

• Akademia Podlaska, Siedlce

Bibliografia

• [1] Algorytmy mrówkowe, http://marti.net26.pl/mrowki/algorytmy_mrowkowe.html
• [2] Ant Colony Optimization, http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
• [3] Ants’2002 Home, http://iridia.ulb.ac.be/~ants/ants2002/index.html
• [4] Biologia - Największa na świecie kolonia mrówek, http://science.eu.org/biologia/mrowki.php
• [5] BULLNHEIMER, B„ HARTL, R. F., STRAUSS Ch. (1999). A New Rank Based Version of the Ant System-A Computational Study, Central European Journal of Operations Research, Vol 7 (1), str. 25-38.
• [6] DORIGO M., MANIEZZO V. & COLORNI A. (1996). The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf
• [7] DORIGO M., Dl CARO G. & GAMBARDELLA L. M. (1999). Ant Algorithms for Discrete Optimization. Artificial Life, ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.23-alife99.pdf
• [8] Mrówki w Internecie, http://free.of.pl/rn/myr
• [9] Optymalizacja kolonii mrówek, http://www.ci.pwr.wroc.pl/~kwasnick/lindaabrichwww/description.html
• [10] STUTZLE T. and HOOS H. (1997). The MAX-MIN Ant System and local Search for Combinatorial Optimization Problems: Towards Adaptive Tools for Global Optimization. 2nd Metaheuristics International Conference (MIC-97), Sophia-Antipolis, France-July 21-24, 1997, http://www.intellektik.informatik.tudarmstadt.de/~tom/publications/MIC97.ps.gz
• [11] Symmetric TSPs, http://www.informatik.uniheidelberg.de/groups/comopt/software/TSPLIB95/STSP.html
• [12] SZEWCZAK M., Sztuczne systemy mrówkowe w optymalizacji problemu komiwojażera, praca licencjacka na prawach manuskryptu, Akademia Podlaska, Siedlce 2003.
• [13] TROJANOWSKI K., Metaheurystyki. Materiały pomocnicze do przedmiotu „Metaheurystyki-laboratorium”, Wydawnictwo WSISiZ, Warszawa 2003.