content_image/434203.jpg content_image/434221.jpg content_image/434224.jpg content_image/434207.jpg content_image/434212.jpg content_image/434206.jpg
<img src='content_image/434203.jpg'>

## III. PARTICLE SWARM OPTIMIZATION 

The PSO algorithm is first described in terms of a general fitness function λ ( θ ), over some parameter set θ . Later, we specialize the discussion to the case of the binary inspiral testbed. 

Let θ = { θ$_{1}$, θ$_{2}$, . . . , θ$_{D}$ } denote a point in R $^{D}$, and λ ( θ ) be the fitness function. The essential idea behind PSO is to compute λ ( θ ) simultaneously at several locations and use these samples to influence the locations for computing the next set of samples. This process continues iteratively until some stopping rule is satisfied. The process can be visualized by treating the sample locations as a swarm of particles that moves in R $^{D}$, hence the name of the algorithm. A precise description now follows. D th 

Let the coordinates in R of the i particle in a swarm of N$_{p}$ particles be Q$_{i}$ [ k ] at the k th step in the search ( k = 0 , 1 , . . . ). Associated with this particle is a velocity vector V$_{i}$ [ k ] that determines Q$_{i}$ [ k + 1], 

The PSO algorithm is usually started with randomly cho- sen particle locations and velocities. In our implementa- tion, we position the particles initially on a regular grid while the initial velocities are kept random. th 

Let the maximum value of λ ( θ ) found by the i parti- cle over k steps be R$_{i}$ ( k ) and the location of R$_{i}$ ( k ), called the particle’s best location pbest , be P$_{i}$ [ k ]. Thus, 

## A. The PSO Algorithm 

<img src='content_image/434221.jpg'>

<img src='content_image/434224.jpg'>

Let the maximum over { R$_{i}$ ( k ) } , i = 1 , . . . , N$_{p}$ , be R$_{g}$ ( k ) and its location, called the global best location gbest be P$_{g}$ [ k ], 

At any step, there is always one particle in the swarm whose pbest is also the gbest . We call this particle the best particle at step k . Note that both pbest and gbest are locations found over the entire past history of the motion of the particles. They need not necessarily change at every step. th 

The velocity for the i particle at the next step, k + 1, is determined by the dynamical equation, 

<img src='content_image/434207.jpg'>

where w , which can depend on k , is called the inertia weight , c$_{1}$ and c$_{2}$ are called acceleration constants , and χ$_{1}$ , χ$_{2}$ are random numbers drawn independently at each step from the uniform distribution on [0 , 1]. 

Finally, for any component V$_{i,m}$ [ p ] of the particle ve- locity V$_{i}$ [ p ] = ( V$_{i,}$$_{1}$ [ p ] , . . . , V$_{i,D}$ [ p ]), 

<img src='content_image/434212.jpg'>

where V$_{max}$$_{,k}$ > 0, k = 1 , . . . , D , and V$_{max}$ = ( V$_{max}$$_{,}$$_{1}$, . . . , V$_{max}$$_{,D}$ ) is called the maximum velocity . 

Like all stochastic methods, PSO involves a compe- tition between wide ranging exploration of the fitness function and convergence to a best value. In order to avoid trapping by a local maximum, the method must be able to explore other parts of the parameter space, while to find the global maximum, the method must eventu- ally explore a progressively smaller region around some point. The way this competition is implemented in the PSO algorithm is seen clearly from Eqs. 10. The first term simply moves a particle along a straight line, while the remaining two terms are sources of acceleration, one pulling it towards its pbest and another pulling it towards gbest . The last two effects are combined with random weights χ$_{1}$ and χ$_{2}$ . The random deflections and inertial motion allow a particle to explore the fitness function, while the attractive pulls of pbest and gbest counter this behavior. With a dynamic inertia weight that decreases in time, the attractive pull eventually wins over. A rudi- mentary emulation of real biological swarming behavior is built in through each particle being aware of gbest . The PSO algorithm has another interesting feature. The best particle, by definition, has its pbest P$_{i}$ [ k ] coin- cident with gbest , P$_{g}$ [ k ], making the terms P$_{i}$ [ k ] − Q$_{i}$ [ k ] and P$_{g}$ [ k ] − Q$_{i}$ [ k ] equal for it. This particle then acceler- ates towards gbest alone and only moves along a straight line through this location. This situation continues un- til a new gbest is found. In effect, one particle at any step shows a convergence behavior, exploring the neigh- borhood of the current gbest , while the other particles continue their exploration. 

<img src='content_image/434206.jpg'>

