Analysis and improvement of neighborhood topology of particle swarm optimization

Abstract

Particle swarm optimization (PSO) is a population-based intelligent algorithm for solving optimization problems. Since the fast convergence and easy implementation, PSO has been successfully applied in some areas. However, the standard PSO also has some inherent drawbacks, and the premature convergence is the main issue. Many PSO variants have been developed to solve this problem. Unlike the previous studies, this paper focuses on the communications among different particles, based on the graph theory and information theory, a new analytical method for PSO topology was proposed. By analysing three typical topologies (star, ring, and von-Neumann), the influence of different topologies was revealed. Therefore, an improved topology combines the advantages of three typical topologies was developed, and the iterations of PSO were divided into three stages. The different stages have different topologies. The benchmark test results show that the improved topology is effective. It applies to both convex and nonconvex optimizations.

Keywords

Particle swarm optimization neighborhood topology graph theory information theory dynamic topology

1. Introduction

Particle Swarm Optimization (PSO) is a widely used computational intelligence algorithm which was firstly introduced by Eberhart and Kennedy in 1995 [1]. PSO belongs to the category of the swarm intelligence methods, which is inspired by the swarm behaviours of animals, such as fish schooling, bird flocking or bee swarming. In this algorithm, the potential solutions are treated as particles. Each particle has individual position and velocity, and they are flying in a multi-dimensional solution space and searching for the optimal global position. Due to the advantages of fewer parameters and easier implementation, the PSO algorithm has better performance in many application fields, such as economics, energy, electronics, electromagnetics, medicals, control science, communication systems, etc.

Although PSO algorithm has some outstanding features, it may easily get trapped in local optima and lead to a premature convergence issue [2], similar to other evolutionary algorithms. In recent years, to improve the global exploration ability and prevent premature convergence of the classic PSO, some researches have been conducted. These works can be categorized into three classes: parameter improvements, hybrid algorithms and new topology [3, 4]. The parameters affect the performance of PSO, such as inertia weight and speed factors. The inertia weight plays a key role in the convergence. Generally, a large inertia weight is helpful when searching for the global optimal, while a small inertia weight will enhance the local search capability [5]. Based on the standard PSO, there are many variants for dynamic inertia weight, such as random inertia weight [6] and time-varying inertia weight [7]. Compared with the inertia weight, the speed factors are usually constant. Besides, many improved PSO algorithms are mixed with other intelligent algorithms. These hybrid algorithms integrate the advantages of two or more algorithms and can overcome some shortcomings of standard PSO. Miranda and Prudêncio [8] apply Grammar-Guided Genetic Programming (GGGP) algorithms for PSO algorithm design problem, and four different GGGP approaches were used to compare the performance of the proposed method. Naderi et al. [9] use Heterogeneous Comprehensive Learning (HCL) strategy and fuzzy system to improve the standard PSO, and this hybrid method was used to solve reactive power dispatch problem. Yan et al. [10] developed a new PSO variant by combining the features of random learning mechanism and levy flight, and the numerical experiments show that the proposed hybrid algorithm is efficient. PSO is usually combined with other evolutionary algorithms, for example combining with Differential Evolution (DE) [11] and Artificial Immune System (AIS) [12].

Using a reasonable topology can also improve the performance. The most common used static topologies are a star, ring, and von-Neumann topologies [13]. Some dynamic topologies have been developed in recent years to improve the standard PSO. Wang et al. [14] used a dynamic tournament topology strategy to improve PSO. Several better solutions guide the particles, and the test results show that this strategy is promising. Augusto et al. [15] adopted a probabilistic method to decide which particles will communicate and developed a new global best strategy to seek an optimal solution, and the proposed dynamic topology was applied on nuclear engineering. Lim and Isa [16] developed a new PSO variant by linearly increasing the particle’s topology connectivity, which can balance the PSO’s exploration/exploitation capacity. Marinakis et al. [17] used a novel expanding neighborhood topology to improve the standard PSO, and the new hybridized algorithm can effectively solve the constrained shortest path problem. Bonyadi et al. [18] proposed a time-adaptive topology to locate many feasible regions at the early stages of the optimization process and to screen the best solution at the latter stages, and this method can find more feasible regions and get higher quality solutions. Mason et al. [19] used a PSO variant with a gradually increasing directed neighborhood to solve dynamic economic emission dispatch problem. In fact, the main difference between the topologies is the count of neighbors, and the dynamic topology of PSO can be achieved by controlling the number of neighbours. Jiang et al. [20] presented a novel age-based topology, which separate particles to different age-groups and the particles can only select the neighbours in younger groups or their group. Numerical analysis shows that the new topology provides better performances on both optimization problems and the data clustering tasks. Lynn et al. [21] pointed out that the two main structured population models are cellular topology and distributed topology. In cellular topology, the whole population is divided into many very small subpopulations. While, the distributed topology subdivides the population into smaller islands, which is isolated from each other and evolves independently. During the iterations, each particle shares its best experiment with its neighbours, so the topology selection is the most challenging aspect in PSO algorithm [22].

Many scholars have realized that PSO with a small neighbourhood performs better on complex problems, while a large neighbourhood performs better on simple problems [4, 16]. Most topology studies only focus on how to establish the dynamic topology, but the reasons that changing topology can improve performance are lack of theoretical analysis. In this paper, a new topological analysis method based on the graph theory and information theory is developed to solve this problem, and a new dynamic topology is proposed according to the analysis results of the different topologies. The following sections of this paper are organized as follows. In Section 2, the commonly used topologies were briefly introduced. In Section 3, some definitions and derived parameters are given to analyse three common used topologies. In Section 4, a newly improved topology is proposed, and the new method was tested in Section 5. Finally, in Section 6, we summarized the research and gave some suggestions for the future work.

2. Typical topologies

PSO typical topologies generally fall into two categories: global version and local version. The global version is a star topology, in which all the particles can communicate with each other, and the optimal particle in every iteration is selected from the whole population. Because there is only one global optimal particle and the other particles use the optimal particle as their learning target, the global version of PSO converges very quickly. The local version has fewer neighbours than the global version. The local optimal particle is selected among the particle itself and its neighbours. Each particle may have different learning target, so it can keep population diversity and avoid premature convergence, but the convergence speed will slow down. Because the global version is easily get trapped in local optima, the local version is widely used. The currently applied PSO algorithms are mostly static topologies with a fixed number of neighbours. Kennedy pointed out the three typical topologies: star, ring, and von-Neumann topologies [13], as shown in Fig. 1.

Figure 1.

Three typical topologies.

Figure 1a shows the star topology. The population size is $n$ , and each particle is connected directly to the $n-1$ neighbours. Figure 1b is the ring topology, in which each particle has only two neighbours. Comparing Fig. 1a and b, the ring topology has fewer direct connections. The von-Neumann topology is also a local version of PSO like ring topology, whose true topology is similar to a swimming ring. If we snipped off the swimming ring horizontally and vertically, the swimming ring will expand into a grid just like the Fig. 1c, in which each particle has four connecting neighbours, above, below, right and left.

3. Theoretical analysis

3.1 Definitions

To analyse the topologies, some parameters need to be defined. Based on Chen’s proposal that the topology of PSO can be analysed by the graph theory [23], a new analytical method combines the graph theory and information theory is proposed. The definitions are as follows:

Distance: Consider an unweighted directed graph $G(V,E)$ with the set of vertices (particles) $V$ and the ordered pairs of vertices $E$ , where $V$ is the population size and the $E$ is the directed edges, the distance $d(i,j)$ between two particles $i$ and $j$ in a directed graph is defined as the number of edges in the shortest path connecting them.

$\displaystyle\bar{d}=\frac{\sum\limits_{i\neq j}d(i,j)}{n(n-1)}$ (1)

Average Distance (AD): the AD is defined as for Eq. (1), where, $n$ is the population size.

Longest Distance (LD): the longest distance $d_{\max}$ is the maximum number of edges in a given graph $G(V,E)$ .

Information: The whole population can be represented as a set of $X=\{x_{1},x_{2},\ldots,x_{n}\}$ , where $x_{1}$ is a single particle, 1 $\leqslant i\leqslant n$ . The states of each particle can be expressed in binary forms: 1 means the particle is the optimal and 0 is not the optimal, probability that a particle is the global optimal is 1/ $n$ , while it may not be optimal is $(n-1)/n$ . Based on the information theory [24], the information carried by each particle can be expressed as,

$\displaystyle H_{G}=-\sum_{i=1}^{n}P(x_{i})\log_{2}P(x_{i})=-\frac{1}{n}\log_{% 2}\frac{1}{n}-\frac{n-1}{n}\log_{2}\frac{n-1}{n}$ (2)

where, $P(x_{i})$ is the probability of each state, in the formula, $P(x_{i})$ is 1/ $n$ or $(n-1)/n$ .

The Eq. (2) can be used to analyse both the global and local versions of PSO. The ring topology, for instance, whose neighbourhood topology contains the particle itself and two neighbours, and the information expressed by the three particles are 001, 010, 100 and so on. Figure 2 is the information schematic diagram.

Figure 2.

The information schematic diagram of the ring topology.

More generally, if a particle has $n^{\prime}$ neighbours (the neighbours and particle itself are total $n^{\prime}+1$ ), the local information carried by each particle is,

$\displaystyle H_{L}=-\frac{1}{n^{\prime}+1}\log_{2}\frac{1}{n^{\prime}+1}-% \frac{n^{\prime}}{n^{\prime}+1}\log_{2}\frac{n^{\prime}}{n^{\prime}+1}$ (3)

therefore, the total information can be divided into two categories,

$\displaystyle\left\{\begin{array}[]{c}I_{1}=n\cdot H_{G}\\ I_{2}=n\cdot H_{L}\end{array}\right.$ (4)

where $I_{1}$ is the total information of the global version and $I_{2}$ is for the local version, and the unit is bit.

Information Transfer Rate (ITR): One of the most important concepts in communication systems is the transfer rate of information. Theoretically, there is more time required for information transmission if the distance between two nodes is longer. In contrast, less time required if the distance is shorter. Therefore, the average transmission time of the unit information of PSO is directly proportional to the AD. In this paper, we set a proportion of 1:1. The average numbers of unit information transmitted per unit time can be expressed as,

$\displaystyle\bar{R}_{B}=\frac{1}{\bar{t}}=\frac{1}{\bar{d}}$ (5)

where, $\bar{t}$ is the average transmission time of the unit information, $\bar{d}$ is the AD. The unit of $\bar{R}_{B}$ is Baud, which can also be called the baud rate.

Based on Eq. (5), the ITR can be expressed as,

$\displaystyle\bar{R}_{b}=\bar{R}_{B}\cdot I=\frac{I}{\bar{d}}$ (6)

In Eq. (6), $I$ is the total information referred to $I_{1}$ or $I_{2}$ of Eq. (4). In binary forms, the unit of ITR is bit/unit time.

3.2 Parameters of the different topologies

Among these topologies, the star topology is the simplest. The AD and LD of the star topology are both 1. Instead, the parameters of the ring and von-Neumann topologies are more complicated.

If the population size of the ring topology is odd, the longest distance from a particle to another particle is $(n-1)/2$ , so the distances from a particle to other particles are 1, 2, …, $(n-1)/2$ . Because the ring topology is a symmetrical structure, the distances must be counted twice, so the total distance from a particle to the other $n-1$ particles based on Eq. (1) is defined as,

$\displaystyle\frac{1}{n}\sum_{i\neq j}d(i,j)=2\times\left(1+\ldots+\frac{n-1}{% 2}\right)=2\times\left(1+\frac{n-1}{2}\right)\frac{n-1}{2}\times\frac{1}{2}=% \frac{(n+1)(n-1)}{4}$ (7)

While, if $n$ is even, the longest distance from a particle to another particle is $n$ /2, and the distances from a particle to other particles are 1, 2, …, $n$ /2. The total distance is calculated by the Eq. (7), and the result is $2\times(1+\ldots+n/2)$ . According to Fig. 1b, the longest distance is counted twice if the $n$ is even, so, in Eq. (8), $n$ /2 must be subtracted.

$\displaystyle\frac{1}{n}\sum_{i\neq j}d(i,j)=2\times\left(1+\ldots+\frac{n}{2}% \right)-\frac{n}{2}=2\times\left(1+\frac{n}{2}\right)\frac{n}{2}\times\frac{1}% {2}-\frac{n}{2}=\frac{n^{2}}{4}$ (8)

From Eqs (1), (7) and (8), the AD of ring topology can be deduced as Eq. (9).

$\displaystyle\left\{\begin{array}[]{ll}\frac{n+1}{4},&n\geqslant 3,n\text{ is % odd}\\ \frac{n^{2}}{4(n-1)},&n\geqslant 3,n\text{ is even}\end{array}\right.$ (9)

Based on Fig. 1b, the LD of ring topology is not difficult to figure out.

$\displaystyle\left\{\begin{array}[]{ll}\frac{n-1}{2},&n\geqslant 3,n\text{ is % odd}\\ \frac{n}{2},&n\geqslant 3,n\text{ is even}\end{array}\right.$ (10)

The above formula can be simplified as Eq. (11), where, the symbol $\lfloor\rfloor$ indicates rounded down.

$\displaystyle\lfloor n/2\rfloor,n\geqslant 3$ (11)

Compared to the ring topology and star topology, the von-Neumann topology is very abstract. Suppose that the length and width of the grid in Fig. 1c are $\alpha$ and $\beta$ . Rolling up the flat grid and connect it the end to end. The true topology of von-Neumann is like a swimming ring, which inspired by reference [13]. Figure 3 is the schematic diagram.

Figure 3.

The true topology of von-Neumann.

From the Fig. 3, we can see the von-Neumann topology has two typical rings in the vertical and horizontal directions. The sizes of the two rings are $\alpha$ and $\beta$ respectively. By calculating the total distance of ring topology, the AD of von-Neumann topology can be divided into four cases:

If $\alpha$ and $\beta$ are both odd, we assume the size of the small ring in Fig. 1 is $\alpha$ , and the large ring is $\beta$ . The process of calculating the total distance can be divided into several steps. Firstly, according to Eq. (7), the total distance of the small ring itself is $(\alpha^{2}-1)/4$ . Besides, there are also $\beta-1$ small rings on the large ring, so the total distance of these small rings is $\beta(\alpha^{2}-1)/4$ . Secondly, the total distance of the large ring is $(\beta^{2}-1)/4$ , and every small ring has $\alpha$ particles, so the distance must be counted as $\alpha$ times. The total distance of large ring is $\alpha(\beta^{2}-1)/4$ . Therefore, the total distance of von-Neumann topology is

$\displaystyle\frac{1}{n}\sum_{i\neq j}d(i,j)=\frac{\beta(\alpha^{2}-1)}{4}+% \frac{\alpha(\beta^{2}-1)}{4}$ (12)

Similarly, if $\alpha$ is odd and $\beta$ is even, the total distance will be

$\displaystyle\frac{1}{n}\sum_{i\neq j}d(i,j)=\frac{\beta(\alpha^{2}-1)}{4}+% \frac{\alpha\beta^{2}}{4}$ (13)

If $\alpha$ and $\beta$ are both even,

$\displaystyle\frac{1}{n}\sum_{i\neq j}d(i,j)=\frac{\beta\alpha^{2}}{4}+\frac{% \alpha\beta^{2}}{4}$ (14)

If $\alpha$ is even and $\beta$ is odd,

$\displaystyle\frac{1}{n}\sum_{i\neq j}d(i,j)=\frac{\beta\alpha^{2}}{4}+\frac{% \alpha(\beta^{2}-1)}{4}$ (15)

The Eqs (12)–(15) are subject to

$\displaystyle n=\alpha\cdot\beta,\alpha\geqslant 3,\beta\geqslant 3$ (16)

According to the Eqs (1), (12)–(16), the AD of von-Neumann topology is

$\displaystyle\left\{\begin{array}[]{ll}\frac{\alpha+\beta}{4},&\alpha\text{ % and }\beta\text{ are both odd}\\ \frac{\beta}{4}+\frac{\alpha^{2}\beta}{4(\alpha\beta-1)},&\alpha\text{ is odd % and }\beta\text{ is even}\\ \frac{\alpha\beta(\alpha+\beta)}{4(\alpha\beta-1)},&\alpha\text{ and }\beta% \text{ are both even}\\ \frac{\alpha}{4}+\frac{\alpha\beta^{2}}{4(\alpha\beta-1)},&\alpha\text{ is % even and }\beta\text{ is odd}\end{array}\right.$ (17)

According to the Fig. 3 and Eq. (11), the LD of von-Neumann topology is

$\displaystyle\lfloor\alpha/2\rfloor+\lfloor\beta/2\rfloor$ (18)

The ITR of the three topologies can be calculated according to the Eqs (2), (3), (6), (9) and (17). The main parameters are summarized in Table 1.

Table 1

Parameters of different topologies

Topologies	Neighbours	AD	LD	Information
Star	$n-1$	1	1	$\log_{2}n+(n-1)\log(n/(n-1))$
Ring	2	See Eq. (9)	$\lfloor n/2\rfloor$	0.918 $n$
Von-Neumann	1	See Eq. (17)	$\lfloor\alpha/2\rfloor+\lfloor\beta/2\rfloor$	0.722 $n$

3.3 Comparisons of the different topologies

This section compares the parameters of the three typical topologies. The parameters include AD, LD, Information and ITR and the population size will gradually increase from 2 to 100.

Figure 4.

The AD of different topologies.

Figure 5.

The LD of different topologies.

Figure 4 shows the AD curves of the three topologies. Because the von-Neumann topology is subject to Eq. (16) and its parameters are not continuous, the scatter plot is used. The AD of the star topology is minimal, and the values keep up to 1. The AD of ring topology is proportional to the population size. As the population size increases, the AD also increases, and the slop of AD is a constant. The AD of von-Neumann topology is between the value of star topology and ring topology, which is not linear and increases slowly.

The LD curves are similar to AD curves. In Fig. 5, the LD of ring topology is the maximum, and the curve shows a linear increase. The von-Neumann topology is medium, and the star topology is still minimal. Compared with other two topologies, the LD of von-Neumann topology is more appropriate, neither too long nor too short. The LD is directly related to the AD. If the AD increases, the LD will increase. When applying graph theory to analyse the topologies, you can choose either one of AD or LD. Although we have analysed AD and LD in different topologies, the impact on performance remains unclear. In the following analysis, the communication mechanism among particles will be analysed.

Figure 6.

The Information of different topologies.

Figure 7.

The ITR of different topologies.

Figure 6 is the information of the whole population. It shows the star topology has the least information. As the population size increases, the total information changes very slowly. Instead, the information of ring and von-Neumann grows very quickly. More specifically, the information change of von-Neumann topology is slightly lower than that of the ring topology. According to Eq. (13), the ring topology has the largest information than any other topologies. Based on the principle of information theory, the more information means, the more communication among particles, so the search ability of ring topology is the best.

Figure 7 is the most important figure in this paper because the ITR can quantify the interaction among particles. If a topology has a higher IRT, it means that the optimal information is transmitted quickly and it will be very helpful for the convergence. In Fig. 7 the ITR of ring topology is the lowest, and it seems not related to the population size, so the ring topology converges very slowly. Unlike the other parameters, the ITR of the star topology is between the other two topologies. Subjectively, the AD of star topology is the shortest, and its transmission speed should be the fastest. However, because of the little information it carried, the ITR of star topology is slower than the von-Neumann topology. The von-Neumann topology has the fastest ITR, which means the exchange of information among particles is very efficient to improve the convergence.

Based on the above analysis, we can draw the following conclusions:

(1)

Star topology has the shortest AD and LD, the least whole information, and the IRT is much higher than the ring topology. The star topology converges very fast.

(2)

The ring topology contains the most information, but its AD and LD are much longer than any other topologies. Accordingly, its ITR is the lowest, and the convergence is the slowest.

(3)

The von-Neumann topology has the fastest ITR, medium AD and LD between the star and ring topologies. Meanwhile, the whole information it carried is much more than the star topology and nearly equal to the ring topology. More information means the particle can get more optimal information from the other particles, and the fast ITR means the information exchange is very efficient, so the von-Neumann topology can offer a solution to balance the searching ability and the convergence.

4. Improved topology

From Section 3, we know that different topologies have different performance and each topology has different advantages and disadvantages. In a traditional PSO, the number of the neighbours are fixed, and the topology is static. Several dynamic topologies suggest that changing topologies can improve the performance. In this section, a new dynamic topology combined with the advantages of three typical topologies is proposed. The improved topology is divided into three stages.

Figure 8.

The three stages of the improved topology.

Figure 8 is the schematic diagram of three stages. In the early stage of iterations, the ring topology is used to search the optimal solution, which has the lowest ITR and the longest AD. It is good for keeping the diversity of the population. In the middle stage, the topology changes to von-Neumann. The proper AD and the fastest ITR mean that the particles have an opportunity to learn more information from the other particles. It is good for improving the searching efficiency. In the final stage, the topology is changed to star topology or ring topology, decided by the objective function. If the objective function is convex, the topology is a star, and it will accelerate the convergence. Otherwise, if the objective function is nonconvex, the topology will be changed to the ring again, which will enhance the local searching ability.

In Fig. 8, $N$ is the total iterations, $m_{1}$ is the beginning of stage 2 and $m_{2}$ is the beginning of stage 3. The values of $N$ , $m_{1}$ , and $m_{2}$ are subject to $m_{1}\leqslant m_{2}\leqslant N$ . The difficulty of this method is how to determine the proper values of $m_{1}$ and $m_{2}$ . A simple way is to divide the total iterations into three equal segments. But this may be unscientific, so we need a scientific and reasonable way to determine them. Because the particles have different positions in searching space, the topology can be changed according to the diversity of the population. The diversity is defined as Eq. (19) [25].

$\displaystyle D=\frac{2}{n(n-1)}\sum_{i=1}^{n}\sum_{j=i+1}^{n}\left(\left\|x_{% i}-x_{j}\right\|\right)$ (19)

where, $\left\|x_{i}-x_{j}\right\|$ represents the Euclidean distance between two particles. The diversity $D$ is the mean value of the Euclidean distance among all particles. Suppose the value of diversity at first iteration is $D_{1}$ , and the $k$ th iteration is $D_{k}$ . We use two parameters $\theta_{1}$ and $\theta_{2}$ to distinguish the three stages, where 0 $\leqslant\theta_{1}\leqslant$ 1 and 0 $\leqslant\theta_{2}\leqslant$ 1.

$\displaystyle\left\{\begin{array}[]{ll}\text{stage }=1,&(D_{k}/D_{1})>\theta_{% 1}\\ \text{stage }=2,&\theta_{2}<(D_{k}/D_{1})\leqslant\theta_{1}\\ \text{stage }=3,&(D_{k}/D_{1})\leqslant\theta_{2}\end{array}\right.$ (20)

Although the values of $\theta_{1}$ and $\theta_{2}$ also have some subjective factors, they are more reasonable than directly setting up the values of $m_{1}$ and $m_{2}$ . By comparing the diversity of the population, we can grasp the aggregation of particles. Therefore, the topology could be changed more scientifically. Since the diversity of the population needs to be calculated, the computation of improved topology is larger than the standard PSO. If the Eq. (19) is calculated at every iteration, the efficiency of the algorithm will be significantly reduced. To avoid this issue, the diversity can be calculated at periodic intervals, not at each iteration. The pseudo code of the PSO with an improved topology is shown in Table 2, and the time complexity of the proposed method is $O(n)$ .

Table 2

Algorithm of PSO with improved topology

Input: Population size $n$ , total iterations $N$ , inertia weight, speed factors, $\theta_{1}$ , $\theta_{2}$ , iteration interval $q$ .
Output: The best solution gbest.
1	Initialize the topology to ring, set positions and speed of the particles randomly, evaluate the initial diversity $D_{1}$ , check the objective function is convex or nonconvex;
2	for $k=$ 1 to $N$
3	for $i=$ 1 to $n$
4	Evaluate the fitness of each particle;
5	Update the best position pbest for each particle;
6	Update the speed for each particle;
7	Update the positon for each particle;
8	end
9	if $k$ is divisible by $q$ (the remainder is 0)
10	Evaluate the diversity $D_{k}$ ;
11	if Eq. (20) is satisfied
12	Change the stage and topology;
13	else
14	Continue;
15	end
16	end
17	Return the best position (gbest) of the whole population.

5. Numerical examples

To verify the effectiveness of the proposed method, we compared the three classical topologies and the improved topology by different benchmark functions. These algorithms are tested in MATLAB, running on a PC with 8 GB memory, and 2.6 GHz CPU and the operating system is Windows 10. Before testing, some test indicators need to be defined.

Mean Best (MB): If an algorithm runs $T$ times independently, the optimal solution of each time is denoted as $y_{t}$ , $t\in[1,T]$ . The mean best is defined as.

$\displaystyle\bar{y}=\frac{1}{T}\sum_{t=1}^{T}y_{t}$ (21)

Best Solution (BS): the best solution among $y_{t}$ .

$\displaystyle y_{\textit{opt}}=\min(\max)\{y_{1},y_{2},\ldots,y_{T}\}$ (22)

Mean Difference (MD):

$\displaystyle\delta=\frac{1}{T}\sum_{t=1}^{T}(y_{t}-\bar{y})$ (23)

If the MD is small, it means that the algorithm is robust. Otherwise, it lacked stability.

Average Elapsed Time (AET): the average of run time.

Success Rate (SR): Under the given maximum iterations, if the optimal solution is better than the convergence criterion, the convergence is successful. Suppose the algorithm runs $L$ times and the successful convergence is $l$ times, the SR is defined as

$\displaystyle\Psi=\frac{l}{L}\times 100\%$ (24)

Average Count of Iterations (ACS): Record the count of iterations when the convergence criterion is satisfied and calculate the average of the $l$ counts.

In this section, the topologies of the algorithms are different, but the parameters are the same. The population size is 30; inertia weight is 0.729; acceleration factors are both 1.494; $\theta_{1}$ is 0.5 and $\theta_{2}$ is 0.2; the iteration interval is 10; the total number of iterations is 3000; each algorithm runs 30 times independently.

Table 3

The benchmark functions

Functions	Formula	Dimension (D)	Search ranges	Extreme value	Criterion
Sphere	$f_{1}(x)=\sum_{d=1}^{D}x_{d}^{2}$	30	[ $-$ 5.12, 5.12]	0	1e $-$ 10
Schaffer f6	$f_{2}(x)=0.5+\frac{\left(\sin\sqrt{x_{1}^{2}+x_{2}^{2}}\right)^{2}-0.5}{[1+0.0% 01(x_{1}^{2}+x_{2}^{2})]^{2}}$	2	[ $-$ 100, 100]	0	5e $-$ 3
Rastrigin	$f_{3}(x)=10n+\sum_{d=1}^{D}\left[x_{d}^{2}-10\cos(2\pi x_{d})\right]$	30	[ $-$ 5.12, 5.12]	0	100
Griewank	$f_{4}(x)=\sum_{d=1}^{D}\frac{x_{d}^{2}}{4000}-\prod_{d=1}^{D}\cos(x_{d}/\sqrt{% d})+1$	30	[ $-$ 600, 600]	0	5e $-$ 2
Ackley	$f_{5}(x)=20+e-20\exp\left(-\frac{1}{5}\sqrt{\frac{1}{D}\sum_{d=1}^{D}x_{d}^{2}% }\right)-$	30	[ $-$ 15, 30]	0	1e $-$ 2
	$\exp\left(\frac{1}{D}\sum_{d=1}^{D}10\cos(2\pi x_{d})\right)$

Table 3 is the benchmark functions marked as $f_{1}\sim f_{5}$ . $f_{1}$ is convex and has only one extreme solution. $f_{2}$ is a multimodal function with infinite local minimums, and it is difficult to find the global optimal solution. $f_{3}$ also has a large number of local minimums, and the solving algorithms are easily trapped into local minimums. $f_{4}$ is a typical non-linear multimodal function, which has a wide searching space. Similar to $f_{2}\sim f_{4}$ , $f_{5}$ is also a non-convex test function. It has a peak or hole in the middle of a flat area, and it is one of the most difficult testing functions.

Table 4

The comparison of test indicators among different topologies

Indicators	Topologies	Sphere	Schaffer f6	Rastrigin	Griewank	Ackley
MB	star	1.321e $-$ 44	2.429e $-$ 3	73.229	1.850e $-$ 2	2.384
	ring	2.962e $-$ 29	1.943e $-$ 3	70.557	2.157e $-$ 3	9.421e $-$ 14
	von-Neumann	1.298e $-$ 36	9.583e $-$ 4	68.188	2.711e $-$ 3	1.085e $-$ 14
	improved	1.150e $-$ 52	3.242e $-$ 4	67.270	1.922e $-$ 3	5.453e $-$ 14
BS	star	8.816e $-$ 55	0	26.979	0	3.633e $-$ 13
	ring	1.041e $-$ 30	0	35.819	0	3.286e $-$ 14
	von-Neumann	5.587e $-$ 39	0	41.787	0	7.994e $-$ 15
	improved	2.547e $-$ 57	0	38.803	0	2.221e $-$ 14
MD	star	6.091e $-$ 44	4.316e $-$ 3	20.495	2.052e $-$ 2	0.944
	ring	3.018e $-$ 29	3.987e $-$ 3	16.184	5.518e $-$ 3	4.843e $-$ 14
	von-Neumann	2.959e $-$ 36	2.393e $-$ 3	13.691	4.223e $-$ 3	3.892e $-$ 15
	improved	3.398e $-$ 52	1.773e $-$ 3	14.094	3.433e $-$ 3	2.937e $-$ 14
SR	star	100%	77%	90%	90%	3%
	ring	100%	80%	97%	100%	100%
	von-Neumann	100%	93%	100%	100%	100%
	improved	100%	97%	100%	100%	100%
ACS	star	718	139	154	332	18
	ring	1181	533	403	653	818
	von-Neumann	556	467	353	504	607
	improved	679	615	297	617	765
AET (sec)	star	0.728	0.281	0.829	0.939	0.734
	ring	7.912	7.339	8.564	9.373	7.818
	von-Neumann	8.012	7.488	8.195	7.910	7.586
	improved	8.691	7.624	9.577	8.197	7.929

Table 4 is the comparison of test indicators among different topologies. In $f_{1}$ , the performance of star topology is better than the ring and von-Neumann topologies, which indicates that the star topology has advantages in convex optimization problems. Compared with the other topologies, the performance of the improved topology is much better, whose indicators (MB, BS, and MD) are many orders of magnitude higher than the other topologies. The improved topology is more suitable for convex optimization. Unlike the performance in $f_{1}$ , the star topology works very poorly in $f_{2}\sim f_{5}$ , and the MB, BS, MD, and SR are not accurate enough. The von-Neumann topology performs very well in $f_{2}\sim f_{5}$ , and its indicators are generally higher than those of the ring and star topologies. The improved topology also works well in $f_{2}\sim f_{4}$ , whose MB, BS, MD, and SR are the best among all the topologies. But in $f_{5}$ , the performance is slightly worse than that of the von-Neumann topology, because the values of $\theta_{1}$ and $\theta_{2}$ are the same as other benchmark functions. In reality, the two parameters can be adjusted appropriately to achieve the better results. As can be seen, the ACS of the improved topology is moderate and the SR is the best no matter for convex or nonconvex optimizations. Since additional computation is required, the AET of the improved topology increased but it didn’t increase so much compared to the von-Neumann topology. It’s worth to improve the performance by consuming a little more time. According to the above analysis, the improved topology can combine the best aspects of different topologies to get the better applicability. The advantages of the improved topology are summarized as follows:

The improved topology is suitable for both convex and non-convex optimization problems.

The optimal searching capability is better than the other traditional topologies.

The improved method has the best stability.

6. Conclusion

In this paper, a new analytical method for PSO topology is developed, which combines the graph theory and information theory. Based on this method, three typical topologies of PSO are analyzed in detail. The star topology converges fast, but it’s easy to be trapped into a local minimum. The population diversity of ring topology is good, but the convergence is the slowest. The convergence of von-Neumann topology is more suitable, but it doesn’t work well in convex optimization problem. The improved topology divides the optimization process into three stages, and each stage has different topologies. Finally, five benchmark functions are used to test the proposed method. The test results reveal that the improved topology has the better comprehensive performance.

For future work, the effects of different values of $\theta_{1}$ and $\theta_{2}$ should be considered, and more real-world applications will be used to test the proposed method. Furthermore, we plan to develop a new strategy for automatically determining $\theta_{1}$ and $\theta_{2}$ .

References

Kennedy

and Eberhart

R.C.

, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks, Perth, Australia, 1995, pp. 1942–1948.

Jiang

Xia

Anh Tran

Q.A.

et al., A new binary hybrid particle swarm optimization with wavelet mutation, Knowledge-Based Systems 130 (2017), 90–101.

Q.H.

Song

Liu

H.M.

et al., Particle swarm optimization algorithm based on parameter improvements, Journal of Computational Methods in Sciences and Engineering (17) (2017), 557–568.

Gou

Lei

Y.X.

Guo

W.P.

et al., A novel improved particle swarm optimization algorithm based on individual difference evolution, Applied Soft Computing 57 (2017), 468–481.

Nickabadi

Ebadzadeh

M.M.

and Safabakhsh

, A novel particle swarm optimization algorithm with adaptive inertia weight, Applied Soft Computing 11 (2011), 3658–3670.

Liang

H.T.

and Kang

F.H.

, Adaptive mutation particle swarm algorithm with dynamic nonlinear changed inertia weight, Optik – International Journal for Light and Electron Optics 127 (2016), 8036–8042.

and Wer

J.D.

, An adaptive particle swarm optimization with multiple adaptive methods, IEEE Transactions on Evolutionary Computation 17 (2013), 705–720.

Miranda

P.B.C.

and Prudêncio

R.B.C.

, Generation of particle swarm optimization algorithms: An experimental study using grammar-guided genetic programming, Applied Soft Computing 60 (2017), 281–296.

Naderi

Narimani

Fathi

et al., A novel fuzzy adaptive configuration of particle swarm optimization to solve large-scale optimal reactive power dispatch, Applied Soft Computing 53 (2017), 441–456.

10.

Yan

Zhao

Zhou

et al., A particle swarm optimization algorithm with random learning mechanism and Levy flight for optimization of atomic clusters, Computer Physics Communications 219 (2017), 79–86.

11.

Epitropakis

M.G.

Plagianakos

V.P.

and Vrahatis

M.H.

, Evolving cognitive and social experience in particle swarm optimization through differential evolution: A hybrid approach, Information Sciences 216 (2012), 50–92.

12.

H.W.

Sun

Liang

Y.C.

et al., An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling, IEEE Transactions on Systems, Man, And Cybernetics – Part A: Systems and Humans 38 (2008), 358–368.

13.

Kennedy

and Mendes

, Neighborhood topologies in fully informed and best-of-neighborhood particle swarms, IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews) 36(2006), 515–519.

14.

Wang

Yang

and Orchard

, Particle swarm optimization using dynamic tournament topology, Applied Soft Computing 48 (2016), 584–596.

15.

Augusto

J.P.D.S.C.

Nicolau

A.D.S.

and Schirru

, PSO with dynamic topology and random keys method applied to nuclear reactor reload, Progress in Nuclear Energy 83 (2015), 191–196.

16.

Lim

W.H.

and Isa

N.A.M.

, Particle swarm optimization with increasing topology connectivity, Engineering Applications of Artificial Intelligence 27 (2014), 80–102.

17.

Marinakis

Migdalas

and Sifaleras

, A hybrid particle swarm optimization – variable neighborhood search algorithm for constrained shortest path problems, European Journal of Operational Research 261 (2017), 819–834.

18.

Bonyadi

M.R.

and Michalewicz

, A hybrid particle swarm with a time-adaptive topology for constrained optimization, Swarm and Evolutionary Computation 18(2014), 22–37.

19.

Mason

Duggan

and Howley

, Multi-objective dynamic economic emission dispatch using particle swarm optimisation variants, Neurocomputing 270 (2017), 188–197.

20.

Jiang

Wang

and Wang

, Particle swarm optimization with age-group topology for multimodal functions and data clustering, Communications in Nonlinear Science and Numerical Simulation 18 (2013), 3134–3145.

21.

Lynn

Ali

M.Z.

and Suganthan

P.N.

, Population topologies for particle swarm optimization and differential evolution, Swarm and Evolutionary Computation 39 (2018), 24–35.

22.

Liu

Wei

Yuan

et al., Topology selection for particle swarm optimization, Information Sciences 363 (2016), 154–173.

23.

Chen

Z.Y.

, Research on neighborhood topologies and modifications of particle swarm optimization . Doctor Thesis, Chongqing University, Chongqing, China, 2009, pp. 1–155.

24.

Stone

J.V.

, Information Theory: A Tutorial Introduction , Sebtel Press: Sheffield; 2018.

25.

Feng

W.X.

Gao

et al., Particle Swarm Optimizer and Multi-object Optimization , Beijing Institute of Technology Press: Beijing; 2013.