Chapter 90 15.8 The Algorithmic Talent of Ants

A group of researchers in Milan, Italy, has proposed some new methods of evolution and learning.Their approach fills some of the gaps in what Akeley refers to as "the space of all possible computations."The researchers dubbed their search method the "ant colony algorithm" because they were inspired by the collective behavior of ant colonies. Ants figured out the distributed parallel system.Ants represent both the history of social organization and the future of computing.A colony may contain hundreds of workers and hundreds of queens, and they can build a city, although each individual is only vaguely aware of the presence of the others.Ants swarm across fields to find good food as if they were giant compound eyes.They travel in coordinated parallel ranks among the grass and trees, and together they keep their nests at a constant temperature, although no ant in the world has ever known how to regulate the temperature.

An army of ants is wise and foolish but does not know how to measure, sees the short and does not look far, but can quickly find the shortest path across the rough ground.This calculation is a perfect reflection of evolutionary search: a group of ignorant and short-sighted individuals working simultaneously on mathematically rough terrain, trying to find an optimal path.An ant colony is a parallel processor. Real ants communicate with each other through chemical systems called pheromones.Ants emit pheromones among themselves and in their environment.These aromatic scents dissipate over time.It can also be relayed through a chain of ants: they smell a certain smell, copy it and pass it on to other ants.Pheromones can be thought of as messages that travel or communicate within the ant system.

The Milan group (with Alberto Colony, Marco Doligu and Vittorio Maneso) constructed the equations following the logic of ants.Their virtual ants are swarms of dumb processors running in parallel.Each virtual ant has a trivial memory system and can communicate locally.If done well, the rewards obtained are also shared with other peers in a distributed computing manner. The Italians tested their ant machine with the standard traveling salesman problem.The problem is described like this: You need to visit many cities, but each city can only be visited once, so which path is the shortest?To solve this problem, each virtual ant in the ant colony set out to roam from city to city, leaving behind a pheromone scent along the way.The shorter the path, the less pheromone is volatilized.The stronger the pheromone signal, the more ants will follow.Those shorter paths are thus self-reinforcing.After running for 5000 rounds, the group thinking of ants will evolve a fairly ideal path.

The Milan group also tried various variations.If the virtual ants all start from one city or are evenly distributed in each city, will there be any difference? (The effect of distribution is better.) Does the number of virtual ants in a round matter? (The more the better, until the ratio of ants to cities is 1:1.) By varying the parameters, Milan's group obtained a series of ant-search algorithms. Ant algorithm is a form of Lamarckian search.When an ant stumbles upon a short path, this information is transmitted indirectly to other virtual ants through the smell of pheromones.In this way, the lifetime learning of a single ant indirectly becomes a part of the information heritage of the entire ant colony.The individual ant effectively disseminates the knowledge it has learned to its own group.Like cultural teaching, dissemination is part of the Lamarckian search."In addition to mating, there are many ways information is exchanged. Like the evening news," Ackley said.

Whether it is real ants or virtual ants, their intelligence lies in the fact that the amount of information invested in "spreading" is very small, the range is very small, and the signal is very weak.The idea of ​​introducing weak propagation into evolution is quite attractive.Even if there is Lamarckian evolution in the biological world of the earth, it must be buried deeply.Still, there is room for all sorts of outlandish algorithms, where all kinds of Lamarckian propagation can find their way.I've heard that some programmers have been tinkering with "meme (meme)" type evolutionary algorithms all day long - that is, imitating the flow of ideas (memes) from one brain to another, trying to capture the essence and power of the cultural revolution .There are thousands of ways to connect distributed computer nodes, and so far, only a handful of methods (such as the ant algorithm) have been investigated.

Until 1990, parallel computers were ridiculed by experts, who believed that there were still many places to be questioned, that they were too professional, and belonged to fanatics.They are messy and difficult to program.But the Zealots don't see it that way. In 1989, Danny Hillis made a public bet with a well-known computer expert, predicting that by 1995, the amount of data processed by parallel machines per month will exceed that of serial machines.It appears he was right.When serial computers groaned as their narrow von Neumann channels were overwhelmed by complex tasks, expert opinion changed overnight and quickly swept the computer industry.Peter Denning, writing in Science ("Highly Parallel Computing", November 30, 1990), states, "The computational speed required to solve advanced scientific problems can only be achieved through highly parallel computing architectures .” John Koza of Stanford’s computer science department was more blunt, “Parallel computers are the future of computing. Period.”

However, parallel computers are still difficult to master.Parallel software is a horizontal, concurrent, intricate causal network.You can't find flaws in such non-linearities, they're all hidden.There are no clear steps to follow, the code cannot be disassembled, and incidents follow one after another.Building a parallel computer is easy, but programming it is hard. Parallel computers face challenges that all distributed cluster systems face—including telephone networks, military systems, global 24-hour financial networks, and vast computer networks.Their complexity tests our ability to master them. "The complexity of programming a massively parallel machine may exceed our ability." Tom Ray told me. "I don't think we'll ever be able to write software that takes full advantage of parallel processing."

Parallel stupid little things can "write" better software than humans, which made Ray think of a way to get the parallel software we want. "You see," he said, "ecological interactions are parallel optimization techniques. Multicellular organisms are essentially running massively parallel codes on a cosmic scale. Evolution can 'figure out' what we can't figure out in our lifetimes Parallel programming of . If we can evolve software, then we can take a huge step forward.” For things like distributed networks, Ray said, “Evolution is the most natural way to program.”

The natural way to program!That sounds really frustrating.Humans should only do what they do best: those small and smart, fast and precise systems.Let (artificially injected) natural evolution do the big messy stuff.