Zastosowanie algorytmów sztucznej inteligencji do rozwiązania problemu komiwojażera

• Autorzy: Krzysztof Ficoń , Grzegorz Krasnodębski

Warianty tytułu

Application of Artificial Intelligence Algorithms to Solve the Traveling Salesman Problem

• Języki publikacji: PL

Abstrakty

W pracy omówiono heurystyczne metody rozwiązania problemu komiwojażera za pomocą algorytmów sztucznej inteligencji. Oprócz niemal klasycznych algorytmów opartych na sztucznych sieciach neuronowych i algorytmach genetycznych (ewolucyjnych) zostały przeanalizowane nowoczesne algorytmy korzystające z tzw. inteligencji roju (stada). W tej grupie zostały przeanalizowane algorytmy kolonii pszczół i stada ptaków. Szerzej zostały przedyskutowane algorytmy mrówkowe, bardzo ściśle związane z suboptymalizacją tras komunikacyjnych. (abstrakt oryginalny)

EN

The paper discusses the heuristic methods of solving the traveling salesman problem using artificial intelligence algorithms. In addition to almost classic algorithms based on artificial neural networks and genetic (evolutionary) algorithms, modern algorithms using the so-called swarm intelligence (herd). In this group, the algorithms for colonies of bees and flocks of birds have been analyzed. The formic algorithms, very closely related to the suboptimization of communication routes, have been discussed in more detail. (original abstract)

Słowa kluczowe

PL

Sztuczna inteligencja; Algorytmy; Metody heurystyczne; Zawód pośrednika

EN

Artificial intelligence; Algorithms; Heuristics methods; Profession of an intermediary

• Czasopismo: Gospodarka Materiałowa i Logistyka
• Rocznik: 2018
• Numer: nr 12 (CD)
• Strony: 286--307

Twórcy

autor

Krzysztof Ficoń

• Akademia Marynarki Wojennej

autor

Grzegorz Krasnodębski

• Akademia Marynarki Wojennej

Bibliografia

• Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J. (2007), The Traveling Salesman Problem. A Computational Study. Lanchester Prize, Princeton University Press.
• Bubal, A.T., Lee, L.S. (2016), Differential Evolution for Urban Transit Routing Problem, Journal of Computer and Communications, 4/2016.
• Christofides, N. (1976), Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388. Graduate School of Industrial Administration, CMU.
• Clerc, M., (2004). Discrete Particle Swarm Optimization Illustrated by the Travelling Salesman Problem. Springer Berlin.
• Cook, W.J. (2012), In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press.
• Dantzig, G., Fulkerson, R., Johnson, S. (1954), Solution of a Large-Scale Traveling - Salesman Problem. RAND Corp. Santa Monica.
• Davendra, D. (2010), Traveling Salesman Problem, Theory and Applications. InTech.
• 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, 26 (1).
• Dorigo, M., Stützle, T., Ant Colony Optimization. MIT Press. 2004.
• Ficoń, K. (2013), Sztuczna inteligencja. Nie tylko dla humanistów. BEL Studio Warszawa.
• Ficoń, K. (2015), Dualizm logistyczno-kombinatoryczny zadania komiwojażera. ZN WAT SLW 42/2015.
• Glover, F. (1990), Tabu Search. Part 1,2, ORSA Journal on Computing.
• Hall, S.N. (2012), A Group Theoretic Tabu Search Approach to the Traveling Salesman Problem. Biblioscholar.
• Holland, J.H. (1975), Adaptation in Natural and Artificial Systems. University of Michigan Press.
• Huibin, J., Mingguang, L. (2009). An Improved Differential Evolution Algorithm for Optimization. IITA International Conference on Control, Automation and Systems Engineering.
• Kennedy, J., Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of the 1995 IEEE International Conference on Neural Networks, IEEE Press.
• Kulikowski, J.J. (1986). Zarys teorii grafów. Zastosowania w technice. PWN Warszawa.
• Lisowski, J. (2017), Metody optymalizacyjne. Wyd. AM Gdynia.
• Mańdziuk, J. (2000), Sieci neuronowe typu Hopfielda. Teoria i przykłady zastosowań. AOW EXIT Warszawa.
• Metropolis, N. et al. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics 21 (6): 108.
• Michalewicz, Z. (2006) i in., Adaptive Business Intelligence. Springer-Verlag Berlin.
• Nilsson, C. (2003), Heuristics for the Traveling Salesman Problem, Department of Computer Science, Linkoping University.
• Ramani, G. (2011), Travelling Salesman Problem (TSP) optimization through Genetic Algorithm. Improvised solution to VLSI Detailed Routing and National Tour Paperback - September 8/2011.
• Reinelt, G. (1994), The Traveling Salesman. Computational Solutions for TSP Applications.
• Robinson, J. B. (1949), On the Hamiltonian Game. A Traveling - Salesman Problem. RAND Corp. Santa Monica.