A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP
This paper presents a discrete particle swarm optimization (DPSO) algorithm with heterogeneous (non-uniform) parameter values for solving the dynamic traveling salesman problem (DTSP). The DTSP can be modeled as a sequence of static sub-problems, each of which is an instance of the TSP. In the propo...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-07-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/21/8/738 |
| _version_ | 1811187128272420864 |
|---|---|
| author | Łukasz Strąk Rafał Skinderowicz Urszula Boryczka Arkadiusz Nowakowski |
| author_facet | Łukasz Strąk Rafał Skinderowicz Urszula Boryczka Arkadiusz Nowakowski |
| author_sort | Łukasz Strąk |
| collection | DOAJ |
| description | This paper presents a discrete particle swarm optimization (DPSO) algorithm with heterogeneous (non-uniform) parameter values for solving the dynamic traveling salesman problem (DTSP). The DTSP can be modeled as a sequence of static sub-problems, each of which is an instance of the TSP. In the proposed DPSO algorithm, the information gathered while solving a sub-problem is retained in the form of a pheromone matrix and used by the algorithm while solving the next sub-problem. We present a method for automatically setting the values of the key DPSO parameters (except for the parameters directly related to the computation time and size of a problem).We show that the diversity of parameters values has a positive effect on the quality of the generated results. Furthermore, the population in the proposed algorithm has a higher level of entropy. We compare the performance of the proposed heterogeneous DPSO with two ant colony optimization (ACO) algorithms. The proposed algorithm outperforms the base DPSO and is competitive with the ACO. |
| first_indexed | 2024-04-11T13:57:49Z |
| format | Article |
| id | doaj.art-433dcce6b8ed4d1b87a084b141de9f6c |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-11T13:57:49Z |
| publishDate | 2019-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-433dcce6b8ed4d1b87a084b141de9f6c2022-12-22T04:20:12ZengMDPI AGEntropy1099-43002019-07-0121873810.3390/e21080738e21080738A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSPŁukasz Strąk0Rafał Skinderowicz1Urszula Boryczka2Arkadiusz Nowakowski3Institute of Computer Science, University of Silesia in Katowice, Będzińska 39, 41-205 Sosnowiec, PolandInstitute of Computer Science, University of Silesia in Katowice, Będzińska 39, 41-205 Sosnowiec, PolandInstitute of Computer Science, University of Silesia in Katowice, Będzińska 39, 41-205 Sosnowiec, PolandInstitute of Computer Science, University of Silesia in Katowice, Będzińska 39, 41-205 Sosnowiec, PolandThis paper presents a discrete particle swarm optimization (DPSO) algorithm with heterogeneous (non-uniform) parameter values for solving the dynamic traveling salesman problem (DTSP). The DTSP can be modeled as a sequence of static sub-problems, each of which is an instance of the TSP. In the proposed DPSO algorithm, the information gathered while solving a sub-problem is retained in the form of a pheromone matrix and used by the algorithm while solving the next sub-problem. We present a method for automatically setting the values of the key DPSO parameters (except for the parameters directly related to the computation time and size of a problem).We show that the diversity of parameters values has a positive effect on the quality of the generated results. Furthermore, the population in the proposed algorithm has a higher level of entropy. We compare the performance of the proposed heterogeneous DPSO with two ant colony optimization (ACO) algorithms. The proposed algorithm outperforms the base DPSO and is competitive with the ACO.https://www.mdpi.com/1099-4300/21/8/738dynamic traveling salesman problempheromonediscrete particle swarm optimizationheterogeneoushomogeneous |
| spellingShingle | Łukasz Strąk Rafał Skinderowicz Urszula Boryczka Arkadiusz Nowakowski A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP Entropy dynamic traveling salesman problem pheromone discrete particle swarm optimization heterogeneous homogeneous |
| title | A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP |
| title_full | A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP |
| title_fullStr | A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP |
| title_full_unstemmed | A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP |
| title_short | A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP |
| title_sort | self adaptive discrete pso algorithm with heterogeneous parameter values for dynamic tsp |
| topic | dynamic traveling salesman problem pheromone discrete particle swarm optimization heterogeneous homogeneous |
| url | https://www.mdpi.com/1099-4300/21/8/738 |
| work_keys_str_mv | AT łukaszstrak aselfadaptivediscretepsoalgorithmwithheterogeneousparametervaluesfordynamictsp AT rafałskinderowicz aselfadaptivediscretepsoalgorithmwithheterogeneousparametervaluesfordynamictsp AT urszulaboryczka aselfadaptivediscretepsoalgorithmwithheterogeneousparametervaluesfordynamictsp AT arkadiusznowakowski aselfadaptivediscretepsoalgorithmwithheterogeneousparametervaluesfordynamictsp AT łukaszstrak selfadaptivediscretepsoalgorithmwithheterogeneousparametervaluesfordynamictsp AT rafałskinderowicz selfadaptivediscretepsoalgorithmwithheterogeneousparametervaluesfordynamictsp AT urszulaboryczka selfadaptivediscretepsoalgorithmwithheterogeneousparametervaluesfordynamictsp AT arkadiusznowakowski selfadaptivediscretepsoalgorithmwithheterogeneousparametervaluesfordynamictsp |