Geology Reference
In-Depth Information
Table 9. PSO convergence parameters
Symbol
Description
Details
t
max
Maximum number of iterations for the
termination criterion.
Determined by the complexity of the problem to be optimized, in
conjunction with other PSO parameters (
n
,
NP
).
k
f
Number of iterations for which the relative
improvement of the objective function satis-
fies the convergence check.
If the relative improvement of the objective function over the last
k
f
iterations (including the current iteration) is less or equal to
f
m
, con-
vergence has been achieved.
f
m
Minimum relative improvement of the value
of the objective function.
PSO for Integer Optimization
The algorithm was inspired by the behaviour of
real ants in nature. In many ant species, individu-
als initially wander randomly and upon finding
a food source return to their colony, depositing
a substance called
pheromone
on the ground.
Other ants smell this substance, and its presence
influences the choice of their path, i.e. they tend
to follow strong pheromone concentrations rather
than travelling completely randomly, returning
and reinforcing it if they eventually find food.
The pheromone deposited on the ground forms
a
pheromone trail
, which allows the ants to find
good sources of food that have been previously
identified by other ants.
As time passes, the pheromone trails start to
evaporate, reducing their strength. The more time
it takes for an ant to travel down a path and back
again, the more time the pheromone trail has to
evaporate. A short path gets marched over faster
than a long one, and thus the pheromone density
remains high as it is laid on the path faster than
it can evaporate. If there was no evaporation, the
paths chosen by the first ants would tend to be
excessively attractive to the following ants and
as a result the exploration of the solution space
would be constrained. In that sense, pheromone
evaporation helps also to avoid convergence to
a locally optimal solution. Positive feedback
eventually leads to most of the ants following a
single “optimum” path.
The idea of the ant colony algorithm is to mimic
this behaviour with simulated ants walking around
the graph representing the problem to solve. The
Since both problems defined in previous section
are integer optimization problems, discrete opti-
mization algorithms are required. For the Step 1
optimization problem described in previous sec-
tion, a discrete version of the PSO algorithm is
employed. In the continuous version of the PSO
method, both particle positions and velocity are
initialized randomly. In this work, the particle
positions are generated randomly over the design
space using discrete Latin Hypercube Sampling,
thus guaranteeing that the initial particle positions
will be integers in the acceptable range. Further-
more, in the case of discrete optimization and in
particular in integer programming, at every step
of the optimization procedure, integer particle
positions should also be generated. In order to
satisfy this, Eq. (7) is modified as follows
(
)
+
(
)
v
j
(
t
+ =
1
)
round
w t
v
j
( )
+
c
r
x
Pb,
j
−
x
j
( )
t
c
r
x
Gb
−
x
j
( )
t
1 1
2 2
(11)
where the vector function
round
(
x
) rounds each
element of the vector
x
into the nearest integer.
ANT COLONY OPTIMIZATION
The
Ant Colony Optimization
(ACO) algorithm
is a population-based probabilistic technique for
solving optimization problems, mainly for finding
optimum paths through graphs (Dorigo, 1992).
Search WWH ::
Custom Search