Tuesday, May 27, 2008

The Ant Colony Algorithm

This is so interesting I had to copy it right over from Wikipedia (the rest of this post is a copy-and-paste):

The ant colony optimization algorithm, introduced by Marco Dorigo in 1992 in his PhD thesis, is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. They are inspired by the behaviour of ants in finding paths from the colony to food.

In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep traveling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food.

Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high as it is laid on the path as fast as it can evaporate. Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.

Thus, when one ant finds a good (i.e. short) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leads all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with "simulated ants" walking around the graph representing the problem to solve.

Ant colony optimization algorithms have been used to produce near-optimal solutions to the traveling salesman problem. They have an advantage over simulated annealing and genetic algorithm approaches when the graph may change dynamically; the ant colony algorithm can be run continuously and adapt to changes in real time. This is of interest in network routing and urban transportation systems.

Monday, May 26, 2008

Wright & Wright on the cooperation arms race

Well this couldn't come at a better time - the great Will Wright says that Cooperation & Competition are a big part of his motivation for working on Spore. Spore is a simulation coming out this fall which looks to re-invent the definition of computer "game" for all of us. Here's Will:

Quotes from this video which are most pertinent to stuff I've talked about before:

"You'll have little cells competing, then at some point, some of them decide to group together and cooperate & become specialized - and you get multicellular creatures. You see a similar pattern when individuals group together, forming very simple societies and out-competing the individuals."

"I see evolution as...this interplay of competition driving cooperation, driving specialization which then brings the competition to the next level."

In other words, competitive pressure drives organizational structures towards ever-greater complexity as previously unrelated entities are forced to either stand together or fall apart.

This is very similar to what Nonzero calls the "logic of human destiny": the reason why sentient life, societies, and world wars were inevitable from the time the first single-celled organisms appeared. I think Robert Wright (author of Nonzero, no relation to Will Wright that I know of) also refers to this as the "arms race" of cooperation: stubborn individualists are eventually dominated by coalitions of their enemies, whether we're talking about cells, species, or societies.

Monday, May 12, 2008

Support for cooperation over competition

Here's an article about a recent study that shows individuals prefer cooperation over competition.

The scenario is that players are grouped into 2 teams, and then each player has 2 options:
  1. Produce 1 point for each ally and remove a point from the other team.
  2. Produce 1 point for each ally without affecting the other team.

The study concludes that people seem to prefer intra-group cooperation over inter-group competition. (Players tended to use option #2 instead of hurting the other team.)

I recently updated my program "The Rise of Cooperation" which you can download here (or from the bar on the right-side of your screen.) It tries to look at a similar theme - whether we can say which of cooperation or competition is a dominant strategy.

If cooperation tends to be a better strategy than competition, then it makes sense that natural selection would have shaped us into beings that prefer cooperation as the study above suggests. If we had an innate preference for an inferior strategy, then natural selection would likely have phased our species out long before certain unnamed hacks could blog about it on the web...