# Dynamic Neighborhood-Based Particle Swarm Optimization for Multimodal Problems

Authors: Xu-Tao Zhang; Biao Xu; Wei Zhang; Jun Zhang; Xin-fang Ji
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Various black-box optimization problems in real world can be classified as multimodal optimization problems. Neighborhood information plays an important role in improving the performance of an evolutionary algorithm when dealing with such problems. In view of this, we propose a particle swarm optimization algorithm based on dynamic neighborhood to solve the multimodal optimization problem. In this paper, a dynamicε-neighborhood selection mechanism is first defined to balance the exploration and exploitation of the algorithm. Then, based on the information provided by the neighborhoods, four different particle position updating strategies are designed to further support the algorithm’s exploration and exploitation of the search space. Finally, the proposed algorithm is compared with 7 state-of-the-art multimodal algorithms on 8 benchmark instances. The experimental results reveal that the proposed algorithm is superior to the compared ones and is an effective method to tackle multimodal optimization problems.


---

## Body

## 1. Introduction

Various black-box problems to be tackled difficultly in the real world have the characteristic of multimodal problem [1]. Strictly speaking, a multimodal optimization problem (MMOP) refers to an optimization problem with multiple global or local optima. Typical instances include drug molecular design [2], truss structure optimization [3], and protein structure prediction [4]. When solving MMOPs, we expect to locate several optimal solutions simultaneously, for the following reasons [5, 6]: (1) finding multiple optimal solutions in different regions of the search space at the same time is conducive to maintaining the diversity of the population and offset the influence of genetic drift. (2) For many real-world engineering optimization problems, designers hope to freely choose solutions to meet different needs from several excellent solutions with great differences. (3) For the black-box problem, in the absence of prior knowledge, the positions and the numbers of the global optima of the problem cannot be obtained. Locating multiple optimal solutions of the problem at the same time can improve the possibility of finding its global optimal solution and can also possibly provide multiple optimal solutions for decision makers. In view of this, the field of multimodal optimization has received more and more attention recently due to its scientific and technological significance.Traditional population-based evolutionary algorithms (EAs), such as genetic algorithm (GA) [7, 8], differential evolutionary (DE) [9], and particle swarm optimization (PSO) [10], are natural candidates for solving MMOPs. However, it should be noted that, in the case of solving MMOPs without special treatment, these EAs can only converge to one optimal solution of the optimization problem at a single run. In order to find multiple optimal solutions of the problem, it is necessary to run them repeatedly and it is expected to find a different optimal solution each time.In order to enable EAs to solve MMOPs effectively, researchers have proposed a series of techniques, most of which are aimed at enhancing the diversity of population and making it converge towards different search directions. These techniques are commonly referred to as niching [5]. Representative niche techniques include crowding [11], clustering [12–14], speciation [15], and stretching and shrinking method [16]. Recently, niching techniques are also embedded into PSO algorithm in a number of literatures. For example, MMOP is solved by changing the topology of PSO, such as niche PSO based on ring topology [13] and PSO based on star topology and ring topology [17]. In addition, the concept of speciation has also been introduced into the species-based PSO [18–20], where species can form adaptively in different optimal states. However, in order to define a species, a niching radius must be provided in advance. Accordingly, species can be merged or separated into new species in each iteration. Other methods, such as nbest PSO [21, 22] and multiswarms [23, 24], are also proposed.To remedy the defect of requirement for providing the niching radius in advance, a parameter, which is easy to set or with little sensitivity to the performance of the algorithm, is employed to complete the clustering or grouping of individuals by replacing the niching radius. Schoeman and Engelbrecht proposed a vector-based PSO algorithm, which uses vector operations to demarcate the boundaries of niches and maintain subswarms without any prior knowledge of the problem domain [25]. A niche is determined by a radius value based on the distance between the optimal of group and the nearest particle. Qu et al. [26] proposed a distance-based locally informed PSO (LIPS), where the global best position is replaced by multiple local best positions to guide the update of particles for converging to different optimal subspaces. However, LIPS needs to specify the neighborhood size of the particles. Based on the locality sensitive hashing, Zhang et al. proposed a fast niching technique to find the neighborhood set of particles, which can keep a balance between the exploration and exploitation of the algorithm while reducing the computational complexity of EAs [27]. Nevertheless, the method depends on the constructed hash functions. Further, Zhang et al. proposed a concept of parameter-free Voronoi neighborhood; the information provided by the Voronoi neighbors is used to estimate the evolutionary state of an individual. And different types of individuals are assigned with different reproduction strategies to support the exploration and exploitation of the search space [28]. As the dimension of the problem increases, the computational complexity of Voronoi will increase dramatically.In order to handle the above problems, a dynamic neighborhood-based multimodal PSO algorithm (DNPSO) is proposed in this paper. The aim is to design different evolutionary strategies based on neighborhood information to balance the exploration and exploitation of the algorithm without specifying an exact neighborhood size. The main contributions of DNPSO are provided as follows:(1)
A dynamicε-neighborhood selection mechanism is proposed. Compared with the existing neighborhood-based method, the neighborhood size of a particle in this paper is dynamically changed, and it is different for different particles. In addition, the proposed mechanism may lead to a larger possibility of information interaction between distant particles, which is beneficial for generating an exploratory offspring and restoring the exploration ability of PSO.(2)
Inspired by the successful application of neighborhood information to the design of the multimodal EAs, four different position updating strategies are presented according to the particle’s position and performance in its neighborhoods. Consequently, the search performance of the algorithm can be improved.The rest of this paper is arranged as follows. Section2 gives the related work for PSO. The proposed DNPSO is presented in Section 3, including the dynamic ε-neighborhood selection mechanism, four different position updating strategies, and the framework of the proposed algorithm. In order to verify the effectiveness of the proposed DNPSO, comparison experiments are presented in Section 4. Section 5 highlights main ﬁndings and future research opportunities as a result of the survey.


## 2. Particle Swarm Optimization Algorithm

Consider the following maximization problem:(1)maxfX,s.t.X∈S⊆RD.where X is a D-dimensional decision variable, S refers to the bound-constraint of the decision space, RD means the D-dimensional space, and f⋅ is the objective function.PSO is a heuristic search algorithm proposed by Kennedy et al. [29]. The searching principle of PSO comes from the imitation of bird foraging behavior. Due to its simple structure and efficient searching performance, PSO has been successfully applied to solving various optimization problems [30–32]. In PSO, the position of each particle in the search space represents the “potential feasible solution” of the problem to be optimized. The particles are initially random in the feasible search space with a random velocity, which aims to converge to the global optimal solution of the optimization problem. During the optimization process, each particle tracks two optimal positions simultaneously. One is the best position that it has achieved so far, also known as the individual guider (Pbest), and the other is the global best position detected so far in the neighborhood of the current particle or in the entire swarm, also known as the global guider (Gbest) [29]. Among them, the tracking of individual guider can be regarded as the component of self-cognition, and the learning of global optimal position can be seen as the component of social cognition. In the next iteration, both the ego and the social cognition components randomly influence the velocity of each particle.Since the PSO was proposed, researchers have proposed numerous PSO variants. Two variants of PSO are presented here, i.e., PSO with inertia weight [29] and LIPS proposed by Qu et al. [26]. At each iteration, the velocity and position of a particle in the PSO with inertia weight are updated as follows:(2)vi,dt+1=wvi,dt+c1r1Pbesti,dt−xi,dt+c2r2Gbestdt−xi,dt,xi,dt+1=xi,dt+vi,dt+1,where t is the number of iterations; Xit=xi,1t,xi,2t,...,xi,Dt and Vit=vi,1t,vi,2t,...,vi,Dt mean the position and velocity of the i-th particle at the t-th iteration, respectively. Pbestit represents the best position found by the i-th particle and refers to the best position of the swarm. w is the inertia weight; c1 and c2 are cognitive and social coefficients, respectively. r1 and r2 are two random values within [0, 1]. Figure 1 shows the flow chart of a conventional PSO.Figure 1
Flow chart of a conventional PSO.The velocity of a particle in LIPS is determined by the information provided by its neighbors, and the velocity of each particle is updated as follows:(3)vi,dt+1=wvi,dt+φPi,dt−xi,dt,where(4)Pit=∑j=1nsizeφjnbestjt/nsizeφ,where φj refers to a random value uniformly distributed in [0, 4.1/nsize] [26], φ=∑j=1nsizeφj,nbestj is the j-th nearest neighborhood to Pbesti, and nsize means the neighborhood size.


## 3. Dynamic Neighborhood-Based PSO for Multimodal Problems

In this section, two key techniques are presented in the proposed DNPSO. One is the definition of dynamicε-neighborhood; the other is the four tailored particle update strategies based on the neighborhood information of the current particle, and the framework of the proposed DNPSO is also provided.


### 3.1. Dynamicε-Neighborhood

At present, a number of researchers try to solve the MMOPs by using distance-based neighborhood to form different species in the search space, and most of them show that neighborhood information is crucial to enhance the diversity of the population [26, 33–35]. However, with neighborhood information, the offspring produced by these methods tend to be attracted to the inner regions enclosed by the initial population. Therefore, the number of optimal solutions is likely to depend on the initial distribution of individuals. To address this issue, we expect that particles can exchange information not only from their nearby particles, but also from the distant particles. Thereby, a balance can be achieved between the exploration and exploitation of the algorithm.In view of this, this section presents a dynamicε-neighborhood approach, where ε refers to the neighborhood radius. This approach is inspired by the idea of density clustering, and readers interested in this can refer to [36]. Some definitions of dynamic ε-neighborhood are presented as follows.Definition 1.
(Core object).Xi is a core object if the ε-neighborhood of Xi contains at least MinPts samples.Definition 2.
(Directly neighborhood-reachable). IfXj is located in the ε-neighborhood of Xi, and Xi is the core object, then Xj is directly reachable by Xi.Definition 3.
(Neighborhood-reachable). ForXi and Xj, if there exists a point p that makes Xi and p directly neighborhood-reachable and p and Xj are also directly neighborhood-reachable, then Xj is reachable by neighborhood of Xi.
Figure2 further illustrates the definitions of dynamic ε-neighborhood. From Figure 2, we can easily obtain that if X is a core object, then A, B, C, D, and E are directly neighborhood-reachable by X, and F, G, H, and I are neighborhood-reachable by X.
It should be noted that the purpose of dynamicε-neighborhood selection mechanism is to obtain the neighbors of each particle in the population. Therefore, each particle in the population is regarded as the core object. According to Definition 1, the ε-neighborhood of a core object should include at least MinPts points. A fixed value for MinPts is first provided in this paper, as the value of ε is difficult to set without prior knowledge. Then, we set εi = dismax, where dismax refers to the maximum distance between Xi and the particles in the set of directly neighborhood-reachable. Based on this, the neighborhood-reachable particles of Xi are found, so as to form the dynamic neighborhood of particle Xi.
The proposed dynamicε-neighborhood has three characteristics. (1) The neighborhood size of particle Xi varies dynamically in different evolutionary stage. (2) The neighborhood sizes of different particles in the same evolutionary stage may also be different. (3) Dynamic ε-neighborhood divides the neighborhood of the particle Xi into two levels. The particles in the group of directly neighborhood-reachable can be regarded as the close neighbors of Xi, while the particles in the group of neighborhood-reachable are regarded as the far neighbors of Xi. Algorithm 1 presents the pseudocode of dynamic ε-neighborhood selection mechanism.Figure 2
Diagram of dynamicε-neighborhood.Algorithm 1: Dynamic ε-neighborhood selection of particle Xi.
Input: Population size,NPSO, MinPts, the i-th particle in the population, Xi;Output: Ndr: Directly neighborhood-reachable group of Xi; Nr: neighborhood-reachable group ofXi;(1) Forj = 1: NPSO;(2) WhileXi∼ = Xj do;(3)  Calculate the Euclidean distance betweenXi and Xj;(4) End;(5) End;(6) Take the nearestMinPts particles with Xi, p1, …, pMinPts, and store them in Ndr;(7) The maximum distance betweenXi and the particles in Ndr is denoted as dismax, and set εi = dismax;(8) Fork = 1: MinPts;(9)  Forj = 1: NPSO;(10)   Whilep1-MinPts∼ = Xj & Xi∼ = Xj do;(11)    Calculate the Euclidean distance betweenpk and Xj. If the distance is less than εi, then put it into Nr.(12)   End;(13)  End;(14)  End.


### 3.2. PSO Based on Neighborhood Information

The neighborhood information of particles is employed to deal with the MMOPs in DNPSO. The detailed pseudocode of DNPSO is shown in Algorithm2. At the beginning of DNPSO, Latin hypercube sampling (LHS) is utilized to generate the initial population with the size of NPSO in the search space. Then, under MaxFEs, the particles are iteratively updated in the population. The detailed procedures are described as follows. Firstly, Algorithm 1 is employed to find the neighborhood of Pbesti in Pbest, including the close neighbors in the group of directly neighborhood-reachable (Ndr) and far neighbors in the group of neighborhood-reachable (Nr). Then, comparing Pbesti with the particles in Ndr and Nr, a position updating strategy is selected for Xi. After the new position of Xi is generated and evaluated, it will be compared with Pbesti. If the performance of the updated Xi is better than that of Pbesti, update Pbesti; otherwise, Pbesti remains unchanged.Algorithm 2: DNPSO.
Input: The population size,NPSO, the maximum number of evaluations, MaxFEs;Output:Pbest;(1) Generate an initial population with the size of NPSO with LHS, initializePbest;(2) Evaluate the fitness of the particles in the initial population;(3)FEs = NPSO;(4) WhileFEs < MaxFEs do;(5) Fori = 1: NPSO;(6)  Find the neighbors ofPbesti with Algorithm1, include Ndr and Nr;(7)  If the fitness ofPbesti is better than that of each individual in Ndr and Nr, then;(8)   Update the position ofXi by strategy (6);(9)  Elseif the fitness ofPbesti is the best in Ndr but is not the best in Nr, then;(10)   Update the velocity and position ofXi using strategies (4) and (2), respectively;(11)  Elseif the fitness ofPbesti is not the best in Ndr and is not the worst in Nr, then;(12)   Update the velocity and position ofXi with strategies (4) and (2), respectively;(13)  Elseif the fitness ofPbesti is worst in Ndr and Nr, then;(14)   Update the velocity and position ofXi with strategies (7) and (2), respectively;(15)  End;(16)  Evaluate the fitness ofXi;(17)  UpdatePbesti;(18)FEs = FEs + 1;(19) End;(20) End.The main idea of DNPSO is to assign the most appropriate position updating strategy to the particles, so that multiple optimal solutions of the optimization problem can be located simultaneously more effectively. Specifically, this paper adopts four updating strategies to generate offspring.Case 1.
WhenPbesti has the optimal performance in its directly neighborhood-reachable set, Ndr, and neighborhood-reachable set, Nr, it indicates that Pbesti is likely to be close to a peak in the search space, as shown in Figure 3(a). Therefore, Pbesti can be modified in a small scale by adding a Gaussian disturbance to it in the expectation that it will move in the direction of its nearest peak. The position update formula of Xi is given as follows:(5)xi,dt+1=Pbesti,dt+Gaussian0,σ,where Gaussian0,σ is the Gaussian distribution with mean zero and standard deviation σ.Figure 3
Illustration of the four cases of particles. The black solid circle is the core particle, the hollow circles are the direct neighborhood-reachable points of the core particle, and the squares are the neighborhood-reachable point of the core particle.
(a)(b)(c)(d)Case 2.
WhenPbesti is optimal in its Ndr but is not the best in its Nr, it indicates that Pbesti may be on a valley or on an unimportant local optimal peak, as shown in Figure 3(b). Therefore, it is necessary to exchange information with the particles in its distant neighbors, i.e., the neighbors in Nr, to make it jump out of the unimportant local optimum. The velocity update strategy of Xi adopts formula (3), where nbest stores all the particles which is better than Pbesti in Nr.Case 3.
WhenPbesti is not optimal in its Ndr and not worst in its Nr, it indicates that Pbesti may be halfway up a hill in the search space, as shown in Figure 3(c). Therefore, the convergence speed can be improved and the exploitation of the algorithm can be improved by exchanging information with the superior particles in the nearest neighbors. Formula (3) is also used for the velocity update of Xi, where nbest is the nearest neighbor set, i.e., the particles which are better than Pbesti in Ndr.Case 4.
WhenPbesti has the worst performance in its Ndr and Nr, indicating that Pbesti may be close to a valley, as shown in Figure 3(d), at this point, it can learn multiple directions, so as to improve the exploration of the algorithm. Then, the velocity update formula of Xi adopts the following formula:(6)vi,dt+1=wvi,dt+c1r1NbestNdr,dt−xi,dt+c2r2NbestNr,dt−xi,dt,where NbestNdrt is the optimal particle in Ndr and NbestNrt is the optimal particle in Nr of Pbesti.
It should be noted that a neighborhood-reachable set, Nr, may be an empty set. In this case, two situations are discussed: (1) whenPbesti is optimal in its Ndr, it will be processed in accordance with Case 1; (2) when Pbesti is not the best in its Ndr, it will be processed in accordance with Case 3.


### 3.3. Complexity Analysis

The time complexity of multimodal EAs is governed by their niching components. Generally, it is estimated by the number of elementary operations performed at each generation. The computational complexity of the proposed DNPSO is composed of two parts: the construction of particle’s neighborhood in Subsection3.1 and the operation of PSO in Subsection 3.2. The complexity of constructing the neighborhood of a particle is OD⋅NPSO+MinPts⋅NPSO. Then, the complexity of constructing all particle’s neighborhood in the population is OD+MinPts⋅NPSO2, where D is the problem dimension and NPSO is the population size. The time complexity of running PSO is ODNPSO. Hence, the total time complexity is OD+MinPts⋅NPSO2+D⋅NPSO. Since the value of NPSO is large, the amortized cost of DNPSO for each generation is OD+MinPts⋅NPSO2.


## 3.1. Dynamicε-Neighborhood

At present, a number of researchers try to solve the MMOPs by using distance-based neighborhood to form different species in the search space, and most of them show that neighborhood information is crucial to enhance the diversity of the population [26, 33–35]. However, with neighborhood information, the offspring produced by these methods tend to be attracted to the inner regions enclosed by the initial population. Therefore, the number of optimal solutions is likely to depend on the initial distribution of individuals. To address this issue, we expect that particles can exchange information not only from their nearby particles, but also from the distant particles. Thereby, a balance can be achieved between the exploration and exploitation of the algorithm.In view of this, this section presents a dynamicε-neighborhood approach, where ε refers to the neighborhood radius. This approach is inspired by the idea of density clustering, and readers interested in this can refer to [36]. Some definitions of dynamic ε-neighborhood are presented as follows.Definition 1.
(Core object).Xi is a core object if the ε-neighborhood of Xi contains at least MinPts samples.Definition 2.
(Directly neighborhood-reachable). IfXj is located in the ε-neighborhood of Xi, and Xi is the core object, then Xj is directly reachable by Xi.Definition 3.
(Neighborhood-reachable). ForXi and Xj, if there exists a point p that makes Xi and p directly neighborhood-reachable and p and Xj are also directly neighborhood-reachable, then Xj is reachable by neighborhood of Xi.
Figure2 further illustrates the definitions of dynamic ε-neighborhood. From Figure 2, we can easily obtain that if X is a core object, then A, B, C, D, and E are directly neighborhood-reachable by X, and F, G, H, and I are neighborhood-reachable by X.
It should be noted that the purpose of dynamicε-neighborhood selection mechanism is to obtain the neighbors of each particle in the population. Therefore, each particle in the population is regarded as the core object. According to Definition 1, the ε-neighborhood of a core object should include at least MinPts points. A fixed value for MinPts is first provided in this paper, as the value of ε is difficult to set without prior knowledge. Then, we set εi = dismax, where dismax refers to the maximum distance between Xi and the particles in the set of directly neighborhood-reachable. Based on this, the neighborhood-reachable particles of Xi are found, so as to form the dynamic neighborhood of particle Xi.
The proposed dynamicε-neighborhood has three characteristics. (1) The neighborhood size of particle Xi varies dynamically in different evolutionary stage. (2) The neighborhood sizes of different particles in the same evolutionary stage may also be different. (3) Dynamic ε-neighborhood divides the neighborhood of the particle Xi into two levels. The particles in the group of directly neighborhood-reachable can be regarded as the close neighbors of Xi, while the particles in the group of neighborhood-reachable are regarded as the far neighbors of Xi. Algorithm 1 presents the pseudocode of dynamic ε-neighborhood selection mechanism.Figure 2
Diagram of dynamicε-neighborhood.Algorithm 1: Dynamic ε-neighborhood selection of particle Xi.
Input: Population size,NPSO, MinPts, the i-th particle in the population, Xi;Output: Ndr: Directly neighborhood-reachable group of Xi; Nr: neighborhood-reachable group ofXi;(1) Forj = 1: NPSO;(2) WhileXi∼ = Xj do;(3)  Calculate the Euclidean distance betweenXi and Xj;(4) End;(5) End;(6) Take the nearestMinPts particles with Xi, p1, …, pMinPts, and store them in Ndr;(7) The maximum distance betweenXi and the particles in Ndr is denoted as dismax, and set εi = dismax;(8) Fork = 1: MinPts;(9)  Forj = 1: NPSO;(10)   Whilep1-MinPts∼ = Xj & Xi∼ = Xj do;(11)    Calculate the Euclidean distance betweenpk and Xj. If the distance is less than εi, then put it into Nr.(12)   End;(13)  End;(14)  End.


## 3.2. PSO Based on Neighborhood Information

The neighborhood information of particles is employed to deal with the MMOPs in DNPSO. The detailed pseudocode of DNPSO is shown in Algorithm2. At the beginning of DNPSO, Latin hypercube sampling (LHS) is utilized to generate the initial population with the size of NPSO in the search space. Then, under MaxFEs, the particles are iteratively updated in the population. The detailed procedures are described as follows. Firstly, Algorithm 1 is employed to find the neighborhood of Pbesti in Pbest, including the close neighbors in the group of directly neighborhood-reachable (Ndr) and far neighbors in the group of neighborhood-reachable (Nr). Then, comparing Pbesti with the particles in Ndr and Nr, a position updating strategy is selected for Xi. After the new position of Xi is generated and evaluated, it will be compared with Pbesti. If the performance of the updated Xi is better than that of Pbesti, update Pbesti; otherwise, Pbesti remains unchanged.Algorithm 2: DNPSO.
Input: The population size,NPSO, the maximum number of evaluations, MaxFEs;Output:Pbest;(1) Generate an initial population with the size of NPSO with LHS, initializePbest;(2) Evaluate the fitness of the particles in the initial population;(3)FEs = NPSO;(4) WhileFEs < MaxFEs do;(5) Fori = 1: NPSO;(6)  Find the neighbors ofPbesti with Algorithm1, include Ndr and Nr;(7)  If the fitness ofPbesti is better than that of each individual in Ndr and Nr, then;(8)   Update the position ofXi by strategy (6);(9)  Elseif the fitness ofPbesti is the best in Ndr but is not the best in Nr, then;(10)   Update the velocity and position ofXi using strategies (4) and (2), respectively;(11)  Elseif the fitness ofPbesti is not the best in Ndr and is not the worst in Nr, then;(12)   Update the velocity and position ofXi with strategies (4) and (2), respectively;(13)  Elseif the fitness ofPbesti is worst in Ndr and Nr, then;(14)   Update the velocity and position ofXi with strategies (7) and (2), respectively;(15)  End;(16)  Evaluate the fitness ofXi;(17)  UpdatePbesti;(18)FEs = FEs + 1;(19) End;(20) End.The main idea of DNPSO is to assign the most appropriate position updating strategy to the particles, so that multiple optimal solutions of the optimization problem can be located simultaneously more effectively. Specifically, this paper adopts four updating strategies to generate offspring.Case 1.
WhenPbesti has the optimal performance in its directly neighborhood-reachable set, Ndr, and neighborhood-reachable set, Nr, it indicates that Pbesti is likely to be close to a peak in the search space, as shown in Figure 3(a). Therefore, Pbesti can be modified in a small scale by adding a Gaussian disturbance to it in the expectation that it will move in the direction of its nearest peak. The position update formula of Xi is given as follows:(5)xi,dt+1=Pbesti,dt+Gaussian0,σ,where Gaussian0,σ is the Gaussian distribution with mean zero and standard deviation σ.Figure 3
Illustration of the four cases of particles. The black solid circle is the core particle, the hollow circles are the direct neighborhood-reachable points of the core particle, and the squares are the neighborhood-reachable point of the core particle.
(a)(b)(c)(d)Case 2.
WhenPbesti is optimal in its Ndr but is not the best in its Nr, it indicates that Pbesti may be on a valley or on an unimportant local optimal peak, as shown in Figure 3(b). Therefore, it is necessary to exchange information with the particles in its distant neighbors, i.e., the neighbors in Nr, to make it jump out of the unimportant local optimum. The velocity update strategy of Xi adopts formula (3), where nbest stores all the particles which is better than Pbesti in Nr.Case 3.
WhenPbesti is not optimal in its Ndr and not worst in its Nr, it indicates that Pbesti may be halfway up a hill in the search space, as shown in Figure 3(c). Therefore, the convergence speed can be improved and the exploitation of the algorithm can be improved by exchanging information with the superior particles in the nearest neighbors. Formula (3) is also used for the velocity update of Xi, where nbest is the nearest neighbor set, i.e., the particles which are better than Pbesti in Ndr.Case 4.
WhenPbesti has the worst performance in its Ndr and Nr, indicating that Pbesti may be close to a valley, as shown in Figure 3(d), at this point, it can learn multiple directions, so as to improve the exploration of the algorithm. Then, the velocity update formula of Xi adopts the following formula:(6)vi,dt+1=wvi,dt+c1r1NbestNdr,dt−xi,dt+c2r2NbestNr,dt−xi,dt,where NbestNdrt is the optimal particle in Ndr and NbestNrt is the optimal particle in Nr of Pbesti.
It should be noted that a neighborhood-reachable set, Nr, may be an empty set. In this case, two situations are discussed: (1) whenPbesti is optimal in its Ndr, it will be processed in accordance with Case 1; (2) when Pbesti is not the best in its Ndr, it will be processed in accordance with Case 3.


## 3.3. Complexity Analysis

The time complexity of multimodal EAs is governed by their niching components. Generally, it is estimated by the number of elementary operations performed at each generation. The computational complexity of the proposed DNPSO is composed of two parts: the construction of particle’s neighborhood in Subsection3.1 and the operation of PSO in Subsection 3.2. The complexity of constructing the neighborhood of a particle is OD⋅NPSO+MinPts⋅NPSO. Then, the complexity of constructing all particle’s neighborhood in the population is OD+MinPts⋅NPSO2, where D is the problem dimension and NPSO is the population size. The time complexity of running PSO is ODNPSO. Hence, the total time complexity is OD+MinPts⋅NPSO2+D⋅NPSO. Since the value of NPSO is large, the amortized cost of DNPSO for each generation is OD+MinPts⋅NPSO2.


## 4. Experiments and Analysis

In order to verify the effectiveness of the proposed DNPSO, the experiment is divided into the following two parts: (1) analyzing the sensitivity of the proposed algorithm to the value ofMinPts and (2) comparing DNPSO with 7 state-of-the-art multimodal EAs to test its capability of tackling MMOPs. In this paper, eight widely used benchmark problems are selected to test the performance of the algorithm. These benchmark problems are derived from the IEEE CEC 2013 special section on multimodal optimization [37]. The characteristics of these instances are shown in Table 1, where the “Peak height” refers to the value of the global optimal solution. All the algorithms are implemented by MATLAB R2014b on a CPU with Intel Core i5 and 1.6 GHz, and the experimental results are the average of 30 independent runs.Table 1
Benchmark instances.
FunctionDDecision spaceNo. of global/ local optimaPeak heightF1Equal maxima1x∈[0 1]5/01F2Uneven decreasing maxima1x∈[0 1]¼1F3Six-hump camel back2x1∈[−1.9 1.9]2/21.0316x2∈[−1.1 1.1]F4Shubert2X∈[−10, 10]218/many186.731Shubert3X∈[−10, 10]381/many2709.093F5Vincent2X∈ [0.25, 10]2361F6Modified Rastrigin2X∈[0, 1]D12/0-2F7Composition function 35/10X∈[−5, 5]D6/many0F8Composition function 45/10X∈[−5, 5]D8/many0


### 4.1. Parameter Settings

In DNPSO, the population size,NPSO, the maximum number of evaluations, MaxFEs, and the niching radius, r (which is used to distinguish the two neighboring global optimal solutions) are all set according to [34], as shown in Table 2. The amplitude accuracy is set to 1E-03. MinPts = 3; in formula (4), w = 0.7298; the standard deviation in formula (6) is 0.1; in formula (7), w = 0.7298, c1 = 2.05, and c2 = 2.05. According to [26], the neighborhood size (nsize) changes within {2, 3, 4, 5} as increase of generations.Table 2
Parameter settings.
F1F2F3F4(2D)F4(3D)F5F6F7F8MaxFEs5 × 1045 × 1045 × 1042 × 1054 × 1052 × 1052 × 1054 × 1054 × 105Npop100100100300300300100200200R0.010.010.50.50.50.20.010.010.01


### 4.2. Performance Metrics

In this paper, two commonly used performance indicators are used to evaluate the performance of an algorithm [28]:(1)
Peak ratio (PR): the peak ratio is the average percentage of the global optima found in multiple independent runs. The PR is calculated using the following formula:(7)PR=∑i=1RNPFiNPF×R,where NPFi is the number of global optima found in the i-th run, NPF denotes the number of know global optima, and R is the number of runs.(2)
Success rate (SR): success rate is the ratio between the number of successful runs (NSR) and the total number of runs (R). A successful run of an algorithm is when all global peaks are found in a run. It is calculated as follows:(8)SR=NSRR.


### 4.3. Analysis on Key Parameters

In this section, F2, F3, and F4 (whenD = 2 and 3) and F6 and F7 (when D = 5) are selected as representatives to analyze the influence of the MinPts and σ, on the performance of DNPSO.


#### 4.3.1. Analysis ofMinPts

The value of MinPts determines the value of neighborhood radius,ε, in Subsection 3.1, which indirectly affects the number of particles in the neighborhood-reachable set, Nr. Here, we analyze the influence of MinPts on the performance of DNPSO, when its values set is 2, 3, 4, and 5, respectively. Table 3 shows the PR and SR values obtained by DNPSO with different values of MinPts.Table 3
Results obtained by DNPSO with differentMinPts values.
2345PRSRPRSRPRSRPRSRF21.001.001.001.001.001.001.001.00F31.001.001.001.001.001.001.001.00F4(2D)0.920.21.001.000.970.60.930.2F4(3D)0.150.000.690.000.550.000.410.00F61.001.001.001.001.001.001.001.00F7(5D)0.130.000.700.000.680.000.680.00It can be concluded from Table3 that (1) for problems F2, F3, and F6, the proposed DNPSO obtains the same PR and SR when MinPts = 2, 3, 4, and 5. (2) For other problems, the PR value achieved from DNPSO when MinPts = 3 is the highest when MinPts = 2, 3, 4, and 5. (3) For F4 (2D), the SR value obtained from DNPSO when MinPts = 3 is higher than those when MinPts = 2, 4, and 5; for F4(3D) and F7(5D), when MinPts = 2, 3, 4, and 5, the SR values obtained from DNPSO are equal to 0. Considering the performance of DNPSO with different values of MinPts, the value of MinPts is set as 3 in subsequent experiments.


#### 4.3.2. Analysis ofσ

The value ofσ determines the size of Gaussian disturbance in formula (6), that is, the range of local search. This section analyzes the influence of σ on the performance of DNPSO, when σ set is 0.01, 0.05, 0.1, and 0.2. Table 4 shows the PR and SR values obtained by DNPSO under different σ values. It can be seen from Table 4 that (1) for F2, F3, and F6, the PR and SR values obtained by different values are similar. (2) For other problems, the PR value obtained when σ = 0.1 is higher than those obtained when σ = 0.01, 0.05, and 0.2. Based on these results, the value σ is set as 0.1 in subsequent experiments.Table 4
Results obtained by DNPSO with differentσ values.
0.010.050.10.2PRSRPRSRPRSRPRSRF21.001.001.001.001.001.001.001.00F31.001.001.001.001.001.001.001.00F4(2D)0.980.801.001.000.980.801.001.00F4(3D)0.440.000.630.000.440.000.630.00F61.001.001.001.001.001.001.001.00F7(5D)0.500.000.580.000.500.000.580.00


### 4.4. Comparison with Multimodal Evolutionary Algorithms

In order to verify the effectiveness of DNPSO, this section compares it with seven state-of-the-art multimodal EAs. These comparison algorithms include three multimodal algorithms based on PSO (R2PSO, R3PSO [15], and LIPS [26]), three multimodal algorithms based on DE (NCDE, NSDE [23], and VCNDE [28]), and one multiobjective EA (EMO-MMO [38–42]). In order to ensure the fairness of comparison, the population size, NPSO, the maximum number of evaluations, MaxFEs, the niching radius, r, and amplitude accuracy of all comparison algorithms are consistent with the proposed DNPSO, and the remaining parameters are set according to their original literatures’ suggestions.Table5 shows the mean value and standard deviation of PR obtained by DNPSO and 7 multimodal EAs when dealing with problems F1–F8, and the optimal results have been highlighted. In this paper, the Mann-Whitney test at a significance level of 5% is employed to evaluate significant difference between DNPSO and the compared algorithms, where “+” and “−” mean that DNPSO is significantly superior to and inferior to the compared one, respectively, and “=” indicates that there is no significant difference between them. In the table, “test” gives the results of the nonparametric test. In the penultimate row of Table 5, “win/tie/lose” is used to calculate the comparison result between DNSPO and each compared algorithm. Among them, “win” means the number of test problems that DNPSO dominates the compared one, “tie” indicates that the performance of DNPSO is similar to that of the compared one, and “lose” means the number of test problems that DNPSO is dominated by the compared one.Table 5
Peak ratios (PRs) achieved from the compared algorithms.
PRDNPSOLIPSEMO-MMOR2PSOR3PSONCDENSDEVNCDEF1Mean1.001.001.001.001.001.000.991.00Std0.000.000.000.000.000.000.000.00Test\=======F2Mean1.001.001.001.001.001.001.001.00Std0.000.000.000.000.000.000.000.00Test\=======F3Mean1.001.001.001.001.001.001.001.00Std0.000.000.000.000.000.000.000.00Test\=======F4 (2D)Mean1.000.751.000.530.690.140.270.96Std0.000.220.000.110.050.010.020.01Test\+=++++=F4 (3D)Mean0.690.490.800.320.280.680.130.74Std0.140.030.230.100.020.040.010.13Test\+=++=+=F5Mean1.000.201.000.010.160.500.060.55Std0.000.050.000.000.010.010.040.05Test\+=+++++F6Mean1.000.841.000.880.871.000.401.00Std0.000.130.000.010.110.000.010.00Test\+====+=F7 (5D)Mean0.700.410.600.140.130.260.350.70Std0.010.010.100.010.010.020.020.02Test\+=++++=F7 (10D)Mean0.540.200.660.060.370.630.520.66Std0.000.000.010.090.000.010.020.00Test\+−+−==−F8 (5D)Mean0.380.090.190.000.020.100.110.37Std0.010.090.040.000.000.020.120.11Test\++++++=F8 (10D)Mean0.160.060.120.000.050.240.120.29Std0.100.020.080.000.100.210.150.33Test\+=++==−Win/tie/lose\8/3/01/9/17/4/06/4/14/7/06/5/01/8/2Rank2.815.182.866.275.904.325.952.68It can be obtained from Table5 that (1) for problems F1, F2, and F3 there is no significant difference between the PR obtained by DNPSO and all compared algorithms. (2) For F4 and F7(5D), except EMO-MMO and VNCDE, PRs obtained by the remaining five algorithms are significantly inferior to DNPSO. (3) For F5, there is no significant difference between DNPSO and EMO-MMO, but the PRs obtained by DNPSO are significantly better than those of the other six compared ones. (4) For F6, the PR obtained by DNPSO is significantly better than those of LIPS and NSDE, with no significant difference from the other 5 compared algorithms. (5) For F7 (10D), the PRs achieved by DNPSO are obviously better than those of LIPS and R2PSO, but worse than those of EMO-MMO, R3PSO, and VNCDE. (6) For F8 (5D), except VNCDE, PRs obtained by the remaining 6 algorithms are significantly inferior to DNPSO. (7) For F8 (10D), the PR achieved by DNPSO is obviously better than those of LIPS, R2PSO, and R3PSO, but worse than that of VNCDE. According to the overall statistical results, DNPSO dominated LIPS on at least 8 instances, superior than R2PSO on at least 7 instances, and outperformed R3PSO and NSDE on at least 6 instances, superior than NCDE on at least 4 instances.In addition, STAC platform is used to test the difference between the proposed DNSPO and the compared algorithms, and Friedman test with significance level of 0.05 is used for analysis. The analysis results are shown in the last row of Table5, and the comprehensive ranking values of all algorithms on PR are given. DNPSO is used as the control method, it can be seen that rank of DNPSO is slightly higher than that of VNCDE, but lower than those of the other 6 compared algorithms. Furthermore, we adjusted the p value of pairwise comparison by using Finner operation, and the results are listed in Table 6. As can be seen from Table 6, DNPSO is statistically superior to LIPS, R2PSO, R3PSO, and NSDE and has similar performance with other three compared algorithms.Table 6
Post hoc analysis using DNPSO as control method.
DNPSO vs LIPSLIPSEMO-MMOR2PSOR3PSONCDENSDEVNCDEStatistic2.260.043.302.951.433.000.13Adjustedp value0.04090.96520.00650.00930.20470.00930.9287Figure4 shows the distribution of Pbest of the proposed DNPSO and LIPS on different population iterations for F6, where F6 has 12 global optimal solutions, as shown by red solid circles in the figure. It can be achieved from the figure that (1) both of them can converge to the vicinity of 12 global optimal solutions within 15 iterations; (2) the blue circles in Figure 4(g) are closer to the red solid circles than those in Figure 4(h), which indicates that the convergence precision of DNPSO is higher than that of LIPS.Figure 4
Distributions of Pbests of DNPSO and LIPS on different stages of F6. (a) Iteration 1 of DNPSO. (b) Iteration 1 of LIPS. (c) Iteration 5 of DNPSO. (d) Iteration 5 of LIPS. (e) Iteration 10 of DNPSO. (f) Iteration 10 of LIPS. (g) Iteration 15 of DNPSO. (h) Iteration 15 of LIPS.
(a)(b)(c)(d)(e)(f)(g)(h)Table7 lists the SR obtained by DNPSO and 7 multimodal EAs when dealing with problems F1–F8. The optimal results have been highlighted. The last row shows the comprehensive ranking values of SR of all algorithms. It can be seen from Table 7 that (1) for problems F1, F2, and F3 DNPSO and all the compared algorithms can find all the optimal solutions in each run. (2) For F4 (2D), the SR of DNPSO and EMO-MMO is equal to 1; the SR of VNCDE is equal to 0.54, while the SR obtained by the remaining 5 algorithms is 0. (3) For F5, the SRs of DNPSO and EMO-MMO are 1, and those of other algorithms are 0. (4) For F6, the SR values of DNPSO, EMO-MMO, NCDE, and VNCDE are all higher than those of the other three compared algorithms. (5) For F4 (3D), F7, and F8, the SR values obtained by all algorithms is 0; that is, no single run can find all the global optimal solutions. (6) From the perspective of rank value, DNPSO and EMO-MMO have similar performance, and the rank value is superior to the other compared algorithms.Table 7
Success rates (SRs) achieved from the compared algorithms.
DNPSOLIPSEMO-MMOR2PSOR3PSONCDENSDEVNCDEF11.001.001.001.001.001.000.981.00F21.001.001.001.001.001.001.001.00F31.001.001.001.001.001.001.001.00F4 (2D)1.000.001.000.000.000.000.000.54F4 (3D)0.000.000.000.000.000.000.000.00F51.000.001.000.000.000.000.000.00F61.000.841.000.220.241.000.001.00F7 (5D)0.000.000.000.000.000.000.000.00F7 (10D)0.000.000.000.000.000.000.000.00F8 (5D)0.000.000.000.000.000.000.000.00F8 (10D)0.000.000.000.000.000.000.000.00Rank3.724.723.724.904.814.505.364.22Table8 lists the running time of DNPSO and 7 multimodal EAs on the problems F1-F8. It can be seen from Table 8 that (1) R2PSO has the shortest running time and VNCDE has the longest running time. (2) The proposed DNPSO has slightly longer running time than those of LIPS, R2PSO, and R3PSO, but less than those of the remaining four algorithms.Table 8
Running time comparison of the multimodal algorithms.
DNPSOLIPSEMO-MMOR2PSOR3PSONCDENSDEVNCDEF10.240.091.070.040.061.175.726.00F20.240.091.080.030.081.126.485.90F30.360.111.090.040.111.176.416.25F4 (2D)3.560.473.450.220.204.7626.1824.48F4 (3D)3.790.463.470.210.614.7122.5724.64F56.911.258.900.600.9310.0151.4246.88F62.110.523.560.210.564.7222.0422.06F7 (5D)17.828.7320.348.019.4116.4854.1756.32F7 (10D)17.909.0323.408.458.6516.7254.5257.15F8 (5D)29.0115.5132.3214.8316.9325.6760.9789.91F8 (10D)30.9816.7135.0115.7522.7526.3462.5393.11


## 4.1. Parameter Settings

In DNPSO, the population size,NPSO, the maximum number of evaluations, MaxFEs, and the niching radius, r (which is used to distinguish the two neighboring global optimal solutions) are all set according to [34], as shown in Table 2. The amplitude accuracy is set to 1E-03. MinPts = 3; in formula (4), w = 0.7298; the standard deviation in formula (6) is 0.1; in formula (7), w = 0.7298, c1 = 2.05, and c2 = 2.05. According to [26], the neighborhood size (nsize) changes within {2, 3, 4, 5} as increase of generations.Table 2
Parameter settings.
F1F2F3F4(2D)F4(3D)F5F6F7F8MaxFEs5 × 1045 × 1045 × 1042 × 1054 × 1052 × 1052 × 1054 × 1054 × 105Npop100100100300300300100200200R0.010.010.50.50.50.20.010.010.01


## 4.2. Performance Metrics

In this paper, two commonly used performance indicators are used to evaluate the performance of an algorithm [28]:(1)
Peak ratio (PR): the peak ratio is the average percentage of the global optima found in multiple independent runs. The PR is calculated using the following formula:(7)PR=∑i=1RNPFiNPF×R,where NPFi is the number of global optima found in the i-th run, NPF denotes the number of know global optima, and R is the number of runs.(2)
Success rate (SR): success rate is the ratio between the number of successful runs (NSR) and the total number of runs (R). A successful run of an algorithm is when all global peaks are found in a run. It is calculated as follows:(8)SR=NSRR.


## 4.3. Analysis on Key Parameters

In this section, F2, F3, and F4 (whenD = 2 and 3) and F6 and F7 (when D = 5) are selected as representatives to analyze the influence of the MinPts and σ, on the performance of DNPSO.


### 4.3.1. Analysis ofMinPts

The value of MinPts determines the value of neighborhood radius,ε, in Subsection 3.1, which indirectly affects the number of particles in the neighborhood-reachable set, Nr. Here, we analyze the influence of MinPts on the performance of DNPSO, when its values set is 2, 3, 4, and 5, respectively. Table 3 shows the PR and SR values obtained by DNPSO with different values of MinPts.Table 3
Results obtained by DNPSO with differentMinPts values.
2345PRSRPRSRPRSRPRSRF21.001.001.001.001.001.001.001.00F31.001.001.001.001.001.001.001.00F4(2D)0.920.21.001.000.970.60.930.2F4(3D)0.150.000.690.000.550.000.410.00F61.001.001.001.001.001.001.001.00F7(5D)0.130.000.700.000.680.000.680.00It can be concluded from Table3 that (1) for problems F2, F3, and F6, the proposed DNPSO obtains the same PR and SR when MinPts = 2, 3, 4, and 5. (2) For other problems, the PR value achieved from DNPSO when MinPts = 3 is the highest when MinPts = 2, 3, 4, and 5. (3) For F4 (2D), the SR value obtained from DNPSO when MinPts = 3 is higher than those when MinPts = 2, 4, and 5; for F4(3D) and F7(5D), when MinPts = 2, 3, 4, and 5, the SR values obtained from DNPSO are equal to 0. Considering the performance of DNPSO with different values of MinPts, the value of MinPts is set as 3 in subsequent experiments.


### 4.3.2. Analysis ofσ

The value ofσ determines the size of Gaussian disturbance in formula (6), that is, the range of local search. This section analyzes the influence of σ on the performance of DNPSO, when σ set is 0.01, 0.05, 0.1, and 0.2. Table 4 shows the PR and SR values obtained by DNPSO under different σ values. It can be seen from Table 4 that (1) for F2, F3, and F6, the PR and SR values obtained by different values are similar. (2) For other problems, the PR value obtained when σ = 0.1 is higher than those obtained when σ = 0.01, 0.05, and 0.2. Based on these results, the value σ is set as 0.1 in subsequent experiments.Table 4
Results obtained by DNPSO with differentσ values.
0.010.050.10.2PRSRPRSRPRSRPRSRF21.001.001.001.001.001.001.001.00F31.001.001.001.001.001.001.001.00F4(2D)0.980.801.001.000.980.801.001.00F4(3D)0.440.000.630.000.440.000.630.00F61.001.001.001.001.001.001.001.00F7(5D)0.500.000.580.000.500.000.580.00


## 4.3.1. Analysis ofMinPts

The value of MinPts determines the value of neighborhood radius,ε, in Subsection 3.1, which indirectly affects the number of particles in the neighborhood-reachable set, Nr. Here, we analyze the influence of MinPts on the performance of DNPSO, when its values set is 2, 3, 4, and 5, respectively. Table 3 shows the PR and SR values obtained by DNPSO with different values of MinPts.Table 3
Results obtained by DNPSO with differentMinPts values.
2345PRSRPRSRPRSRPRSRF21.001.001.001.001.001.001.001.00F31.001.001.001.001.001.001.001.00F4(2D)0.920.21.001.000.970.60.930.2F4(3D)0.150.000.690.000.550.000.410.00F61.001.001.001.001.001.001.001.00F7(5D)0.130.000.700.000.680.000.680.00It can be concluded from Table3 that (1) for problems F2, F3, and F6, the proposed DNPSO obtains the same PR and SR when MinPts = 2, 3, 4, and 5. (2) For other problems, the PR value achieved from DNPSO when MinPts = 3 is the highest when MinPts = 2, 3, 4, and 5. (3) For F4 (2D), the SR value obtained from DNPSO when MinPts = 3 is higher than those when MinPts = 2, 4, and 5; for F4(3D) and F7(5D), when MinPts = 2, 3, 4, and 5, the SR values obtained from DNPSO are equal to 0. Considering the performance of DNPSO with different values of MinPts, the value of MinPts is set as 3 in subsequent experiments.


## 4.3.2. Analysis ofσ

The value ofσ determines the size of Gaussian disturbance in formula (6), that is, the range of local search. This section analyzes the influence of σ on the performance of DNPSO, when σ set is 0.01, 0.05, 0.1, and 0.2. Table 4 shows the PR and SR values obtained by DNPSO under different σ values. It can be seen from Table 4 that (1) for F2, F3, and F6, the PR and SR values obtained by different values are similar. (2) For other problems, the PR value obtained when σ = 0.1 is higher than those obtained when σ = 0.01, 0.05, and 0.2. Based on these results, the value σ is set as 0.1 in subsequent experiments.Table 4
Results obtained by DNPSO with differentσ values.
0.010.050.10.2PRSRPRSRPRSRPRSRF21.001.001.001.001.001.001.001.00F31.001.001.001.001.001.001.001.00F4(2D)0.980.801.001.000.980.801.001.00F4(3D)0.440.000.630.000.440.000.630.00F61.001.001.001.001.001.001.001.00F7(5D)0.500.000.580.000.500.000.580.00


## 4.4. Comparison with Multimodal Evolutionary Algorithms

In order to verify the effectiveness of DNPSO, this section compares it with seven state-of-the-art multimodal EAs. These comparison algorithms include three multimodal algorithms based on PSO (R2PSO, R3PSO [15], and LIPS [26]), three multimodal algorithms based on DE (NCDE, NSDE [23], and VCNDE [28]), and one multiobjective EA (EMO-MMO [38–42]). In order to ensure the fairness of comparison, the population size, NPSO, the maximum number of evaluations, MaxFEs, the niching radius, r, and amplitude accuracy of all comparison algorithms are consistent with the proposed DNPSO, and the remaining parameters are set according to their original literatures’ suggestions.Table5 shows the mean value and standard deviation of PR obtained by DNPSO and 7 multimodal EAs when dealing with problems F1–F8, and the optimal results have been highlighted. In this paper, the Mann-Whitney test at a significance level of 5% is employed to evaluate significant difference between DNPSO and the compared algorithms, where “+” and “−” mean that DNPSO is significantly superior to and inferior to the compared one, respectively, and “=” indicates that there is no significant difference between them. In the table, “test” gives the results of the nonparametric test. In the penultimate row of Table 5, “win/tie/lose” is used to calculate the comparison result between DNSPO and each compared algorithm. Among them, “win” means the number of test problems that DNPSO dominates the compared one, “tie” indicates that the performance of DNPSO is similar to that of the compared one, and “lose” means the number of test problems that DNPSO is dominated by the compared one.Table 5
Peak ratios (PRs) achieved from the compared algorithms.
PRDNPSOLIPSEMO-MMOR2PSOR3PSONCDENSDEVNCDEF1Mean1.001.001.001.001.001.000.991.00Std0.000.000.000.000.000.000.000.00Test\=======F2Mean1.001.001.001.001.001.001.001.00Std0.000.000.000.000.000.000.000.00Test\=======F3Mean1.001.001.001.001.001.001.001.00Std0.000.000.000.000.000.000.000.00Test\=======F4 (2D)Mean1.000.751.000.530.690.140.270.96Std0.000.220.000.110.050.010.020.01Test\+=++++=F4 (3D)Mean0.690.490.800.320.280.680.130.74Std0.140.030.230.100.020.040.010.13Test\+=++=+=F5Mean1.000.201.000.010.160.500.060.55Std0.000.050.000.000.010.010.040.05Test\+=+++++F6Mean1.000.841.000.880.871.000.401.00Std0.000.130.000.010.110.000.010.00Test\+====+=F7 (5D)Mean0.700.410.600.140.130.260.350.70Std0.010.010.100.010.010.020.020.02Test\+=++++=F7 (10D)Mean0.540.200.660.060.370.630.520.66Std0.000.000.010.090.000.010.020.00Test\+−+−==−F8 (5D)Mean0.380.090.190.000.020.100.110.37Std0.010.090.040.000.000.020.120.11Test\++++++=F8 (10D)Mean0.160.060.120.000.050.240.120.29Std0.100.020.080.000.100.210.150.33Test\+=++==−Win/tie/lose\8/3/01/9/17/4/06/4/14/7/06/5/01/8/2Rank2.815.182.866.275.904.325.952.68It can be obtained from Table5 that (1) for problems F1, F2, and F3 there is no significant difference between the PR obtained by DNPSO and all compared algorithms. (2) For F4 and F7(5D), except EMO-MMO and VNCDE, PRs obtained by the remaining five algorithms are significantly inferior to DNPSO. (3) For F5, there is no significant difference between DNPSO and EMO-MMO, but the PRs obtained by DNPSO are significantly better than those of the other six compared ones. (4) For F6, the PR obtained by DNPSO is significantly better than those of LIPS and NSDE, with no significant difference from the other 5 compared algorithms. (5) For F7 (10D), the PRs achieved by DNPSO are obviously better than those of LIPS and R2PSO, but worse than those of EMO-MMO, R3PSO, and VNCDE. (6) For F8 (5D), except VNCDE, PRs obtained by the remaining 6 algorithms are significantly inferior to DNPSO. (7) For F8 (10D), the PR achieved by DNPSO is obviously better than those of LIPS, R2PSO, and R3PSO, but worse than that of VNCDE. According to the overall statistical results, DNPSO dominated LIPS on at least 8 instances, superior than R2PSO on at least 7 instances, and outperformed R3PSO and NSDE on at least 6 instances, superior than NCDE on at least 4 instances.In addition, STAC platform is used to test the difference between the proposed DNSPO and the compared algorithms, and Friedman test with significance level of 0.05 is used for analysis. The analysis results are shown in the last row of Table5, and the comprehensive ranking values of all algorithms on PR are given. DNPSO is used as the control method, it can be seen that rank of DNPSO is slightly higher than that of VNCDE, but lower than those of the other 6 compared algorithms. Furthermore, we adjusted the p value of pairwise comparison by using Finner operation, and the results are listed in Table 6. As can be seen from Table 6, DNPSO is statistically superior to LIPS, R2PSO, R3PSO, and NSDE and has similar performance with other three compared algorithms.Table 6
Post hoc analysis using DNPSO as control method.
DNPSO vs LIPSLIPSEMO-MMOR2PSOR3PSONCDENSDEVNCDEStatistic2.260.043.302.951.433.000.13Adjustedp value0.04090.96520.00650.00930.20470.00930.9287Figure4 shows the distribution of Pbest of the proposed DNPSO and LIPS on different population iterations for F6, where F6 has 12 global optimal solutions, as shown by red solid circles in the figure. It can be achieved from the figure that (1) both of them can converge to the vicinity of 12 global optimal solutions within 15 iterations; (2) the blue circles in Figure 4(g) are closer to the red solid circles than those in Figure 4(h), which indicates that the convergence precision of DNPSO is higher than that of LIPS.Figure 4
Distributions of Pbests of DNPSO and LIPS on different stages of F6. (a) Iteration 1 of DNPSO. (b) Iteration 1 of LIPS. (c) Iteration 5 of DNPSO. (d) Iteration 5 of LIPS. (e) Iteration 10 of DNPSO. (f) Iteration 10 of LIPS. (g) Iteration 15 of DNPSO. (h) Iteration 15 of LIPS.
(a)(b)(c)(d)(e)(f)(g)(h)Table7 lists the SR obtained by DNPSO and 7 multimodal EAs when dealing with problems F1–F8. The optimal results have been highlighted. The last row shows the comprehensive ranking values of SR of all algorithms. It can be seen from Table 7 that (1) for problems F1, F2, and F3 DNPSO and all the compared algorithms can find all the optimal solutions in each run. (2) For F4 (2D), the SR of DNPSO and EMO-MMO is equal to 1; the SR of VNCDE is equal to 0.54, while the SR obtained by the remaining 5 algorithms is 0. (3) For F5, the SRs of DNPSO and EMO-MMO are 1, and those of other algorithms are 0. (4) For F6, the SR values of DNPSO, EMO-MMO, NCDE, and VNCDE are all higher than those of the other three compared algorithms. (5) For F4 (3D), F7, and F8, the SR values obtained by all algorithms is 0; that is, no single run can find all the global optimal solutions. (6) From the perspective of rank value, DNPSO and EMO-MMO have similar performance, and the rank value is superior to the other compared algorithms.Table 7
Success rates (SRs) achieved from the compared algorithms.
DNPSOLIPSEMO-MMOR2PSOR3PSONCDENSDEVNCDEF11.001.001.001.001.001.000.981.00F21.001.001.001.001.001.001.001.00F31.001.001.001.001.001.001.001.00F4 (2D)1.000.001.000.000.000.000.000.54F4 (3D)0.000.000.000.000.000.000.000.00F51.000.001.000.000.000.000.000.00F61.000.841.000.220.241.000.001.00F7 (5D)0.000.000.000.000.000.000.000.00F7 (10D)0.000.000.000.000.000.000.000.00F8 (5D)0.000.000.000.000.000.000.000.00F8 (10D)0.000.000.000.000.000.000.000.00Rank3.724.723.724.904.814.505.364.22Table8 lists the running time of DNPSO and 7 multimodal EAs on the problems F1-F8. It can be seen from Table 8 that (1) R2PSO has the shortest running time and VNCDE has the longest running time. (2) The proposed DNPSO has slightly longer running time than those of LIPS, R2PSO, and R3PSO, but less than those of the remaining four algorithms.Table 8
Running time comparison of the multimodal algorithms.
DNPSOLIPSEMO-MMOR2PSOR3PSONCDENSDEVNCDEF10.240.091.070.040.061.175.726.00F20.240.091.080.030.081.126.485.90F30.360.111.090.040.111.176.416.25F4 (2D)3.560.473.450.220.204.7626.1824.48F4 (3D)3.790.463.470.210.614.7122.5724.64F56.911.258.900.600.9310.0151.4246.88F62.110.523.560.210.564.7222.0422.06F7 (5D)17.828.7320.348.019.4116.4854.1756.32F7 (10D)17.909.0323.408.458.6516.7254.5257.15F8 (5D)29.0115.5132.3214.8316.9325.6760.9789.91F8 (10D)30.9816.7135.0115.7522.7526.3462.5393.11


## 5. Conclusions

To tackle MMOPs, this paper presents a multimodal particle swarm optimization algorithm based on dynamic neighborhood, called DNPSO. The proposed DNPSO defines a dynamic neighborhood selection mechanism, which makes the neighborhood size of particles change dynamically in the process of evolution, and distinguishes the particles in the neighborhood between directly neighborhood-reachable and neighborhood-reachable at the same time, so as to balance the exploration and exploitation of the algorithm. Following that, based on the information provided by the neighbors, four different particle position updating strategies are designed to further support the algorithm's exploration and exploitation of the search space. The experimental results on eight test benchmark functions show that the proposed algorithm is competitive with several existing multimodal EAs and is an effective method to deal with MMOPs.DNPSO, like other EAs, shows poor performance when dealing with high-dimensional MMOPs, which requires further study. It is also suggested to extend this dynamic neighborhood method to other EAs like DE in the future. In addition, it may be worthy to apply DNPSO to real-world problems such as feature selection.



---

*Source: 6675996-2020-12-21.xml*