Information Technology Reference
In-Depth Information
almost all species have a
punctuated equilibrium
[3], [4] that makes them intimately
connected. Any perturbation of this equilibrium involves large fluctuations, called
critical avalanches
[3], in the configuration of the fitness values, potentially making
any configuration accessible when the system slides back to a self-organization state.
The BS model demonstrated that the duration
t
of that avalanches follow a power-law
distribution
()
P
t
∝
t
−
, where the avalanche exponential τ is a small real number
close to 1.
Extremal Optimization (EO) is a heuristic search method introduced by Boettcher
and Percus [5] for solving combinatorial and physical optimization problems. It was
motivated by the Bak-Sneppen model [3] which was converted into an incomplete
optimization algorithm. EO heuristic search can be outlined as follows. Let consider a
system described by a set of
N
species
x
i
with an associated fitness value
λ
i
also
()
called individual cost [5]. The cost function
C
S
of a configuration
S
consists of the
individual cost contributions
λ
i
. EO starts from an initial random state of the system
and at each step performs search on a single configuration
S
. The variables are ranked
from the worst to the best according to their fitness values and the variable with the
smallest fitness value is randomly updated. The configuration with minimum cost is
then maintained. The rank ordering allows EO to preserve well-adapted pieces of a
solution, while updating a weak variable gives the system enough flexibility to ex-
plore various space configurations.
An improved variant of EO [6], [7], called τ-EO, consists to rank all variables
from rank
n
=1 for the worst fitness to rank
n
=
N
for the best fitness λ. According to
the BS model, a power-law distribution over the rank order is considered. For a given
value of τ,
()
(
)
(1)
−
τ
P
n
∝
n
,
1
≤
n
≤
N
()
P
and change the state of the vari-
able
x
k
. The variable with rank 1 (worst variable) will be chosen most frequently,
while the higher ones will sometimes be updated. In this way, a bias against worst
variables is maintained and no rank gets completely excluded from the selection
process. However, the search performance depends on the value of the parameter
At each update, select a rank
k
according to
τ
.
For
=0, the algorithm is simply a random walk through the search space. While for
too large values of τ the process approaches a deterministic local search where only a
small number of variables with particularly bad fitness would be chosen at each itera-
tion. An optimal value of τ will allow even the variable with the highest rank to be
selected during a given run time. Boettcher and Percus [7] have established a relation
between τ, the run time
t
max
and the number
N
of the variables of the system, to esti-
mate the optimal value of τ. Let
t=AN
where
A
is a constant, then
()
τ
(
)
ln
A
ln
N
(
)
(2)
τ
~
1
+
N
→
∞
,
1
<<
A
<<
N
()
ln
N
Search WWH ::
Custom Search