Elitism set based particle swarm optimization and its application

Yanxia Sun; Zenghui Wang

doi:10.2991/ijcis.10.1.92

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 10, Issue 1, 2017, Pages 1316 - 1329

Elitism set based particle swarm optimization and its application

Authors

Yanxia Sun¹^,sunyanxia@gmail.com, Zenghui Wang²^,wangz@unisa.ac.za

Received 31 March 2017, Accepted 30 August 2017, Available Online 14 September 2017.

DOI: 10.2991/ijcis.10.1.92 How to use a DOI?
Keywords: Particle swarm optimization; Statistical method; Topology structure; Elitism set
Abstract: Topology plays an important role for Particle Swarm Optimization (PSO) to achieve good optimization performance. It is difficult to find one topology structure for the particles to achieve better optimization performance than the others since the optimization performance not only depends on the searching abilities of the particles, also depends on the type of the optimization problems. Three elitist set based PSO algorithm without using explicit topology structure is proposed in this paper. An elitist set, which is based on the individual best experience, is used to communicate among the particles. Moreover, to avoid the premature of the particles, different statistical methods have been used in these three proposed methods. The performance of the proposed PSOs is compared with the results of the standard PSO 2011 and several PSO with different topologies, and the simulation results and comparisons demonstrate that the proposed PSO with adaptive probabilistic preference can achieve good optimization performance.
Copyright: © 2017, the Authors. Published by Atlantis Press.
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

Many systems need to solve more than one nonlinear optimization problems. However, the analytical methods may be in difficulty in improving the slow convergence and the curse of dimensionality, various bio-inspired optimization algorithms can be good choices. There are two of the most famous swarm intelligence based optimization algorithms, one is the ant colony optimization which was proposed by Dorigo [12]. The other one is particle swarm optimization (PSO) which was proposed by Kennedy and Eberhart [11]. PSO has been widely studied from various perspectives such as in artificial life, social psychology, engineering, computer science and so forth since there are more and more researchers are interested in PSO [14].

The topology of the particle swarm has great effect on the optimization performance. The topology structures of particles have been studied in two general types of neighbourhoods: 1) global best (g_best) and 2) local best (l_best) [4, 5]. In the neighborhood, the particles are attracted to the best solution found by any member of the swarm, and it represents a fully connected network in which each particle has access to the information of all other members in the community as shown in Fig. 1(a) [4]. However, in the case of using the local best approach, each particle has access to the information corresponding to its immediate neighbours, according to a certain swarm topology [4]. These two most common ‘local best’ topologies are the ring topology, in which each particle is connected with two neighbours as shown in Fig. 1(b), and the wheel topology (typical for highly centralized business organizations), in which the individuals are isolated from one another and all the information is communicated to a focal individual as shown in Fig. 1(c) [4].

Kennedy [6] suggested that some versions as shown in Fig. 1 converge fast but may be easily trapped in a local minimum, while others have more chance to find an optimal solution although with slower convergence. Kennedy and Mendes [4, 7] have evaluated all topologies in Fig. 1, as well as the case of random neighbours. In their investigations with a total number of 20 particles, they found that the best performance occurred in a randomly generated neighbourhood with an average size of five particles. The authors also suggested that the Von Neumann configuration may perform better than other topologies including the g_best version. Nevertheless, selecting the most efficient neighbourhood structure, in general, depends on the type of problems. One structure may more effective for certain types of problems, yet has a worse performance for other problems [4]. Recently some PSOs with dynamic topology have been proposed to avoid the problems caused by the fixed topology. In [22], the PSO with dynamic random population topologies has been proposed and the dynamic topologies are determined based on the degree of a particle in the swarm or the average degree of a population. In [23] a fitness-driven edge-changing (FE) topology based PSO was proposed. A PSO with dynamic topology and a conservation of evaluations strategy was proposed in [24]. The performance can be improved if the dynamic topology is used properly [22–24]. However, the topology is still used in the proposed versions of PSO and there may be the similar problems as in the PSO with fixed topology. Hence it would be better to apply the topology free method to the algorithms than those topology structure reliant algorithms.

In this paper, one elitist set based PSO is proposed and the proposed method does not depend on the explicit topology structure. The rest parts of this paper is arranged as follows. Section 2 gives a brief description of PSO. Three elitist set based PSO algorithms are presented in Section 3. Section 4 presents the simulation results and analyses comparing with the standard PSO (SPSO) 2011 [8], which is also using the dynamic/random topology, and PSOs with different topologies. In Section 5, the application of the proposed method has been presented. Finally, the conclusions are presented in Section 6.

2. Brief description of PSO

Generally, the optimisation problems can be abstracted as [2]:

(1)min(g(Xi)), Xi =[xi1,xi2,⋯ xin],

where g(·) denotes the objective function without considering constraints; X_i(t) is the position vector of particle i consisting of n variables. Every candidate solution is called a particle.

The originally proposed PSO works by iteratively searching in a region and is concerned with the best previous success of each particle, the best previous success of the particle swarm, the current position, and the velocity of each particle [2]. The particle updates it velocity and position according to

(2)Vi(t+1)=ωVi(t)+c1R1(Pi−Xi(t))+c2R2(Pg−Xi(t)),

(3)Xi(t+1)=Xi(t)+Vi(t+1),

where Vi=[vi1,vi2,⋯ vin] is the velocity of particle i; Xi =[xi1,xi2,⋯ xin] represents the position of particle i; P_i represents the best previous position of particle i (indicating the best discoveries or previous experience of particle i); P_g represents the best previous position among all particles (indicating the best discovery or previous experience of the social swarm); ω is the inertia weight that controls the impact of the previous velocity of the particle on its current velocity and is sometimes adaptive [10]; R₁ and R₂ are two random weights whose components r1j and r2j (j = 1,2⋯, n,) are chosen uniformly within the interval [0,1] which might not guarantee the convergence of the particle trajectory; c₁ and c₂ are the positive constant parameters. Generally, the value of each component in V_i should be clamped to the range [−v_max, v_max] in order to control excessive roaming of particles outside the search space. In order to compare the performance between the proposed methods with the standard PSO 2011 (SPSO 2011), whose codes are provided by Mahamed Omran [8], and PSOs with different topologies including full connection topology, ring topology and scale free topology. The parameters are set as:

(4)ω=1/2×log(2),

(5)c1=c2=0.5+log(2)

and the swarm sizes is floor(10+2D) for SPSO 2011. Here, log() is the natural logarithm function, and floor() is the round toward the negative infinity function. Moreover, the random topology is used in SPSO 2011 to prevent premature.

3. Elitist set based particle swarm optimization

Although the topology of the particle swarm has great effect on the optimisation performance of PSO, it is difficult to determine which topology is dominant in different topologies since one structure may perform better for certain types of problems, yet worse for other problems. Hence it is necessary to have a topology free particle swarm optimization, which does not depend on specific topology structures, to solve different kinds of optimization problems so no attention is needed for choosing the topology structure for different optimization problems. There are some intelligent optimization algorithms which are not dependent on the explicit topologies such as ant colony optimization algorithm [12], genetic algorithm [16, 17], and so forth. The different topologies of particle swarm optimization provide different communication channels among particles. If the topologies of particles are not used explicit, a certain communication media or channels must be constructed for the information exchange among the particles. In the intelligent optimization algorithms, the elitist set has been used in several algorithms such as genetic algorithm [16, 17], tabu search [18], iterated greedy heuristic [19], and so on, and it is a commonly used strategy for information exchanging purpose among the agents such as genes. If the topology is not be used explicitly for the modified particle swarm optimization, the elitist set can be a good choice to replace the explicit topology. In all the intelligent optimization algorithms, the probabilistic techniques play important roles to achieve good performance and prevent premature of the optimization process. Hence, we can use the elitist set and the proper probabilistic technique to take place of the topology structure of the particle swarm optimization.

3.1. Probabilistic preference and Elitist set based Particle Swarm Optimization (PEPSO)

Among the intelligent optimization algorithms, the ant colony optimization algorithm (ACO) is using the environment as a medium of communication and they exchange information indirectly by depositing pheromones [12] and there is no explicit topology structure in ACO. In this study, we refer to the probabilistic technique of ant colony optimization algorithm to design a new algorithm which can keep the advantages of particle swarm optimization and ant colony optimization algorithm while no explicit topology is needed.

To propose an elitist set based PSO algorithm, some characteristics of ACO can be used, such as using the environment as a medium of communication, the level of pheromone trails indicates the desirability of the future move. There is no pheromone used in PSO; and it is not necessary and proper to directly add pheromone in particle swarm optimization. However, the characteristic of ACO can be utilized by the particles to choose the elitist set instead of the best experience of the particle swarm. An external set can be used to store elitism experiences and this external set is used as the medium of communication among the particles. This set can be used to store the elitists and it can be called elitist set. Here the individual best history best experience makes up the elitist set. The following rules should be considered to determine and use the elitist set:

1)
The members of elitist set are determined by the particles’ individual best experiences as using different topologies of particles to prevent premature and keeping a good distribution in the problem space based on the individual best experiences.
2)
The global best experience must be the member of elitist set and it should have the biggest possibility to be chosen to direct the future move or do contribution to the velocity.
3)
The objective fitness value corresponding to different members of elitist set can be used to determine the desirability of the future move.

Based on the above three rules, the elitist set can be updated at each iteration or every n iterations (n is an integer). In general, we can allow the multiple local best from the same particle from different iterations in the past, but it is difficult to determine the criterions of choosing the multiple local best if the elitist set is from different iterations including the part results. To simplify the choice of the elitist set, we use all particles’ best experiences to construct the elitist set which means the number of the elitist set members is chosen as N, and the elitist set is updated at each iteration. For example, the elitist set is shown in Table 1.

Objective Fitness value	f_e1	f_e2	⋯	f_eN
Problem Variables	xe11	xe21	⋯	xeN1
	xe12	xe22	⋯	xeN2
	⋮	⋮	⋮	⋮
	xe1n	xe2n	⋯	xeNn

Table 1.

Elitist set structure

After the members of elitist set are ranked according to the objective fitness value, one of them should be chosen to replace p_g of equation (2) and the possibility of choosing the ‘p_g’ obeys exponential distribution. The motivation of the exponential distribution is the result about the connectivity distribution of small-world network including the social network: peaks at an average value but decays exponentially [25]. Without loss of generality, in this study, the probabilities with exponential distribution are calculated based on

pj=e1−j∑i=1Ne1−i,

where i is an integer and p_j is the jth best elitist set member. There are other methods to get the exponential distributed possibility based on the similar calculation formula.

To realize the proposed method, the procedure are as follows:

1)
Initialize the PSO parameters.
2)
Calculate the fitness function and set it as the best position of each particle.
3)
Determine the elitist set and re-arrange the members of the elitist set by the ascending order.
4)
All the particles positions are updated according to (2)–(3). Here, Pg of equation (2) is chosen based on Table 1 and the possibility of choosing the ‘Pg’ obeys exponential distribution.
5)
Constraints check: if the position is out of boundary, the position is set to the border value and velocity is set to zero.
6)
Calculate the fitness function for each particle.
7)
Repeat steps 3)-6) until a stopping criterion is met (here the maximum number is used.).

3.2. Probabilistic preference and Elitist set based Particle Swarm Optimization considering the individual two nearest experience neighbours (PEPSO II)

In section 3.1, all the members of the elitist are used to determine the effect of the swarm on the individual particle. Due to the transmissibility of the information based on the elitist set it is not necessary to use all the members of the elitist set and we can only use the two closest neighbours which are determined based on the fitness space. Then two preference probabilities need to be chosen: one is the preferring probability to the individual richer neighbour whose experienced fitness value is just better than the individual; and another is the preferring probability to the individual poorer neighbour whose history fitness value is just less than the individual fitness value. The values of the preferring probability can be easily chosen based on the experiences of the researcher. For example, we always want the preferring probability to the individual richer neighbour to be higher than the preferring probability to the individual poorer neighbour. For example we can set the preferring probability to the individual richer neighbour Prob_R = 0.9 and the preferring probability to the individual poorer neighbour Prob_P = 0.1. It should be noted that

(6)Prob_R+Prob_P=1

due to the fact there are only two possible states which the individual particle will move to. There are two specific cases which should be solved carefully: one is that the individual particle has the best history fitness value among the swarm; and another case is that the individual particle has the worst history fitness value. For the first case, we can choose the individual richer neighbour as itself; and for the second case the best history fitness related the particle is chosen as the ‘poor’ neighbour as the best history fitness value related particle.

3.3. Adaptive Probabilistic preference and Elitist set based Particle Swarm Optimization considering the individual two nearest experience neighbours (APEPSO)

The method proposed in section 3.2 is a simplified method. However, there is still a problem that there is one variable, which is Prob_R or Prob_P, should be determined and the choice of the variable will affect the optimization performance a lot. According the meanings of Prob_R and Prob_P, the Prob_R can be smaller at the beginning stage and it can increase until it reach 1 at the last stage so the particle can avoid the premature at the beginning stage and converge to the global best position at the last stage. When Prob_R = Prob_P = 0.5, the possibilities of the particle move to the ‘rich’ neighbour and the ‘poor’ neighbour are same and it can improve the exploring ability to the new space and the history experience still has effects on the particle movement. At the last stage, it would be better that the particle converges to the best experience of the swarm and Prob_R can be set 1 while Prob_P = 0. Hence we can set the variable be adaptive according to the following formula.

(7)Prob_R=0.5+t*0.5/t_max

4. Experimental Verification and Analysis

To validate the proposed method, we chose some famous benchmarks and compare the proposed method with SPSO 2011 and some PSOs with full connection topology, ring topology and scale free topology. The parameters are set as SPSO 2011 except PSO with scale free topology (the number of particles is chosen as 50 which is used in Ref [26]), and all methods were run for 50 times per function with a maximum number of function evaluations of 20000 for each run. Table 2 lists the benchmark functions.

Function Name	Formulation	Dimension	Initial Range
Rastrigin function	f1(X)=∑i=1D[xi2−10 cos(2πxi)+10]	10	±500
Step function	f2(X)=∑i=1D⌊xi+0.5⌋2	10	±500
Rosenbrock function	f3(X)=∑i=1D[100(xi+1−xi2)2+(xi−1)2]	10	±500
Salomon function	f4=− cos(2π∑i=1Dxi2)+0.1∑i=1Dxi2+1	10	±500
Quartic function	f5(X)=∑i=1D(ixi4)+rand(0,1)	10	±500
Shifted Griewank function	f6(X)=∑i=1Dzi24000−∏i=1Dcos(zii)+1−180 where z_i = x_i − o_i and O = [o₁, o₂,…o₃₀] =[-2.7626840e+002 -1.1911000e+001 -5.7878840e+002 - 2.8764860e+002 -8.4385800e+001 -2.2867530e+002 - 4.5815160e+002 -2.0221450e+002 -1.0586420e+002 - 9.6489800e+001 -3.9574680e+002 -5.7294980e+002 - 2.7036410e+002 -5.6685430e+002 -1.5242040e+002 - 5.8838190e+002 -2.8288920e+002 -4.8888650e+002 - 3.4698170e+002 -4.5304470e+002 -5.0658570e+002 - 4.7599870e+002 -3.6204920e+002 -2.3323670e+002 - 4.9198640e+002 -5.4408980e+002 -7.3445600e+001 - 5.2690110e+002 -5.0225610e+002 -5.3723530e+002];	10	±500
Gear Train	f7(X)=16.931−(y1y2y3y4)2 where Y = ⌊X⌋ and the constraint penalty is f₇(X) + 10⁶ if y_i > 60 or y_i < 12 (i = 1,2,3,4).	4	±500
Rastrigin function	f8(X)=∑i=1D[xi2−10 cos(2πxi)+10]	30	±500
Step function	f9(X)=∑i=1D⌊xi+0.5⌋2	30	±500
Rosenbrock function	f10(X)=∑i=1D[100(xi+1−xi2)2+(xi−1)2]	30	±500
Salomon function	f11=− cos(2π∑i=1Dxi2)+0.1∑i=1Dxi2+1	30	±500
Quartic function	f12(X)=∑i=1D(ixi4)+rand (0,1)	30	±500
Shifted Griewank function	f13(X)=∑i=1Dzi24000−∏i=1Dcos(zii)+1−180 where the variables are same f₆(X).	30	±500

Table 2.

Benchmark functions

Table 3 shows the statistical simulation results. In Table 3, it can be seen that the APEPSO can achieve better optimization performance than other PSOs for almost all the benchmark functions when the dimensions are 10. Moreover, according the Table 3, APEPSO can achieve better optimization performance than PEPSO and PEPSO II, which is caused by the facts that PEPSO is easily premature due to the particles are very possible to be attracted to the best experience of the swarm or the global best experience, and PEPSO II can have good exploring ability but at the end stage it is difficult to be converged to the global best experience due to the fixed preferring probability. However, APEPSO can adaptively change the preferring probability which can make the particles have good global search ability at the beginning stage and have good local search ability around the global best experience at the end of the search process.

Problem	Method	best	Mean	Worst	Std.dev
Rastrigin function f₁	Standard PSO 2011	1.99	7.68	15.19	3.35
	Global PSO	8.95	31.50	85.57	19.90
	Ring PSO	3.97	14.10	33.83	6.62
	Scale free PSO	1.99	8.62	21.89	4.30
	PEPSO	1.98	10.01	54.72	7.87
	PEPSO II	1.99	6.89	15.94	3.52
	APEPSO	0.99	7.17	17.10	3.47
Step f₂	Standard PSO 2011	0	0.02	1	0.14
	Global PSO	0	37.40	1453	205.60
	Ring PSO	0	0	0	0
	Scale free PSO	0	0	0	0
	PEPSO	0	0.46	4	0.78
	PEPSO II	0	0.06	1	0.23
	APEPSO	0	0	0	0
Rosenbrock function f₃	Standard PSO 2011	0.0198	118.6752	1.6093e+003	277.7117
	Global PSO	1.5354	183.3550	2705.6	534.8952
	Ring PSO	0.0956	68.5896	1.2178e+003	197.9942
	Scale free PSO	0.0029	91.5759	887.2938	198.2804
	PEPSO	0.01	119.04	1.4581e+003	313.36
	PEPSO II	0.01	70.04	749.21	159.56
	APEPSO	0.008	14.6994	268.5352	40.71
Salomon f₄	Standard PSO 2011	0.0999	0.1059	0.1999	0.0240
	Global PSO	0.2999	0.7279	1.8999	0.3435
	Ring PSO	0.0999	0.3879	1.2999	0.2027
	Scale free PSO	0.0999	0.1406	0.1999	0.0492
	PEPSO	0.0999	0.2139	0.5999	0.1125
	PEPSO II	0.0999	0.1079	0.1999	0.0274
	APEPSO	0.0999	0.0999	0.0999	6.3693e-008
Quartic function f₅	Standard PSO 2011	4.8605e-004	0.0030	0.0080	0.0018
	Global PSO	0.0045	0.0411	0.1536	0.0338
	Ring PSO	0.0024	0.0150	0.0584	0.0115
	Scale free PSO	6.8133e-004	0.0043	0.0102	0.0023
	PEPSO	4.0183e-004	0.0060	0.0278	0.0057
	PEPSO II	6.3750e-004	0.0030	0.0133	0.0024
	APEPSO	2.8797e-004	0.0022	0.0056	0.0012
Shifted Griewank f₆	Standard PSO 2011	-178.3345	-177.9024	-177.4938	0.3987
	Global PSO	-178.3345	-177.4310	-164.9795	1.8316
	Ring PSO	-178.3345	-177.9581	-177.4936	0.4010
	Scale free PSO	-178.3345	-178.0864	-177.5053	0.3626
	PEPSO	-178.3345	-177.8133	-177.4838	0.3808
	PEPSO II	-178.3345	-177.9374	-177.5053	0.4126
	APEPSO	-178.3345	-178.1117	-177.5126	0.3591
Gear Train f₇	Standard PSO 2011	2.7009e-012	6.0000e+004	1.0000e+006	2.3990e+005
	Global PSO	1.3616e-009	7.8000e+005	3.0000e+006	6.1578e+005
	Ring PSO	2.7009e-012	1.4000e+005	1.0000e+006	3.5051e+005
	Scale free PSO	2.7009e-012	2.8710e-010	2.3576e-009	6.1553e-010
	PEPSO	2.7009e-012	3.6000e+005	1.0000e+006	4.8487e+005
	PEPSO II	2.7009e-012	2.0000e+004	1.0000e+006	1.4142e+005
	APEPSO	2.7009e-012	2.6151e-011	1.1661e-010	3.5087e-011
Rastrigin function f₈	Standard PSO 2011	32.8336	89.8984	298.4771	43.6188
	Global PSO	622.3752	4182.2	17830	3862.6
	Ring PSO	38.5440	156.7057	468.6710	79.3877
	Scale free PSO	40.9874	110.0675	318.3709	46.9874
	PEPSO	93.5257	327.3153	1.0415e+003	215.0473
	PEPSO II	44.8941	112.4166	263.6165	43.3539
	APEPSO	54.2447	129.4380	180.3438	34.4006
Step function f₉	Standard PSO 2011	0	7.1800	85	17.1758
	Global PSO	577	11178	61946	13475
	Ring PSO	0	3.66	49	8.2055
	Scale free PSO	0	7.94	84	14.9713
	PEPSO	9	355.8400	5965	880.1073
	PEPSO II	0	1.200	6	1.3702
	APEPSO	0	0.8000	4	0.9035
Rosenbrock function f₁₀	Standard PSO 2011	15.4579	1.9012e+003	2.8153e+004	5.0678e+003
	Global PSO	95913	1.5928e+009	1.3550e+008	2.7114e+008
	Ring PSO	6.022	509.0070	1.3291e+004	1.8700e+003
	Scale free PSO	47.7010	4.6389e+003	4.0019e+004	1.0457e+004
	PEPSO	4.4350	328.6860	2.6561e+003	608.8560
	PEPSO II	27.3376	3.0540e+003	4.6219e+004	8.1221e+003
	APEPSO	28.5644	3.7352e+003	4.8893e+004	9.1864e+003
Salomon function f₁₁	Standard PSO 2011	0.2999	0.4306	0.9999	0.1154
	Global PSO	5.0999	14.0179	30.6999	5.7751
	Ring PSO	1.0999	2.5339	6.7999	1.2133
	Scale free PSO	0.5364	1.0531	2.2999	0.4125
	PEPSO	0.4999	2.8599	7.8999	2.0383
	PEPSO II	0.2999	0.4305	0.7014	0.1169
	APEPSO	0.2999	0.4452	0.6002	0.0674
Quartic function f₁₂	Standard PSO 2011	0.0287	0.0969	0.7344	0.1019
	Global PSO	2.1656e+004	9.4473e+007	2.1442e+009	3.2115e+008
	Ring PSO	0.1002	0.2785	0.6410	0.1262
	Scale free PSO	0.0689	0.2627	0.8817	0.1533
	PEPSO	0.0523	0.2471	1.3855	0.2542
	PEPSO II	0.0271	0.0964	0.2887	0.0516
	APEPSO	0.0252	0.2159	0.5084	0.1101
Shifted Griewank function f₁₃	Standard PSO 2011	-172.0213	-172.0213	-172.0213	8.6373e-013
	Global PSO	-172.0072	-150.5217	-10.4725	35.1150
	Ring PSO	-172.0213	-172.0213	-172.0213	1.2489e-011
	Scale free PSO	-172.0213	-172.0213	-172.0213	3.3581e-005
	PEPSO	-172.0213	-171.5842	-160.2380	2.0375
	PEPSO II	-172.0213	-172.0213	-172.0213	3.1368e-009
	APEPSO	-172.0213	-172.0213	-172.0213	1.1237e-007

Table 3.

Statistical results when the maximum number of function evaluations is 20000

However, when the dimension D = 30, the standard PSO 2011 can achieve better optimization results for some benchmark functions than APEPSO according to Table 3. Moreover, since the standard PSO 2011 can achieve better optimization performance than PSOs with ring/full connection/scale free topologies, and APEPSO is derived from PEPSO and PEPSO II and it can achieve better optimization results than PEPSO and PEPSO II for the most of the benchmark functions and it does not need to choose the preferring possibility value or parameter, it will be fine to focus on the comparisons between APEPSO and standard PSO 2011, and it is better to draw the figures of time evolutions of the best fitness function values to find whether APEPSO is premature earlier than the standard PSO 2011. According to the simulations, the time evolutions of the best fitness function value are shown in Figures 2–8 about the benchmark function f1 to f7 when the dimension D=10. In Figures 2–8, there are 50 curves with the same colour related to the 50 trials for the standard PSO 2011 or APEPSO. It should be noted that the red lines are the results using the standard PSO 2011 and the blue lines are the results using APEPSO in Figures 2–16. To get a clear vision about the optimization process the log coordinate in y axis has been used for the time evolution figures except the figures with negative fitness values.

According to Figures 2–8, APEPSO takes more time to reach its stable status especially Figures 2, 4 and 6, APEPSO is still in the process of achieving better results although the standard PSO 2011 has reached its mature stations for most of the tries, which means that the standard PSO 2011 is easier to be premature than APEPSO. The convergence of APEPSO is a little bit slower than the standard PSO 2011 because APEPSO takes more time to find the global best results without being trapped in the local minimums in a short time. When the dimension D = 30 the optimization performance for some benchmark functions are not better than the standard PSO 2011 according to Table 4, it is logical to assume this result is caused by the maximum number of function evaluations, which is set 20000 for every trial and may be not enough for APEPSO. To investigate whether this guess is correct, we set the maximum number of function evaluations as 40000 for every trial and other parameters are not changed; and the simulation results are listed in Table 4. According to the statistical results in Table 4, it proves our guess that the maximum number of function evaluations limited the optimization performance of APEPSO since the optimization performance has been improved with the increment of the maximum number of function evaluations.

Problem	Method	best	Mean	Worst	Std.dev
Rastrigin function f₈	Standard PSO 2011	39.7983	90.6006	382.0256	54.2689
Rastrigin function f₈	APEPSO	23.9677	77.4392	141.0321	32.6765
Step function f₉	Standard PSO 2011	0	18.74	611	87.85
Step function f₉	APEPSO	0	0.62	3	0.7253
Rosenbrock function f₁₀	Standard PSO 2011	10.0945	300.3639	2.528e+003	543.1381
Rosenbrock function f₁₀	APEPSO	7.4338	120.3019	901.9223	172.2884
Salomon function f₁₁	Standard PSO 2011	0.1999	0.3019	0.4999	0.0714
Salomon function f₁₁	APEPSO	0.1999	0.2323	0.2999	0.0469
Quartic function f₁₂	Standard PSO 2011	0.0083	0.0272	0.0887	0.0149
Quartic function f₁₂	APEPSO	0.0048	0.0177	0.0443	0.0087
Shifted Griewank function f₁₃	Standard PSO 2011	- 172.0213	- 172.0213	-172.0213	0
Shifted Griewank function f₁₃	APEPSO	- 172.0213	- 172.0213	-172.0213	0

Table 4.

Statistical results of SPSO 2011 and APEPSO when the maximum number of function evaluations is 40000 for every trial and the function dimension is 30

To check whether the APEPSO is ‘mature’ at the end of the optimization process, the time evolution figures of the best fitness function value have been shown in Figures 9–14. According to Figures 9–14, they further prove that APEPSO is not easy to be premature and can achieve better optimization results than standard PSO 2011.

According to Figures 9 and 11, APEPSO may not achieve its potential. Hence we set the maximum number of function evaluations 100000 for every trial and do simulation for f8 and f10 based on APEPSO, and the results are shown in Table 5. Comparing Table 3 and 4, the optimization performance has been further improved when the maximum number of function evaluations is 100000 for every trial. The relevant time evolutions of the best fitness function value for f8 and f10 are shown in Figures 15 and 16, which meet the results of Table 4.

Problem	Method	best	Mean	Worst	Std.dev
Rastrigin function f₈	APEPSO	12.9345	32.0719	95.3182	16.6891
Rosenbrock function f₁₀	APEPSO	3.8793	74.89.15	564.1397	97.2075

Table 5.

Results using APEPSO when the maximum number of function evaluations is 100000 for every trial

According to Figures 15 and 16, APEPSO keeps on searching and achieving better results although the process is approaching the last stage, especially in Figure 15, APEPSO is not mature, which shows that APEPSO can achieve better optimization result and does not need explicit topology information and no extra parameters need to be set.

5. Transmission network planning

Transmission network planning begins with the establishment of power demand growth scenarios, in accordance with forecasts along the time. Given these scenarios, one can verify the eventual need to broaden and to strengthen the network. In case electric service conditions are not satisfied, there should be proposed a plan that has coherence among the power supply availability, demand, and installation of new equipment in the network. Integration of these new equipment in the network, aimed at maintaining suitable technical and operating conditions, requires planning of the allocation of such reinforcement [20]. Main objective of the transmission expansion planning is to obtain the optimal expansion plan, while fulfilling operating and economic requirements. One classical transmission network expansion planning (TNEP), which does not consider the security constraints, is to determine the set of new lines to be constructed such that the cost of expansion plan is minimum and no overloads are produced during the planning horizon. A DC power flow based model is used for TNEP [20, 21]. The TNEP without security constraints can be stated as follows [20, 21],

(8)minv=∑l∈Ωclnl

subject to

Sf + g = d
fl−γl(nl0+nl)(Δθl)=0 , for l ∈ 1,2……,
|fl|≤(nl0+nl)fl¯ for l ∈ 1,2……, nl
0≤nl≤nl¯
f_l and θ_l are unbounded
n_l ≥ 0 and is integer for l ∈ 1,2……, nl
l ∈ Ω.

c_l:: cost of line added in l^th right-of-way,

S:: branch-node incidence transposed matrix of the power system,

f:: vector with elements f_l,

γ_l:: susceptance of the circuit that can be added to l^th right-of-way,

n_l:: the number of circuits added in l^th right-of-way,

nl0 :: no. of circuits in the base case,

Δθ_l:: phase angle difference in l^th right-of-way,

f_l:: total real power flow by the circuit in l^th right-of-way,

fl¯ :: maximum allowed real power flow in the circuit in l^th right-of-way,

nl¯ :: maximum number of circuits that can be added in l^th right-of-way,

Ω:: set of all right-of-ways,

nl:: total number of lines in circuit.

The transmission lines added in any right-of–way are the decision variables. The cost of each solution to the TNEP without security constraints can be obtained using the following function:

(9)Minimize: f=∑l∈Ωclnl+W1∑ol(abs(fl)−fl¯)+W2(nl−nl¯)

where ol represents the set of overloaded lines.

The objective of the TNEP is to find the set of transmission lines to be constructed such that the cost of expansion plan is minimum and no overloads are produced during the planning horizon. Hence, first term in the equation (9) indicates the total investment cost of a transmission expansion plan. The second term is added to the objective function for the real power flow constraint violations. The third term is added to the objective function if maximum number of circuits that can be added in lth right-of-way exceeds the maximum limit. W1, W2 are constants. The second and third terms are added to the fitness function only in case of violations.

We set the maximum number of function evaluations as 100000 for every trial and other parameters are not changed; and the simulation results are listed in Table 6. As can be seen from the Table 6, APEPSO achieved the optimal value and the statistical results, and it is proven that APEPSO can achieve better optimization results than SPSO in this application.

Problem	Method	best	Mean	Worst	Std.dev
Transmission Network Expansion Planning Problem	Standard PSO 2011	220	234.54	323	24.1358
Transmission Network Expansion Planning Problem	APEPSO	220	220	220	0

Table 6.

Results using the standard PSO 2011 and APEPSO for Transmission Network Expansion Planning Problem

6. Conclusion

This paper proposed three elitist set based particle swarm optimization algorithms, which are called 1) Probabilistic preference and Elitist set based Particle Swarm Optimization (PEPSO), 2) Probabilistic preference and Elitist set based Particle Swarm Optimization considering the individual two nearest experience neighbours (PEPSO II) and 3) Adaptive Probabilistic preference and Elitist set based Particle Swarm Optimization considering the individual two nearest experience neighbours (APEPSO). These methods do not need explicit topology structures, and an elitist set is used and based on the individual best experiences for the swarm communication. These three methods have been applied to several well-known benchmarks and achieved good optimization results. Among these three proposed algorithms, APEPSO can achieve better optimization performance than the standard PSO 2011 and some other PSOs with different topologies for all the benchmark functions and the application, and it does not need to turn the parameters. In the future, we will focus on the theoretic analysis of the proposed method.

Acknowledgement

The author declares that there is no conflict of interest regarding the publication of this paper. The author thanks the Matlab for the version codes of SPSO 2011 by Mahamed Omran, available on the particle swarm central website [8].

References

1.CM Huang, CJ Huang, and ML Wang, A particle swarm optimisation to identifying the ARMAX model for short-term load forecasting, IEEE Transaction on Power Systems, Vol. 20, No. 2, 2005, pp. 1126-1133.

2.M Clerc, Particle Swarm Optimisation, ISTE Publishing Company, 2006.

3.N Nedjah and LDM Mourelle, Systems Engineering Using Particle Swarm Optimisation, Nova Science Publishers, 2007.

4.Y del Valle and GK Venayagamoorthy, Particle Swarm Optimisation: Basic Concepts, Variants and Applications in Power Systems, IEEE Transactions on Evolutionary Computation, Vol. 12, No. 2, 2008, pp. 171-195.

5.J Kennedy, EC Eberhart, and YH Shi, Swarm intelligence, Morgan Kaufmann Publisher, San Francisco, 2001.

6.J Kennedy, Small worlds and mega-minds: Effects of neighbourhood topology on particle swarm performance, Bureau of Labor Statistics, USA, in Proc. of IEEE Congress Evolutionary Computation, July (1999), Vol. 3, pp. 1931-1938.

7.J Kennedy and R Mendes, Population structure and particle swarm performance, in Proc. of IEEE Congress Evolutionary Computation (Honolulu, HI, USA, May 2002), Vol. 2, pp. 1671-1676.

8.J Kennedy, M Clerc, et al., Particle Swarm Central, 2012. http://www.particleswarm.info/Programs.html

9.M Clerc and J Kennedy, The particle Swarm: explosion, stability, and convergence in multi-dimension complex space, IEEE Transactions on Evolutionary Computation, Vol. 6, No. 1, 2002, pp. 58-73.

10.B Liu, L Wang, YH Jin, F Tang, and DX Huang, Improved particle swarm optimization combined with chaos, Chaos, Solitons and Fractals, Vol. 25, 2005, pp. 1261-1271.

11.J Kennedy and RC Eberhart, Particle swarm optimisation, in Proc. of. IEEE International Conference Neural Networks (Perth, Australia, 1995), pp. 1942-1948.

12.M Dorigo, Optimization, Learning and Natural Algorithms, Politecnico di Milano, Italie, 1992. PhD thesis,

13.S Rahnamayan, HR Tizhoosh, and MMA Salama, Opposition-based differential evoution, IEEE transactions On Evolutionary Computation, Vol. 12, No. 1, 2008, pp. 64-79.

14.Y Zhang, S Wang, and G Ji, A Comprehensive Survey on Particle Swarm Optimization Algorithm and Its Applications, Mathematical Problems in Engineering, 2015, pp. 38. Article ID 931256,

15.I F Jr., M Perc, K Ljubiˇc, SM Kamal, and A Iglesias, Particle swarm optimization for automatic creation of complex graphic characters, Chaos, Solitons & Fractals, Vol. 73, 2015, pp. 29-35.

16.Z Yaqin, L Beizhi, and W Lv, Study on job-shop scheduling with multi-objectives based on genetic algorithms, in Proc. of the International Conference on Computer Application and System Modelling (ICCASM ’10) (Taiyuan, China, October 2010), pp. v10294-v10298.

17.NH Moin, OC Sin, and M Omar, Hybrid Genetic Algorithm with Multiparents Crossover for Job Shop Scheduling Problems, Mathematical Problems in Engineering, Vol. 2015, 2015, pp. 12. Article ID 210680,

18.J Gao, R Chen, and W Deng, An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem, International Journal of Production Research, Vol. 51, No. 3, 2013, pp. 641-651.

19.QK Pan and R Ruiz, An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem, Omega, Vol. 44, 2014, pp. 41-50.

20.T Celso, MC Miasaki, F Edgar, and AR Ruben, Transmission Network Expansion Planning Considering Phase-Shifter Transformers, Journal of Electrical and Computer Engineering, Vol. 2012, 2012, pp. 10. Article ID 527258,

21.S Das and PN Suganthan, Problem Definitions and Evaluation Criteria for CEC 2011 Competition on Testing Evolutionary Algorithms on Real World Optimization Problems, Jadavpur University, India and Nanyang Technological University, 2010. Technical Report,

22.Q Ni, X Yin, K Tian, and Y Zhai, Particle swarm optimization with dynamic random population topology strategies for a generalized portfolio selection problem Natural Computing, Natural Computing: an international journal, Vol. 16, No. 1, 2017, pp. 31-44.

23.D Chen, R Zhang, C Yao, and Z Zhao, Dynamic topology multi force particle swarm optimization algorithm and its application, Chinese Journal of Mechanical Engineering, Vol. 29, No. 1, 2016, pp. 124-135.

24.CM Fernandes, JLJ Laredo, JJ Merelo, C Cotta, and AC Rosa, Particle swarm optimization with dynamic topology and conservation of evaluations, Studies in Computational Intelligence, Vol. 620, 2016, pp. 97-111.

25.DJ Watts and SH Strogatz, Collective dynamics of ‘small-world’ networks, Nature, Vol. 393, 1998, pp. 440-442.

26.C Liu, WB Du, and WX Wang, Particle swarm optimization with scale-free interactions, Plos One, Vol. 9, No. 5, 2014, pp. 1-8.

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 10 - 1
Pages: 1316 - 1329
Publication Date: 2017/09/14
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.10.1.92 How to use a DOI?
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - Yanxia Sun
AU  - Zenghui Wang
PY  - 2017
DA  - 2017/09/14
TI  - Elitism set based particle swarm optimization and its application
JO  - International Journal of Computational Intelligence Systems
SP  - 1316
EP  - 1329
VL  - 10
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.10.1.92
DO  - 10.2991/ijcis.10.1.92
ID  - Sun2017
ER  -

download .riscopy to clipboard