Algorytm hybrydowy dla probabilistycznego problemu komiwojażera

• Autorzy: Kiełkowicz K. , Kokosiński Z.

Warianty tytułu

EN

A hybrid algorithm for probabilistic traveling salesman problem

• Języki publikacji: PL

Abstrakty

PL

W artykule rozważono Probabilistyczny Problem Komiwojażera (PTSP), dla którego został zaproponowany algorytm hybrydowy, łączący algorytm ewolucyjny z metodami optymalizacji lokalnej i obliczeniami równoległymi. Metody optymalizacji lokalnej obejmują operatory 1-shift i 2-p-opt. Przebadano eksperymentalnie kilka wariantów algorytmu ewolucyjnego i hybrydowego oraz wpływ zastosowanych metod optymalizacji lokalnej i metod zrównoleglenia obliczeń na jakość znajdowanych rozwiązań.

EN

In this paper Probabilistic Traveling Salesman Problem (PTSP) is considered and a hybrid algorithm is proposed, in which an evolutionary algorithm is combined with local optimization and parallelization techniques. Local optimization methods include 1-shift and 2-p-opt operators. Several basic variants of evolutionary and hybrid algorithms are experimentally tested and compared.

Słowa kluczowe

PL

PTSP; algorytm ewolucyjny; równoległy algorytm ewolucyjny; algorytm hybrydowy

EN

PTSP; evolutionary algorithm; parallel evolutionary algorithm; hybrid algorithm

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Automatyka
• Rocznik: 2012
• Tom: R. 109, z. 1-AC
• Strony: 115--126
• Opis fizyczny: Bibliogr. 13 poz., wz., tab., rys.

Twórcy

autor

Kiełkowicz K.

autor

Kokosiński Z.

• Katedra Automatyki i Technik Informacyjnych, Wydział Inżynierii Elektrycznej i Komputerowej, Politechnika Krakowska

Bibliografia

• [1] Bertsimas D.J., Howell L., Further results on the probabilistic traveling salesman problem, European Journal of Operational Research, 65, 1993, 68-95.
• [2] Bianchi L., Ant colony optimization and local search for the probabilistic travelling salesman problem: a case study in stochastic combinatorial optimization, PhD thesis, Universite Libre de Bruxelles, Brussels 2006.
• [3] Branke J., Guntsch M., Solving the Probabilistic TSP with Ant Colony Optimization, Journal of Mathematical Modelling and Algorithms 3, 2004, 403-425.
• [4] Jaillet P., Probabilistic Traveling Salesman Problems, PhD thesis, MIT, Cambridge 1985.
• [5] Jaillet P., A priori solution of a travelling salesman problem in which a random subset of the customers are visited, Operations Research, 36(6), 1988, 929-936.
• [6] Kiełkowicz K., Hybrydowe algorytmy iteracyjne w optymalizacji kombinatorycznej, praca dyplomowa, Politechnika Krakowska, Kraków 2009.
• [7] Kokosiński Z., Studzienny Ł., Hybrid Genetic Algorithms for the Open-Shop Scheduling Problem, IJCSNS International Journal of Computer Science and Network Security, vol. 7, No. 9, 2007, 136-145.
• [8] Liu Y.-H., A Scatter Search Based Approach with Approximate Evaluation for the Heterogeneous Probabilistic Traveling Salesman Problem, Journal of Mathematical Modelling and Algorithms 3, 2004b, 403-425.
• [9] Liu Y.-H., A hybrid scatter search for the probabilistic traveling salesman problem, Elsevier Computers & Operations Research 34, 2007, 2949-2963.
• [10] Liu Y.-H., Solving the Probabilistic Travelling Salesman Problem Based on Genetic Algorithm with Queen Selection Scheme, September 2008, I-Tech, Vienna, Austria.
• [11] MPICH2, http://www.mcs.anl.gov/research/projects/mpich2/, (access 19.10.2012).
• [12] Suh J.Y., Van Gucht D., Incorporating Heuristic Information into Genetic Search, Proc. 2nd Int. Conf. on Genetic Algorithms, 1987, 100-107.
• [13] TSPLib, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/ (access 27.10.2012).