Modified Bare Bones Particle Swarms for Large Scale Global Optimization
6.2 Proposal of BBPSO-DE for LSGO Problems
In this section, a simple yet effective BBPSO-DE algorithm [98] using the ring neighbour-hood topology, which does not require any parameters, is proposed for large scale global optimization.
6.2.1 Ring Topology of BBPSO-DE
Niching is an important technique for large scale multimodal optimization. Reference [54]
demonstrates that an𝑙𝑏𝑒𝑠𝑡 PSO using a ring topology is able to induce stable niching be-haviours. The definition originally introduced by M.Clerc [15] is that a swarm can be viewed as a combination of explorer-swarm and memory-swarm according to their differences in functionality. The explorer-swarm is composed of particles moving around in large step sizes and more frequently, each particle strongly influenced by its velocity and previous
po-6.2 Proposal of BBPSO-DE for LSGO Problems
Fig. 6.1 Ring topology ofexplorer-swarm
sition. The memory-swarmconsists of personal bests of all particles. The memory-swarm is more effective in retaining better positions found so far by the swarm as a whole. In this part, the ring topologies of explorer-swarm and memory-swarm used by BBPSO-DE are described respectively.
Figure 6.1 shows an example ofexplorer-swarm using a ring topology with a popula-tion of four particles. Here the explorer-swarm consists of particles (𝑥𝑖) as marked from numbers 1 to 4. Each member interacts only with its immediate left and right neighbours.
Theexplorer-swarm, sampled from Gaussian distribution, is more effective in exploring the widely available search space. It is important to note that each particle defined in the BBPSO-DE possesses local memory including its personal best memory𝑝𝑖and its local best memory 𝑙𝑏𝑒𝑠𝑡𝑖.
Figure 6.2 shows thememory-swarmusing ring topology with a population of four per-sonal best memory (𝑝𝑖) and four local best memory (𝑙𝑏𝑒𝑠𝑡𝑖). Each𝑙𝑏𝑒𝑠𝑡𝑖has three informants, from two immediate neighbouring particles' best memory and its own best memory. It also illustrates the relationship between𝑝𝑖 and𝑙𝑏𝑒𝑠𝑡𝑖. Figure 6.3 describes the detailed
proce-Fig. 6.2 Ring topology ofmemory-swarm
dure of how to achieve the𝑙𝑏𝑒𝑠𝑡swarm. For instance, we suppose that𝑝𝑏𝑒𝑠𝑡𝑛represents the left neighbour of𝑝𝑏𝑒𝑠𝑡1, and𝑝𝑏𝑒𝑠𝑡2shows the right neighbour. The best one from the three informants is chosen as𝑙𝑏𝑒𝑠𝑡1. Similarly, a swarm of𝑙𝑏𝑒𝑠𝑡𝑖is created by chosen the best one from the𝐿𝑝𝑏𝑒𝑠𝑡swarm, the𝑝𝑏𝑒𝑠𝑡swarm and the𝑅𝑝𝑏𝑒𝑠𝑡swarm.
6.2.2 Integrated BBPSO-DE with Differential Evolution
The mutation and crossover operators of DE are employed for updating 𝑙𝑏𝑒𝑠𝑡𝑖 when the current particle's𝑝𝑖objective function value happens to be the same as that of𝑙𝑏𝑒𝑠𝑡𝑖:
𝑙𝑏𝑒𝑠𝑡𝑖=
⎧⎪
⎨⎪
⎩
𝑝𝑖1 + 0.5 ∗ (𝑝𝑖2 −𝑝𝑖3) if𝑈 (0, 1) < 0.5
𝑙𝑏𝑒𝑠𝑡𝑖 otherwise
(6.2)
Where𝑖 ≠ 𝑖1 ≠ 𝑖2 ≠ 𝑖3, and𝑝𝑖1,𝑝𝑖2,𝑝𝑖3 are randomly chosen from the previous personal best positions. 𝑈 (0, 1)is a function that generates uniformly distributed random numbers between zero and one. From equation 6.2, we can see that there is a50%chance that the𝑙𝑏𝑒𝑠𝑡𝑖
6.2 Proposal of BBPSO-DE for LSGO Problems
Fig. 6.3 Group three swarms as one team swarm
is updated by the mutation operator of DE, whose information comes from the randomly chosen previous best positions. However, there is a50%possibility that the𝑙𝑏𝑒𝑠𝑡𝑖keeps the previous position. If the standard deviation𝜎approaches zero, that is the current particle's 𝑝𝑏𝑒𝑠𝑡 equals to the 𝑙𝑏𝑒𝑠𝑡 position, then the global best position of the whole swarm will not be updated. Thus, the new definitions of the mean 𝜇 and the standard deviation 𝜎 is developed to maintain the swarm diversity by increasing the particles' variance.
6.2.3 Redefining the Sample Equations
In general, the particles can explore the search space more broadly by using individual's localmemory-swarm to form a stable network retaining the best positions found so far. In particularly for the 𝑙𝑏𝑒𝑠𝑡𝑖 shown in Fig.6.2, which is more likely to strengthen the global exploration capability while successfully maintain the local exploitation functionality. In BBPSO-DE, we try to redefine the equations of mean𝜇and standard deviation𝜎with𝑙𝑏𝑒𝑠𝑡𝑖 and𝑋. Here is the new equations used in BBPSO-DE.
𝜇 = 𝑙𝑏𝑒𝑠𝑡𝑖+ 𝑋
2 (6.3)
𝜎 = |𝑙𝑏𝑒𝑠𝑡𝑖− 𝑋| (6.4)
𝑥𝑖=
⎧⎪
⎨⎪
⎩
𝑁(𝜇, 𝜎) if𝑈 (0, 1) < 0.5 𝑙𝑏𝑒𝑠𝑡𝑖 otherwise
(6.5)
Where𝑋denotes the centroid position of all particles. The swarm's centroid position is first used in Competitive Swarm Optimization (CSO) [12], which is a novel swarm intelligence algorithm for large scale optimization. The motivation for us to introduce centroid position in BBPSO-DE is to increase swarm diversity, which potentially enhances the global search capability of BBPSO-DE.
6.2.4 Pseudocode of BBPSO-DE
BBPSO-DE is a variant of BBPSO-MC-lbest. The differences between them are the new equations for the Gaussian distribution and ring topology of BBPSO-DE. The main function of BBPSO-DE is demonstrated in Algorithm 13. In algorithm 13, all the different lines with BBPSO-MC-lbest are marked with underline. As shown in lines 13, 15 and 20, a new method is proposed to calculate the Gaussian distribution. We consider that this method is useful to improve the search performance of BBPSO-DE.
In order to investigate the performance of BBPSO-DE, we present here a compared al-gorithm named Modified Competitive Particle Swarm Optimization (MCPSO). Which can be seemed as a variant of PSO used for large scale optimization. In MCPSO, each particle only has one specified neighbourhood. The updated rules are borrowed from CSO [12].
6.2 Proposal of BBPSO-DE for LSGO Problems
Algorithm 13Pseudocode of BBPSO-DE
1: Initialize particles𝑥𝑖: 𝑥𝑖 = 𝑟𝑎𝑛𝑑() ∈ (𝑥𝑚𝑖𝑛,𝑥𝑚𝑎𝑥),𝑖 ∈ [1..𝑛]
2: Initialize personal best particles𝑝𝑖, 𝑖 ∈ [1..𝑛]
3: Initialize local best particles𝑙𝑏𝑒𝑠𝑡𝑖, 𝑖 ∈ [1..𝑛]
4: Initialize iteration counter,𝑡 = 0, 𝑡𝑚𝑎𝑥 = 𝑀𝑎𝑥𝑖𝑡𝑒𝑟
5: while𝑡 < 𝑀𝑎𝑥𝑖𝑡𝑒𝑟do
6: foreach particle𝑥𝑖do
7: if𝐹 𝑖𝑡𝑛𝑒𝑠𝑠(𝑝𝑖) = 𝐹 𝑖𝑡𝑛𝑒𝑠𝑠(𝑙𝑏𝑒𝑠𝑡𝑖)then
8: Randomly set𝑖1, 𝑖2, 𝑖3.(𝑖 ≠ 𝑖1 ≠ 𝑖2 ≠ 𝑖3)
9: if𝑈 [0, 1] < 0.5then
10: 𝑙𝑏𝑒𝑠𝑡𝑖 =𝑝𝑖1 + 0.5 ∗ (𝑝𝑖2 −𝑝𝑖3)
11: end if
12: end if
13: Get the mean value of all particles: 𝑋
14:
15: 𝜇 = 𝑙𝑏𝑒𝑠𝑡𝑖+ 𝑋
2 , 𝜎 = |𝑙𝑏𝑒𝑠𝑡𝑖− 𝑋|
16:
17: if𝜎 = 0then
18: 𝜎 = 0.001
19: end if
20: 𝑥𝑖=
{
𝑁(𝜇, 𝜎) if𝑈 (0, 1) < 0.5 𝑙𝑏𝑒𝑠𝑡𝑖 otherwise
21:
22: if𝑥𝑖< 𝑥𝑚𝑖𝑛 OR𝑥𝑖> 𝑥𝑚𝑎𝑥 then
23: 𝑥𝑖 = 𝑥𝑚𝑖𝑛+ 𝑈 [0, 1] ∗ (𝑥𝑚𝑎𝑥− 𝑥𝑚𝑖𝑛)
24: end if
25: if𝐹 𝑖𝑡𝑛𝑒𝑠𝑠(𝑥𝑖) < 𝐹 𝑖𝑡𝑛𝑒𝑠𝑠(𝑝𝑏𝑒𝑠𝑡𝑖)then
26: 𝑝𝑏𝑒𝑠𝑡𝑖 =𝑥𝑖
27: end if
28: Create𝑝𝑏𝑒𝑠𝑡's left and right neighbour swarms
29: Group three swarms as a team: 𝑙𝑏𝑒𝑠𝑡𝐺𝑟𝑝
30:
31: 𝑙𝑏𝑒𝑠𝑡𝑖= 𝑎𝑟𝑔𝑚𝑖𝑛(𝐹 𝑖𝑡𝑛𝑒𝑠𝑠(𝑙𝑏𝑒𝑠𝑡𝐺𝑟𝑝𝑖))
32: end for
33: 𝑡 = 𝑡 + 1
34: end while
35: Output the global optimum of the team𝑙𝑏𝑒𝑠𝑡𝐺𝑟𝑝
𝑣𝑖(𝑡) = 𝑟1∗𝑣𝑖(𝑡 − 1) + 𝑟2∗ (𝑙𝑏𝑒𝑠𝑡𝑖(𝑡 − 1) −𝑥𝑖(𝑡)) + 𝑟3∗ (𝑋(𝑡 − 1) −𝑥𝑖(𝑡 − 1)) (6.6)
𝑥𝑖(𝑡) =𝑥𝑖(𝑡 − 1) +𝑣𝑖(𝑡) (6.7) Where𝑡is the current iteration (generation) number,𝑣𝑖(𝑡)and𝑥𝑖(𝑡)represent the velocity and position of the particle𝑖, respectively. 𝑟1,𝑟2, 𝑟3are three independent random numbers uniquely generated at every update for each individual dimension in the range [0,1]. If each particle𝑥𝑖only has one neighbourhood, then its𝑙𝑏𝑒𝑠𝑡𝑖can be seemed as a result of pairwise competition. This pairwise competition mechanism has been used by some researchers and showed promising performance on large scale problems.