Adaptacyjny algorytm optymalizacji stadnej cząsteczek dla dynamicznego problemu komiwojażera

Abstract

The main assumption of the dissertation is the application of pheromone memory in the discrete version of the PSO algorithm (Discrete Particle Swarm Optimization) with a view to adjusting it to solving the DTSP - DTSP (Dynamic Traveling Salesman Problem). The Traveling Salesman Problem has not only a theoretical (many combinatorial problems can be reduced to the TSP problem), but also a practical meaning - especially in transport, from which it originated. The reasons behind the creation of the dynamic version of the problem are practical. What can happen very often in the road is traffic congestion, as a result of which the route is longer. The distance between vertices may refer not only to the distance but also, e.g. time or also incurred cost. Owing to that the scope of applications of the static and dynamic TSP is significantly wider. In this dissertation the Dynamic Traveling Salesman Problem was defined as a sequence of consecutive static Traveling Salesman Problems (sub-problems). The difference between one another lies in some percent of changes in the distance matrix. Despite the substantial number of works dedicated to both the static and dynamic problem, many questions still remain unanswered. These especially concern the dynamic version of TSP. The following two areas are explored in this dissertation: • theoretical and practical analysis of the Traveling Salesman Problem, as well as its dynamic version, • overview of literature connected with the computational intelligence and the most important concepts related to this field of science, among others synergy or cooperation, • description of selected computational intelligence algorithms together with explanation of how they work. The subsequent chapters include: • description of how the version of the Particle Swarm Optimization Algorithm with pheromone suggested in the dissertation works, as well as the means of adjusting it to the discussed problem, • analysis of the influence of the values of parameters of the prepared solutions on the quality of the achieved results, • description of the self-adaptive (heterogenic) version of the DPSO algorithm, • assessment of the usefulness of knowledge regarding the solution to the previous sub-problem, in order to accelerate the convergence of the DPSO algorithm for the new sub-problem in the solved DTSP problem, • comparison, by the means of static tests, of the hybrid DPSO algorithm with pheromone with the selected computational intelligence algorithms: ACO (Ant Colony Optimization) and PACO (Population Ant Colony Optimization). The tool suggested in the dissertation makes use of a limited list of neighborhoods for every vertex. This procedure reduces the overview of solution space and hence improves the rate of algorithm convergence. It has some disadvantages, e.g. the probability of finding the solution decreases in case of a lack of an edge that would belong to the optimum solution in the vertex neighborhood. Very effective Helsgaun's neighborhood was applied in the dissertation. Substantial attention was also given to examination of the influence of various parameter values on the functioning of the DPSO algorithm with pheromone, which was the purpose of creating a heterogeneous algorithm. In algorithm every particle can have different parameter values. However, their complete randomness may lead to chaotic solution space searching. Therefore, in order to prevent that a proper distribution of similarities of selection of given parameter values was chosen. It was preceded by an analysis of characteristic values of the DPSO algorithm with pheromone. The diversity of parameter values improved the quality of the obtained results. However, the main reason behind creating the heterogeneous version was the reduction of the number of algorithm parameters. The final parameters were restricted to the number of iterations, size of swarm and size of neighborhood. These are parameters, the values of which should be defined on the basis of the size of the (n) problem and the available computational budget, since the first two parameters influence the computational time. The third parameter influences the degree of exploration and exploitation of the solution space. The thesis of the dissertation „The Application of Pheromone Memory and Heterogeneity in the Discrete PSO Algorithm for the Dynamic Traveling Salesman Problem” Makes it Possible to Improve the Quality of the Obtained Results was proved on the basis of the results of computational experiments subjected to statistical analysis.