|
04/04/2000
Traveling Salesmen and Computerized Ants
Have you heard the one about the traveling salesman? No, this
one does not involve a farmer''s daughter; in fact, it''s not even a
joke. Suppose you own a company making widgets and you
want your sales rep to take a sales tour of 15 cities scattered all
over the country. Since your guy or gal is on an expense account
you want his or her overall route to be the shortest possible and
you''d like not to duplicate visits to any of the cities. Now, you
might think that it shouldn''t be too difficult to come up with the
shortest route, especially if you have a computer handy. Not so!
There are billions of possible routes available and solving this
"traveling salesman" problem has occupied mathematicians for
many years.
When I was at Bell Labs in those ancient days of the old Bell
System, we had in a darkened area of our reception lobby a huge
map of the U.S. This map had little colored lights lighting up
the various telephone linkages to the various cities. It was a
beautiful display of the complexity of the Bell System and
illustrated the problem of rerouting telephone calls in cases of
breakdowns or overloading of circuits. This telephone routing is
not unlike the routing problems of our traveling salesman. Some
years ago, a mathematician by the name of Karmarkar at Bell
Labs made a big splash with an approach to the traveling
salesman problem that made an approximation to the ultimate
solution less tedious and quicker for the computers to handle. As
I recall, Karmarkar''s "linear programming algorithm" was
patented and licensed to customers with problems of a similar
nature.
Another approach to this problem has now arisen based on the
study of ants and their own technique for solving the traveling
salesman problem. An article by two French authors in the
March 2000 Scientific American titled "Swarm Smarts"
describes the concept of "swarm intelligence". The ant
exemplifies swarm intelligence in that each individual ant seems
to be on its own; yet, as a group or swarm, difficult feats can be
accomplished in what appears to be a highly organized manner.
Take the problem of finding and retrieving a source of food,
perhaps a plump juicy caterpillar. Suppose there are two paths to
get to the caterpillar, one pretty direct, the other around a tree
stump and three times as far a trip. How do the ants tend to
gather in large numbers and take the shorter path to the food?
The answer lies in pheromones. Pheromones are chemical
substances emitted or deposited by many creatures, typically to
attract mates. (There is, I believe, still some concern as to
whether humans also use pheromones for the same purpose.)
But, sex aside, the issue here is sustenance. What has been found
is that, with the ant species L. humile, a foraging ant lays down a
trial of pheromone on its quest for food. This pheromone attracts
the attention of the other ants. Suppose that in their search for
the caterpillar, two ants leave the nest at the same time. Ant A
happens to take the short path, while ant B goes around the
stump. Ant A stumbles upon the caterpillar first and reports back
to the nest retracing his steps along path A, laying down
pheromone along the way. When he arrives near the nest, path A
now has double the amount of pheromone as path B, ant B being
still out there looking for food. The ants near the nest will
naturally be attracted to the double-strength scented path A and
follow it to the caterpillar, depositing their own pheromone. By
the time ant B gets back to the nest, all excited by his find of the
caterpillar, the other ants ignore him because by then path A has
much more pheromone than the now double-strength path B. So,
we see a steady stream of ants traveling back and forth in a
continuous line on the shorter path. It''s not that the individual
ant is all that brainy. It''s the fact that the simple act of laying
down the pheromone results in "swarm intelligence".
"Wait a minute", some of you might say. What if Ant A either
stayed home in the nest or dawdled around along path A and ant
B scooted quickly along path B and got back before ant A?
You''re right. The other ants would naturally follow path B and
reject ant A''s pleas that his route was shorter, path B already
being more heavily scented with pheromone. This was indeed
shown experimentally. Swarm intelligence in this case seems
more like swarm stupidity.
Let''s now bring into the picture the computer software guys such
as Marco Dorigo of the Free University in Brussels. He wrote
software that attempts to make "artificial" ants with the ability to
do the equivalent of laying down pheromone as they travel. But
Dorigo made the swarm intelligence of these artificial ants
greater than that of the real insects. Specifically, he introduced
two features that make a lot of sense. First, the pheromone
deposited along a path is allowed to "evaporate" over a period of
time. This feature helps to avoid the situation described in the
preceding paragraph where the ants get locked into the longer
path. With an evaporating pheromone, there would be less of it
after ant B''s round trip because of the longer distance and time to
complete the trip. A second, very helpful feature with the
artificial ants is that the amount of pheromone laid down is made
greater for shorter trips. This certainly imbues these ants with a
degree of "intelligence" not found in the real ants.
Ok, now we turn these artificial ants loose to randomly meander
along whatever paths they "choose" to cover the 15-city routes of
our salesman. When they''ve all returned and the proper
assignments of pheromone strengths are made to each link, the
ants are sent out again and the process is repeated. Sure enough,
as the process was repeated over and over again, the overall trips
became shorter and shorter in length. Not surprisingly, it was
found that the longer links in a shorter overall tour might be
rejected initially. However, eventually they would be stumbled
on by chance and then reinforced with pheromone and eventually
win out. Of course, the strengths of the pheromone in these
simulations must simply be designated by some form of
numerical assignments, I assume.
While the artificial ants have not come up with the ultimate
shortest overall tour of the 15 cities, the resulting tour distances
prove quite adequate and worth the effort. The article mentions
that an advantage of these calculations is that additional paths are
delineated in case links are blocked on the shortest tour. These
same types of calculations can be used to route our telephone
calls or data transmission when lines get overloaded or blocked,
due to various causes.
I remember AT&T once sponsored a phone-in sale of a popular
AT&T computer, just for AT&T employees. The response was
so great that, AT&T had to block the number for fear of bringing
down the whole phone system in certain areas of the country! I
carried my cordless phone around with me for a whole weekend,
punching REDIAL repeatedly only to get a busy signal. AT&T
apologized to the employees for the problem and it turned out all
the computers had been sold within a couple of hours of the sale.
Returning to the ants, another interesting feat is their apparent
organization in carrying an object, be it a caterpillar or a leaf
back to the nest. Again, it seems to be a case of swarm
intelligence. Guided by the knowledge of the direction to their
nest, perhaps via the pheromone trail, the ants converge on the
leaf, for example. We''ve all seen pictures of ants lined up
perfectly single file like little soldiers carrying their burden.
Careful observations have shown that initially they actually line
up randomly pushing or pulling this way and that. Only
gradually do they shift positions when they realize the overall
motion is not in the nest direction. Finally, they all get lined up
in the right direction to accomplish their task. While it looks
very organized, they got to their positions by random actions.
This aspect of ant behavior has also been mimicked, this time at
the University of Alberta, using a bunch of mechanical robots.
The robots were deliberately programmed with very simple
instructions: (1) find a lighted box, (2) place yourself between
the box and a lighted goal and (3) push the box towards the light.
The article showed a sequence of pictures of the behavior of 5 of
these robots setting out on their mission to push the box to the
goal. They all started out in a corner of the enclosure. Four of
the robots found the box and though not lined up in a military
fashion like the ants, managed to move the box towards the goal,
a beam of light. I was taken by the behavior of the 5th robot,
which was attracted to the goal, not the box. The robot seemed
to realize its mistake and retreated back to a neutral corner to
start over again.
After reading this article, I found myself wondering if maybe we
humans aren''t quite as intelligent as we give ourselves credit for.
In some respects we sure seem to be driven by swarm behavior.
At least that''s what the advertisers on TV hope happens, us
swarming to their products. Not to mention in this election year
the all-out efforts to win our votes.
Back to insects, in last week''s column I said it would be the last
one originating from Marco Island. Somehow, in our last few
days here, I had a sudden burst of energy - hence this column.
Perhaps this energy came from the ingestion of hundreds, maybe
thousands of no-see-ums (spelling?) at a lunch on the beach at a
hotel in Naples. In case you''ve been fortunate enough not to
encounter this particular member of the insect family, these were
like tiny specks of moving cinnamon. The occasion was an
annual mini-reunion of some fellow alumnae (they were all
women) of Dickinson College and some spouses. The no-see-
ums invaded our table, seemingly by the zillions and, spreading
rapidly over our bodies and in our hair, caused intense itching. It
was the only time in my life when a waitress has served a can of
aerosol bug repellant along with our grouper sandwiches! Said
sandwiches and my Bloody Mary obviously had also been
invaded by these barely visible little guys but, hey, we
Dickinsonians are a hardy (foolish?) bunch and finished our
meal, no-see-ums and all! We did forego the key lime pie for
dessert, however. The next column will absolutely originate
back in New Jersey, where we only have to worry about ticks
carrying Lyme disease and possibly mosquitoes with some kind
of East (or is it West?) Nile virus.
Allen F. Bortrum
|
