Multi-objective particle swarm optimization algorithm based on leader combination of decomposition and dominance

2.1 The concepts of multi-objective optimization

 Multi-objective optimization deals with the simultaneous optimization of two or more objectives which are generally conflicting with each other. Without loss of generality, a MOP could be defined as follows:

Min : F ( X ) = { f 1 ( x → ) , f 2 ( x → ) , f 3 ( x → ) . . . f m ( x → ) } Subject to : x → ∈ R n(1)

 Where, f _i (i ∈ 1, 2, 3 . . . m) are m conflicting objective functions. R ⁿ is the decision variable space. Denote a solution x → by x → = ( x 1 , x 2 , x 3 . . . x n ), where d is the number of variables. Maximization of a scalar objective function f _i is the same as minimization of -f _i .

Definition 1. x → ⪯ x → ′ , which solution x → is weakly dominate solution x′, if f i ( x → ) ≤ f i ( x → ′ ) , ∀ i ∈ m and ∃i ∈ m, f i ( x → ) < f i ( x → ′ ) .

Definition 2. x → ≺ x → ′ , which solution x → is dominate solution x → , if f i ( x → ) < f i ( x → ′ ) , ∀i ∈ m.

Definition 3. A solution x → is Pareto optimal if ¬ ∃ x → ′ ∈ R n , x → ′ ⪯ x → .

Definition 4. A set PS of all Pareto optimal solution is called Pareto optimal set, PS = { x → | ¬ ∃ x → ′ ⪯ x → } .

Definition 5. A set that contains all the Pareto optimal objective vectors is called the Pareto Front, denoted by PF = { f ( x → ) | X ∈ PS } .

 This sub-section gives a relatively basic concept of the PSO algorithm. In the continuous space coordinate system, the PSO algorithm model can be described as follows. Assume that swarm size is N, particle i position vector in n-dimensional space is x → i = ( x i 1 , x i 2 , ⋯ , x i k , ⋯ , x i n ) , i ∈ N; velocity vector is v → i = ( v i 1 , v i 2 , ⋯ , v i k , ⋯ , v i n ) , i ∈ N. The position of each particle is changed according to its own experience by adding a velocity, which is defined in Equation (3). The velocity vector reflects the socially exchanged information and it is defined in Equation (2). v i , t + 1 k = ω * v i , t k + c 1 * r 1 * ( pb i k - x i , t k ) + c 2 * r 2 * ( gb i k - x i , t k )(2) x i , t + 1 k = x i , t k + v i , t + 1 k(3) where, v i , t + 1 k is dimensional k of velocity vector for the particle i at time t + 1; x i , t k is dimensional k of velocity vector for the particle i at time t + 1; ω is inertia weight. r₁, r₂ ∈[0 1] are two random value. c₁, c₂ are the learning factors. pb is the particle’s location at which the best fitness so far has been achieved for this particle; gb is the population global location at which the best fitness so far has been achieved.

 The velocity vector Equation (2) can be divided into 3 parts: the first part is the particle acceleration based on its current velocity by iteration weight, which represents the preservation of particle history movement; the second part is the particle self-cognition, which represents the improvement of particle history movement; the third part is social activity, which represents the information sharing and swarm cooperation.

 The early published manuscript using PSO strategy solving multi-objective problems could be found at [2, 3]. Since then, MOPSO have attracted a wide range of researchers and readers from all fields of science and engineering on intelligence algorithm methodologies to optimize complicated problems. Coello uses the concept of Pareto dominance to determine the flight direction of a particle, and non-dominated vectors in a global repository have been used by other particles to guide their own flight [3]. These research of multi-objective particle swarm optimization with evolutionary algorithms make evident that non-dominated Pareto sorting could be a straightforward way to extend PSO approach to handle multi-objective optimization problem. The historical record of best solutions found by a particle could be used to store non-dominated solutions generated in the past, which is similar to the external elite archive in genetic-based algorithm. In these former MOPSOs, the global optimal particles are found by the non-dominated sorting. It is equal to say that a global repository in which every particle will deposit its flight experiences based on non-dominated sorting.

 There is other approach using particle swarm intelligence to optimize MOPs. Multi-objective optimization using dynamic neighborhood particle swarm optimization is proposed by Hu and Eberhart in [4]. In this algorithm, only one objective is optimized at a time using a scheme similar to lexicographic ordering, which is useful only when few objective functions are used. Their later research adopted a secondary population and introduced some further improvements to their dynamic neighborhood PSO approach [5]. Though these approaches achieve better than the former version, this algorithm fails in searching the Pareto front in some test functions.

 OMOPSO is presented based on Pareto dominance and the use of a crowding factor to filter out the list of available leaders [13]. Swarm have been divided into different subdivision and different mutation operators have been employed. Algorithm also incorporates the ε-dominance concept to fix the size of the set of final solutions.

 SMPSO, which is based on the OMOPSO, incorporates a velocity constriction procedure to produce new effective particle positions [12]. It also employs polynomial mutation as turbulence factor and an external archive to store the non-dominated solutions found during the search.

 CMPSO is a novel and effective approach which used an external shared archive for different populations to exchange search information [14]. Two novel designs have been used to enhance the performance. One design is to modify the velocity update equation to use the search information found by different populations, which is benefit to the convergence. The other one is to use an elitist learning strategy for the archive update to bring in diversity to avoid falling into local Pareto front.

 pccsAMOPSO is proposed by Hu in [16]. The strategies proposed for selecting global best and personal best, maintaining archive, adjusting flight parameters, and perturbing stagnation are integrated into a self-adaptive MOPSO, abbreviated as pccsAMOPSO. This algorithm is designed to dynamically adjust the balance in exploration and exploitation according to the feedback information detected from the evolutionary environment.

 MOPSO/GMR deploys the position information of individuals in objective space to gain the margin of dominance throughout the population [17]. An innovative strategy for selecting gBest and pBest in presented by integrating the GMR and the individual’s density information. The method not only considers the distribution of swarm, but also incorporates the associated information of particles.

 D²MOPSO incorporates dominance with decomposition used in the context of multi-objective optimisation [15]. Decomposition simplifies a MOP by transforming it to a set of aggregation problems, whereas dominance plays a major role in building the leaders archive. It also introduces a new archiving technique to achieve better diversity and convergence in both objective and decision spaces. In D²MOPSO, dominance-based selection mechanism is used to store only non-dominated particles along with crowding distance, and decomposition-based selection mechanism is used to update the personal best values. While, the evolutionary operator of this MOPSO still remain the original version without adjusting based on MOPs.

 Coello summarized a survey of the existing MOPSOs, and provided a complete taxonomy of these algorithms [1]. The authors considered as the main features of all existing MOPSOs the following ones: the existence of an external archive of non-dominated solutions, the selection strategy of non-dominated solutions as leaders for guiding the swarm, the neighborhood topology, and the existence or not of a mutation operator.

 To apply a PSO algorithm in MOPs, three important issues should be considered [1]:

How to select the particles, which give preference to non-dominated solutions, to be used as leader particles?

 These issues maybe more hard to deal with when Pareto front process some special features: (1) Multi-modality increases the possibility of falling into local optima; An objective function is multi-modality when it has multiple local optima. We consider a MOP is multi-modal if there is at least one multi-modal objective function. (2) A deception Pareto front may mislead the search direction isolation lacks information to guide the search. We consider a MOP is deceptive if there are at least two optima front: a true optimum and a deceptive optimum. (3) The shape of Pareto front (convex or concave, continues or discontinues) may affect convergence and diversity, especially when weight of decomposition-based algorithm has not been selected appropriately.

3.1 The update mechanism of pbest and gbest

 Most of former research about MOPSOs is based on non-dominated Pareto relationship, while the decomposition-based approaches seem to be a promising way in some specific test problem with complicated Pareto front. Compared with the dominance-based MOEAs, decomposition-based algorithm have shown some advantages on maintaining better population diversity. Decomposition-based algorithms are good at handling problems with multi-modality and lots of local Pareto fronts which are not uniformly distributed in its global Pareto front. To improve the robustness of MOPSO, dominance-based approach and decomposition-based approach are combined into proposed algorithm to guide the leader particle update.

 Each particle in swarm archive towards the a promising direction guided by the gbest and the pbest together, and the whole swarm follows the trajectory of gbest [16]. Therefore, choosing the appropriate social and cognitive guide (gbest and pbest) is the key problems of the MOPSO algorithm. The leader particle update process of PSO algorithm is different from the genetic-based algorithm, which is shown in Fig. 1. In genetic-based algorithm, the individuals exchange information with each other by crossover operation, which is bi-direction information sharing operation. While in traditional PSO-based algorithm, the particles are updated by its previous position and velocity. In some MOPSOs, gbest are used to share information with the other particles. Selecting an appropriate leader particle in MOPSO is a feasible way to control its convergence and promote its diversity. Therefore, the selection of gbest for each particle in evolutionary process is a crucial step in MOPSO. The number of gbest particles is not always fixed. The more gbest particle have been selected, the more particles will spread along the objective space and the better diversity will achieve. But it also affects the convergence speed and some particles which are not process good property will reserve. On the contrary, the less number of the gbest particles is selected, the higher the selection pressure is, which leads to a fast convergence speed. The selection of the gbest should simultaneously provide effective guidance for the particles to obtain a better convergence speed and to maintain the diversity on Pareto front. Based on the discussion, the decomposition and dominance selection mechanism are both introduced into leader particle selection on social and cognitive guide (gbest and pbest). As illustration of former research, dominance-based algorithms focus on the convergence to the Pareto front, and may lead the particles into some local region. On the contrary, decomposition-based algorithms pay more attention on the diversity, which makes some solution converge slow. Therefore, these two selection mechanisms are used to select the global and personal best of particles: decomposition is used to selection gbest, and dominance is used to select pbest. When the swarm information update, the newly-generated particles are combined with pbest and gbest, respectively. Then, each pbest is assigned a gbest based on the distance between each other. After that, the particle update based on its pbest and gbest, which are in pair. The detail of solution comparison and the pair pattern are shown in Fig. 2.

OPEN IN VIEWER

Fig.1

The different child-generate mechanism between Genetic-based algorithm and PSO algorithm.

OPEN IN VIEWER

Fig.2

The comparison between solutions obtained by decomposition-based and dominance-based algorithms.

 Based on the former discussion about leader particles and selection mechanism, this section illustrates the details of proposed algorithm. Procedure of the proposed DDMOPSO algorithm is described as Algorithm 1. The flow diagram of DDMOPSO is shown in Fig. 3.

Algorithm 1 Pseudo code of DDMOPSO

Input:

 NP, population size;

 NFE, number of fitness evaluation;

 ω, inertia weight;

 c₁, c₂, learning factors;

 Position constraints and velocity constraints.

Output:

  gbest

 1: Initialize velocity and a swarm X with NP particles;

 2: set gbest =X;

 3: while i < NFE do

 4: Generate a swarm X _child with NP base on the particle position formula, evaluate the particle fitness;

 5: i = i + NP;

 6: X _comb  = pbest ∪ X _child ;

 7: Update pbest based non-dominated sort from X _comb ;

 8: X _comb  = gbest ∪ X _child ;

 9: Update gbest based decomposition from X _comb ;

 10: Pair the pbest and gbest into a new swarm;

 11: Update velocity;

 12: end while

 13: return gbest;

3.3 Convergence analysis

 There are research on analysis of the stability and convergence properties of particle swarm optimizer (PSO), while most of them are centered on the single-objective PSO algorithm [18]. This section presents a simple convergence analysis of the MOPSO with the combination on both dominance-based and decomposition-based selection mechanism.

Theorem. Let the Pareto-optimal be represented by Λ^*. If X is the initial swarm in a multi-objective search space, a MOPSO algorithm will lead the swarm mean to converge to the center of the Pareto-optimal set Λ^*, i.e. if μ _n is the expected population mean after n iterations, then lim n → ∞ μ n = X ˆ * ; where X ˆ * denotes the center of Pareto-optimalset.

Proof. Let X^* be a random chosen solution from Pareto-optimal set Λ^*. Then a local best particle P i l ( t ) and global best particle P ^g  (t) could be expressed as: { P i l ( t ) = X * + D Li ( t ) P g ( t ) = X * + D Gi ( t )(4) where D _Li  (t) and D _Gi  (t) are the distance of the personal best position found by a particle and the global best particle of the swarm from X^* at time-step iteration t. Then, the velocity update and position update formulas could be rewritten as:

V i ( t + 1 ) = ω · V i ( t ) + ( c 1 · r 1 + c 2 · r 2 ) · ( X * - X i ( t ) ) + c 1 · r 1 · D Li ( t ) + c 2 · r 2 · D Gi ( t )(5)

X i ( t + 1 ) = [ 1 + ω - ( c 1 · r 1 + c 2 · r 2 ) ] X i ( t ) - ω · X i ( t - 1 ) + ( c 1 · r 1 + c 2 · r 2 ) · X * + c 1 · r 1 · D Li ( t ) + c 2 · r 2 · D Gi ( t )(6)

 Then, taking expectations on both sides of position update Equation (6) and denote the mean value of the position of the “ith” particle at iteration number “t” as μ _i  (t).

μ i ( t ) = [ 1 + ω - c 1 + c 2 2 ] · μ i ( t - 1 ) - ω · μ i ( t - 2 ) + c 1 + c 2 2 ( X ˆ * ) + 1 2 [ c 1 D ˆ Li ( t - 1 ) + c 2 D ˆ Gi ( t - 1 ) ](7)

 Where, D ˆ Li = E ( D Li ) and D ˆ Gi = E ( D Gi ) . Then, taking Z-transform of both side of Equation (7). Dropping the subscript for each such particle “i”,

μ ( z ) · ( 1 - α · z - 1 + ω · z - 2 ) = c 1 + c 2 2 · X ˆ * · Z ( U ( t ) ) + 1 2 [ c 1 · z - 1 · D ˆ L ( z ) + c 2 · z - 1 · D ˆ G ( z ) ](8)

 Where, α = ( 1 + ω - c 1 + c 2 2 ) and U (t) denotes the unit step function.

μ ( z ) = c 1 + c 2 2 · X ˆ * z 3 ( z 2 - α · z + ω ) · 1 z - 1 + z 2 · ( z 2 - α · z + ω ) · ( c 1 · D ˆ L ( z ) + c 2 · D ˆ G ( z ) )(9)

 Based on the hypothesis lim t → ∞ μ ( t ) = lim z → 1 ( z - 1 ) μ ( t ) , the final value provided the limit exists. Then,

lim t → ∞ μ ( t ) = c 1 + c 2 2 X ˆ * lim z → 1 [ z 3 ( z 2 - α · z + ω ) ] + c 1 2 lim z → 1 [ z ( z - 1 ) ( z 2 - α · z + ω ) · D ˆ L ( z ) ] + c 2 2 lim z → 1 [ z ( z - 1 ) ( z 2 - α · z + ω ) · D ˆ G ( z ) ](10)

 Based on the analysis in [18], the lim t → ∞ μ ( t ) could be simplified as: lim t → ∞ μ ( t ) = c 1 + c 2 2 · X ˆ * · 1 c 1 + c 2 2 + 0 + 0(11)

 Then, lim t → ∞ μ ( t ) = X ˆ * , and this proves the theorem.

4.1 The experimental setup

 In this section, two sets of MOP benchmark functions, ZDT and DTLZ, and two types of multi objective optimization methods, MOPSOs and MOEAs, are employed to evaluate the performance of the proposed algorithm. It is noted that the test instance ZDT5 is omitted because it is a Boolean function and requires binary encoding. The features, dimensions of each test instance are listed in Table 1.

 Convergence and diversity are two different parts which should be considered when designing a MOEA. For this purpose, we choose the Inverse Generational Distance (IGD) [70] as the performance metric to measure the performance of the obtained solutions. The smaller the IGD value is, the better the performance of MOEA is. If P^* is the set of uniformly distributed Pareto optimal solutions in the objective space and A is the obtained approximation set of non-dominated solutions in the objective space from a MOEA, the IGD value for the approximation set is defined by Equation (12): IGD ( A , P * ) = ∑ v ∈ P * d ( v , A ) ) | P * |(12) where, d (v, A) is the minimum Euclidean distance between v and points in A, and |P^*| is the cardinality of P^*. The sample size of the true Pareto front (No. of Pf) could also be found at Table 1.

 In order to validate performance the proposed PSO algorithm, five state-of-the-art MOEAs are selected as the comparison algorithms in the experiments. These algorithms could be divided in two categories based on the evolutionary operator. (1) The MOEAs, which include NSGA-II [9] and MOEA/D [10], are genetic based algorithm. The main difference of the two algorithms is their selection mechanism: NSGA-II is based on Pareto non-dominated relationship, while MOEA/D is based on a decomposition method to decompose a MOP into a number of scalar optimization problems. These two MOEAs have been proven to be very successful in most of MOPs. (2) The MOPSOs include two classical algorithms: OMOPSO [13], SMPSO [12] and a newly-proposed algorithm MIMOPSO [11]. Maximum function evaluations has been set as 100,000. Each algorithm has been run 30 times. Population size NP has been set as 100, 150 for m = 2, 3 objectives, respectively. Population size of MOEA/D is decided by weight vectors based on [10]. The parameter settings of all compared algorithms are listed in Table 2. The experiments are conducted on MATLAB R2010b with Microsoft Windows 7 64-bit. The hardware configurations used to run the algorithms are provided below: Processor: Intel Core (TM) i5-4590 3.3 GHz, RAM capacity: 8 GB.

 Based on the former section, IGD has been selected as the metric to evaluate the performance of these algorithms. Table 3 shows the details about the IGD results of 5 algorithms over 30 independently runs on 10 MOPs with 100,000 function evolutions. The first line of each benchmark is the mean value of IGD metric, and the second line is standard deviation. The last two lines in this table are the count of algorithm on rank 1st/2nd/3th for mean value and standard deviation. The proposed algorithm achieves the 5 optimal and 4 suboptimal mean values of 10 benchmarks. From the experimental results, we find that MOPSOs shows a clearly better performance than MOEAs, and decomposition-based algorithms perform better than dominance-based on standard deviation. To a further comparison between proposed algorithm and the other MOEAs and MOPSOs in statistics, the distribution of the IGD metrics is presented by box-plots in Fig. 4. From the IGD table and IGD boxplot, the proposed algorithm achieves 4 of 5 best on ZDT test suite. To a further comparison among these algorithms, the Pareto front of ZDT and DTLZ test suite obtained by these algorithm are shown in Figs. 6 and 7, respectively. It is clear that the combination on leader particle selection mechanism performs well in 2-dimensional problems. For convex and multi-modal problem ZDT4, the algorithms based on evolutionary operator did not achieve a good convergence. While the particle-swarm-based algorithm all converge to the Pareto fronton ZDT4.

OPEN IN VIEWER

Fig.3

The flow diagram of DDMOPSO.

OPEN IN VIEWER

Fig.4

The boxplot of IGD.

OPEN IN VIEWER

Fig.5

The convergence curves of IGD (For interpretation of the references to color in the text, the reader is referred to the web version of this article).

OPEN IN VIEWER

Fig.6

The Pareto front of ZDT test suite (For interpretation of the references to color in the text, the reader is referred to the web version of this article).

OPEN IN VIEWER

Fig.7

The Pareto front of DTLZ test suite (For interpretation of the references to color in the text, the reader is referred to the web version of this article).

 To further investigate the convergence behavior of all the compared MOEAs, Fig. 5 illustrate the plots of average IGD results obtained by all the algorithms versus the number of function evaluations on each test problem. The convergence curves indicates that the proposed algorithm can effectively avoid premature convergence and evolutionary stagnation. Based the composite analysis of Figs. 4 and 5, the proposed algorithm performs best in 2-objective optimization problems. In 3-dimensional problem, the convergence speed of DDMOPSO is also acceptable in most benchmarks. On DTLZ7 with deceptive Pareto front, the proposed algorithm did not achieve a good performance, which is also shown in Fig. 7. Based on the Pareto front of DTLZ test suites and the IGD table, OMOPSO performs best in DTLZ4 and DTLZ7, while it did not converge to the Pareto front of DTLZ1 and DTLZ3. These also prove the “No free lunch” theory that no a single algorithm could achieve best performance on all test problems.