|
|
 |
Swarm
Intelligence has been applied to the classic Traveling Salesman
Problem. This challenge asks for the shortest distance a salesman
must travel if he is to visit N different cities. Though the problem
statement appears trivial, it has survived for more than 150 years
without a general solution. The use of swarm intelligence, specifically
ant systems, has been quite successful in finding the salesman's
optimal path. Its success can be attributed to the fact that swarm
intelligence excels in combinatorial optimization problems. Locating
the optimal path mirrors the process of ants foraging for food.
In both cases, ants are dispersed randomly in search of the nearest
city. The ant that returns first communicates its findings to the
colony. This communication attracts other ants and "directly reinforces
[a] good solution" (Bonabeau). Information sharing is essential
to swarm intelligence and useful in helping the salesman to find
the best path.
Within
the realm of combinatorial optimization, swarm intelligence finds
its niche in routing applications and in specialized job scheduling
tasks. Not surprisingly, these two applications correlate very well
with two fundamental traits of swarm intelligence: positive feedback
and division of labor. As Bonabeau explains in a recent article
in Nature, communications "routing is the control mechanism that
directs every message in a communications network from its source
node to its destination node through a sequence of intermediate
nodes or switching stations" (Bonabeau). The key to maintaining
global, self-organized behavior is the social interaction between
the system's individuals. In routing, true problems arise when portions
of a network become congested and new routes must be found rapidly.
However, the dynamic capability of swarm intelligence trivializes
this concern.
Besides
the mechanism of positive feedback, the cooperative nature of social
insect swarms has other features to offer to the study of combinatorial
optimization problem solving. One such feature is division of labor.
Insects efficiently allocate specialized tasks and display extreme
versatility among different jobs; as a result, their collective
behavior has become a model for dynamic task scheduling problems.
The Job-Shop Scheduling Problem, for instance, is a challenge in
assigning jobs to machine times such that no two jobs are being
performed on the same machine at a given time and job completion
times are minimized. Needless to say, this optimization problem
is of practical relevance to industry managers whose aim is to maximize
profits. Swarm intelligence has been shown to successfully solve
the Job-Shop Scheduling Problem for up to 10 jobs and 15 machines
(Bonabeau ).
Real
world examples:
White
papers on our products and technologies are available upon request.
E-mail us at innovation@bluetronix.net
or call 440.247.3434.
|
