A New Particle Swarm Optimization for Dynamic Environments (Applications of Intelligent Methods for Security)

Abstract

Dynamic optimization in which global optima and local optima change over time is always a hot research topic. It has been shown that particle swarm optimization works well facing into dynamic environments. From another hands, learning automata is considered as an intelligent tool (agent) which can learn what action is the best one interacting with its environment. The great deluge algorithm is also a search algorithm applied to optimization problems. All these algorithms have their special drawbacks and advantages. In this paper it is examined can the combination of these algorithms results in the better performance dealing with dynamic problems. Indeed a learning automaton is employed per each particle of the swarm to decide whether the corresponding particle updates its velocity (and consequently its position) considering the best global particle, the best local particle or the combination global and local particles. Water level in the deluge algorithm is used in the progress of the algorithm. Experimental results on different dynamic environments modeled by moving peaks benchmark show that the combination of these algorithms outperforms Particle Swarm Optimization (PSO) algorithm, Fast Multi-Swarm Optimization (FMSO) method, a similar particle swarm algorithm for dynamic environments, for all tested environments.

Keywords: Particle Swarm Optimization, Great Deluge, Learning Automaton, Moving Peaks, Dynamic Environments.

Introduction

The standard particle swarm optimization algorithms have been performed well for static environment. Also it is shown that original PSO can’t handle dynamic environments. So researchers turn to new variations of PSO to overcome its inefficiency [1].

Hu and Eberhart proposed re-randomization PSO (RPSO) for optimization in dynamic environments [13] in which some particles randomly are relocated after a change is detected or when the diversity is lost, to prevent losing the diversity. Li and Dam [14] showed that a grid-like neighborhood structure used in FGPSO [11] can perform better than RPSO in high dimensional dynamic environments by restricting the information sharing and preventing the convergence of particles to the global best position, thereby enhancing population diversity. Janson and Middendorf [7] proposed hierarchical PSO (HPSO), a tree-like structure hierarchical PSO, and reported improvements over standard PSO for dynamic environments. They also suggested Partitioned Hierarchical PSO in which a hierarchy of particles is partitioned into several sub-swarms for a limited number of generations after a change in the environment is detected [8]. Lung and Dumitresc [19] used two collaborating populations with same size which one swarm is responsible for preserving the diversity of the particles by using a crowding differential evolutionary algorithm [20] while the other keeps track of global optimum with a PSO algorithm.

Li and Yang proposed a FMSO method which maintains the diversity through the run [16]. To meet this goal two types of swarm are used: a parent swarm which maintains the diversity and detects the promising search area in the whole search space using a fast evolutionary programming algorithm, and a group of child swarms which explore the local area for the local optima found by the parent using a fast PSO algorithm. This mechanism makes the child swarms spread out over the highest multiple peaks, as many as possible, and guarantees to converge to a local optimum in a short time. Moreover, in [15], the authors introduced a clustering particle swarm optimizer in which a clustering algorithm partitions the swarm into several sub-swarms each searching for a local optimum.

Liu et al. [17] introduced compound particle swarm optimization (CPSO) utilizing a new type of particles which helps explore the search space more comprehensively after a change occurred in the environment. In another work, they used composite particles which help quickly find the promising optima in the search space while maintaining the diversity by a scattering operator [18].

Hashemi and Meybodi introduced cellular PSO, a hybrid model of cellular automata and PSO [6]. In cellular PSO, a cellular automaton partitions the search space into cells. At any time, in some cells of the cellular automaton a group of particles search for a local optimum using their best personal experiences and the best solution found in their neighborhood cells. To prevent losing the diversity, a limit on the number of particles in each cell is imposed. Furthermore, to track the changes in the environment, in [6] particles in cellular PSO change their role to quantum particles and perform a random search around the previously found optima for a few iterations after a change is detected in the environment.

Kamosi et al. propose some variations of PSO that can perform well for dynamic environments [9]. In their work, they proposed a multi-swarm algorithm for dynamic environments which address the diversity loss problem by introducing two types of swarm: a parent swarm, which explores the search space to find promising area containing local optima and several non-overlapping child swarms, each of which is responsible for exploiting a promising area found by the parent swarm.

Related Work

A learning automaton (LA) is an adaptive decision-making unit that is situated in a random environment and learns the optimal state-action set through many repeated interactions with its environment. The actions are chosen according to a specific probability distribution which is updated based on the environment responses to the action taken by the automaton. Given a finite number of actions that can be performed in a random environment, when a specific action is taken place the environment provides a random response which is either favorable or unfavorable. The objective in the design of the automaton is to determine how the choice of the action at any stage should be guided by past actions and responses [21].

The PSO is first introduced by Kennedy and Eberhart [10]. In PSO, a potential solution for a problem is considered as a bird, which is called a particle, flies through a D-dimensional space and adjusts its position according to its own experience and other particles’. In PSO, a particle is represented by its position vector x and its velocity vector v.

The great deluge algorithm (GD) is first introduced by Dueck [5], but unfortunately was not widely useful in succeeding years. This local search meta-heuristic is different from its predecessors (e.g. Hill-Climbing or Simulated Annealing) in the acceptance of a candidate solution from a neighborhood. The GD algorithm accepts all solutions, for which absolute values of the cost function are less than or equal to the current boundary value, called "level". The local search starts with the initial value of "level" equal to an initial cost function and during the search its value is monotonically reduced. A decrement of the reduction (defined by the user) appears as a single algorithmic parameter.

Proposed Combination Framework of PSO, LA and GD Algorithms

To get rid of the premature convergence of PSO algorithm, it is needed to use a mechanism that produces perturbation in population. A very promising method is to turn to multi-swarm mechanisms. In the multi-swarm mechanism, there must be a parent swarm which is responsible for finding promising area in the search space and also some child swarms which are created to exploit the new found promising area [1-3] and [10].

This paper differently deals with the premature problem. It uses a PSO in which each particle uses a learning automaton based on which the particle decides how to update its velocity. Indeed each automaton learns how to behave in predefined situations. These situations contain variance of the best fitness of local optima and the distance of the particle to its local and global optima. The learning of the automaton is based on feedbacks received from the environment. A feedback per each particle is set according to its current position’s fitness and the previous position’s fitness. It means that if the previous position’s fitness is higher than the current position’s, the action taken on the previous position to reach the current position is punishes else it is rewarded.

In the proposed method, the states of learning automaton Aj is a triple denoted by (var,diS 1,diS 2), where var, diS1 and diS2 are three quantitative variables belong to {0,1,2}. To calculate var first maximum distance between two arbitrary selected X\ (ie 1..N) is defined as max_disqp.

Then the normalized variance of denoted by nvar is defined as follow.

whereis the variance ofNow var is calculated according the following equations.

where v1 and v2 are two user-specified thresholds. For calculating diS 1, max_disp is first defined as following equation.

Then the normalized distance between X\ and Xg denoted by ndiS 1 is defined as follow.

Now diS1 is calculated according the following equations.

where dn and d12 are two user-specified thresholds. And finally for calculating diS 2, max_disq is first defined as following equation.

Then the normalized distance between X\ and Xj denoted by ndiS 2 is defined as following.

Now diS 2 is calculated according the following equation.

where d21 and d22 are two user-specified thresholds. Pseudo code of the proposed algorithm is presented in the Fig. 1. In this code r1 and r2 are both 0.5. Also all w1, w2 and w3 are 0.33.

Fig. 1. Pseudo code of the proposed algorithm

Experimental Study

Branke [4] introduced a dynamic benchmark problem, called moving peaks benchmark (MPB) problem. In this problem, there are some peaks in a multidimensional space, where the height, width and position of each peak change during the environment change. This function is widely used as a benchmark for dynamic environments in literature [12] and [17].

Table 1. Parameters of Moving Peaks Benchmark

Parameter	Value
number of peaks	10
f	every 5000 evaluations
height severity	7.0
width severity	1.0
peak shape	cone
shift length s	{0.0}
number of dimensions D	5
A	[0, 1001
H	[30.0, 70,0]
W	[1, 121
I	50.0

The default parameter setting of MPB used in the experiments is presented in Table 1. In MPB, shift length, s, is the radius of peak movement after an environment change. m is the number of peaks. f is the frequency of environment change as number of fitness evaluations. H and W denote range of height and width of peaks which will change after a change in environment by height severity and width severity respectively. I is the initial heights for all peaks. Parameter A denotes minimum and maximum value on all dimensions. For evaluating the efficiency of the algorithms, we use the offline error measure, the average deviation of the best individual from the optimum in all iterations.

Table 2. Offline error ±Standard Error for f =500 and f =1000

	Proposed algorithm f=500	Multi Swarm PSO f=500	CellularP SO f=500	FMSO f=500	mQSO10 f=500	Proposed algorithm f=1000	Multi SwarmPSO f=1000	CellularP SO f=1000	FMSO f=1000	mQSO10 f=1000
1	12.49±0.21	5.46±0.30	13.4±0.74	27.58±0.9	33.67±3.4	6.12±0.22	2.90±0.18	6.77±0.38	14.42±0.4	18.6±1.6
5	11.87±0.24	5.48±0.19	9.63±0.49	19.45±0.4	11.91±0.7	5.66±0.20	3.35±0.18	5.30±0.32	10.59±0.2	6.56±0.38
10	9.26±0.12	5.95±0.09	9.42±0.21	18.26±0.3	9.62±0.34	5.88±0.16	3.94 ±0.08	5.15±0.13	10.40±0.1	5.71±0.22
20	7.39±0.17	6.45±0.16	8.84±0.28	17.34±0.3	9.07±0.25	5.36±0.16	4.33±0.12	5.23±0.18	10.33±0.1	5.85±0.15
30	7.74±0.11	6.60±0.14	8.81±0.24	16.39±0.4	8.80±0.21	5.37±0.16	4.41±0.11	5.33±0.16	10.06±0.1	5.81±0.15
40	6.32±0.14	6.85±0.13	8.94±0.24	15.34±0.4	8.55±0.21	4.45±0.11	4.52±0.09	5.61±0.16	9.85±0.11	5.70±0.14
50	5.97±0.16	7.04±0.10	8.62±0.23	15.54±0.2	8.72±0.20	4.49±0.15	4.57±0.08	5.55±0.14	9.54±0.11	5.87±0.13
100	5.65±0.12	7.39±0.13	8.54±0.21	12.87±0.6	8.54±0.16	3.79±0.09	4.77±0.08	5.57±0.12	8.77±0.09	5.83±0.13
200	5.55±0.11	7.52±0.12	8.28±0.18	11.52±0.6	8.19±0.17	3.93±0.10	4.76±0.07	5.50±0.12	8.06±0.07	5.54±0.11

In the proposed method the acceleration coefficients c1 and c2 are set to 2.8 and 1.3 and the inertial weight w is set to mean of c1 and c2 (2.05). The number of particles in the swarm is set to 20 particles. Parameters dn, d21, d12, d22, v1 and v2 are user-specified which are experimentally set to 0.4, 0.4, 0.6, 0.6, 0.4 and 0.6 respectively. The proposed algorithm is compared with Multi-Swarm PSO [9], mQSO [1], FMSO [16], and cellular PSO [6]. In Multi-Swarm PSO the acceleration coefficients c1 and c2 are set to 1.496180 and the inertial weight w is set to 0.729844. The number of particles in the parent swarm and the child swarms (n) are set to 5 and 10 particles, respectively in Multi-Swarm PSO. The radius of the child swarms (r), the minimum allowed distance between two child swarm (rexcl) and the radius of quantum particles (rs) are set to 30.0, 30.0, and 0.5, respectively. For mQSO we adapted a configuration 10(5+5q) which creates 10 swarms with 5 neutral (standard) particles and 5 quantum particles with rcloud=0.5 and rexcl=rconv=3l.5, as suggested in [1]. For FMSO, there are at most 10 child swarms each has a radius of 25.0. The size of the parent and the child swarms are set to 100 and 10 particles, respectively [16]. For cellular PSO, a 5-Dimensional cellular automaton with 105 cells and Moore neighborhood with radius of two cells is embedded into the search space. The maximum velocity of particles is set to the neighborhood radius of the cellular automaton and the radius for the random local search (r) is set to 0.5 for all experiments. The cell capacity 0 is set to 10 particles for every cell [6].

As depicted in the Table 2 and Table 3, the proposed algorithm outperforms other tested PSO algorithms when the number of peaks increases.

Table 3. Offline error ±Standard Error for f =5000 and f =10000

	Proposed	MultiSw	CellularP	FMSO	mQSO10	Proposed	MultiSw	CellularP	FMSO	mQSO10
	algorithm	armPSO	SO	f=5000	f=5000	algorithm	armPSO	SO	f=10000	f=10000
	f=5000	f=5000	f=5000			f=10000	f=10000	f=10000
1	2.54±0.19	0.56±0.04	2.55±0.12	3.44±0.11	3.82±0.35	1.52±0.17	0.27±0.02	1.53±0.12	1.90±0.06	1.90±0.18
5	1.49±0.11	1.06±0.06	1.68±0.11	2.94±0.07	1.90±0.08	0.88±0.11	0.70±0.10	0.92±0.10	1.75±0.06	1.03±0.06
10	1.44±0.10	1.51±0.04	1.78±0.05	3.11±0.06	1.91±0.08	0.91±0.06	0.97±0.04	1.19±0.07	1.91±0.04	1.10±0.07
20	1.85±0.11	1.89±0.04	2.61±0.07	3.36±0.06	2.56±0.10	1.32±0.07	1.34±0.08	2.20±0.10	2.16±0.04	1.84±0.08
30	2.00±0.09	2.03±0.06	2.93±0.08	3.28±0.05	2.68±0.10	1.35±0.05	1.43±0.05	2.60±0.13	2.18±0.04	2.00±0.09
40	2.02±0.08	2.04±0.06	3.14±0.08	3.26±0.04	2.65±0.08	1.27±0.04	1.47±0.06	2.73±0.11	2.21±0.03	1.99±0.07
50	2.03 ±0.08	2.08±0.02	3.26±0.08	3.22±0.05	2.63±0.08	1.30±0.03	1.47±0.04	2.84±0.12	2.60±0.08	1.99±0.07
100	2.23±0.04	2.14±0.02	3.41±0.07	3.06±0.04	2.52±0.06	1.32±0.03	1.50±0.03	2.93±0.09	2.20±0.03	1.85±0.05
200	2.54±0.19	0.56±0.04	2.55±0.12	3.44±0.11	3.82±0.35	1.51±0.02	1.48±0.02	2.88±0.07	2.00±0.02	1.71±0.04

For all algorithms we reported the average offline error and 95% confidence interval for 100 runs. Offline error of the proposed algorithm, mQSO10(5+5q) [1], FMSO [16], cellular PSO [6], and Multi-Swarm PSO [9] for different dynamic environment is presented in Table 2 and Table 3. For each environment, result of the best performing algorithm(s) with 95% confidence is printed in bold.

Conclusions

In this paper, a new PSO algorithm is proposed to deal with the dynamic environments. In the proposed PSO there is one Learning Automaton per each particle which it is to learn for its corresponding particle how to act during the evolution. To prevent redundant search in the same area, the LA belonging to particle Pi, which is denoted by Li, learns the relationship between the variance of the solutions, normalized distance between the position xi and position of its local optima and normalized distance between the position of its local optima and global optima, and the behavior of the particles i. Indeed the proposed PSO is a kind of indirect niching method. In addition, the deluge water level is employed during the evolution.

Results of the experiments show that for many tested dynamic environments the proposed algorithm outperforms all competent tested PSO algorithms.