Geology Reference
In-Depth Information
similar to all problems that have been proven to
be NP-hard (Lawler, 1985).
Consider a TSP with
N
cities (vertices or
nodes). The TSP can be represented by a complete
weighted graph G=(N,A), with N the set of nodes
and A the set of arcs (edges or connections) that
fully connects the components of N. A cost func-
tion is assigned to every connection between two
nodes
i
and
j
, that is the distance between the two
nodes
d
i
,
j
(
i
≠
j
). In the symmetric TSP, it is
d
i
,
j
=
d
j
,
i
.
A solution to the TSP is a permutation
p
={
p
(1),
…,
p
(N)} of the node indices {1, …, N}, as every
node must appear only once in a solution. The
optimum solution is the one that minimizes the
total length
L
(
p
) given by
and position according to its own “experience”
as well as the experience of other (neighbouring)
particles. Particle's experience is built by tracking
and memorizing the best position encountered.
As every particle remembers the best position it
has visited during its “flight”, the PSO possesses
a memory. A PSO system combines local search
method (through self-experience) with global
search method (through neighbouring experience),
attempting to balance exploration and exploitation.
Mathematical Formulation of PSO
Each particle maintains two basic characteristics,
velocity and position, in the multi-dimensional
search space that are updated as follows
N
−
∑
1
(
)
+
L
( )
p
=
d
d
1
(5)
p i p i
( ), (
+
1
)
p N p
(
), ( )
(
)
+
(
)
j
j
Pb,
j
j
Gb
j
v
(
t
+ =
1
)
w t
v
( )
+
c
r
x
−
x
( )
t
c
r
x
−
x
( )
t
i
=
1
1 1
2 2
(7)
Thus, the corresponding prioritization problem
is defined as follows
j
j
j
x
(
t
+ =
1
)
x
( )
t
+
v
(
t
+
1
)
(8)
( )
i
where
v
j
(
t
) denotes the velocity vector of particle
j
at time
t
,
x
j
(
t
) represents the position vector of
particle
j
at time
t,
vector
x
Pb,
j
is the personal 'best
ever' position of the j
th
particle, and vector
x
Gb
is
the global best location found by the entire swarm.
The acceleration coefficients
c
1
and
c
2
indicate
the degree of confidence in the best solution found
by the individual particle (
c
1
- cognitive param-
eter) and by the whole swarm (
c
2
- social param-
eter), respectively, while
r
1
and
r
2
are two random
vectors uniformly distributed in the interval [0,
1]. The symbol “
” of Eq. (7) denotes the Had-
amard product, i.e. the element-wise vector or
matrix multiplication.
Figure 4 depicts a particle's movement, in
a two-dimensional design space, according to
Eqs. (7) and (8). The particle's current position
x
j
(
t
) at time
t
is represented by the dotted circle
at the lower left of the drawing, while the new
position
x
j
(
t
+1) at time
t
+1 is represented by the
dotted bold circle at the upper right hand of the
n
−
∑
1
SB
1 ...,
N
IG
min
d SB SB
(
,
)
+
d SB
(
,
SB
) ,
i
=
,
k
k
+
1
( )
i
1
n
SB
k
=
1
(6)
where
d
(
SB
k
, SB
k
+1
) is the distance between the
building block
SB
k
and
k
+1
th
. The main objective
is to define the shortest possible route between
the structural blocks that have been assigned in
Step 1
to each inspection group.
PARTICLE SWARM
OPTIMIZATION ALGORITHM
In a PSO formulation, multiple candidate solutions
coexist and collaborate simultaneously. Each solu-
tion is called a “particle” that has a position and
a velocity in the multidimensional design space.
A particle “flies” in the problem search space
looking for the optimal position. As “time” passes
through its quest, a particle adjusts its velocity
Search WWH ::
Custom Search