Information Technology Reference
In-Depth Information
4.2
Bio-inspired Algorithms
Nature computes when it elaborates the biological information involved in complex
processes by means of specific sophisticated mechanisms of control, coordination,
organization, and finalization of particular objectives. As we have already noticed,
natural computing can be seen as a perspective intrinsically related to computer sci-
ence. If natural systems are the most complex systems we know, and if any complex
system can work on the basis of a related system of information elaboration, the
analysis of living phenomena from a computational perspective is appropriate in the
same manner as it is appropriate to observe birds for designing flying objects.
In this section, we present some relevant algorithmic paradigms directly sug-
gested by nature. The main stress of this analysis is on the algorithms rather than on
the systems for realizing them. The latter pertain to “hardware”, for example, DNA
computing or Membrane computing, but also Neural Computing [9, 8], or Cellu-
lar automata (introduced by von Neumann) [161], while the former pertain to the
methods and the paradigms for designing resolutive strategies for specific classes of
problems.
The unifying aspects of all the methods we present briefly are the
population-
based strategies
. In a sense, all the algorithmic methods suggested by nature have
in common, even if at different levels, the notion of populations of individuals and
the solutions are found by means of suitable processes pushing an initial population
(of solutions or of solvers) to evolve toward a final state providing the solutions we
search for.
These algorithms apply usually to problems of a combinatorial or optimization
nature. In fact, their strategies are typical of situations which nature has to cope
with, for finding the best cases satisfying the constraints imposed by life.
Evolutionary algorithms [127] follow a general (abstract) schema of resolution
that is suggested by the basic mechanism of Darwin's natural selection.
Ta b l e 4 . 3
The general schema of an evolutionary algorithm
Initialize
the population
S
of solutions with a set
S
0
of
possible solutions
Evaluate
a
fitness
level
F
over
S
,and
while
F
is under a given threshold
do
Select
a subset
S
of
S
Expand
S
into a population
S
according to a
generation
mechanism
done
Output
the population
S
reaching the fitness threshold.
The fitness function and the threshold value depend on the specific problem under
investigation. However, crucial and particular features of evolutionary algorithms
are the selective and the evolutive mechanisms. For example, each solution can pro-
vide new solutions by using casual changes or by specializing certain aspects, and
then the solutions which solve, at least a given fraction of test cases, are selected.
