Swarm Routing
  Clockless Processors
 

Autonomous Agents

  Mobile Communication
  Genetic Algorithms
  Swarm Intelligence
  Neural Networks
  Machine 2 Machine
  Grid Computing
  Ultra-Wideband Tech
 
Bluetronix, Inc.
35 River Street
Chagrin Falls, OH 44022
440.247.3434
innovation@bluetronix.net

 

Technologies>Swarm Intelligence

Traveling Salesman
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.

 
   
   
Copyright 2006 Bluetronix, Inc. | All Rights Reserved