The application of computational intelligence methods for the solution to the travelling salesman problem

The thesis comprises of the description of the travelling salesman problem, together with the review of computational complexity classes and the computational intelligence methods applied to solve it. The travelling salesman problem is one of the class NP-complete, for which the application of exact algorithms is impractical, hence heuristic algorithms are most frequently applied to obtain the solution. In the thesis, the genetic algorithm has been described as an example of evolutionary computations, whereas the ant colony optimization algorithm and the particle swarm optimization algorithm as an example of swarm intelligence. All the three algorithms have been minutely described and each of them has been supported by an example of implementation. Each algorithm has undergone experiments, which made it possible to compare the computational possibilities and the effectiveness of the suggested algorithms. A C++ language application was written to perform the experiments. It was implemented with the algorithms described in the thesis. The program is didactic in its character and has a user-friendly graphical interface, which helps to perform tests and to compare the algorithm possibilities, together with any parameter configuration for different cases of the travelling salesman problem.Praca zawiera opis problemu komiwojażera wraz z przeglądem klas złożoności obliczeniowych oraz metod inteligencji obliczeniowej wykorzystywanych do jego rozwiązania. Problem komiwojażera należy do klasy problemów NP-zupełnych, dla których stosowanie algorytmów dokładnych jest niepraktyczne i do jego rozwiązania wykorzystuje się najczęściej algorytmy heurystyczne. W pracy opisano algorytm genetyczny jako przykład obliczeń ewolucyjnych oraz algorytmy optymalizacyjne kolonią mrówek i rojem cząstek, jako przykład inteligencji rojowej. Wszystkie trzy algorytmy zostały szczegółowo opisane i dla każdego z nich przedstawiono przykład implementacji. Każdy algorytm został poddany eksperymentom, które pozwoliły na porównanie możliwości obliczeniowych oraz efektywności proponowanych algorytmów. Do eksperymentów wykorzystana została aplikacja napisana na potrzeby pracy w języku C++, w której zaimplementowano przedstawione w pracy propozycje algorytmów. Program ma charakter dydaktyczny, został wyposażony w przyjazny dla użytkownika interfejs graficzny, który umożliwia przeprowadzenie testów oraz porównanie możliwości algorytmów z ich dowolną konfiguracją parametrów dla różnych przypadków problemu komiwojażera