Next Article in Journal
Fluid Flow and Entropy Generation Analysis of Al2O3–Water Nanofluid in Microchannel Plate Fin Heat Sinks
Next Article in Special Issue
Surfing on Fitness Landscapes: A Boost on Optimization by Fourier Surrogate Modeling
Previous Article in Journal
Electron Traversal Times in Disordered Graphene Nanoribbons
Previous Article in Special Issue
User-Oriented Summaries Using a PSO Based Scoring Optimization Method
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Entropy
Volume 21
Issue 8
10.3390/e21080738
entropy-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP

by
Łukasz Strąk
*,
Rafał Skinderowicz
,
Urszula Boryczka
and
Arkadiusz Nowakowski
Institute of Computer Science, University of Silesia in Katowice, Będzińska 39, 41-205 Sosnowiec, Poland
*
Author to whom correspondence should be addressed.
Entropy 2019, 21(8), 738; https://doi.org/10.3390/e21080738
Submission received: 12 June 2019 / Revised: 23 July 2019 / Accepted: 24 July 2019 / Published: 27 July 2019
(This article belongs to the Special Issue Unconventional Methods for Particle Swarm Optimization)
Browse Figures
Versions Notes

Abstract

:
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.

Graphical Abstract

1. Introduction

In recent years, considerable attention has been paid to optimization in a dynamically-changing environment in which the problem being solved is modified periodically or even continuously [1]. This interest is related to the growing practical demand for such solutions. For example, in the problem of task scheduling in a factory, a change to the production schedule might be required if there is a malfunction of part of the production line. The optimization algorithms should be able to adapt rapidly to changes so that the quality of the generated solutions remains acceptable. A problem in which the input data are conditional upon time is called a dynamic optimization problem (DOP). The aim of optimization in a DOP is a constant trace and an adaptation to changes, in order to allow high-quality solutions to be found efficiently [2].
A simple example of a DOP is the dynamic traveling salesman problem (DTSP). This consists of a sequence of static traveling salesman problem (TSP) instances (sub-problems). Each successive sub-problem is created on the basis of the previous one. A portion of the sub-problem’s data is transferred unchanged from the predecessor, while the remaining portion is modified. Figure 1 summarizes this concept.
The aim is to find an optimal solution to every sub-problem. If all the sub-problems are solved to optimality, then the resulting sum of the solution (route) lengths is also minimal. Our DTSP benchmark generator includes the optimal value for every sub-problem; hence, the aim can be expressed in terms of finding the minimal sum of the differences between the generated solutions and the optima for the sub-problems. If the value of the sum is zero, then the optimum value is found for every sub-problem.
The particle swarm optimization (PSO) algorithm is an optimization technique created by Kennedy and Eberhart [3] in 1995. This technique is inspired by the natural behavior of a group of animals, e.g., a shoal of fish or a flock of birds. Every particle represents one of the possible solutions to a problem. In the continuous optimization case, the solution is a point in a real-valued space. The movement of the swarm can be interpreted as searching in the solution space. At the beginning of execution of the algorithm, the position of each particle is chosen randomly. Then, in each iteration of the algorithm, the velocities of the particles are calculated (direction of searching) and their positions updated. This results in a new solution to the problem. The velocity of the particle is influenced by the best-so-far solution (position) of the swarm and the best-so-far (previous) position of the particle. This process allows the swarm of particles to learn and move towards the areas of the problem solution space that contain higher quality solutions. The movement of the swarm in the solution space is described by the following equations:
v → i k + 1 ← ω · v → i k + U → ( 0 , ϕ 1 ) ⊗ ( p B e s t → i − x → i k ) + U → ( 0 , ϕ 2 ) ⊗ ( g B e s t → − x → i k ) ,
x → i k + 1 ← x → i k + v → i k + 1 , v → , x → , g B e s t → , p B e s t → i ∈ R n ,
where i indexes the particles, k is the current iteration, v → i k is the velocity of the i-th particle in the k-th iteration, x → i k is the position of the particle equal to one of the solutions of the problem, the function U ( 0 , ϕ ) takes a uniform random value in the range [ 0 , ϕ ] , and ω is an inertia parameter. The variables p B e s t → i and g B e s t → denote the best-so-far solutions found by the particle and by the swarm, respectively, and ϕ 1 and ϕ 2 are cognitive and social parameters, respectively, that scale the influence of p B e s t i → and g B e s t → on the position of the next particle.
Initially, the algorithm was created for optimization in a continuous space, but was later adapted to discrete optimization. In 1997, Kennedy and Eberhart [4] presented the first discrete PSO (DPSO) algorithm, in which the particle position was a binary vector and the velocity (direction of movement through the solution space) was the probability of a binary negation of the bits of the particle position. In 2004, Clerc [5] proposed a new DPSO algorithm and applied it to solve the TSP. In this algorithm, the particle position was a vector of vertices, while the velocity comprised a list of pairs of vertices, which changed in the next solution. In 2007, Shi et al. [6] presented an improved DPSO algorithm, which they used to solve the following TSP instances: eil51, berlin52, st70, eil76, and pr70. In their algorithm, the particle position is a permutation, and its modification resembles the well-known crossover found in genetic algorithms. Shi et al. showed that the proposed algorithm is capable of solving the generalized TSP, in which the edge lengths do not satisfy the triangle inequality. The homogeneous and heterogeneous versions of the DPSO algorithm described in the present paper are based on work by Zhong et al. [7] and on our previous DTSP variant [8]. In the implementation presented here, the particle position comprises a set of edges connecting TSP cities (nodes) and the corresponding probabilities of selecting the edges to the next solution (the next position of the particle). As far as we know, our previous work on applying the DPSO to solving the DTSP was the first publication on this topic in the literature.
The original PSO algorithm and its discrete versions are homogeneous, i.e., all particles have the same values of the parameters and hence share the same pattern of moving through a solution space [4]. However, heterogeneous populations are common in a natural environment [9]. One of the most important problems with the PSO concerns the balance between exploration and exploitation. A heterogeneous population allows particles to have various patterns of moving through the solution space and thus to exhibit different levels of emphasis on the exploitation and exploration of the solution space. It is possible that some of the parameter values might turn out to be useful at the beginning of the algorithm runtime, and others in the later stages. In this way, the balance between exploration and exploitation can be influenced [10,11].

1.1. Self-Adaptivity

To solve hard problems, algorithms like bio-inspired algorithms use different models, which change their behavior and allow performing specific tasks, like keeping a population diversity, increasing a search range, etc. Switching a model in order to solve a problem in a changing environment is called adaptation. Self-adaptivity can, therefore, be defined as the capability of a system to achieve its goals in a changing environment, by autonomously executing and switching between models [12]. Adaptivity has been widely studied since the mid-1960s, and several application areas relating to self-adaptivity have assumed greater importance. Thereafter, the scientific literature on self-adaptivity has been extensive, mainly over the past 16 years [13]. Self-adaptivity has been studied from the perspectives of software engineering, systems theory, artificial intelligence, and computer science, providing theoretical foundations and application fields such as: control engineering, mobile and autonomous robots, multi-agent systems, fault-tolerant computing, dependable computing, distributed systems, autonomous computing, self-managing systems, autonomous communications, adaptable user interfaces, machine learning, economic and financial systems, business and military strategic planning, sensor networks, pervasive and ubiquitous computing, etc. [13]. Another application is the self-adaptivity of bio-inspired algorithms like:
  • evolution algorithms [14],
  • differential evolution [15],
  • particle swarm optimization [16].
Self-adaptivity from the perspectives of bio-inspired algorithms indicates automatic adjustment of an algorithm’s control parameters. Control parameters can be of various forms, for example: mutation rates, recombination probabilities, population size, or selection operators. We have combined particle swarm optimization with self-adaptation through the implementation of the characteristic sets of parameter values’ switching mechanism, as described in the Section 5.

1.2. Contributions

Our previous work focused mainly on DPSO with homogeneous (uniform) parameter values [8]. In this paper, we extend our initial work on DPSO in which individual particles may have non-uniform (varying) values of the parameters [17]. Specifically, our contributions are as follows:
  • We propose a method for automatically setting the values of four crucial DPSO parameters. This method is based on discrete probability distributions defined to diversify the behaviors of the particles in the heterogeneous DPSO. The aim of this diversification is to improve the convergence of the algorithm.
  • We perform an analysis of the convergence of the proposed algorithm based on computational experiments conducted on a set of DTSP instances of varying sizes. We discuss the relationships between the values of the DPSO parameters and their effect on particle movement through the problem’s solution search space.
  • We study the diversity of the population of particles in the proposed heterogeneous DPSO and the original approach based on the information entropy calculated in two ways. The former method considers the edges, which are building blocks of the solutions to the TSP and DTSP. The latter focuses only on the quality of the solutions
  • We compare the efficiency of the proposed heterogeneous DPSO with that of the base DPSO and two algorithms based on ant colony optimization (ACO). The results show that the proposed algorithm outperforms the base DPSO and is competitive with the ACO-based algorithms.
The structure of this paper is as follows. Section 2 presents a review of the literature concerning the DTSP. Section 3 describes the heterogeneous version of PSO. Section 4 gives a brief description of DPSO with pheromone. Section 5 describes the heterogeneous swarm. Section 6 presents our experimental results. Finally, Section 7 presents a summary and conclusions.

2. Dynamic Traveling Salesman Problem

The dynamic nature of the DTSP can entail changes in the distances between cities (nodes) and in the number of cities to be visited [18,19]. Every data transformation can trigger changes in local and global optima. The distance matrix can be defined as:
D ( t ) = { d i j ( t ) } n ( t ) × n ( t ) ,
where t is time, i and j denote vertices, and n is the number of vertices. Most often, it is assumed that the time is discrete, and hence, the DTSP can be viewed as a series of static TSP instances (Figure 1). Each sub-problem can be more or less similar to the previous one, depending on the number of changes and their magnitude. In this paper, we assume that only the distances between the cities are subject to change, while the number of nodes (vertices) remains constant.
Obviously, each of the DTSP sub-problems can be solved separately using one of the methods developed for the TSP [20]. Nevertheless, if the differences between consecutive DTSP sub-problems are small, it is possible that the optimal solutions differ only slightly. In such a case, it is possible to use the knowledge gathered while solving the previous sub-problem to speed up solving the current one. A summary of recent research on solving the DTSP that has been presented in the literature is given in Table 1.

3. Heterogeneity

Heterogeneity can be defined as the absence of uniformity (diversity). In computational intelligence algorithms, it can appear in many ways. A taxonomy of the various levels of heterogeneity that are possible in the PSO algorithm was given by Montes de Oca et al. [11], who divided heterogeneity into the following four categories:
  • Neighborhood heterogeneity: This concerns cases in which the size of the neighborhood is different for every particle, and hence, the virtual topology of connections between particles is not regular. Some particles can have a wider influence than others on the movement of the swarm.
  • Best-particle heterogeneity: Here, there can be variations in the method of selecting the best particle, i.e., the particle whose position is used when updating the current velocity and position. For instance, one particle might update its position following the best particle in its (small) neighborhood, while the second particle might be fully informed and follow the global best particle.
  • Heterogeneity of the position update strategy: Here, the particles differ in their patterns of movement (searching) through the solution space. For example, one group of particles might explore the solution space, while the other group might conduct a local search by restricting their velocities or even positions to a certain range. This type of heterogeneity diversifies the population to the greatest extent, since it provides the greatest flexibility in diversifying particle movement.
  • Heterogeneity of parameter values: Here, each particle or group of particles in the swarm can have different values of the parameters. For example, some particles might have a large inertia ω and explore the solution space, whereas other particles might have a small value of ω and perform the search locally (around the best position found). Although this type of heterogeneity is not as flexible as the heterogeneity of the position update strategy, it requires relatively few changes to the PSO, since only the values of the particle parameters need be set individually. It is this strategy that we apply in the proposed heterogeneous DPSO algorithm.
Although there is a lack of information in the literature with regard to heterogeneity in the case of the DPSO algorithm, it is possible to adapt the solutions proposed for standard PSO.
There are several methods of measuring population diversity in the population-based optimization algorithms. One of them is entropy, which is a formal method often found in the literature. Essentially, entropy is a measure of disorder or uncertainty. In information theory, it determines the amount of information within data and is frequently used for analytical purposes. It can also be used to control the behavior of an algorithm, e.g., as a stopping criterion [36,37] or a signal for resetting the population if the entropy drops below a threshold value [38]. It can be applied as a criterion for achieving a specified diversity of the initial population, as well. For example, new solutions can be created until the entropy exceeds a specific limit, which allows improving the convergence to the optimal solution [39,40].
The solution proposed in the article uses the last category of heterogeneity of the above classification: a variety of parameter values.

4. DPSO with Pheromone

A (homogeneous) DPSO algorithm with pheromone was proposed in our previous work [8], and this section contains only a brief description. Adaptation to a discrete space forces some changes to the original PSO algorithm designed for solving continuous optimization problems. All variables (i.e., X and V) become sets of edges instead of real-valued vectors. An edge is represented by a tuple: 〈 p , { a , b } 〉 , where a and b are endpoints and p is the probability of selecting the edge ( a , b ) to become part of the constructed solution. The solution to the TSP problem is the set of edges that form the Hamilton cycle. The equations governing the movement of the particles become:
V i k + 1 = c 2 · U ( 0 , 1 ) · ( g B e s t ∖ X i k ) ∪ c 1 · U ( 0 , 1 ) · ( p B e s t i ∖ X i k ) ∪ ω · V i k ,
X i k + 1 = Δ τ k ( V i k + 1 ) ⊕ c 3 · U ( 0 , 1 ) · X i k ,
where i is the particle index, k is the iteration, and U ( 0 , 1 ) is a uniform random number from the range [ 0 , 1 ] . The operators ∪ and ∖ denote the classical operations on sets, while the multiplication of a set by a scalar (i.e., c 2 · U ( 0 , 1 ) · ( g B e s t ∖ X i k ) ) represents multiplication of the p value of each edge by the scalar. The ⊕ operator does not exist in classical PSO; its purpose in DPSO is to complete the solution with missing edges so that it forms a Hamiltonian cycle. After the velocity is calculated, the result set may not create a Hamiltonian cycle. To create a feasible solution, the algorithm will be adding edges from nearest neighbor heuristics until a feasible solution is created. The Δ τ function changes the probability p of the edge using the pheromone matrix familiar from ACO. The pheromone has two main functions in the algorithm:
  • It alters the probability of edge selection during the solution construction process; i.e., the higher the value of the pheromone, the greater is the probability of selecting the corresponding edge. In other words, the pheromone serves as an additional memory of the swarm, allowing it to learn the structure of high-quality solutions and, potentially, improve the convergence of the algorithm.
  • The pheromone matrix created while solving the current DTSP sub-problem is retained and used when solving the next sub-problem. This allows knowledge about the previous solution search space to be transferred with the aim of helping the construction of high-quality solutions to the current sub-problem. This implicitly assumes that the changes between consecutive sub-problems are not very great, so that the high-quality solutions to the current sub-problem share most of their structure with the high-quality solutions to the previous one.
For example, let G u be the undirected graph defined as follows:
V u = { 1 , 2 , 3 , 4 , 5 , 6 } , | E u | = n 2
(all two-pair combinations of the set G u ). Let the first particle in the first iteration represent the solution:
X 0 1 = { 〈 1 , { 1 , 4 } 〉 , 〈 1 , { 4 , 2 } 〉 , 〈 1 , { 2 , 5 } 〉 , 〈 1 , { 5 , 3 } 〉 , 〈 1 , { 3 , 6 } 〉 , 〈 1 , { 6 , 1 } 〉 } , V 0 1 = { 〈 1 , { 2 , 5 } 〉 } , g B e s t = { 〈 1 , { 1 , 2 } 〉 , 〈 1 , { 2 , 3 } 〉 , 〈 1 , { 3 , 4 } 〉 , 〈 1 , { 4 , 5 } 〉 , 〈 1 , { 5 , 6 } 〉 , 〈 1 , { 6 , 1 } 〉 } , p B e s t 0 = { 〈 1 , { 1 , 2 } 〉 , 〈 1 , { 2 , 3 } 〉 , 〈 1 , { 3 , 5 } 〉 , 〈 1 , { 5 , 4 } 〉 , 〈 1 , { 4 , 6 } 〉 , 〈 1 , { 6 , 1 } 〉 } .
The result of applying Equation (4) is:
g B e s t ∖ X 0 1 = { 〈 1 , { 1 , 2 } 〉 , 〈 1 , { 2 , 3 } 〉 , 〈 1 , { 3 , 4 } 〉 , 〈 1 , { 4 , 5 } 〉 , 〈 1 , { 5 , 6 } 〉 } , p B e s t 0 ∖ X 0 1 = { 〈 1 , { 1 , 2 } 〉 , 〈 1 , { 2 , 3 } 〉 , 〈 1 , { 5 , 4 } 〉 , 〈 1 , { 4 , 6 } 〉 } .
The next velocity of the particle V 0 2 after the operation of multiplication by c 1 · r a n d ( ) , c 2 · r a n d ( ) , or  ω · r a n d ( ) is:
( g B e s t ∖ X 0 1 ) ∪ ( p B e s t i ∖ X 0 1 ) ∪ V 0 1 = { 〈 0.3 , { 1 , 2 } 〉 , 〈 0.1 , { 2 , 3 } 〉 , 〈 0.5 , { 3 , 4 } 〉 , 〈 0.6 , { 4 , 5 } 〉 , 〈 0.1 , { 5 , 6 } 〉 , 〈 0.2 , { 1 , 2 } 〉 , 〈 0.9 , { 2 , 3 } 〉 , 〈 0.7 , { 5 , 4 } 〉 , 〈 0.4 , { 4 , 6 } 〉 } .
The edge from the previous velocity is not added to the sum, because of the rule forbidding any vertex (node) from occurring more than four times ( deg ( 2 ) = 5 ) [7]. Let us assume that pheromone reinforcement is equal to zero (no influence) and that the random function returns the values 0.1, 0.7, 0.49, 0.5, 0.9, 0.3, 0.6, 0.55, 0.39. Then, after the filtration stage, the (incomplete) particle position set is:
X 0 2 = { 〈 0 . 3 , { 1 , 2 } 〉 , 〈 0 . 5 , { 3 , 4 } 〉 , 〈 0 . 6 , { 4 , 5 } 〉 , 〈 0 . 9 , { 2 , 3 } 〉 , 〈 0 . 7 , { 5 , 4 } 〉 , 〈 0 . 4 , { 4 , 6 } 〉 } .
The next stage is more restrictive. Any edge that creates an incorrect tour is removed from the set. The edge 〈 0.4 , { 4 , 6 } 〉 is rejected, because deg ( 4 ) = 3 . The edge 〈 0.7 , { 5 , 4 } 〉 is also rejected, because the edge with { 4 , 5 } endpoints already exists in the next position. The next incomplete particle position is:
X 0 2 = { 〈 0 . 3 , { 1 , 2 } 〉 , 〈 0 . 5 , { 3 , 4 } 〉 , 〈 0 . 6 , { 4 , 5 } 〉 , 〈 0 . 9 , { 2 , 3 } 〉 } .
At this stage, the first part of Equation (5) is completed. The operation ⊕ adds to the result the edge ( X 0 2 ) 〈 1 , { 6 , 1 } 〉 chosen from the previous particle position set. To complete the set to form the Hamiltonian cycle, the nearest-neighbor heuristic is used, and the edge 〈 1 , { 5 , 6 } 〉 is selected. The final particle position is:
X 0 2 = { 〈 1 , { 1 , 2 } 〉 , 〈 1 , { 2 , 3 } 〉 , 〈 1 , { 3 , 4 } 〉 , 〈 1 , { 4 , 5 } 〉 , 〈 1 , { 5 , 6 } 〉 , 〈 1 , { 6 , 1 } 〉 } .
Figure 2 presents a visualization of all the primary operations, i.e., the edges from the particle’s previous position X i k − 1 before the filtration (a), after the filtration (b), and the final particle position (c). The dashed line marks the edge from Equation (5) and the dotted line the edge from the completion process (c).

5. Heterogeneous Swarm

The DPSO has four main parameters that influence particle movement through the solution search space: c 1 , c 2 , c 3 , and ω . To better understand how the parameter values are set in the proposed heterogeneous DPSO, it is helpful to focus on how the parameters govern the swarm behavior. Zhong et al. [7] suggested the following ranges of values for the parameters: c 1 ∈ [ 0 , 1.5 ] , c 2 , c 3 ∈ [ 0 , 2 ] , ω ∈ [ 0 , 0.6 ] . Setting the parameters to small values, i.e., close to the start of the range, forces the particles to change their positions (edges) frequently, since the probability of selecting the edges from the current best positions (local and global) is relatively small. Furthermore, in the initial stage of execution of the algorithm, the pheromone values cannot guide the construction process, since they are also small. On the other hand, setting the parameters to higher values forces the solution construction process to become more exploitative, since the constructed solutions resemble the previously-obtained high-quality solutions. Based on the expertise gathered during our earlier studies of the DPSO algorithm, we have selected the characteristic sets of the parameter values, which are shown in Table 2. For each set, we provide a brief description of the corresponding DPSO particle behavior. Below, we present a more detailed description of the sets, supported by some experimental data analysis.
Figure 3 presents the numbers of new edges for X k − 1 and X k (the previous and current positions). The blue line indicates the particle parameter values, which often change edges (Setting 1), and the red line is for more stable particles, with less frequent changes (Setting 4).
The first and fourth sets of parameter values from Table 2 differ in terms of the dynamics of changes in the number of common edges between the current and previous positions of the particle. For the small parameter values taken from the first set, the probability of edge selection to the next position (p) is very small and can only be increased if the corresponding pheromone has a high value. On the other hand, in the fourth set of parameters, c 3 has the highest value from the range. As a result, the edges from the previous position will be added to the next position of the particle with high probability. Both characteristics can be clearly seen in Figure 3. The blue line is below the red one, which means that the position of the particle from the first set has more changed edges.
An analogous comparison can be made for the second and third sets of values shown in Table 2. Figure 4 shows the average numbers of common edges between the current position of a particle, X k , and the best positions, i.e., the particle’s local best p B e s t and the swarm’s best g B e s t . For the second set of parameter values, the number of edges shared with p B e s t was higher than for the third set. This was caused by the high c 1 value, equal to two, which affected in particular the initial iterations of the algorithm. After the first 100 iterations, the number began to change as p B e s t and g B e s t became more similar. This is an effect of the high value of the c 2 parameter in the third set of parameter values. The bottom plot in Figure 4 shows the average number of common edges for the sets X k and g B e s t . We can see a growing similarity of the current position X k to the current best position p B e s t . This effect can be observed for both sets of parameter values. The number of common edges was higher for the third set, since it had the highest possible value of c 1 .
An analogous comparison, this time for Sets 5–8 from Table 2, is presented in Figure 5. The largest differences can be observed for the fifth and the sixth sets, and the smallest for the seventh and eighth. This is due mainly to the small differences between the parameter values, namely Δ c 1 = 0.25 and Δ ω = 0.25 (the remaining parameters c 2 and c 3 have the same value).
Based on the number of times each value of a parameter appears in Table 2, an independent discrete probability distribution for the parameters can be defined:
  • c 1 : P ( 0.1 ) = 0.4, P ( 0.75 ) = 0.15, P ( 1.5 ) = 0.3, P ( 1.75 ) = 0.15;
  • c 2 and c 3 : P ( 0.1 ) = 0.4, P ( 1 ) = 0.15, P ( 1.5 ) = 0.15, P ( 2 ) = 0.3;
  • ω : P ( 0.1 ) = 0.4, P ( 0.25 ) = 0.2, P ( 0.5 ) = 0.4.
This allows the values of the DPSO parameters to be controlled, while also allowing them to be mixed together; i.e., any combination of the listed values is possible. As a result, we can expect that both the exploration- and exploitation-oriented behaviors of the particles will be present in a swarm, hence increasing the chances of finding high-quality solutions regardless of the “landscape” of the solution space. This also has the advantage of being more computationally efficient compared with a completely-random setting (e.g., with uniform probability), since, in the latter case, one would need a larger number of particles to observe a similar mix of characteristic particle behaviors.

6. Experimental Results

This section is divided into three parts. In the first, we focus on the effect of the parameter values on the performance of individual particles in the heterogeneous DPSO algorithm. In the second, we conduct a comparison between the homogeneous DPSO, the proposed heterogeneous DPSO, and two well-known ACO algorithms, namely the ant colony system (ACS) and population-based ACO (PACO). The third part presents a study of the population entropy and its influence on the algorithm convergence.

6.1. Convergence Analysis for Various Sets of Parameters

To assess the performance of individual particles in a swarm of the heterogeneous DPSO, we counted the number of times the particle improved the current global best solution g B e s t . The parameter values were set randomly according to the discrete probability distribution described in Section 5, independently of the other parameters values. The gr666 TSP instance (666 cities) was used as a test bed.
Table 4 shows the sets of parameter values for which the particles were able to improve the global best solution most frequently. As can be seen, the top two are the sets in which the parameters c 1 , c 2 , c 3 , and ω are relatively small. These values favor exploratory behavior of the DPSO particles, and hence, the particles are more likely to find an improved solution, especially in the initial phases of algorithm execution. The set for which the behavior should be more stable and less exploratory, i.e., with c 2 = 2 , turned up as third in the ranking. The relatively large difference of 53 between the second and third positions is also noteworthy. The lower rankings of the particles exhibiting more exploitative behavior confirmed that they could be more important in the later stages of algorithm execution, in which smaller changes to the solution structure are preferred.
To clarify this distinction, we analyzed which values of the parameters proved to be working best during subsequent phases of algorithm execution. The phases were defined by dividing the total number of iterations into equal parts (intervals). For each interval, we ranked the sets of parameter values based on the number of times they led to a new global best solution within the respective interval. Table 5 presents the results, while Figure 6 shows the speed of convergence towards an optimum in each phase. As can be seen, different sets of parameter values dominate subsequent phases (intervals) of the computations. In the first interval (0–1250), the sets with small parameter values are predominant, which indicates that rapid changes in the particle solutions are beneficial. In the third interval (2500–3750), the sets of parameter values are mixed, i.e., they contain both small and high values. This can be interpreted as a sign that the exploration of the solution space slows down and, more importantly, becomes exploitation. In the last interval (5000–6144), the best particles have relatively high parameter values, which, combined with stronger pheromone reinforcement, causes mainly small changes to the particle positions.

6.2. Comparative Study

To evaluate the performance of the proposed DPSO algorithm, we compared it with the homogeneous version of the DPSO and with ACS and PACO, which are among the best-performing metaheuristics for the TSP and DTSP problems. The DTSP test instances were generated based on the static TSP instances from the well-known TSPLIB repository. The test data can be found in a public repository (https://github.com/lukaszstrak/DTSP-repository). Algorithm 1 presents an outline of the general test procedure used to solve the DPSO with the algorithms mentioned.
Algorithm 1 Outline of the procedure for solving the DTSP.
  • Load the static TSP instance  ▹ The original TSP instance becomes the first DTSP sub-problem
  • Initialize the algorithm-related data
  • while Stop criterion is not met do
  •     sub-problem-related initialization            ▹ Create swarm, neighborhood, etc.
  •     Solve the current sub-problem                ▹ Solve with DPSO, ACO, etc.
  •     Modify the current sub-problem to obtain the next one
  • end while
To make the comparison fair, all algorithms were solving the same DTSP instances, i.e., starting from the same static TSP and including the same DTSP-related changes to the positions of the cities. Each DTSP instance comprised 11 static TSP sub-problems, namely the original problem from TSPLIB and ten sub-problems resulting from random changes to the position of the cities. The gr666 problem was an exception, since it included only one sub-problem (the original TSPLIB problem). Figure 7 shows an example of a DTSP instance consisting of two static TSP sub-problems. The optimum solutions for each of the DTSP sub-problems were obtained using the well-known Concorde solver by Applegate et al. [41]. The number of changes in the city position between successive sub-problems was set to 3% in all DTSP cases.
Table 6 shows the parameter values of the two DPSO variants. The numbers of iterations used are shown alongside the results in Table 7. The size of the swarm and the size of the particle neighborhood were determined from preliminary computations, keeping in mind that both parameters strongly influence the computation time and the quality of the solutions. A smaller neighborhood limits the solution space and speeds up computation. However, too low a value could hamper finding the optimum. The parameters ( c 1 , c 2 , c 3 , ω , S w a r m S i z e , and n e i g h b o r h o o d ) for the homogeneous version of the DPSO were chosen based on preliminary computations and our previous work on DPSO.
The ACS and PACO parameters were set as follows: number of ants = 10; number of iterations = ⌊ 0.1 · p e v ⌋ ; β = 3 ; local and global pheromone evaporation coefficients α = 0.1 and ρ = 0.1 , respectively; and q 0 = ( n − 10 ) / n , where n is the size of the problem. For the PACO algorithm, q 0 = 0.8 was used, and the age-based strategy for updating the solution archive (of size five) was used. The values of the parameters were set based on preliminary computations and the suggestions by Cáceres el al. [42], in which the ACO was tested with a small computation budget.
All the considered algorithms, including DPSO and ACO, were allowed to construct and evaluate exactly the same number of solutions ( p e v ) to a problem. For example, the DPSO algorithm with 104 iterations and a swarm of size 32 constructed a total of p e v = 104 · 32 = 3328 solutions. All algorithms were implemented in the C# language and run on a computer with an Intel i7 3.2-GHz CPU. All computations were repeated 30 times, and the results were averaged.
For the smallest DTSP instance (berlin52), both DPSO versions generated results that were of similar quality and, at the same time, better than those of the ACO algorithms. For the larger instances, the heterogeneous DPSO showed a clear advantage over the homogeneous DPSO. The biggest differences were observed for the pcb442 and gr202 instances, for which the heterogeneous version generated higher quality solutions, especially if the number of iterations was low. This confirms that the heterogeneity of the parameter values resulted in a broader exploration of the solution search space. At the same time, the heterogeneous DPSO was also more consistent in finding high-quality solutions, which was manifested in the smaller average standard deviation compared with the homogeneous version. When the number of iterations grew, the advantage of the heterogeneous DPSO became less, confirming that, in the later stages of the computations, the exploitative nature of the algorithm became more important. Generally, both DPSO versions benefited from a larger number of iterations. Compared with the ACO algorithms, the results of the DPSO were worse in four out of six cases for the lowest number of iterations. However, for the largest number of iterations allowed, the DPSO lost only once (for the kroA200 DTSP instance) even though the ACO algorithms also benefited from the larger computation time. This suggests that, compared with the ACO algorithms, the DPSO variants converged more rapidly, although their search through the solution space was more explorative at the beginning. Increasing the number of iterations past a certain point allowed DPSO to outperform ACS and PACO in almost all cases.

6.3. Entropy Study

Maintaining a diversified population during the execution of the DPSO algorithm is a desired feature that may reduce the chance of getting stuck in local minima. In this section, we study the diversity of the population in the proposed self-adaptive DPSO and the original DPSO approach. In order to estimate the diversification, we used the entropy, which is measured in two ways. In the first way, the measurement concerns the edges comprising the solutions from the population (particles). Specifically, we defined a discrete probability distribution by counting edges’ occurrences in the population. For example, in the two following solutions (particles’ positions): { { 1 , 2 } , { 2 , 3 } , { 3 , 4 } , { 4 , 1 } }, and { { 1 , 2 } , { 2 , 4 } , { 4 , 3 } , { 3 , 1 } }, the edges { 1 , 2 } and { 3 , 4 } appear two times and { 2 , 3 } , { 1 , 4 } , { 2 , 4 } , and { 1 , 3 } appear once; hence, the entropy equals: H = − 2 · 2 2 log 2 ( 2 2 ) + 4 · 1 2 log 2 ( 1 2 ) = 2 . The second measure of the entropy was defined analogously, but the length of the solutions was used in the place of the edges. Figure 8 shows the population entropy, which counts the number of different edges for the proposed heterogeneous DPSO and the original homogeneous DPSO. The results were obtained for 30 runs of the algorithms, which solved the gr666 TSP problem instance. As can be seen, the entropy for the homogeneous DPSO was relatively large during the first few hundred iterations, but quickly fell to much lower levels. On the contrary, the entropy in the heterogeneous DPSO dropped faster during the initial stage of the algorithm execution, but after the first 2000 iterations, it consistently remained higher than in the homogeneous DPSO. The more balanced exploration to exploitation ratio resulting from the diversity of the particles’ behaviors can explain the higher levels of the entropy for the heterogeneous DPSO.
Figure 9 presents the box-plot of the entropy levels’ measurements based on the lengths of the solutions corresponding to the DPSO population. The results were consistent with the previous entropy observations, i.e., the solutions generated by the homogeneous DPSO were less diverse in terms of the tours lengths than the solutions obtained for the heterogeneous DPSO.
Similar results were obtained for the rat783 TSP instance (Figure A1 and Figure A2) and the pcb1173 TSP problem instance (Figure A3 and Figure A4), which can be found in the Appendix section. The parameters values were used the same as for the gr666 TSP problem instance (Table 6).
Summarizing, the presented study of the entropy confirmed the efficiency of the proposed method in enforcing the diversity of the behaviors of the particles in the DPSO. This was especially important in the later stages of the algorithm execution as the more diverse population increased the probability of escaping from local minima and often resulted in a higher quality of the final solutions, as confirmed by the results summarized in Table 7.

7. Conclusions

We have proposed a heterogeneous DPSO algorithm for solving the DTSP. In this algorithm, each particle can have different values of the crucial DPSO parameters c 1 , c 2 , c 3 , and ω . These values were chosen randomly according to the discrete probability distribution defined so that different behaviors of the DPSO particles could be obtained. Computational experiments conducted on a set of DTSP instances showed that it is beneficial if some particles explore the solution space while others are more exploitative, i.e., narrow their search by constructing solutions similar to the high-quality solutions found so far. The diversity of the parameter values in the heterogeneous DPSO produced a higher entropy of the population of the generated solutions in comparison with the homogeneous variant of the algorithm. As a consequence, the heterogeneous DPSO algorithm improved the quality of the results obtained compared with the homogeneous version. Moreover, the algorithm was easier to use, since fewer parameters had to be set manually, which is important because choosing the right values of the parameters can be especially difficult for the DTSP. It is also worth emphasizing that both versions of the DPSO algorithm were comparable to the proven ACS and PACO metaheuristics in terms of solution quality. In fact, heterogeneous DPSO was able to generate solutions of better quality than both of the ACO-based algorithms in most cases, while also exhibiting more rapid convergence if the computation time was extended.
In the future, we plan to test different types of heterogeneity in addition to the parameter diversity considered here.

Author Contributions

Conceptualization, Ł.S., R.S., U.B., and A.N.; formal analysis, Ł.S., R.S., and U.B.; investigation, Ł.S., R.S., U.B., and A.N.; methodology, Ł.S., R.S., U.B., and A.N.; project administration, Ł.S. and R.S.; resources, Ł.S. and R.S.; software, Ł.S. and R.S.; supervision, Ł.S. and R.S.; validation, Ł.S. and R.S.; visualization, Ł.S. and R.S.; writing, original draft, Ł.S., R.S., and U.B.; writing, review and editing, Ł.S., R.S., U.B., and A.N.

Funding

This research received no external funding

Conflicts of Interest

The authors declare no conflict of interest.

Abbreviations

The following abbreviations are used in this paper:
ACOant colony optimization
DPSOdiscrete particle swarm optimization
DTSPdynamic traveling salesman problem
PACOpopulation ant colony optimization
PSOparticle swarm optimization
TSPtraveling salesman problem

Appendix A. The Entropy Study for the Other TSP Instances

Entropy 21 00738 g0a1 550
Figure A1. The comparison of the entropy of the homogeneous and the proposed heterogeneous DPSO for the rat783 TSP problem instance. The entropy was calculated based on the numbers of occurrences of the edges comprising the particles’ solutions. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Figure A1. The comparison of the entropy of the homogeneous and the proposed heterogeneous DPSO for the rat783 TSP problem instance. The entropy was calculated based on the numbers of occurrences of the edges comprising the particles’ solutions. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Entropy 21 00738 g0a1
Entropy 21 00738 g0a2 550
Figure A2. The comparison of the entropy, which was calculated based on the solution lengths in the populations of the homogeneous DPSO and the proposed heterogeneous DPSO for the rat783 TSP problem instance. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Figure A2. The comparison of the entropy, which was calculated based on the solution lengths in the populations of the homogeneous DPSO and the proposed heterogeneous DPSO for the rat783 TSP problem instance. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Entropy 21 00738 g0a2
Entropy 21 00738 g0a3 550
Figure A3. The comparison of the entropy of the homogeneous and the proposed heterogeneous DPSO for the pcb1173 TSP problem instance. The entropy was calculated based on the numbers of occurrences of the edges comprising the particles’ solutions. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Figure A3. The comparison of the entropy of the homogeneous and the proposed heterogeneous DPSO for the pcb1173 TSP problem instance. The entropy was calculated based on the numbers of occurrences of the edges comprising the particles’ solutions. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Entropy 21 00738 g0a3
Entropy 21 00738 g0a4 550
Figure A4. The comparison of the entropy, which was calculated based on the solutions lengths in the populations of the homogeneous DPSO and the proposed heterogeneous DPSO for the pcb1173 TSP problem instance. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Figure A4. The comparison of the entropy, which was calculated based on the solutions lengths in the populations of the homogeneous DPSO and the proposed heterogeneous DPSO for the pcb1173 TSP problem instance. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Entropy 21 00738 g0a4

References

  1. Branke, J. Evolutionary approaches to dynamic environments. In Proceedings of the GECCO Workshop on Evolutionary Algorithms for Dynamics Optimization Problems, San Francisco, CA, USA, 7–11 July 2001. [Google Scholar]
  2. Li, W. A parallel multi-start search algorithm for dynamic traveling salesman problem. In Proceedings of the International Symposium on Experimental Algorithms, Crete, Greece, 5–7 May 2011; pp. 65–75. [Google Scholar]
  3. Kennedy, J.; Eberhart, R. Particle Swarm Optimization. In Proceedings of the IEEE International Conference on Neural Networks, Perth, WA, Australia, 27 November–1 December 1995; pp. 1942–1948. [Google Scholar]
  4. Kennedy, J.; Eberhart, R.C. A discrete binary version of the particle swarm algorithm. In Proceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics, Orlando, FL, USA, 12–15 October 1997; Volume 5, pp. 4104–4108. [Google Scholar]
  5. Clerc, M. Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem. In New Optimization Techniques in Engineering; Springer: Berlin/Heidelberg, Germany, 2004; Volume 141, pp. 219–239. [Google Scholar]
  6. Shi, X.H.; Liang, Y.C.; Lee, H.P.; Lu, C.; Wang, Q. Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf. Process. Lett. 2007, 103, 169–176. [Google Scholar] [CrossRef]
  7. Chen, W.N.; Zhang, J.; Chung, H.S.; Zhong, W.L.; Wu, W.G.; Shi, Y.H. A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems. IEEE Trans. Evol. Comput. 2010, 14, 3283–3287. [Google Scholar]
  8. Strąk, Ł.; Skinderowicz, R.; Boryczka, U. Adjustability of a discrete particle swarm optimization for the dynamic TSP. Soft Comput. 2018, 22, 7633–7648. [Google Scholar] [CrossRef]
  9. Hansell, M. Built by Animals; Oxford University Press: New York, NY, USA, 2007. [Google Scholar]
  10. Nepomuceno, F.V.; Engelbrecht, A.P. A Self-adaptive Heterogeneous PSO Inspired by Ants. In Swarm Intelligence; Springer: Berlin/Heidelberg, Germany, 2012; Volume 7461, pp. 188–195. [Google Scholar] [CrossRef]
  11. Montes de Oca, M.A.; Peña, J.; Stützle, T.; Pinciroli, C.; Dorigo, M. Heterogeneous Particle Swarm Optimizers. In IEEE Congress on Evolutionary Computation (CEC 2009); Haddow, P., Ed.; IEEE Press: Piscatway, NJ, USA, 2009; pp. 698–705. [Google Scholar]
  12. Ravindranathan, M.; Leitch, R. Heterogeneous intelligent control systems. IEE Proc. Control Theory Appl. 1998, 145, 551–558. [Google Scholar] [CrossRef]
  13. Macías-Escrivá, F.D.; Haber, R.; Del Toro, R.; Hernandez, V. Self-adaptive systems: A survey of current approaches, research challenges and applications. Expert Syst. Appl. 2013, 40, 7267–7279. [Google Scholar] [CrossRef]
  14. Meyer-Nieberg, S.; Beyer, H.G. Self-adaptation in evolutionary algorithms. In Parameter Setting in Evolutionary Algorithms; Springer: Berlin/Heidelberg, Germany, 2007; pp. 47–75. [Google Scholar]
  15. Qin, A.K.; Suganthan, P.N. Self-adaptive differential evolution algorithm for numerical optimization. In Proceedings of the 2005 IEEE Congress on Evolutionary Computation, Edinburgh, UK, 2–5 September 2005; Volume 2, pp. 1785–1791. [Google Scholar]
  16. Jiang, Y.; Li, X.; Huang, C. Automatic calibration a hydrological model using a master–slave swarms shuffling evolution algorithm based on self-adaptive particle swarm optimization. Expert Syst. Appl. 2013, 40, 752–757. [Google Scholar] [CrossRef]
  17. Boryczka, U.; Strąk, L. Heterogeneous DPSO Algorithm for DTSP. In Computational Collective Intelligence; Núñez, M., Nguyen, N.T., Camacho, D., Trawiński, B., Eds.; Springer: Cham, Switzerland, 2015; Volume 9330, pp. 119–128. [Google Scholar]
  18. Psaraftis, H. Dynamic vehicle routing problems. Veh. Routing Methods Stud. 1988, 16, 223–248. [Google Scholar]
  19. Li, C.; Yang, M.; Kang, L. A new approach to solving dynamic traveling salesman problems. In Proceedings of the 6th international conference on Simulated Evolution And Learning, Hefei, China, 15–18 October 2006; pp. 236–243. [Google Scholar]
  20. Cook, W.J. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation; Princeton University Press: Princeton, NJ, USA, 2011. [Google Scholar]
  21. Guntsch, M.; Middendorf, M. Pheromone Modification Strategies for Ant Algorithms Applied to Dynamic TSP. In Applications of Evolutionary Computing; Springer: Berlin/Heidelberg, Germany, 2001; Volume 2037, pp. 213–222. [Google Scholar]
  22. Eyckelhof, C.J.; Snoek, M. Ant Systems for a Dynamic TSP. In Ant Algorithms; Springer: Berlin/Heidelberg, Germany, 2002; Volume 2463, pp. 88–99. [Google Scholar]
  23. Helsgaun, K. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. Eur. J. Oper. Res. 2000, 126, 106–130. [Google Scholar] [CrossRef]
  24. Mavrovouniotis, M.; Yang, S. Ant Colony Optimization with Immigrants Schemes in Dynamic Environments. In Parallel Problem Solving from Nature, PPSN XI; Springer: Berlin/Heidelberg, Germany, 2010; Volume 6239, pp. 371–380. [Google Scholar]
  25. Simões, A.; Costa, E. CHC-Based Algorithms for the Dynamic Traveling Salesman Problem. In Applications of Evolutionary Computation; Springer: Berlin/Heidelberg, Germany, 2011; Volume 6624, pp. 354–363. [Google Scholar]
  26. Younes, A.; Basir, O.; Calamai, P. A Benchmark Generator for Dynamic Optimization. In Proceedings of the 3rd WSEAS International Conference on Soft Computing, Optimization, Simulation & Manufacturing Systems, Malta, 1–3 September 2003. [Google Scholar]
  27. Tinós, R.; Whitley, D.; Howe, A. Use of Explicit Memory in the Dynamic Traveling Salesman Problem. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Vancouver, BC, Canada, 12–16 July 2014; pp. 999–1006. [Google Scholar]
  28. Zhang, Y.; Zhao, G. Research on Multi-service Demand Path Planning Based on Continuous Hopfield Neural Network. In Proceedings of China Modern Logistics Engineering; Springer: Berlin/Heidelberg, Germany, 2015; pp. 417–430. [Google Scholar]
  29. Eaton, J.; Yang, S.; Mavrovouniotis, M. Ant colony optimization with immigrants schemes for the dynamic railway junction rescheduling problem with multiple delays. Soft Comput. 2016, 20, 2951–2966. [Google Scholar] [CrossRef]
  30. Mavrovouniotis, M.; Shengxiang, Y. Empirical study on the effect of population size on MAX-MIN ant system in dynamic environments. In Proceedings of the 2016 IEEE Congress on Evolutionary Computation (CEC), Vancouver, BC, Canada, 24–29 July 2016; pp. 853–860. [Google Scholar] [CrossRef]
  31. Mavrovouniotis, M.; Müller, F.M.; Shengxiang, Y.M.M. Ant Colony Optimization with Local Search for Dynamic Traveling Salesman Problems. IEEE Trans. Cybern. 2017, 47, 1743–1756. [Google Scholar] [CrossRef] [PubMed]
  32. Chowdhury, S.; Marufuzzaman, M.; Tunc, H.; Bian, L.; Bullington, W. A Modified Ant Colony Optimization Algorithm to Solve A Dynamic Traveling Salesman Problem: A Case Study with Drones for Wildlife Surveillance. J. Comput. Des. Eng. 2019, 6, 368–386. [Google Scholar] [CrossRef]
  33. Schmitt, J.P.; Baldo, F.; Parpinelli, R.S. A MAX-MIN Ant System with Short-Term Memory Applied to the Dynamic and Asymmetric Traveling Salesman Problem. In Proceedings of the 2018 7th Brazilian Conference on Intelligent Systems (BRACIS), São Paulo, SP, Brazil, 22–25 October 2018; pp. 1–6. [Google Scholar]
  34. Wang, Y.; Gao, S.; Todo, Y. Ant colony systems for optimization problems in dynamic environments. Swarm Intell. Princ. Curr. Algorithms Methods 2018, 119, 85. [Google Scholar]
  35. Huang, Y.W.; Liu, C.F.; Hu, S.F.; Fu, Z.H.; Chen, Y.Q. Dynamic Task Sequencing of Manipulator by Monte Carlo Tree Search. In Proceedings of the 2018 IEEE International Conference on Robotics and Biomimetics (ROBIO), Kuala Lumpur, Malaysia, 12–15 December 2018; pp. 569–574. [Google Scholar]
  36. Yu, S.; Príncipe, J.C. Simple stopping criteria for information theoretic feature selection. Entropy 2019, 21, 99. [Google Scholar]
  37. Saxena, D.K.; Sinha, A.; Duro, J.A.; Zhang, Q. Entropy-Based Termination Criterion for Multiobjective Evolutionary Algorithms. IEEE Trans. Evol. Comput. 2016, 20, 485–498. [Google Scholar] [CrossRef]
  38. Boryczka, U.; Strąk, L. Diversification and Entropy Improvement on the DPSO Algorithm for DTSP. In Intelligent Information and Database Systems; Nguyen, N.T., Trawiński, B., Kosala, R., Eds.; Springer International Publishing: Cham, Switzerland, 2015; Volume 9011, pp. 337–347. [Google Scholar]
  39. Diaz-Gomez, A.P.; Hougen, D. Empirical Study: Initial Population Diversity and Genetic Algorithm Performance. Artif. Intell. Pattern Recogn. 2007, 2007, 334–341. [Google Scholar]
  40. Cruz Chávez, M.; Martinez, A. Feasible Initial Population with Genetic Diversity for a Population-Based Algorithm Applied to the Vehicle Routing Problem with Time Windows. Math. Probl. Eng. 2016, 2016, 3851520. [Google Scholar] [CrossRef]
  41. Applegate, D.L.; Bixby, R.E.; Chvatal, V.; Cook, W.J. The Traveling Salesman Problem: A Computational Study; Princeton University Press: Princeton, NJ, USA, 2007; ISBN 978-0-691-12993-8. [Google Scholar]
  42. Cáceres, L.P.; López-Ibánez, M.; Stützle, T. Ant colony optimization on a budget of 1000. In Swarm Intelligence; Springer: Berlin/Heidelberg, Germany, 2014; pp. 50–61. [Google Scholar]
Entropy 21 00738 g001 550
Figure 1. An example of a dynamic optimization problem (DOP), the DTSP. A change in the problem instance may affect both the distances between the cities and the number of cities (vertices). This figure presents an example of a DTSP that includes a primary sub-problem ( I 0 ) and three successive sub-problems.
Figure 1. An example of a dynamic optimization problem (DOP), the DTSP. A change in the problem instance may affect both the distances between the cities and the number of cities (vertices). This figure presents an example of a DTSP that includes a primary sub-problem ( I 0 ) and three successive sub-problems.
Entropy 21 00738 g001
Entropy 21 00738 g002 550
Figure 2. Example of the calculation of a new particle position in the DPSO, (a) before the filtration, (b) after the filtration, and (c) the final particle position.
Figure 2. Example of the calculation of a new particle position in the DPSO, (a) before the filtration, (b) after the filtration, and (c) the final particle position.
Entropy 21 00738 g002
Entropy 21 00738 g003 550
Figure 3. Numbers of new (different) edges between X k − 1 and X k (the previous and current positions) in the DPSO solving the static kroA200 TSP instance (200 cities). The blue line indicates the particles with the first set of values from Table 2 (Setting 1), and the red line is for the more “stable” particles for which the fourth set (Setting 4) of parameter values was used. The remaining parameters were taken from Table 3. The values were averaged over 30 runs of the algorithm.
Figure 3. Numbers of new (different) edges between X k − 1 and X k (the previous and current positions) in the DPSO solving the static kroA200 TSP instance (200 cities). The blue line indicates the particles with the first set of values from Table 2 (Setting 1), and the red line is for the more “stable” particles for which the fourth set (Setting 4) of parameter values was used. The remaining parameters were taken from Table 3. The values were averaged over 30 runs of the algorithm.
Entropy 21 00738 g003
Entropy 21 00738 g004 550
Figure 4. Numbers of common edges between X k and p B e s t (top) and X k and g B e s t (bottom) for the second and third sets of characteristic parameter values (Table 2). The DPSO algorithm was run for the static kroA200 TSP instance (200 cities). The remaining parameters were taken from Table 3. The values were averaged over 30 runs of the algorithm.
Figure 4. Numbers of common edges between X k and p B e s t (top) and X k and g B e s t (bottom) for the second and third sets of characteristic parameter values (Table 2). The DPSO algorithm was run for the static kroA200 TSP instance (200 cities). The remaining parameters were taken from Table 3. The values were averaged over 30 runs of the algorithm.
Entropy 21 00738 g004
Entropy 21 00738 g005 550
Figure 5. Total numbers of common edges between the current position of the particle, X k , and p B e s t , and between X k and g B e s t for the DPSO solving the kroA200 TSP instance (200 cities) with the parameters given by Sets 5–8 in Table 2. The remaining parameters were taken from Table 3. The values were averaged over 30 runs of the algorithm.
Figure 5. Total numbers of common edges between the current position of the particle, X k , and p B e s t , and between X k and g B e s t for the DPSO solving the kroA200 TSP instance (200 cities) with the parameters given by Sets 5–8 in Table 2. The remaining parameters were taken from Table 3. The values were averaged over 30 runs of the algorithm.
Entropy 21 00738 g005
Entropy 21 00738 g006 550
Figure 6. Chart showing convergence with the optimum of the heterogeneous version of the algorithm for the gr666 problem.
Figure 6. Chart showing convergence with the optimum of the heterogeneous version of the algorithm for the gr666 problem.
Entropy 21 00738 g006
Entropy 21 00738 g007 550
Figure 7. Visualization of the optimum routes for the static kroA100 TSP instance (left side) and the DTSP instance after a random relocation of some cities (right side). The edges differentiating the new optimum from the previous are marked in red.
Figure 7. Visualization of the optimum routes for the static kroA100 TSP instance (left side) and the DTSP instance after a random relocation of some cities (right side). The edges differentiating the new optimum from the previous are marked in red.
Entropy 21 00738 g007
Entropy 21 00738 g008 550
Figure 8. The comparison of the entropy of the homogeneous and the proposed heterogeneous DPSO for the gr666 TSP problem instance. The entropy was calculated based on the numbers of occurrences of the edges comprising the particles’ solutions. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Figure 8. The comparison of the entropy of the homogeneous and the proposed heterogeneous DPSO for the gr666 TSP problem instance. The entropy was calculated based on the numbers of occurrences of the edges comprising the particles’ solutions. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Entropy 21 00738 g008
Entropy 21 00738 g009 550
Figure 9. The comparison of the entropy, which was calculated based on the solution length in the populations of the homogeneous DPSO and the proposed heterogeneous DPSO for the gr666 TSP problem instance. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Figure 9. The comparison of the entropy, which was calculated based on the solution length in the populations of the homogeneous DPSO and the proposed heterogeneous DPSO for the gr666 TSP problem instance. The plot shows the spread of the entropy levels, which were measured in 30 executions of the algorithms.
Entropy 21 00738 g009
Table
Table 1. Summary of recent papers on solving the DTSP with computational intelligence methods.
Table 1. Summary of recent papers on solving the DTSP with computational intelligence methods.
YearAuthorsAlgorithmDTSP Variant
2001Guntsch and
Middendorf [21]		ACO with local and global
reset of the pheromone		Addition/removal of vertices
2002Eyckelhof and Snoek [22]ACO with various variants of
pheromone matrix update to
maintain diversity		Changes in edge lengths with
time (simulated traffic jam
on a road)
2006Li et al. [19]GSInver-over and gene pool
with the α -measure [23]		CHN145 + 1: 145 cities and
one satellite
2010Mavrovouniotis and
Yang [24]		ACO with immigrants
scheme to increase
population diversity		Coefficients: frequency and
size of changes
2011Simões and Costa [25]CHCalgorithmA test involving the addition of
changes and their
subsequent withdrawal [26].
In that way, the optima at
the beginning and the end
are the same.
2014Tinós et al. [27]EA algorithmRandom changes in the problem
2014Zhang and Zhao [28]Hopfield neural networkSimulation of various types of
real random events in a street
2016Eaton et al. [29]ACO with immigrants schemeChanges in edge lengths.
Simulated delays of trains.
2016Mavrovouniotis and
Yang [30]		MMASEncoding of the problem is
changed, but the optimal solution
remains the same
2017Mavrovouniotis et al. [31]ACODistances between cities are
changed. The problem can be
transformed to an asymmetric one.
2018Chowdhury et al. [32]ACORandom DTSP, dynamic changes
occur randomly. Cyclic DTSP,
dynamic changes occur with
a cyclic pattern.
2018Schmitt et al. [33]MMASAcyclic DTSP with changes in
edge lengths with time
2018Yirui Wang et al. [34]ACO
2018Yan-Wei Huang et al. [35]MCTSAddition/removal of vertices
Table
Table 2. Characteristic sets of particle parameter values for the DPSO algorithm along with their influence on particle movement.
Table 2. Characteristic sets of particle parameter values for the DPSO algorithm along with their influence on particle movement.
No. c 1 c 2 c 3 ω Description
10.10.10.10.1Favors quick changes of position
22.00.10.10.1Emphasis on the information from p B e s t
30.12.00.10.1Emphasis on the information from g B e s t
40.10.12.00.5Very slow changes of position
50.751.01.00.25Weak p B e s t , g B e s t influence
61.251.51.50.5Stronger p B e s t , g B e s t influence
71.52.02.00.5Strong p B e s t , g B e s t influence
81.752.02.00.75Very strong p B e s t , g B e s t influence
Table
Table 3. Values of DPSO-related parameters.
Table 3. Values of DPSO-related parameters.
Problem c 1 c 2 c 3 ω SwarmSize Neighborhood
berlin520.50.50.50.2327
kroA1000.50.50.50.5647
kroA2000.50.50.50.5807
gr2020.50.50.50.510110
pcb4420.51.50.50.510415
gr6660.51.01.50.611230
Table
Table 4. Ranking of parameter values after 6144 iterations for which the particles in the heterogeneous DPSO were able to improve the global best solution the greatest number of times. The results are accumulated over 30 executions for the gr666 TSP instance.
Table 4. Ranking of parameter values after 6144 iterations for which the particles in the heterogeneous DPSO were able to improve the global best solution the greatest number of times. The results are accumulated over 30 executions for the gr666 TSP instance.
RankParametersNumber of gBest Improvements
c 1 c 2 c 3 ω
10.10.10.10.5113
20.10.10.10.1102
30.120.10.149
40.1220.546
50.1220.142
60.11.50.10.539
70.110.10.138
80.110.10.2534
90.75220.2527
100.1120.126
110.120.10.2524
120.75220.122
131.51.520.521
141.520.10.121
151.520.10.2520
Table
Table 5. Ranking of parameter values for which the particles in the heterogeneous DPSO were able to improve the global best solution the greatest number of times within five designed subsequent phases of the computations. The results are accumulated over 30 executions for the gr666 TSP instance.
Table 5. Ranking of parameter values for which the particles in the heterogeneous DPSO were able to improve the global best solution the greatest number of times within five designed subsequent phases of the computations. The results are accumulated over 30 executions for the gr666 TSP instance.
IterationsParametersNumber of gBest Improvements
c 1 c 2 c 3 ω
0–12500.10.10.10.194
0.10.10.10.593
0.1220.538
0.120.10.138
0.1220.132
1250–25000.75220.2512
1.520.10.110
0.120.10.110
0.11.50.10.59
0.1120.18
2500–37500.10.10.10.510
1.51.520.54
1.520.10.254
0.75220.253
0.1120.13
3750–50000.110.10.12
0.1120.12
0.750.120.52
1.50.120.12
1.521.50.12
5000–61441.75210.53
1.521.50.12
1.750.120.52
0.11.50.10.52
1.5110.11
Table
Table 6. Values of DPSO-related parameters.
Table 6. Values of DPSO-related parameters.
Homogeneous DPSOHeterogeneous DPSOCommon Parameters
Problem c 1 c 2 c 3 ω Problem c 1 c 2 c 3 ω SwarmSize Neighborhood
berlin520.50.50.50.2berlin52Chosen randomly
as described in Section 5		327
kroA1000.50.50.50.5kroA100647
kroA2000.50.50.50.5kroA200807
gr2020.50.50.50.5gr20210110
pcb4420.51.50.50.5pcb44210415
gr6660.51.01.50.6gr66611230
Table
Table 7. Comparison of results for the homo and heterogeneous DPSO variants and the ACO algorithms obtained for four DTSP (berlin52, …, pcb442) and one TSP (gr666) instances. “G” denotes the distance to the optimum and “D” the average standard deviation of this distance. The numbers of iterations are given per sub-problem. The best solutions found by the DPSO algorithms are marked in boldface. All computations were repeated 30 times. PACO, population-based ACO.
Table 7. Comparison of results for the homo and heterogeneous DPSO variants and the ACO algorithms obtained for four DTSP (berlin52, …, pcb442) and one TSP (gr666) instances. “G” denotes the distance to the optimum and “D” the average standard deviation of this distance. The numbers of iterations are given per sub-problem. The best solutions found by the DPSO algorithms are marked in boldface. All computations were repeated 30 times. PACO, population-based ACO.
ProblemIterationsDPSO AlgorithmsCounterparts
HomogeneousHeterogeneousACSPACO
T (s)G (%)D (%)T (s)G (%)D (%)G (%)G (%)
berlin521040.130.150.320.130.130.150.960.96
berlin524160.30.010.040.280.010.050.50.5
berlin5216640.98000.890.010.050.460.46
kroA1001001.035.442.470.862.681.41.82.97
kroA1004001.631.281.021.271.050.811.312.13
kroA10016004.110.640.693.380.780.770.821.36
kroA2001602.4915.632.772.185.141.842.413.33
kroA2006405.134.451.624.462.891.091.622.71
kroA200256015.61.620.8113.182.020.81.472.28
gr2021288.8213.752.068.174.191.26.264.91
gr20251211.546.812.1110.881.970.664.883.9
gr202204823.011.520.621.981.530.553.933.34
pcb44227211.2229.315.3311.166.731.686.184.44
pcb442108828.5213.41530.692.870.894.873.56
pcb4424352102.783.131.52108.251.920.793.913.3
gr66638485.1910.841.5291.839.580.869.185.89
gr66676898.367.371.0115.196.880.787.464.77
gr6661536124.845.620.84163.485.330.576.094.51
gr6663072180.664.880.632594.520.885.674.14
gr6666144296.833.990.77453.833.80.784.924.21

Share and Cite

MDPI and ACS Style

Strąk, Ł.; Skinderowicz, R.; Boryczka, U.; Nowakowski, A. A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP. Entropy 2019, 21, 738. https://doi.org/10.3390/e21080738

AMA Style

Strąk Ł, Skinderowicz R, Boryczka U, Nowakowski A. A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP. Entropy. 2019; 21(8):738. https://doi.org/10.3390/e21080738

Chicago/Turabian Style

Strąk, Łukasz, Rafał Skinderowicz, Urszula Boryczka, and Arkadiusz Nowakowski. 2019. "A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP" Entropy 21, no. 8: 738. https://doi.org/10.3390/e21080738

APA Style

Strąk, Ł., Skinderowicz, R., Boryczka, U., & Nowakowski, A. (2019). A Self-Adaptive Discrete PSO Algorithm with Heterogeneous Parameter Values for Dynamic TSP. Entropy, 21(8), 738. https://doi.org/10.3390/e21080738

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop