Lazinica A. (ed.) Particle Swarm Optimization

Подождите немного. Документ загружается.

A Particle Swarm Optimisation Approach to Graph Permutations

301

Following the definition of the basic swap sequence and swap sequence in Algorithm 2 and

Algorithm 3 respectively, the proposed combinatorial PSO algorithm can now be defined.

Algorithm 4 describes the procedural implementation of the swap sequence within the

context of the traditional PSO algorithm.

7. Algorithmic Analysis

The behaviour of each particle in the swarm can be viewed as a traditional line-search

procedure dependent on a stochastic step size and a stochastic search direction. Both the

stochastic step size and search direction depend on the selection of social and cognitive

parameters. In addition, the stochastic search direction is driven by the best design space

locations found by each particle and by the swarm as a whole. Unlike traditional line-search

procedures however, PSO uses information from neighbouring particles to influence the

search direction at each iteration. This exchange of information plays an important role in

the stability and performance of the swarm. In the following section, the spectral properties

of algebraic graph theory are used to show that for a fully interconnected swarm, the

particles will reach a consensus on the equilibrium. The analysis begins by considering the

original PSO algorithm with velocity and position update given by Eq. (1a) and Eq. (1b).

0: for all particle

i do

1: initialise position

x randomly in the search space

2: end for

3: while termination criteria not satisfied do

4: for all particle

5: set personal best

p as the best position found by the particle so far

6: set global best

p as the best position found by the swarm so far

7: end for

8: for all particle

9: update local velocity according to

)),((

pxcvwv Δ

′

⋅+⋅=

10: update global velocity according to

)),((

pxcvwv Δ

′

⋅+⋅=

11: normalise local velocity according to

},max{arg

,,,,

vvvv =

12: normalise global velocity according to

},max{arg

,,,,

vvvv =

13: update position according to

SSxx

⊕=

where

SS is determined from Algorithm 3

14: end for

15: end while

Algorithm 4. Combinatorial Optimisation PSO

Particle Swarm Optimization

302

Without loss of generality, consider the following objective function for the combinatorial

optimisation problem:

)(minarg xfx

Xx∈

∗

= Xx∈∀

Then, the personal best

p is the current best solution of the i -th particle found so far; i.e.

ττ

minarg= ,

],0( k∈∀

; and the global best

p is the current best solution of the global

swarm found so far; i.e.

ττ

minarg= ,

],0( k∈∀

, Ni∈∀ . The swarm of particles is said

to have reached an equilibria if and only if all the particles have reached a consensus on the

value of

p , i.e.,

ppp == . For asymptotic convergence, all the particles in the swarm

must globally asymptotically reach a consensus on the global best solution, such that

+∞→

= lim , and )min(

Xxx

== , Xji ∈∀ , ,

i ≠ . For convenience, Eq. (1a) and Eq.

(1b) are combined into compact matrix form:

⎥

⎦

⎤

⎢

⎣

⎡

⋅

⎥

⎦

⎤

⎢

⎣

⎡

⎥

⎦

⎤

⎢

⎣

⎡

⋅

⎥

⎦

⎤

⎢

⎣

⎡

+−

⎥

⎦

⎤

⎢

⎣

⎡

rcrc

wrcrc

2211

)(

(13)

which can be considered as a discrete-dynamic system representation of the original PSO

algorithm.

7.1 Equilibrium of the PSO

Before the main analysis results are presented, a brief introduction into algebraic graph

modelling of swarms is presented. The information flow in the swarm of particles can be

represented using an interconnected graph

),( EVG =

, where V is the enumerated set of

particles Vx

∈ , },,1{ Ni K∈ in the swarm, and VVE ×⊆ is the set of edge relations between

neighbouring particles. The order

V and size E of the graph G physically represents the

number of particles in the swarm and the number of edge connections. For a fully connected

swarm, each particle communicates with every other particle in the population, and the

graph is said to be complete. This is the case of the original PSO algorithm. The connectivity

of a graph is described by the square matrix

, with size V , and elements

a describing the

connectivity of adjacent vertices

and

, such that:

()

otherwise

, if

Exx

∈

⎩

⎨

⎧

(14)

The matrix

uniquely defines the connectivity of the graph G and is referred to as the

adjacency matrix. Associated with the adjacency matrix

is the graph Laplacian

, and its

Laplacian potential

Ψ :

)(

AL −ΛΛ=

−

(15)

A Particle Swarm Optimisation Approach to Graph Permutations

303

Lxx

=Ψ

(16)

where Λ is the square matrix containing the out-degree of each vertex along the diagonal,

and

is the concatenation of particles in the swarm. A well-known property of the

Laplacian potential is that it is positive semi-definite and satisfies the following sum-of-

squares property (Godsil and Royle, 2001):

()

Eji

xxxALxx R∈−=

∑

∈

(17)

Using Eq. (17), the objective is to show that the personal best positions of each particle

reaches a consensus (by way of equilibria) coincident to the global best of the swarm, i.e.

pp = , P∈∀ . Eq. (16) becomes:

()

Eji

kij

pppALpp R∈−=

∑

∈

(18)

where

p is the concatenated states of the personal best of each of the particles in the swarm.

The closed-loop dynamics of the global best position evolve according to the following

continuous-time dynamic equation:

Lpp Ψ−∇=−=

(19)

The equilibrium points of Eq. (19) correspond to stationary points of

and the region

outside of these points, the potential is strictly decreasing (Moreau, 2004); i.e., if

x is an

equilibrium of Eq. (18), then

Lx . From Eq. (16):

0)(

)( ==Ψ

eTee

Lppp (20)

Following the connectivity of

G , cpp

== , Nji ∈∀ , , i.e.

ccp ),,( K= , Xc∈ . Since the

Laplacian potential equals zero at equilibrium, then

)min(pp

= is an invariant quantity,

Given the invariance property of

)min(p , then ))0(min()min( pp

= , and cp

=)min( . This

implies ))0(min(

= , Pi∈∀ (Olfati-Saber and Murray, 2003). This leads to the following

observations for the particle dynamics in Eq. (1a) and Eq. (1b) that are consistent with the

works of (Clerc and Kennedy, 2002); (Trelea, 2003); and (Kadirkamanathan et al., 2006):

1. The system dynamics are stochastic and order two;

2. The system does not have an equilibrium point if

pp ≠ ;

3. If

ppp == is time invariant, there is a unique equilibrium at

px = .

An equilibrium point thus exists only for the best particle whose local best solution is the

same as the global best solution (Kadirkamanathan et al., 2006).

Consider the case for a given particle i when the external input is constant (as is the case

when no personal or global better positions are found). From Eq. (15) the eigenvalues of

−

Particle Swarm Optimization

304

are negative in the complex plane. Then, for particle i , the position asymptotically

converges to the point

x in the eigenspace associated to the global minimum found by the

swarm of particles (Olfati-Saber and Murray, 2003). Such a position

x is not necessarily a

local or global minimiser of the combinatorial optimisation problem. Instead, it will improve

towards the optimum

∗

x if a better individual or global position is found. Discovery of

better individual or global positions can be improved by increasing the population diversity

of the swarm through the introduction of chaos or turbulence (Kennedy and Eberhart, 1995).

In the following section, a non-stationary Markov chain is constructed to integrate the

discrete syntactic swap operators introduced in Section 5 to the continuous time-dynamics

of the traditional PSO

7.2 Non-Stationary Markov Model of combinatorial PSO

Markov chains are important in the theoretical analysis of evolutionary algorithms

operating on discrete search spaces (Poli et al., 2007) and have been used to model the

probabilistic convergence of population-based meta-heuristic algorithms (see (Rudolph,

1996); (Cao and Wu, 1997); (Poli and Langdon, 2007); and (Greenwood and Zhu, 2001) for

examples of their implementation). While traditional PSO has operated on a continuous

search space, the combinatorial PSO operates on a discrete combinatorial space. This makes

Markov chains a suitable method of modelling and analysing the behaviour of the

combinatorial PSO. The use of Markov chains on bare-bones PSO has previously been

investigated by (Poli and Langdon, 2007) where the continuous search space was discretised

using a hypercube sampling. In the following section, a non-stationary Markov chain is used

to model the combinatorial PSO and account for the newly introduced swap operator.

Let

denote the finite state space describing the set of permutation encodings with

!nXr == possible solutions. Let

⊂

be a population of solutions from

with size

NP = . Then a finite Markov chain

X⊆

describes a probabilistic trajectory over the finite

state space

(Rudolph, 1996) with )(

−+

−

N possible populations as states; i.e.:

},,,{

21 N

SSSX K= (21)

The probability )(Pr:

SSq =Γ=Γ=

−

of transitioning from state XS

∈ to XS

∈ ,

N∈nm, at step k is called the transition probability from

at step k . The transition

probability of a finite Markov chain can be gathered into a transition matrix }{

kkk

−

(Rudolph, 1994), where each dimension ]1,0[

∈

−

q . In a stationary Markov chain the

probabilities remain fixed, and the Markov chain is said to be homogenous; i.e.,

}{

kkk

qQQ

−

== , K,2,1=∀k , and N,,2,1, K=nm . In the case of the combinatorial PSO, the

probabilities of the swap operator are updated according to Eq. (8a) and Eq. (8b). This

results in a non-stationary Markov chain. The transition probabilities of non-stationary

Markov chains are calculated by considering how the population incidence vector

S describes the composition of the next iteration (Cao and Wu, 1997). Denote

vpxz

)Pr( == as the sampling probability when the personal best is

p ; likewise,

A Particle Swarm Optimisation Approach to Graph Permutations

305

denote

vpxz == )Pr(

as the sampling probability when the global best is

p . The

probability that a particle

i will move according to

px a or

px a

x is given by

)(

ppz U= . From Algorithm 3, the dimension for )Pr(

, i

pxz = and )Pr(

, g

pxz = is

calculated independently using Eq. (8a) and Eq. (8b) and the probability of a particle

sampling

p or

p is given by:

()

∏

dpdpdpdppp

)(),()()(Pr)Pr( UU (22a)

))(Pr())(Pr())(Pr())(Pr()Pr(

dpdpdpdppp

∏

⋅−+=U (22b)

Since personal bests can only change if there is a fitness improvement, only certain state

transitions can occur. That is, a transition from state

SS a

is possible only if the fitness of

at least one particle in the swarm improves (Poli and Langdon, 2007). Because of the

independence of the particles (over one time step), the state transition probability for the

whole PSO is given by:

∏

−

ppq )Pr(

U (23)

From Sec. 6.1, the local velocity

and global velocity

will tend to zero as +∞→k . This

implies

0limlimlim

===

∞→∞→−∞→

kkk

vvq , N,,2,1, K=nm . Therefore, the swap operator

preserves the convergent behaviour of traditional PSO and the combinatorial PSO converges

to the equilibrium pair

),(

vx .

8. Numerical Examples

8.1 The Travelling Salesman Problem

To test the efficiency of the proposed algorithm, the combinatorial optimisation PSO is

tested on the travelling salesman problem (TSP). TSP is an invaluable test problem that

belongs to the class of NP -hard combinatorial optimisation problems. The objective of

TSP is to find a minimum-cost tour that visits a set of

cities and returns to an initial

point (Applegate et al., 2006). Mathematically, TSP is a combinatorial optimisation

problem on an undirected graph

),( EVG = . Each city

][nc

∈

, ni ,,2,1 K= , is represented

by a vertex

∈ in the graph ),( EVG = with cost of travel between adjacent cities given

by Eh

∈ . A solution to TSP can be represented as a sequence of cities encoded by a

permutation

Xx∈ . Mathematically, the objective of TSP is given by the following

optimisation problem:

))1(),(())1(),((minarg

xnxhdxdxhxXx

ijXx

++=⇔∈

∑

−

∈

∗∗

(24)

Particle Swarm Optimization

306

Various problems, including path-finding, routing, and scheduling, can be modelled as a

TSP. A repository of test-instances (and their solutions) is available through the TSPLIB

library (Reinelt, 1991). In the following section, the combinatorial PSO is tested on several

instances of the TPSLIB library. Table 1 summarises the test instances of TSPLIB used to

validate and compare the combinatorial PSO.

Name Dimension

Optimal

)(xf

Optimal Solution

burma 14 30.8785

gr17 17 2085

gr24 24 1272

eil51 51 426

Table 1. Test instances taken from TSPLIB (Reinelt, 1991) used for the validation of the

combinatorial PSO

A Particle Swarm Optimisation Approach to Graph Permutations

307

8.2 Optimisation Results and Discussion

In the following experiments, the combinatorial PSO is applied to each case of the TSP in

Table 1. The parameters used in each experiment are selected based on the findings reported

in the literature (Zhang et al., 2005); (Shi and Eberhart, 1998a); (Zheng et al., 2003); (Clerc

and Kennedy, 2002); and (Eberhart and Shi, 2000). While the inertia weight, cognitive and

social parameters are sensitive to the problem domain in traditional PSO, a parametric

analysis of their influence on the combinatorial PSO is beyond the scope of this chapter. For

illustrative purposes, the parameters given in Table 2 are considered throughout the

remainder of this chapter. The influence of these parameters on the performance of the

combinatorial PSO remains the subject of future research.

Parameter Value

0.8

2.025

Table 2. Combinatorial PSO parameters

To demonstrate the relative efficiency of the proposed algorithm, the performance of the

combinatorial PSO is compared to a genetic algorithm. Each TSP experiment was trialled

100 times using randomly generated individuals. In both algorithms, a population of

30=P was maintained for each iteration. The fitness values obtained by the combinatorial

PSO and the GA over the 100 trials are presented in Table 3. Table 4 compares the success

rate of the PSO and GA for each of the problems. Figure 3 compares the percentage of the

solution space explored by the combinatorial PSO and the GA. This is determined as the

number of unique solutions tested Xx

∈ , Pi∈∀ , 1000,,1K=k by the PSO and GA versus

the size of the solution space

!nX =

Minimum Maximum Average

Problem

Optimal

Solution

PSO GA PSO GA PSO GA

burma 30.87 30.87 30.87 30.87 34.62 30.87 31.20

gr17 2085 2085 2085 2687 2489 2141.55 2175.02

gr24 1272 1272 1282 1632 1810 1453.52 1488.68

eil51 426 494.80 495.46 687.52 671.85 573.55 573.95

Table 3. Performance of the proposed algorithm compared to a traditional genetic algorithm

for combinatorial optimisation

From Table 3, the combinatorial PSO outperformed the GA in all problem instances, except

for the 51 variable eil51 problem. In this case, both the GA and combinatorial PSO failed to

find the best solution over the 100 trials. Examination of Fig. 3 suggests that both the

combinatorial PSO and GA were only able to search a small percentage (

%1<< ) of the total

solution space over the 1000 iterations. This suggests, that both the combinatorial PSO and

GA experience a loss of solution diversity over the optimisation procedure. Figure 3 also

Particle Swarm Optimization

308

indicates that the GA was able to cover a larger percentage of the solution space for each

trial than the combinatorial PSO. This suggests that the combinatorial PSO suffers from the

same rapid convergence and stagnation issues of traditional PSO. Loss of solution diversity

and rapid convergence is a well-known problem in traditional PSO. In traditional PSO, the

performance of the algorithm deteriorates as the number of iterations increases. Once the

algorithm has slowed down (becomes stagnant), it is usually difficult to achieve a better

fitness value; particularly for high-dimensionality problem spaces.

Success Rate (%)

Problem

PSO GA

burma 100 92

gr17 36 17

gr24 4 0

eil51 0 0

Table 4. Success rate of the combinatorial PSO and GA

Recently, several methods have been proposed to improve solution diversity and avoid

stagnation in traditional PSO. These methods include the use of chaos variables (Fieldsend

and Singh, 2002); (Kennedy and Eberhart, 1995); and (He et al., 2004); variable

neighbourhood topologies (Kennedy, 1999); and (Liu et al., 2007a); and mutation operators

(Liu et al., 2007b); and (Andrews, 2006). Many of these techniques have had varying levels

of success on the traditional PSO algorithm. It is expected, that these same strategies can be

adapted to the combinatorial PSO. Future work aims to investigate the potential to

implement these algorithmic improvements to the combinatorial PSO and solve for larger

scale combinatorial optimisation problems.

Average % Solution Space Searched

1.00E-60

1.00E-54

1.00E-48

1.00E-42

1.00E-36

1.00E-30

1.00E-24

1.00E-18

1.00E-12

1.00E-06

1.00E+00

Test Instances

% Solution Space Searched

PSO

1.58E-05 7.65E-09 2.05E-17 2.35E-60

2.54E-05 2.78E-08 3.34E-17 5.74E-59

burma gr17 gr24 eil51

Figure 3. Comparison of the solution space searched by the combinatorial PSO and the GA

A Particle Swarm Optimisation Approach to Graph Permutations

309

9. Conclusion

The PSO’s simplicity, robustness, and low computational costs, makes it an ideal method for

continuous optimisation problems. Previous efforts to adapt the traditional PSO algorithm

to combinatorial spaces have shown varying levels of success. In this chapter, a new

combinatorial optimisation PSO that builds on previous works is introduced. A distance

metric was introduced to define a metric space for the combinatorial optimisation problem

and a syntactic swap operator introduced. Motion was induced by associating a probability

sampling function to the velocity profile of a particle on the combinatorial space and

invoking the defined swap operator. The proposed algorithm was tested on several

instances of TSPLIB and compared to the performance of a GA. Preliminary test results

demonstrated superior performance over the GA in all test cases. For larger set sizes, the

proposed algorithm failed to converge to the optimal solution. Examination of the sampled

solution space suggested that the proposed algorithm suffered from the same rapid

convergence and stagnation issues observed in traditional PSO. Further research is needed

to clarify the effect of the various tuning parameters on the performance of the proposed

algorithm, and their influence on loss of solution diversity. The generalised approach to the

algorithm’s development allows for the consideration of other metrics on discrete spaces,

and the implementation of further algorithmic improvements. Future work aims to

investigate methods to mitigate the stagnation issues of the proposed algorithm and

extending the combinatorial optimisation PSO’s capabilities to other discrete optimisation

problems.

10. References

Aardal, K., Hoesel, S. v., Lenstra, J. K. and Stougie, L. (1997). A Decade of Combinatorial

Optimization. Department of Information and Computing Sciences, Utrecht

University, UU-CS-1997-12,

Aguilar, J. (2001). A General Ant Colony Model to solve Combinatorial Optimization

Problems. Revista Colombiana De Computación, 2, 7 - 18.

Andrews, P. S. (2006). An Investigation into Mutation Operators for Particle Swarm

Optimization, Proceedings of IEEE Congress on Evolutionary Computation, pp. 1044 -

1051, Vancouver BC, Canada, July,

Applegate, D. L., Bixby, R. E., Chvátal, V. e. and Cook, W. J. (2006). The Traveling Salesman

Problem, Princeton University Press, New Jersey.

Bean, J. (1994). Genetic Algorithms and Random Keys for Sequencing and Optimization.

ORSA Journal on Computing, 6, 154 - 160.

Bóna, M. (2004). Combinatorics of Permutations, Chapman & Hall/CRC, New York.

Bonyadi, M. R., Azghadi, S. M. R. and Hosseini, H. S. (2007). Solving Traveling Salesman

Problem Using Combinational Evolutionary Algorithm, In Artificial Intelligence and

Innovations 2007: From Theory to Applications, Vol. 247 (Eds, Boukis, C.,

Pnevmatikakis, L. and Polymenakos, L.) Springer, Boston, pp. 37 - 44.

Cao, Y. J. and Wu, Q. H. (1997). Convergence Analysis of Adaptive Genetic Algorithms,

Proceedings of Genetic Algorithms in Engineering Systems: Innovations and Applications,

pp. 85 - 89, 2 - 4 September,

Particle Swarm Optimization

310

Clerc, M. and Kennedy, J. (2002). The Particle Swarm - Explosion, Stability, and

Convergence in a Multidimensional Complex Space. IEEE Transactions on

Evolutionary Computation, 6, 58 - 73.

Eberhart, R. C. and Shi, Y. (2000). Comparing Inertia Weights and Constriction Factors in

Particle Swarn Optimization, Proceedings of IEEE Congress on Evolutionary

Computation, pp. 84-88, San Diego, CA,

Festa, P. and Resende, M. G. C. (2008). Hybrid Grasp Heuristics. AT&T Labs Research,

Florham Park, July

Fieldsend, J. E. and Singh, S. (2002). A Multi-Objective Algorithm Based Upon Particle

Swarm Optimisation, an Efficient Data Structure and Turbulence, Proceedings of UK

Workshop on Computational Intelligence, pp. 37 - 44, UK,

Godsil, C. and Royle, G. (2001). Algebraic Graph Theory, Springer-Verlag, New York.

Goldberg, D. and Lingle, J. R. (1985). Alleles, Loci and the TSP, Proceedings of First

International Conference on Genetic Algorithms and Their Applications, pp. 154 - 159,

Hillsdale, Hew Jersey,

Greenwood, G. W. and Zhu, Q. J. (2001). Convergence in Evolutionary Programs with Self-

Adaptation. Evolutionary Computation, 2, 147 - 157.

He, S., Wu, Q. H., Wen, J. Y., Saunders, J. R. and Paton, R. C. (2004). A Particle Swarm

Optimizer with Passive Congregation. Biosystems, 78, 135 - 147.

Kadirkamanathan, V., Selvarajah, K. and Fleming, P. J. (2006). Stability Analysis of the

Particle Dynamics in Particle Swarm Optimizer. IEEE Transactions on Evolutionary

Computation, 10, 245 - 255.

Kennedy, J. (1999). Small Worlds and Mega-Minds: Effects of Neighborhood Topology on

Particle Swarm Performance, Proceedings of Congress on Evolutionary Computation,

pp. 1931 - 1938, Washington DC, USA,

Kennedy, J. and Eberhart, R. (1995). Particle Swarm Optimization, Proceedings of IEEE

International Conference on Neural Networks, pp. 1942-1948, 27th November - 1

December, 1995,

Kennedy, J. and Eberhart, R. C. (1997). A Discrete Binary Version of the Particle Swarm

Algorithm, Proceedings of IEEE International Conference on Systems, Man, and

Cybernetics, pp.

Knuth, D. E. (1998). The Art of Computer Programming, Addison-Wesley, Reading.

Liu, H., Abraham, A. and Grosan, C. (2007a). A Novel Variable Neighborhood Particle

Swarm Optimization for Multi-Objective Flexible Job-Shop Scheduling Problems,

Proceedings of 2nd International Conference on Digital Information Management, pp. 138

- 145, October,

Liu, J., Fan, X. and Qu, Z. (2007b). An Improved Particle Swarm Optimization with Mutation

Based on Similarity, Proceedings of Third International Conference on Natural

Computation, pp. Haikou, China,

Martínez García, F. J. and Moreno Pérez, J. A. (2008). Jumping Frogs Optimization: A New

Swarm Method for Discrete Optimization. Department of Statistics, O. R. and

Computing, University of La Laguna, Tenerife, Spain, DEIOC 3/2008,

Misevicius, A., Blažauskas, T., Blonskis, J. and Smolinskas, J. (2004). An Overview of Some

Heuristic Algorithms for Combinatorial Optimization Problems. Information

Technology and Control, 30, 21 - 31.