Information Technology Reference
In-Depth Information
However, in both the previous cases, each agent searches for the global solution to
the problem in question, therefore in this sense the cooperation is complementary to
a competition, because each agent wants to win the “solver cup”.
Algorithms based on strategies of cooperation and distribution try to assemble
solutions by composing some partial solutions devolved to the single agents. In
some cases the agent population is articulated in many levels or roles, and even
the structure of a solution strategy can reflect this articulation, in such a way that
any agent is required only for some steps and in different phases of construction of
the solution. All these cases are strongly suggested by mechanisms found in nature
(bacteria, ants, and bees).
A paradigm very useful in optimization problems is the
swarm intelligence
.It
refers to situations where a collective solution emerges from many coordinated in-
dividual behaviors that follow simple rules of action and communication, usually
driven by common finalities (reaching a place, searching for food, escape from a
danger, and attack an enemy). Special cases of swarm intelligence are: ACO (Ant
Colony Optimization), PSO (Particle Swarm Optimization), and FSO (Flock of Star-
lings Optimization). A similar idea inspired a computational model, called
Boids
that was elaborated in 1987 [149], where the flocking behavior of birds (in a stereo-
typical New York pronunciation boids corresponds to birds) is simulated by using
very simple rules aimed at avoiding trajectory conflicts, at keeping spatial vicinity,
and at sharing move direction.
Many aspects of animal intelligence, even if based on specific phenomena, are
easily representable in computational terms. For example, the method of ACO (Ant
Colony Optimization) is used for the search for a minimum path between two points.
Each ant going from a point A to a point B follows, at first casually, an itinerary.
However, during the journey each ant releases on the ground a substance, called a
pheromone
. If we assume that only some paths can be followed; of course the paths
which are shorter are also the paths traversed by more ants and consequently having
more pheromone along them. In this way, paths richer in this substance have a major
score, and in this way the solution
emerges
automatically as a consequence of the
population-based strategy the ants follow.
Apart from the application to optimization problems [148], swarm intelligence
and similar paradigms could play a crucial role in the definition of algorithmic mod-
els of biological behaviors. In fact, if rules and computations can be established that
are able to reproduce some behaviors, this can shed light on the possible internal
mechanisms that are responsible of emergent functionalities in biological popula-
tions (of particles, cells, and animals).
In concluding the section, we mention the
self-assembly algorithms
, which ap-
ply a natural mechanism that is based on DNA computing algorithms and other
algorithms which are inspired by DNA recombinant power. In this case, a solution
is constructed by connecting some basic pieces which have an intrinsic tendency
to assemble with other pieces, according to forces attracting them toward com-
plementary pieces. In other words, any piece follows a local satisfaction principle
which is reached when it combines with its correct companion. In this way, struc-
tures are generated spontaneously which provide some possible solutions for a given
