A novel multi-objective PSO algorithm based on completion-checking

Abstract

Multi-objective particle swarm optimization (MOPSO) algorithms are shown to have enormous potential in solving multi-objective optimization problems (MOPs). However, most MOPSO is difficult to balance the exploration and exploitation, which may cause some problems to find true Pareto fronts when tackling some complex MOPs. A multi-objective decomposition particle swarm optimization based on completion-checking (C-DMOPSO) is improved in this paper. The updating mode of velocity is changed dynamically according to the algorithm’s evolutionary process, which balances the exploration and exploitation effectively. In addition, simulated binary crossover and opposition-based learning are adopted to improve the diversity, and the archive set strategy is added to store the optimal solutions. Furthermore, polynomial mutation is performed in archive. The effectiveness of the proposed algorithm is tested by nineteen standard functions, including ZDT, DTLZ and UF, and the experimental results show that C-DMOPSO performs better on most of test problems.

Keywords

Multi-objective optimization evolutionary algorithms decomposition particle swarm optimization

1 Introduction

There are many problems require the optimization of several conflicting objectives simultaneously in most practical engineering applications, which affect each other and with high computational complexity. These problems are called multi-objective optimization problems (MOPs). As a single solution is not available to minimize all objectives, the optimal solution of MOPs is a set with many trade-off solutions. Multi-objective evolutionary algorithms (MOEAs) are easy to understand and implement without much specific information, so they are very popular in solving MOPs [4] and developed in real-word application such as rolling schedules [11], sensor networking and path planning [29]. Particle swarm algorithm (PSO) [12] is a group intelligent algorithm for simulating bird flight. The main idea of PSO algorithm is closely related to evolutionary algorithm: PSO uses a swarm mode which makes it to simultaneously search large region in the solution space to optimize objective functions just like evolutionary algorithms. Particles in the swarm are moved to find the optimal value by global search and local search, and the algorithm is simple and feasible in dealing with single objective optimization problems (SOPs), especially in optimization of optimal power flow [22] and manufacturing process parameters [21]. This has motivated researchers to extended it to MOPs [8].

The methods for solving MOPs can be divided into three categories: dominance-based, decomposition-based and indicator-based methods [7]. Among them, the dominance-based and the decomposition-based method are widely used.

Dominance-based approach is a fundamental method to deal with MOPs, and NSGAII algorithm [6] is one of a remarkable MOEA based on the dominance-based framework. However, it is ineffective when dealing with many-objective optimization problems or the problems with complicated Pareto front.

In decomposition-based method, the MOP is transformed into a series of scalar functions so that objective function can be optimized by solving single objective problem directly. One of the famous representative MOEAs based on decomposition is MOEA/D [27]. This approach has received much attention because it can be used to simplify MOPs. MOPSO/D [19], dMOPSO [25] are two multi-objective PSO algorithms based on decomposition. Because of its low complexity and good performance, the multi-objective PSO algorithm based on decomposition is widely studied.

The third type of MOEA is indicator-based method, it mainly updates offspring according to searching for information depends on the performance of the indicator such as the hypervolume [2] and R2 [20], which are used to measure the fitness of a solution by assessing its contribution to the both convergence and diversity of a MOEA.

In addition, PSO possesses different improvements in many aspects recently [23]. In the aspect of parameter adjustment, the adjustment based on Bayesian techniques [26], exponential decreasing inertia weight strategy [16] are proposed as the algorithm with the fixed inertia weight usually cannot get satisfactory results. Inspired by the idea of time-varying inertia weight, learning factors changed with time is adopted in [17]. In the population structure, Gülcü [9] proposed a new multi-population parallel collaborative particle swarm optimization algorithm, which made it easy to the effective communication between the particles. Nevertheless, the use of multiple computers to exchange information increases the difficulty on the realization of the algorithm. In the ways of searching, Lin, Q [15] and others proposed a new particle swarm update formula, which can balance the population diversity and convergence ability. DDMOPSO [1] combined the idea of decomposition and dominance, which makes the particle swarm converge to the real front without using genetic operations. However, when dealing with high-dimensional problems, the algorithm is slow to converge and inefficient.

Therefore, when using PSO to deal with MOPs, the key is to update the individual optimal location and global optimal location, and make sure to: a) converge as fast as possible, b) gain a good distribution on the Pareto front, c) avoid falling into local optimum which result in premature convergence. Considering the optimized form of PSO, it can be divided into some aspects as follows: the expansion of population topology, the improvement of particle searching, the study of hybrid strategy PSO and the adjustment of parameters.

Existing studies have shown that a single speed update mode often leads to over-exploration or over-exploitation, which result in poor convergence or premature convergence. For MOPs, using the dominance method alone may cause the high complexity and slow convergence rate, while using the decomposition method alone may generate poor distribution on the Pareto front. Therefore, combining the two methods is a key factor to the effectiveness of the algorithm.

Based on the existing research, main improvements of this paper are listed bellow:

For PSO, the speed update formula is improved for the problem that exploration and exploitation is difficult to balance in the process. The completion-checking factor is proposed in order to speed up the convergence rate of the algorithm. The speed update pattern is changed and the particle neighborhood size is adjusted dynamically by checking the algorithm process.

In order to solve the problem that the population is easy to fall into local optimum during the updating process, simulated binary crossover (SBX) and opposition-based learning (OBL) are adopted in this paper to maintain the diversity of particle swarm.

For the problem that it is difficult to make full use of the good information after updating of each generation, the archive set is introduced to preserve the good solutions in population. What’s more, polynomial mutation (PM) is used to the archive set to avoid the premature convergence.

The remainder of this paper is organized as follows. Section 2 provides the background and related work for understanding the rest of the paper. Section 3 explains the proposed approach in detail. In Section 4, the results is shown of comparative study. Finally, Section 5 provides the conclusions and some possible paths for future work.

2 Background and related work

2.1 Multi-objective optimization

Without loss of generality, a continuous or unconstrained multi-objective optimization problem can be described as follows:

$\begin{matrix} \min F (x) = (f_{1} (x), f_{2} (x), . . ., f_{m} (x))^{T} \\ s . t . x \in Ω^{D} \end{matrix}$ (1) where x = (x¹, x², . . . , x^D) is one of the solutions with D-dimensional decision variables in the decision space Ω^D, x = (x₁, x₂, . . . x_N) ^T and N is the scale of the solution set. m is the number of objective functions and the mapping function F: Ω^D → R^m defines m objective functions in the objective space R^m.

2.2 Particle swarm optimization

PSO is a metaheuristic which aims to deal with continuous and unconstrained nonlinear optimization problems. PSO simulates the movements of a flock of birds to find food. In PSO, a particle is expressed by a solution x_i ∈ Ω^D, i = 1, 2, . . . , N. A population can be defined by one swarm with N particles. The swarm is evolved by updating both the velocity v^t+1 and the position of each particle x^t+1. The velocity of each particle is updated by the following equation:

$\begin{matrix} v_{i}^{d} (t + 1) & = & {wv}_{i}^{d} (t) + c_{1} \cdot rand ({pbest}_{i}^{d} - x_{i}^{d} (t)) \\ + c_{2} \cdot rand ({gbest}^{d} - x_{i}^{d} (t)) \end{matrix}$ (2) and the iteration of each particle position is updated according to the following equation: $x_{i}^{d} (t + 1) = x_{i}^{d} (t) + v_{i}^{d} (t + 1)$ (3) where ${pbest}_{i}^{d}$ and gbest^d (d = 1, 2, . . . , D) are the personal best of the i-th particle and the global best performance respectively; t is iteration number, w is the inertia weight, c₁ and c₂ are two learning factors, r₁ and r₂ are two random value generated uniformly in the range [0,1].

2.3 Decomposition approach

Zhang [27] proposed a multi-objective algorithm based on decomposition, which transforms a MOP into a series of SOPs. In [13], the results show that different decomposition methods produce great influence on the performance of algorithm.

After considering the characteristics of each decomposition method, C-DMOPSO adopts Tchebycheff decomposition method. The optimal solutions of the aggregate function is the Pareto optimal solutions of MOPs, and the corresponding aggregate function formula is as follows:

$\begin{matrix} \min g^{te} (x ∣ λ, z^{*}) = max_{1 \leq i \leq m} {λ_{i} | f_{i} (x) - z_{i}^{*} |} \\ s . t . x \in Ω^{D} \end{matrix}$ (4) where $z^{*} = (z_{1}^{*}, z_{2}^{*}, . . ., z_{m}^{*})^{T}$ is reference point, $z_{i}^{*} = \min {f_{i} (x) ∣ x \in Ω^{D}}$ , i = 1, 2, . . . , m, λ_i is equal to the weight vector w_i corresponding to the i-th subproblem.

3 Improved multi-objective decomposition particle swarm optimization

The proposed C-DMOPSO algorithm combines the dominance and decomposition approach. The former is used to provide selection pressure in updating and maintenance of archive, while the latter transforms MOPs into a set of scalar aggregation problems. In order to make clear of C-DMOPSO, it consist of four parts, i.e. an update mode based on completion-checking factor, population evolution strategy, updating and maintenance of archive. In the following paragraphs, the implementation details of each component in C-DMOPSO will be explained step-by-step.

3.1 Dynamic update mode based on completion-checking factor

The iterative formula is the fundamental driving force for the stepwise optimization of the swarm. In the standard PSO, the speed and position of the child particles are determined according to Equations (2) and (3) in each generation, then the individual optimum and global optimum are updated gradually. In the updating process, the particles need to make better use of the current generation and historical information in order to speed up the convergence rate of the algorithm. Many literatures make further research on the velocity formula [15], and proposes different improvement methods to help the particles choose the next flight mode. Considering the characteristics of particle’s flight, this paper proposes a completion-checking factor ξ to help the particle select the information they needed to update their velocity.

Adaptation mechanism of evolutionary operator should be used to solve searching issue during different stages in evolutionary process [10]. In evolutionary process, the number of non-dominated solutions are augmented with the iterations increasing. The completion-checking factor ξ is determined by the size of non-dominated solutions in current archive set. When dealing with complex problems, the number of non-dominated solutions is very scant at the beginning of the algorithm, so the exploration is needed to augment the number of non-dominated solutions as quickly as possible. When the number of non-dominated solutions reaches a certain extent, it will be considered that the completion degree is better and the corresponding ξ is bigger. At this point, the global excellent information is needed to guide the next flight of particles during the updating of the particles. In addition, in order to avoid falling into local optimum and losing diversity, favorable perturbation from the archive set is imposed in particles’ flight. According to above idea, the particle’s update mode of velocity is proposed in Algorithm 1:

Algorithm 1 Update mode of velocity

Input: v_i (t)

Output: v_i (t + 1)

1: for each particle in POP do

2: if ξ_now < ξ

3: $v_{i}^{d} (t + 1) = {wv}_{i}^{d} (t) + c_{1} rand ({pbest}_{i}^{d} - x_{i}^{d} (t))$

4: else

5: if rand < ms,

6: $v_{i}^{d} (t + 1) = {wv}_{i}^{d} (t) + c_{1} rand ({pbest}_{i}^{d} - x_{i}^{d} (t)) + c_{2} rand ({gbest}^{d} - x_{i}^{d} (t))$

7: else

8: $v_{i}^{d} (t + 1) = c_{2} rand ({gbest}^{d} - x_{i}^{d} (t)) + c_{3} rand ({arch}_{g}^{d} - x_{i}^{d} (t))$

9: end

10: end

11: end for

In Algorithm 1, $w = w_{start} - \frac{t_{\max} - t}{t_{\max}} (w_{start} - w_{end})$ is decreasing linearly; $ξ_{now} = \frac{size_arch}{N}$ , where size _ arch is the size of the current archive set; c₃ is the learning factor of perturbation and ${arch}_{g}^{d}$ is a random particle in archive; mode selection factor ms = 0.3 empirically; $ξ = ξ_{start} + \frac{t_{\max} - t}{t_{\max}} (ξ_{end} - ξ_{start})$ is a self-adaptive parameter in the algorithmic process, ξ_start = 0.5 and ξ_end = 1 and it indicates that the number of non-dominated solutions is becoming more and more with the number of iterations increasing.

At the beginning of the iteration, the number of non-dominated solutions is small with a small value of ξ, and the search pattern of the population are supposed to focus on the exploration. Namely, the individual history optimum is used to guide the particles’ flight. With the iterations increasing, the number of non-dominated solutions are increasing quickly to make the population close to the real Pareto front. By this time, the value of ξ increases gradually. In this case, the searching pattern should be changed to local search, that is, the global optimal guide the particles’ flight. Besides, the perturbation term is added to make the particles jump out of the local optimum in order to avoid premature convergence.

In addition, ξ also determines the neighborhood size of the particles, and T (t) = ξ * T (t - 1). When ξ is small, the neighborhood size is large, so that the neighborhood is used to find the global optimum. While, the neighborhood size decreases with a large ξ, then the population change to local search to approximate the optimal front at this point.

3.2 Population evolution strategy

3.2.1 Crossing and opposition-based learning operator

For the complex Pareto front, the population often tends to fall into local optimum during the iterative process. In order to make better use of the information in each generation, SBX [14] is adopted in C-DMOPSO to assist in generating offspring particles.

Besides, OBL is a strategy from machine intelligence which has been proven to be an effective technique on PSO [28]. It generates a reverse solution which is far from the local optimal to guide the population out of the local optimum region and the searching range is extended to facilitate the global optimum.

A parent particle intersects with a offspring particle to produce two new particles. Between two new particles, a particle is randomly selected for executing subsequent OBL operator. The pseudocode is listed in Algorithm 2.

Algorithm 2 Crossing and opposition-based learning operator

Input: POP

Output: X _new

1: X = POP

2: for i = 1 to N do

3: Generate a random integer j in [1, N];

4: $[{new}_{1}, {new}_{2}] = SBX (X_{i}^{t} . X_{i}^{t - 1});$

5: Generate a random integer k in [1, 2];

6: X_inew = OBL (new_k);

7: end for

3.2.2 Re-initialize the particles

In order to speed up convergence of the algorithm, the re-initialization strategy is adopted [25]. If the particle does not improve its individual optimum during the flight, its age is increased by one. When the particle’s age reaches the maximum age predefined, the position of the particle is re-initialized. The individual optimum and global optimum of the current generation is utilized with the Gaussian distribution, which makes the particle fly to the favorable direction. The formula is shown in Equation (5). $x_{i}^{d} (t + 1) = N (m, σ)$ (5) where $m = 0.5 * ({gbest}_{i}^{d} (t) - {pbest}_{i}^{d} (t))$ and $σ = | {gbest}_{i}^{d} (t) - {pbest}_{i}^{d} (t) |$ , N (m, σ) represents a random number using a normal distribution with mean m and sigma σ.

3.2.3 Update mechanism of pbest and gbest

In PSO, a particle is an independent agent which can search the objective space according to the experience of its own and its companions. Both pbest and gbest play key roles in guiding the search of particles. Therefore, how to choose pbest and gbest is a key problem when designing a MOPSO algorithm.

On the one hand, the pbest of a particle needs to be updated to make better use of its personal knowledge. As shown in Fig. 1, the curve represents a true Pareto front. In the event that there are too many particles in swarm, A will be removed based on the dominance method because D dominates A. However, it is apparent that A is a useful particle because it locates a relatively sparse area. The diversity may be lost if the algorithm updates the pbest under the dominance mechanism. As a consequence, different from other algorithms, the decomposition method is adopted in C-DMOPSO instead of non-dominated sorting, which uniformly generate N vectors in the target space. The particle swarm is divided into N subproblems, and the particles are updated step by step under the direction vector.

Fig.1

Illustration of why not use dominance mechanism to update pbest.

The individual optimal value of the particle plays a guiding role in the exploration of the whole population. For the updating of pbest, the Tchebycheff approach is adopted in C-DMOPSO to construct the aggregate function. In the ideal state, the individual optimal value of any particle in the population is updated as shown in Fig. 2(a). In the figure, the dotted line represents the direction vector in the target space, the real curve represents the real front of the function, and the hollow dots are the particles in the existing population. In the process of pbest updating, A is the position of the particle at the last generation, B is the position of this particle current generation, and C is the position of this particle’s individual optimum is to run next generation. The particle is updated along the direction vector of the corresponding subproblem in each generation, the individual optimal value is updated when the aggregate function of the offspring particle is better than the original individual optimal value at this direction vector. Otherwise, the original individual optimal value unchanged. The pseudocode is listed in Algorithm 3.

Algorithm 3 Update for pbest

Input: pbest (t - 1)

Output: pbest (t)

1: for i = 1 to N do

2: if g^te (x_i|λ_i, z^*) > g^te (pbest_i|λ_i, z^*)

3: pbest_i = x_i

4: age_i = 0

5: else

6: age_i = age_i + 1

7: end if

8: end for

On the other hand, the global best of particles is used to guide exploitation of particles. The information of neighborhood particles is used to update the gbest of particles. The updating trajectory of global optimal value of a particle within the population is shown in Fig. 2(b). In the process of gbest updating, A is the position of the gbest at the last generation, B is the position of gbest current generation, and C is the position of the gbest is to run next generation. The gbest are updated by the optimal information of the corresponding neighborhood particles. Unlike the SOP, the gbest of a MOP is not a particle, but the optimal particle with N particles in the corresponding neighborhood region. And their fitness is not a value, but a Pareto approximation front.

Fig.2

Update pbest and gbest.

3.3 Update and maintenance of archive

The selection of the archive set: in order to distinguish good solutions from the whole population, an archive set is selected to record the information of the elite particles in population according to the idea of dominance relation. Most of the existing literatures [1, 15] choose the non-dominated solutions of each generation population to join the archive set. In this paper, the selection of elite particles obeys the following rules: the pbest and gbest of the population are sorted by the dominance relation after each iteration, only the first front’s particles are selected as the elite particles to add the archive set.

The maintenance of the archive set: as the increase of the iteration, the number of non-dominated solutions is increasing. Hence, the crowding distance strategy is used to maintain the archive scale. When the archive set exceed the predetermined scale, the crowding distance between the particles is calculated, and the particles with the smallest crowding distance are removed. The above steps are repeated until the archive size is maintained at the predetermined value.

Archive set variation: premature convergence phenomenon often emerged in PSO when it updates to a certain extent when dealing with complex problems. In order to jump out of premature convergence and improve the diversity, polynomial mutation(PM) [3] is imposed on the archive.

Algorithm 4 lists the pseudocode of updating and maintenance of archive.

Algorithm 4 Archive update

Input: archive (t - 1)

Output: archive (t)

1: for i = 1 to |archive| do

2: archive_i = PM (archive_i)

3: end for

4: while |archive| > ARCH do

5: Execute non-dominated sorting on archive;

6: Calculate the crowding distance d_i for each particle in archive;

7: Remove the archive_i with d_min;

8: end while

Algorithm 5 C-DMOPSO

Input: N, FE, parameters

Output: archive

1: Part1: Initialization

2: Initialize velocity and position of the population;

3: Set pbest = gbest = POP and archive = Φ;

4: Initialize the reference point $z^{*} = (z_{1}^{*}, z_{2}^{*}, . . ., z_{m}^{*})$ , $z_{j}^{*} = \min f_{j} (x)$ and j = 1, . . . , m;

5: Initialize the N weight vectors and the particle neighborhood;

6: Part2: Iteration and Update

7: while evaluation <FEs do

8: for i = 1 to N do

9: if age_i < age_max

10: Update the particle according to Algorithm 1 and Eq.(3)

11: else

12: Re-initialized the particles according to Eq.(5)

13: end if

14: end for

15: Execute Algorithm 2 of population evolution strategy;

16: Calculate the fitness and update the z^*;

17: Update the pbest according to Algorithm 3;

18: Update the gbest according to the neighborhood information;

19: archive = archive ⋃ pbest ⋃ gbest, execute Algorithm 4;

20: end while

21: Return the final result in the archive.

3.4 The complete C-DMOPSO algorithm

The above subsections have described the procedures of velocity updating mode, evolution strategy, the updating and maintenance of archive, which compose the main components of C-DMOPSO. The complete C-DMOPSO algorithm is illustrated in Algorithm 5, where N is the size of population and archive, evaluation refers to the number of function evaluations, and FEs represents the maximum number of function evaluations.

4 Experimental results

In order to assess the performance of the proposed approach, the results of C-DMOPSO are compared with respect to those obtained by MOEA/D [27], dMOPSO [25], NSGAII [6], MOPSO [5] and a newly-proposed algorithm MIMOPSO [24].

4.1 Test instances

Nineteen test problems are adopted to estimate the performance of algorithms, whose Pareto fronts have different characteristics including convexity, concavity, connection, disconnection and multi-modality. They are two-objective test suites of Zitzler-Deb Thiele(ZDT), three-objective problems of Deb-Thiele-Laumanns Zitzler(DTLZ) and CEC’09 benchmark problems(UF1-UF10). There are 30 decision variables for ZDT1-ZDT3 and UF1-UF10. ZDT6 is tested using 10 decision variables. For DTLZ2 and DTLZ4, 12 variables are adopted. DTLZ1 and DTLZ7 are tested with 7 and 22 decision variables respectively.

4.2 Experimental settings

The parameters of C-DMOPSO are as follows: inertia weight w_start = 0.9, w_end = 0.4, learning factors c₁ = c₂ = c₃ = 1.5; neighborhood size T = 20, crossover probability pc = 0.5, mutation probability pm = 0.05, distribution index η_c = η_m = 20; agemax = 2.

ZDT: m = 2, N = 100, FEs = 30000; DTLZ: m = 3, N = 210, FEs = 210000; UF: N = 300, FEs = 300000. For each test function, all the algorithms run 30 times independently.

Parameter settings of all compared algorithms are shown in Table 1.

Table 1
Parameter settings of all compared algorithms

Algorithm Parameter settings

MOEA/D T = 20, pc = 0.5, pm = 1/n, η_c = η_m = 20

dMOPSO T = 20, age_max = 2

NSGAII pc = 0.9, pm = 1/n, η_c = η_m = 20

MOPSO mutation rate=0.5, N_grid = 30

MIMOPSO MR = 0.5, α = 0.5

Algorithm	Parameter settings
MOEA/D	T = 20, pc = 0.5, pm = 1/n, η_c = η_m = 20
dMOPSO	T = 20, age_max = 2
NSGAII	pc = 0.9, pm = 1/n, η_c = η_m = 20
MOPSO	mutation rate=0.5, N_grid = 30
MIMOPSO	MR = 0.5, α = 0.5

4.3 Performance measure

The inverse generation distance(IGD) [18] can measure both convergence and diversity of an algorithm. The lower the value, the better the convergence and diversity of the Pareto solution set, namely the approximate Pareto front of C-DMOPSO gained are closed to the true Pareto front. Let P be a proper representation of the true Pareto front, the IGD for a set of approximated solutions P′ is calculated as: $IGD = \frac{\sum_{i = 1}^{| P |} d (p_{i}, P^{'})}{| P |}$ (6) where d (p_i, P′) is a minimum distance between p_i and any point in P′ and |P| is the scale of P.

4.4 Discussion of results

In order to verify the validity of the proposed algorithm, five kinds of contrastive algorithms are selected: MOEA/D, dMOPSO, NSGAII, MOPSO and MIMOPSO. Furthermore, for the purpose of testing the validity of the updating mode based on completion-checking factor, the algorithm with the original velocity formula is compared with C-DMOPSO as well. Tables 2 and 3 show the mean and standard deviation(std) of the IGD performance metrics for seven algorithms, where C-D refers to C-DMOPSO and C-D1 represents the algorithm with the original velocity formula. In these tables, the best results of the mean or standard deviation for each test function are identified with bold font. In addition, the p-value(p) of Wilcoxsom rank sum test with significant level α = 0.05 are also recorded for each function, which examine that whether the IGD mean values obtained by C-DMOPSO are different from that obtained by the other algorithms statistically. Namely, when p-value is bigger than 0.05, it means that the compared IGD mean values are similar in statistics. The bold italics in tables show that there is no significant difference between C-DMOPSO and the contrastive algorithm in the corresponding test function under the Wilcoxsom rank sum test. The better/similar/worse (+/=/-) show that C-DMOPSO is superior to, similar to, and inferior to the number of the comparison algorithm on all test functions in table.

Table 2
IGD values on ZDT and DTLZ

C-D C-D1 MOEA/D dMOPSO NSGAII MOPSO MIMOPSO

ZDT1 mean 3.903E-03 3.910E-03 7.544E-03 3.899E-03 4.929E-03 1.817E-02 4.041E-03

std 6.180E-05 5.238E-05 8.473E-04 3.839E-05 2.043E-04 3.243E-03 4.758E-05

p-value 6.627E-01 8.534E-01 3.016E-11 3.016E-11 3.016E-11 4.195E-10

ZDT2 mean 3.990E-03 1.545E-02 2.503E-02 6.442E-02 4.900E-03 1.923E-02 4.032E-03

std 6.195E-05 4.308E-02 1.104E-01 1.849E-01 2.074E-04 3.412E-03 4.462E-05

p-value 1.564E-02 1.065E-07 6.669E-03 3.020E-11 3.020E-11 6.913E-04

ZDT3 mean 4.442E-03 4.466E-03 1.212E-02 1.064E-02 7.254E-03 2.425E-02 4.673E-03

std 1.993E-04 2.004E-04 5.585E-03 7.098E-04 7.634E-03 5.872E-03 1.649E-04

p-value 7.506E-01 3.020E-11 3.020E-11 3.020E-11 9.919E-11 1.248E-04

ZDT4 mean 4.914E-03 7.425E-03 2.452E-01 5.972E+00 8.420E-03 3.804E+01 5.211E-03

std 1.843E-04 1.108E-03 1.571E-01 4.477E+00 2.731E-03 7.686E+00 4.117E-04

p-value 3.886E-09 4.127E-11 4.462E-11 4.462E-11 5.338E-10 1.931E-03

ZDT6 mean 2.372E-03 2.488E-03 1.892E-03 1.879E-03 2.696E-03 1.059E-02 2.431E-03

std 9.613E-05 2.123E-05 1.179E-05 8.549E-06 4.111E-05 3.589E-03 8.340E-05

p-value 1.171E-02 3.020E-11 3.338E-11 3.020E-11 1.286E-06 1.076E-02

DTLZ1 mean 3.572E-02 3.349E-02 1.842E-02 1.529E+01 1.935E-02 8.220E+00 1.988E-02

std 9.425E-03 1.041E-02 4.773E-04 1.180E+01 6.011E-04 2.307E+00 1.566E-03

p-value 5.298E-01 3.020E-11 3.020E-11 3.020E-11 3.020E-11 4.975E-11

DTLZ2 mean 4.289E-02 4.335E-02 4.597E-02 4.716E-02 5.315E-02 7.542E-02 4.294E-02

std 1.171E-03 1.124E-03 1.218E-03 1.489E-03 2.373E-03 3.010E-03 2.293E-03

p-value 1.494E-01 8.993E-11 1.070E-09 3.020E-11 3.020E-11 9.705E-01

DTLZ4 mean 1.263E-01 1.308E-01 5.160E-02 1.175E-01 5.417E-02 1.852E-01 4.756E-02

std 1.282E-01 1.287E-01 1.948E-03 7.627E-02 1.727E-03 3.196E-02 1.551E-03

p-value 3.329E-01 2.499E-03 1.297E-01 1.953E-03 1.221E-02 1.501E-02

DTLZ7 mean 5.058E-02 5.090E-02 1.271E-01 1.265E-01 7.129E-02 5.327E-02 5.161E-02

std 2.252E-03 1.957E-03 5.106E-03 6.728E-03 5.101E-02 1.862E-03 1.444E-03

p-value 3.183E-01 3.020E-11 3.020E-11 1.167E-05 3.338E-11 4.727E-02

+/=/- 3/6/0 5/1/3 6/1/2 7/0/2 9/0/0 6/1/2

		C-D	C-D1	MOEA/D	dMOPSO	NSGAII	MOPSO	MIMOPSO
ZDT1	mean	3.903E-03	3.910E-03	7.544E-03	3.899E-03	4.929E-03	1.817E-02	4.041E-03
	std	6.180E-05	5.238E-05	8.473E-04	3.839E-05	2.043E-04	3.243E-03	4.758E-05
	p-value		6.627E-01	8.534E-01	3.016E-11	3.016E-11	3.016E-11	4.195E-10
ZDT2	mean	3.990E-03	1.545E-02	2.503E-02	6.442E-02	4.900E-03	1.923E-02	4.032E-03
	std	6.195E-05	4.308E-02	1.104E-01	1.849E-01	2.074E-04	3.412E-03	4.462E-05
	p-value		1.564E-02	1.065E-07	6.669E-03	3.020E-11	3.020E-11	6.913E-04
ZDT3	mean	4.442E-03	4.466E-03	1.212E-02	1.064E-02	7.254E-03	2.425E-02	4.673E-03
	std	1.993E-04	2.004E-04	5.585E-03	7.098E-04	7.634E-03	5.872E-03	1.649E-04
	p-value		7.506E-01	3.020E-11	3.020E-11	3.020E-11	9.919E-11	1.248E-04
ZDT4	mean	4.914E-03	7.425E-03	2.452E-01	5.972E+00	8.420E-03	3.804E+01	5.211E-03
	std	1.843E-04	1.108E-03	1.571E-01	4.477E+00	2.731E-03	7.686E+00	4.117E-04
	p-value		3.886E-09	4.127E-11	4.462E-11	4.462E-11	5.338E-10	1.931E-03
ZDT6	mean	2.372E-03	2.488E-03	1.892E-03	1.879E-03	2.696E-03	1.059E-02	2.431E-03
	std	9.613E-05	2.123E-05	1.179E-05	8.549E-06	4.111E-05	3.589E-03	8.340E-05
	p-value		1.171E-02	3.020E-11	3.338E-11	3.020E-11	1.286E-06	1.076E-02
DTLZ1	mean	3.572E-02	3.349E-02	1.842E-02	1.529E+01	1.935E-02	8.220E+00	1.988E-02
	std	9.425E-03	1.041E-02	4.773E-04	1.180E+01	6.011E-04	2.307E+00	1.566E-03
	p-value		5.298E-01	3.020E-11	3.020E-11	3.020E-11	3.020E-11	4.975E-11
DTLZ2	mean	4.289E-02	4.335E-02	4.597E-02	4.716E-02	5.315E-02	7.542E-02	4.294E-02
	std	1.171E-03	1.124E-03	1.218E-03	1.489E-03	2.373E-03	3.010E-03	2.293E-03
	p-value		1.494E-01	8.993E-11	1.070E-09	3.020E-11	3.020E-11	9.705E-01
DTLZ4	mean	1.263E-01	1.308E-01	5.160E-02	1.175E-01	5.417E-02	1.852E-01	4.756E-02
	std	1.282E-01	1.287E-01	1.948E-03	7.627E-02	1.727E-03	3.196E-02	1.551E-03
	p-value		3.329E-01	2.499E-03	1.297E-01	1.953E-03	1.221E-02	1.501E-02
DTLZ7	mean	5.058E-02	5.090E-02	1.271E-01	1.265E-01	7.129E-02	5.327E-02	5.161E-02
	std	2.252E-03	1.957E-03	5.106E-03	6.728E-03	5.101E-02	1.862E-03	1.444E-03
	p-value		3.183E-01	3.020E-11	3.020E-11	1.167E-05	3.338E-11	4.727E-02
+/=/-		3/6/0	5/1/3	6/1/2	7/0/2	9/0/0	6/1/2

Table 3

IGD values on UF

		C-D	C-D1	MOEA/D	dMOPSO	NSGAII	MOPSO	MIMOPSO
UF1	mean	5.197E-02	8.502E-02	8.155E-02	9.159E-02	8.653E-02	1.563E-01	5.602E-02
	std	1.199E-02	1.090E-02	3.326E-02	1.151E-02	2.873E-02	2.069E-02	1.904E-02
	p-value		5.573E-10	8.153E-11	1.868E-05	3.020E-11	2.572E-07	9.823E-03
UF2	mean	2.773E-02	2.798E-02	2.821E-02	4.729E-02	2.828E-02	1.090E-01	1.735E-02
	std	2.882E-03	3.644E-03	5.200E-03	8.118E-03	8.947E-03	7.463E-03	1.267E-03
	p-value		8.883E-01	3.020E-11	8.883E-01	3.020E-11	1.907E-01	3.020E-11
UF3	mean	3.001E-01	3.059E-01	4.724E-01	5.012E-01	2.367E-01	5.934E-01	8.632E-02
	std	2.328E-02	3.614E-02	7.183E-02	2.563E-01	8.829E-02	1.454E-01	1.907E-02
	p-value		9.941E-01	1.947E-03	4.504E-11	3.020E-11	5.084E-03	3.020E-11
UF4	mean	4.754E-02	5.362E-02	6.793E-02	9.213E-02	5.173E-02	5.865E-02	5.362E-02
	std	1.025E-03	6.945E-04	3.347E-03	4.959E-03	1.771E-03	2.887E-03	9.996E-04
	p-value		3.020E-11	3.020E-11	3.020E-11	3.474E-10	3.835E-06	3.020E-11
UF5	mean	7.118E-01	7.649E-01	4.526E-01	7.095E-01	3.233E-01	1.888E+00	4.568E-01
	std	8.324E-02	9.081E-02	1.281E-01	1.731E-01	1.159E-01	1.506E-01	9.561E-02
	p-value		2.324E-02	3.711E-01	4.200E-10	3.020E-11	3.020E-11	5.494E-11
UF6	mean	4.293E-01	4.397E-01	5.271E-01	4.394E-01	3.690E-01	1.801E+00	4.800E-01
	std	5.445E-02	3.271E-02	1.828E-01	2.098E-01	1.334E-01	1.781E-01	1.542E-01
	p-value		2.068E-02	1.624E-01	9.883E-03	3.020E-11	2.891E-03	6.414E-01
UF7	mean	3.356E-02	4.634E-02	2.704E-01	1.372E-01	1.478E-01	1.203E-01	5.152E-02
	std	3.766E-03	5.323E-03	1.901E-01	1.296E-01	1.576E-01	2.581E-02	6.780E-02
	p-value		8.101E-10	1.957E-10	5.561E-04	3.020E-11	9.234E-01	3.644E-02
UF8	mean	1.852E-01	3.340E-01	1.170E-01	1.968E-01	1.601E-01	3.082E-01	1.920E-01
	std	5.470E-03	3.340E-02	1.198E-01	3.136E-02	4.457E-02	2.122E-02	1.708E-02
	p-value		3.020E-11	1.911E-02	6.722E-10	3.020E-11	4.444E-07	2.581E-01
UF9	mean	9.889E-02	1.054E-01	1.434E-01	1.142E-01	2.425E-01	3.814E-01	1.109E-01
	std	4.295E-02	2.002E-02	5.087E-02	2.881E-02	8.280E-02	2.009E-02	8.222E-02
	p-value		1.076E-02	4.119E-01	7.959E-03	3.020E-11	3.020E-11	4.033E-03
UF10	mean	1.745E-01	1.023E+00	5.945E-01	1.011E+00	7.823E-01	3.756E+00	1.771E-01
	std	7.945E-04	1.100E-01	2.187E-01	1.742E-01	1.550E-01	3.165E-01	2.928E-03
	p-value		1.720E-12	1.102E-11	3.020E-11	3.020E-11	3.020E-11	1.748E-05
+/=/-			8/2/0	6/3/1	8/1/1	6/0/4	8/2/0	5/2/3
total			11/8/0	11/4/4	14/2/3	13/0/6	17/2/0	11/3/5

As shown in Table 2 and Fig. 3, C-DMOPSO produces a better diversity along the Pareto front on ZDT functions except ZDT6. However, the differences between C-DMOPSO and dMOPSO in the IGD values obtained are not significant on ZDT6. ZDT4 has many local Pareto fronts, while C-DMOPSO attains a better diversity compares with other five algorithms except MIMOPSO. Meanwhile, Fig. 4 indicates that C-DMOPSO also gains good distribution along the Pareto front on DTLZ problems. But on DTLZ1, C-DMOPSO performs slightly worse than MOEA/D, NSGAII and MIMOPSO. On DTLZ4, the performance of C-DMOPSO is poor and with low std value, which because there are some bad IGD value during 30 times running. It is obvious that C-DMOPSO is better than dMOPSO in 6 test functions and only worse than it on ZDT6. C-DMOPSO is significantly better than MOPSO on all 9 test problems.

Fig.3

Pareto front of C-DMOPSO, MOEA/D, dMOPSO, NSGAII, MIMOPSO on ZDT3 and ZDT4. (a)-(f) represent the compare algorithms on ZDT3 and (g)-(l) represent the compare algorithms on ZDT4.

Fig.4

Pareto front of C-DMOPSO, MOEA/D, dMOPSO, NSGAII, MIMOPSO on DTLZ1, DTLZ4 and DTLZ7, (a)-(f) represent the compare algorithms on DTLZ1, (g)-(l) represent the compare algorithms on DTLZ4, and (m)-(r) represent the compare algorithms on DTLZ7.

As can be seen in Table 3, C-DMOPSO obtains weak performance than NSGAII on UF5 and UF6 in terms of reducing IGD value. In fact, UF5 has 21 local Pareto fronts which may impede the convergence ability of C-DMOPSO, while UF6 has one isolated point and two disconnected parts which may cause difficulty in finding a good diverse set of solutions. The permissible function evaluations might not be good enough to deal with such complicated problems. In summary, the results show that the overall IGD value obtained by the proposed algorithm is superior to the other six contrast algorithms on most of the nineteen test problems. According to no free lunch theory, we can not expect the proposed algorithm is better than the contrast algorithm on each function. C-DMOPSO gains good values on most of test problems compared with C-D1, which indicates that the update mode based on completion-checking factor is effective in handling complex MOPs. The final assessment of the nineteen functions is recorded in the last column of Table 3, which verifies that the proposed algorithm outperformed among MOEA/D, dMOPSO, NSGAII, MOPSO and MIMOPSO in most of the functions with respect to the IGD.

Figures 3, 4 and 5 show the approximate Pareto fronts obtained by C-DMOPSO, MOEA/D, dMOPSO, NSGAII, MOPSO and MIMOPSO in some test problems with clearer discrimination. It can be seen that C-DMOPSO produces better approximated PF on ZDT, DTLZ, and most UF test instances in these figures which demonstrate the good distributivity of C-DMOPSO.

Fig.5

Pareto front of C-DMOPSO, MOEA/D, dMOPSO, NSGAII, MIMOPSO on UF1, UF7 and UF9, (a)-(f) represent the compare algorithms on UF1, (g)-(l) represent the compare algorithms on UF7, and (m)-(r) represent the compare algorithms on UF9.

To compare the convergence speed of the six algorithm, the trends in the IGD of the algorithms on some test functions with significant differences are depicted in Fig. 6, which indicates that C-DMOPSO gains a good convergence. In these figures, the x-coordinate is the number of function evaluations, while it’s noted that the y-coordinate is log (IGD) for ease of observing expediently. It is discovered from Fig. 6 that C-DMOPSO performs better than other algorithms on most of the test problems during the whole evolutionary process. For ZDT functions, C-DMOPSO gains the fastest convergence rate. DTLZ1 is a multi-modal function, which may weaken the convergence of algorithm. This is the reason for the slow convergence of the algorithms on DTLZ1. For complicated test problems, C-DMOPSO performs well except for UF2.

Fig.6

Variation of IGD metric value.

In conclusion, it is not difficult to find that the solutions obtained by C-DMOPSO receive a good distribution on the Pareto front and a good convergence speed during evolutionary process. Besides, C-DMOPSO does well in handling discontinuous MOPs which benefit from the searching mechanism randomly of PSO. All of these results indicate the improvement of convergence and diversity, which claim great potential of C-DMOPSO to deal with MOPs.

5 Conclusions and future work

In this paper, an improved decomposition multi-objective particle swarm optimization algorithm based on completion-checking factor is proposed. In the updating process of particle swarm, the velocity update pattern and the size of neighborhood are determined by the completion-checking factor, which change the search pattern of the particle and improve the population convergence speed. In addition, SBX and OBL are added to enhance the global search ability in decision space. Besides, PM is performed on the non-dominated solutions in the archive to improve the diversity. After compared with the other six algorithms, it can be concluded that the C-DMOPSO can obtain better results in most test functions with respect to the IGD performance measure.

C-DMOPSO avoids over-exploration or excessive exploitation and makes a balance between convergence and diversity during evolutionary process. Besides, it combines dominance-based with decomposition-based method effectively. Actually, there is still some challenging and promising research direction on C-DMOPSO. Although the C-DMOPSO algorithm is improved in performance, the setting of parameters cannot be adjusted with the change of environment. As part of our future work, it is necessary to further study the adaptive adjustment of the parameters in C-DMOPSO. Furthermore, C-DMOPSO will be extended to many objectives optimization problems(MaOPs) in our future work.

Footnotes

Acknowledgments

The authors would like to thank the editor and reviewers for their helpful comments and suggestions to improve the quality of this paper. This work was supported by the Natural Science Foundation of Hebei Province (No. F2016203249).

References

Al Moubayed

, Petrovski

and McCall

, D 2 mopso: Mopso based on decomposition and dominance with archiving using crowding distance in objective and solution spaces, Evolutionary Computation 22(1) (2014), 47–77.

Bader

and Zitzler

, Hype: An algorithm for fast hypervolumebased many-objective optimization, Evolutionary Computation 19(1) (2011), 45–76.

Chen

, Lin

and Ji

, A hybrid immune multiobjective optimization algorithm, European Journal of Operational Research 204(2) (2010), 294–302.

Coello

C.A.C.

, Lamont

G.B.

, Van Veldhuizen

D.A.

, et al., Evolutionary algorithms for solving multi-objective problems, vol. 5. Springer, 2007.

Coello

C.A.C.

, Pulido

G.T.

and Lechuga

M.S.

, Handling multiple objectives with particle swarm optimization, IEEE Transactions on Evolutionary Computation 8(3) (2004), 256–279.

Deb

, Pratap

, Agarwal

and Meyarivan

, A fast and elitist multiobjective genetic algorithm: Nsga-ii, IEEE Transactions on Evolutionary Computation 6(2) (2002), 182–197.

Giagkiozis

and Fleming

P.J.

, Methods for multi-objective optimization: An analysis, Information Sciences 293 (2015), 338–350.

Giagkiozis

, Purshouse

R.C.

and Fleming

P.J.

, An overview of population-based algorithms for multi-objective optimisation, International Journal of Systems Science 46(9) (2015), 1572–1599.

Gülcü

Ş.

and Kodaz

, A novel parallel multi-swarm algorithm based on comprehensive learning particle swarm optimization, Engineering Applications of Artificial Intelligence 45 (2015), 33–45.

10.

, Yang

, Sun

, Wei

and Zhao

, An improved multiobjective evolutionary algorithm based on environmental and history information, Neurocomputing 222 (2017), 170–182.

11.

Z.Y.

, Yang

J.M.

, Zhao

Z.W.

, Sun

and Che

H.J.

, Multiobjective optimization of rolling schedules on aluminum hot tandem rolling, The International Journal of Advanced Manufacturing Technology 85(1-4) (2016), 85–97.

12.

Kennedy

and Eberhart

, Particle swarm optimization, In: Neural Networks, 1995 Proceedings, IEEE International Conference on, vol. 4, 1995, pp. 1942–1948. DOI 10.1109/ICNN.1995.488968

13.

Lee

L.H.

, Chew

E.P.

, Yu

, Li

and Liu

, A study on multiobjective particle swarm optimization with weighted scalarizing functions, In: Proceedings of the 2014 Winter Simulation Conference, 2014, pp. 3718–3729. IEEE Press.

14.

Lin

and Chen

, A novel micro-population immune multiobjective optimization algorithm, Computers & Operations Research 40(6) (2013), 1590–1601.

15.

Lin

, Li

, Du

, Chen

and Ming

, A novel multiobjective particle swarm optimization with multiple search strategies, European Journal of Operational Research 247(3) (2015), 732–744.

16.

, Hu

and Bai

, Generalized radial basis function neural network based on an improved dynamic particle swarm optimization and adaboost algorithm, Neurocomputing 152 (2015), 305–315.

17.

Mohammadi-Ivatloo

, Moradi-Dalvand

and Rabiee

, Combined heat and power economic dispatch problem solution using particle swarm optimization with time varying acceleration coefficients, Electric Power Systems Research 95 (2013), 9–18.

18.

Neri

and Cotta

, Memetic algorithms and memetic computing optimization: A literature review, Swarm and Evolutionary Computation 2 (2012), 1–14.

19.

Peng

and Zhang

, A decomposition-based multi-objective particle swarm optimization algorithm for continuous optimization problems, In: Granular Computing, 2008 GrC 2008 IEEE International Conference on, 2008, pp. 534–537. IEEE.

20.

Phan

D.H.

and Suzuki

, R2-ibea: R2 indicator based evolutionary algorithm for multiobjective optimization, In: Evolutionary Computation (CEC), 2013 IEEE Congress on, 2013, pp. 1836–1845. IEEE.

21.

Vasant

, Handbook of Research on Artificial Intelligence Techniques and Algorithms, 2 Volumes, Information Science Reference-Imprint of: IGI Publishing, 2015.

22.

Vasant

P.M.

, Meta-heuristics optimization algorithms in engineering, business, economics, and finance, IGI Global, 2012, pp. 1–42.

23.

Wang

, Tan

and Liu

, Particle swarm optimization algorithm: an overview, Soft Computing (2017), 1–22.

24.

Yang

, Mu

, Haijun

, Ziyu

and Yuhao

, Improved multi-objective particle swarm optimization algorithm based on multiple strategies, Control and Decision 32(3) (2017), 435–442.

25.

Martínez

S.Z.

and Coello Coello

C.A.

, A multi-objective particle swarm optimizer based on decomposition, In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, 2011, pp. 69–76. ACM.

26.

Zhang

, Tang

, Hua

and Guan

, A new particle swarm optimization algorithm with adaptive inertia weight based on bayesian techniques, Applied Soft Computing 28 (2015), 138–149.

27.

Zhang

and Li

, Moea/d: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation 11(6) (2007), 712–731.

28.

Zhou

, Fang

, Wu

, Sun

and Cheng

, An oppositionbased learning competitive particle swarm optimizer, In: Evolutionary Computation (CEC), 2016 IEEE Congress on, 2016, pp. 515–521. IEEE.

29.

Zhu

, Xiao

, Li

J.Q.

, Wang

and Zhang

, Global path planning of wheeled robots using multi-objective memetic algorithms, Integrated Computer-Aided Engineering 22(4) (2015), 387–404.

A novel multi-objective PSO algorithm based on completion-checking

Abstract

Keywords

1 Introduction

2 Background and related work

2.1 Multi-objective optimization

3.1 Dynamic update mode based on completion-checking factor

3.2 Population evolution strategy

3.2.1 Crossing and opposition-based learning operator

3.2.2 Re-initialize the particles

3.4 The complete C-DMOPSO algorithm

4 Experimental results

4.1 Test instances

4.2 Experimental settings

Table 1 Parameter settings of all compared algorithms Algorithm Parameter settings MOEA/D T = 20, pc = 0.5, pm = 1/n, η c = η m = 20 dMOPSO T = 20, age max = 2 NSGAII pc = 0.9, pm = 1/n, η c = η m = 20 MOPSO mutation rate=0.5, N grid = 30 MIMOPSO MR = 0.5, α = 0.5

Footnotes

Acknowledgments

References

Table 1
Parameter settings of all compared algorithms

Algorithm Parameter settings

MOEA/D T = 20, pc = 0.5, pm = 1/n, η_c = η_m = 20

dMOPSO T = 20, age_max = 2

NSGAII pc = 0.9, pm = 1/n, η_c = η_m = 20

MOPSO mutation rate=0.5, N_grid = 30

MIMOPSO MR = 0.5, α = 0.5