Evolving genetic algorithms

Found this intriguing gem yesterday about �genetic algorithms�-
Evolution could speed net downloads - and began to wonder how the organizational gurus would soon begin to apply this thinking to human behavior and social networks and life-caching.


� Internet download speeds could be improved dramatically by mimicking Darwin's evolution to "breed" the best networking strategies, say computer scientists.

Transferring popular data across the internet repeatedly can be inefficient and costly, so networking companies have developed ways of temporarily storing, or "caching", data at different locations to reduce costs and increase download speeds.

But figuring out where to store data and for how long is a complex problem. One solution might be to have caches "talk" to each other repeatedly, but this is inefficient as it takes up a lot of bandwidth.

To tackle the challenge, Pablo Funes of US company Icosystem and J�rgen Branke and Frederik Theil of the University of Karlsruhe in Germany used "genetic algorithms", which mimic Darwinian evolution, to develop strategies for internet servers to use when caching data. Using a simulation they were able to improve download speeds over existing caching schemes.

The researchers evolved algorithms for specific types of network, for example networks with a bottleneck. But they also developed algorithms that worked well on various types of network.


Major intersection

Funes told New Scientist the scheme could eventually be used to allow caches to automatically "evolve" their configuration. "Further development could involve different rules suited to each individual host or subnet involved in the internet," says Funes. "One can even imagine each host evolving its own optimal rule."

The team used a network simulator to test out different caching strategies. They created a simulation of a branch of internet network where data could be copied and stored at every major intersection. They used this simulation to test algorithms used to configure the caches.

The algorithms take known variables, such as the number of times a piece of data is requested, the number of points it has to pass through and its overall size, and work out whether it should be stored and for how long.

The key to finding an efficient algorithm was "evolving" it from a population of randomly generated ones. The starting population of algorithms was tested on the simulator using randomly generated requests.


Algorithm breeding

The algorithms that reduced network traffic and improved download speeds best were then used to "breed" a new population of algorithms. Breeding involves combining different pieces of an algorithm and introducing some random mutations. The process can be repeated again and again to improve efficiency.

When tested on a simulated network of 300 intersections, or "nodes", the algorithms they developed were twice as fast as the best existing strategy.

"It is quite neat," says Jon Crowcroft, at the UK's Cambridge University. "The novelty lies in the rather 'inelegant' algorithm that they evolve."

But Funes admits there are limitations. An important consideration is what incentives there are for caching information for other users. He suggests networks might in the future be designed to work out who deserves the most help for themselves. "Sophisticated network behaviours might implement rules for reciprocity and trust," he says. "And conversely, for not cooperating with other others who try to abuse our resources." �