Mozart meets Darwin now on Android

Our experiment "Mozart meets Darwin" (see my previous blog article about it for details) is online again. You can take part in the experiment by voting using the Flash application below. We also provide a version for Android mobile phones now (the download is free). Please spread the word and tell your friends: we expect many votes in order to make this work.
I will provide an analysis of the results after a few weeks.

• Project page about Mozart meets Darwin experiment
• Android App: Mozart meets Darwin (needs Android Version 2.2 or above)
• www.demesos.tk - Our research project (funded by Lakeside Labs)

So when do we call a system self-organizing?

Recently, in a PhD seminar talk the discussion arose, if a particular system is self-organizing or not. Such discussions are emerging with high probability every now and then followed by a discussion that lasts for some time.
It seems that the term "self-organizing system" is a very difficult concept for the following reasons:
First, being named self-organizing, such system are often literally understood as some entity that organizes itself, like a person managing her own affairs in life. The "self" can be misleading here since it may be understood as a single controlling entity.
Actually in self-organization, there is no "self" that organizes. It rather means that systems appear to organize themselves without external direction, manipulation, or control.

Cloth of gold cone: visible pattern as a result
of a self-organizing process (Image: Wikipedia)

To avoid this misinterpretation, the term is sometimes replaced or augmented with spontaneous pattern emergence. But this creates a mental image of patterns in the reader's mind (like the cone displayed to the right). Other self-organizing processes like coherent laser light or clock synchronization create internal order, but no visible pattern.
Another problem is that you can change a system with external control to one without by redrawing the systems boundaries. So a bunch of workers being instructed by a foreman would not be perceived as self-organizing, but a construction cite with different teams, each one coming with a foreman, but otherwise loosely interacting might be seen as self-organizing (unless you model in the blueprints).
Gershenson and Heylighen proposed a nice way out of this dilemma by stating "self-organization is a way of observing systems, not an absolute class of systems". So depending if the self-organizing view is beneficial, you should model your system accordingly, otherwise not.
Another difficulty arises from the fact that self-organization roots in several disciplines, there are many notions and definitions from biology, chemistry, computer science, cybernetics, economics, mathematics, physics, and sociology. Most of these disciplines contribute one or more definitions on self-organization based on the discipline-specific terminology.
As shown by the following examples, there is no single brief but comprehensive definition for self-organization. The following definitions may be useful though:

A self-organizing system (SOS) consists of a set of entities that obtains an emerging global system behavior via local interactions without centralized control.
(from Research Days'08, see [IWSOS:2008]))

Self-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning. (Wikipedia)

A self-organizing system is a system that changes its basic structure as a function of its experience and environment. (Farley and Clark 1954)

Are they really refering to the same thing? So be warned, when a discussion heads towards the definition of self-organization!

• C. Gershenson, F. Heylighen. When Can we Call a System Self-organizing? In Banzhaf, W, T. Christaller, P. Dittrich, J. T. Kim, and J. Ziegler, Advances in Artificial Life, 7th European Conference, ECAL 2003, Dortmund, Germany, pp. 606-614. LNAI 2801. Springer.
  
• W. Elmenreich, H. de Meer. Self-organizing networked systems for technical applications: A discussion on open issues. In J.P.G. Sterbenz. K.A. Hummel, editor, Proceedings of the Third International Workshop on Self-Organizing Systems, pages 1–9. Springer Verlag, 2008.
  

A self-organizing algorithm for video distribution networks

The way how users consume videos has changed with the availability of large repositories with a high number of more or less related videos. Many users are only interested in tiny fractions of a video and not even necessarily in the original temporal order. Moreover, they might wish to dynamically compose portions of di erent videos into one presentation.
For example, take a video recording of a ski-jumping competition. Some users might be interested in watching it sequentially. A trainer might be interested in studying the jumping-off technique of athletes in parallel. Another user might be interested in the performance of several jumpers from one country.
In order to keep up with this emergent access patterns, we invented a self-organizing video delivery network that is based on artificial hormones which are spread throughout the network when a particular video is requested. The hormone spreading is affected by the bandwidth and delay parameters of the network edges, thus indirectly help in searching for the (currently) best path to transmit a video.
The interactions between nodes like spreading/evaporating hormone or moving a video according to the neighbor with highest hormone gradient are all local within a node's neighborhood. Still, the system is able
to guide the overall transportation and placement of units in the system up to near optimum.

• A. Sobe, W. Elmenreich, and L. Böszörmenyi. Towards a Self-Organizing Replication Model for Non-Sequential Media Access ACM Multimedia 2010 Workshop - Social, Adaptive and Personalized Multimedia Interaction and Access, SAPMIA 2010
  
• videonetwork - A simulator for self-organizing video replication and delivery @ Google Code
  
• Self Organizing Multimedia Architecture - A Lakeside Labs Research Project

Mozart meets Darwin - Creating music by evolution

Mozart meets Darwin is a case study where we try to evolve a piece of music, a simple melody. To evolve something, we need a model of the canditates, a method to mutate a candidate (that is apply some random perturbations), a method to recombine two parent candidates into similar children canditates, and a way to assess the fitness of a result. Using the music notes as DNA, we came up with solutions for mutation and recombination. But the assessment of the quality cannot be done by the machine - that is where we need you to indicate which piece of music is better than the other.




In the application above, you can listen to sets of five examples and rank them according to your personal preference. A computer program on a server will gather the rankings until it has sufficient input to decide how to evolve to the next generation. Mutation and recombination will be the "creativity" of the computer program. Please rank a few sets and get an impression of the approach. If you come back later, you will notice that the music pieces have improved, typically towards the overall music taste - hopefully you like it!
The results will be posted later under the GNU FDL license - so you can use the evolved melody in a song if you like.

Ig Nobel Prize goes to research on self-organizing slime mold

The behavior of slime mold, a fungus-like organism, has been one of the most famous models of selforganization. Slime mold begin life as amoeba-like cells, each wandering around in random walk behavior. But under certain environmental conditions they suddenly change their behavior and aggregate to a single multi-cellular body; with the help of chemical signals they self-organize into a network of protoplasmic strands. This emergent behavior can solve complex tasks like creating shortest interconnections between food sources in a maze.

Fuligo septica slime mold
(not dog vomit ;-)
from Wikipedia.org/CC license

A research team in Japan discovered that if they placed food piles (oat flakes) around a central slime mold in the same layout as 36 outlying cities around Tokyo, the mold created a network connecting the food sources that looked similar to the existing rail system. By introducing also topographical barriers, the results were even more similar.
Out of this team, Mark Fricker and Dan Bebber recently received the Ig Nobel award in transportation. The Ig Nobel Prizes are given annually for ten achievements that "first make people laugh, and then make them think.". But they are also a show that makes people's interested in science, so the Ig Nobel award might be considered more than just a Nobel Prize parody. However, the slime mold result being awarded there shows that many people still perceive complex systems result as something strange, funny, or improbable. Still, it is great to see research on self-organizing systems awarded!

• A. Tero, S. Takagi, T. Saigusa, K. Ito, D. P. Bebber, M. D. Fricker, K. Yumiki, R. Kobayashi, and T. NakagakiRules for Biologically Inspired Adaptive Network Design, Science 22 January 2010, Vol. 327. no. 5964, pp. 439 - 442.
  
• K. Harmon, Slime mold validates efficiency of Tokyo rail network Scientific American Observations Blog, Jan, 2010.
• The Ig® Nobel Prizes
  

Maxis' forgotten game

Maxis has quite a record in providing interesting simulation games since they came out with SimCity. The game SimLife: The Genetic Playground, however, never became a hit. In the game you can simulate an ecosystem including a climate simulation, a plant groth model and a complex model of animals including herbivores (plant eaters), carnivores (meat eaters), and filter feeders. Not enough, they added an evolution model including genes and phenotypes for all plants and animals.
At this point it becomes clear why this game was without success: it is more a research simulation than an actual game. The number of statistics and graphs also support this impression. Moreover, I guess that the actual processing power at the beginning of the nineties did not allow for extensive simulation experiments. Another distinctive feature between a game and a scientific experiment: a game is designed to give the player a fair chance of success (at least in the lower level). In contrast, SimLife simulations tend to end up in extinct animals and low-diversity flora very often. For example, Spore (from Electronic Arts, which bought Maxis some time ago) has a similar scenario, but is designed as a game. I was not really able to create a stable ecology with more than 5 different species, but still I prefer SimLife over Spore.



In overall, SimLife is interesting from a complex systems point of view even still today. If you want to try it, find it at some abandonware site and run it using an emulator, e.g. dosbox.

• DOSBox, an x86 emulator with DOS
  
• Simlife@Wikipedia
  

Evolving cooperative behavior with neural controllers

In a computer experiment, we have investigated the evolution of cooperative behavior in multi-player games. Players were randomly mixed into groups and had the chance to increase their investment by paying money into a pot where it was multiplied. However, the payout money was evenly distributed to all of the players regardless of their contribution. So a freerider could get money without paying into the pot as long as some others did.
The players were controlled by a neural network that controlled the setting strategy. Using our evolutionary design tool FREVO, we evolved the behavior in order to maximize the profit for each player. There was a pool of players controlled by neural networks. After several rounds, the more successful (thus richer) individuals were allowed to stay in the pool and produce more offspring than the less successful ones.
In the first scenario the payout was the pot times three. So if, everybody would cooperate, you can earn your money gets tripled. If the maximum bet was 20$ this means a 60$ return, in other words a 40$ revenue. But if everybody in a group pays in, it's even better to defect - let's say five out of six cooperate, you get a 50$ revenue.
The game was played iteratively 10 rounds. Originally, we expected a strategy like Tit-for-Tat to evolve and prevail. However, defection turned out to be the only stable strategy. For each system state, individuals with the defecting gene could make more revenue. In other words, ruthless behavior paid off.
The situation changed, when we introduced a "synergy factor" into the payoffs. This meant that the money of cooperating players was not multiplied linearly, but over proportionally. Assume you are working with some colleagues on a common project, let's say writing a book. If you alone invest enough time into you chapter, the book still sucks because of the other chapters which are lame or missing. If half of the authors cooperate, the book might be accepted by a mediocre publisher, but still would not be that promising. But if everybody cooperates, the result is not double the revenue of the 50% case but much more!
In the experiment we reflected this issue by a quadratic factor in the pot function. Evolving the stable strategies again showed that after some generations of defecting players, cooperation evolved as a stable strategy!

This still gives hope for our civilization - although reading the daily newspaper does not always feed this hope.

• I. Fehérvári and W. Elmenreich. Towards evolving cooperative behavior with neural controllers.In IFIP Fourth International Workshop on Self-Organizing Systems, 2009.
• Public Goods Game@Wikipedia
• Prisoner's Dilemma@Wikipedia
• FREVO - a tool for engineering self-organizing systems
• Our project DEMESOS