Evolutionary Algorithms – Directing the undirected

July 30, 2010 by Roger Alsing 3 Comments

This is a followup to my previous post on the same topic : http://rogeralsing.com/2010/07/29/evolutionary-algorithms-problems-with-directed-evolution/

I started thinking about possible solutions after I published my last post, and I think I might have something that could work.

In order to harness the full power of evolution, we need to be able to simulate undirected evolution.
Undirected evolution requires more than one environment, so that organisms can evolve and niche into specific environments instead of just competing for the same environment.

In our case, the “environment” is the “problem” that we want to solve.
The more fit an organism is in our environment, the better it is to solve our given problem.

So far, I think everyone have been applying evolutionary/genetic algorithms on individual problems, evolving algorithms/solutions for a single purpose..
And thus, experiencing the problems of irreducible complexity.

But what if we were to introduce an entire “world” of problems?

If we have a shared “world” where we can introduce our new problems, the problem would be like an island in this world, and this island would be a new environment where existing organisms can niche into.
This way, we could see organisms re-use solutions from other problems, and with crossover we could see combinations of multiple solutions for other problems.

The solutions would of course have to be generic enough to handle pretty much every kind of algorithm, so I guess the DNA of the organisms needs to be very close to a real GPL language.
Possibly something like serialized Lisp/Clojure, running in a sandboxed environment…

By adding more and more problems to this “world”, the better it would become at solving harder problems since it can reuse existing solutions.

The structure of it all would be something like:

The “World” is the container for “Problems”.
“Problems” contains input/output sampling and “populations of organisms”, thus, each problem have its own eco system.
“organisms” evolve by mutations and genetic crossover, they can also migrate to other “problems” from time to time.

This way, an organism from the “SSH Encryption island” may migrate over to the island of “Bank authentication login code generator island” and possibly be used as a module in one of the branches of one of the organisms in there, and thus removing “irreducible complexity” from the equation here..
Evolution would be locally directed and globally undirected…

I think this could work at least to some extent, or?

//Roger

Filed under Evolution Tagged with , , , ,

Evolutionary Algorithms – Problems with Directed Evolution

July 29, 2010 by Roger Alsing 16 Comments

Creationists often use “irreducible complexity” as an argument against evolution.
e.g. you need all parts in place and functioning before the “whole” can do its work and thus reproduce and spread its features.

The bacteria flangellum is one such feature that have been attributed with “irreducible complexity”.
You need the “tail” and some “engine” parts in place before it can be used as a propeller and drive the bacteria forwards.

Evolutionists have however proven this wrong and shown that each of these parts have had other purposes before they were re-used/combined for propulsion, so each part was already present.

The key here is that evolution in reality is not directed to a “final goal” it simply makes organisms adapt to their current environment.
e.g. an organism might evolve a single pair of legs and later generations might get more of those legs if that is beneficial.
The front pair of legs might even later evolve into a pair of arms that allows the organisms to grab food while they eat and so on.

In short, existing features can be reused and refined in order to reach a higher fitness level in the current environment.

As far as I know, we still have not managed to accomplish this sort of “undirected evolution” in computer programs in the same sense.
If we make a program that are supposed to come up with a solution for a given problem, I would use “directed evolution” and try to breed solutions that are better and better at solving the given problem.
So if our program was supposed to come up with a propulsion system for a body, it would fail at evolving the bacteria flangellum since we experience the effects of irreducible complexity, our program is unable to evolve all the parts for other reasons than moving the body forwards.

In order to harness the full power of evolution in computer programs, we need to be able to simulate “undirected evolution” so that we can evolve all these parts that later can be re-used for other purposes.

Are there any research going on in this topic at all?

I know that the old “Tierra” simulation was sort of undirected, the only goal was to consume as much CPU as possible, but it sure could use undirected evolution to get to that goal.

But other than that, anything?

Filed under Evolution Tagged with , , ,

Plastic Language take 2

June 17, 2010 by Roger Alsing 4 Comments

This is a follow-up on my earlier posts regarding my toy language plastic:
http://rogeralsing.com/2010/04/14/playing-with-plastic/
http://rogeralsing.com/2010/04/17/more-on-plastic/

After some brain storming with my colleague Sebastian Markbåge, we’ve come up with some alternative approaches to chained method calls.

Instead of chaining calls syntactically, I could instead chain them by passing the result of the last statement into the next function invocation, somewhat like pipelining in F# but without any syntactic interference.

 Lets take the “if / else” scenario which I have used before.

In my first attempt in plastic, the syntax would be:

if (condition)
{
   ...body...
}
else
{
   ...body...
}; // <- terminate the if / else chain with ";"

This worked fine, but it came with the drawback that I had to terminate every chain with “;”, even a single if statement.. if (…) {…};
It was also up to the “if” function to decide if the “else” function would be called.

With the new approach, the “if” function would execute like normal, and if the condition was not met, it would return the value/symbol “fail”.
The “else” function would be a special function that requires a “last value” as its first argument, this way, the evaluator “knows” that the last evaluated result should be applied to the “else” function.

Like this:

if (condition) //if condition fails, return "fail"
{
   ...body...
}
else //the last evaluated value and the else body is applied to the else function.
{
   ...body...
} // <- don't need any terminator, all {..} blocks always terminate a statement

This way, the else function would have two arguments, the last result and a closure representing it’s body.

The else function would be implemented like this:

func else (lastresult,body)
{
  let result = lastresult;

  if (last == fail) // if the last function returned fail, then execute the else body
     result = body(); //invoke the body and assign to result

    result;
}

This means that I can make a language wich is syntactically very similar to JavaScript (for whatever that is worth) and at the same time support invocation chains of functions/macros.
So this is more powerful than the earlier attempt and with a nicer syntax due to the skipped requirement of terminating chains with “;”

Ideas?

Filed under .NET, C#, Domain Specific Languages

Synthetic life unveiled

May 22, 2010 by Roger Alsing 2 Comments

This is just a must see.
Scientists have designed a DNA sequence in a computer and managed to create real, self replicating cell, with it’s own email address encoded in the DNA :-)

http://www.ted.com/talks/craig_venter_unveils_synthetic_life.html

Filed under Evolution

More on Plastic

April 17, 2010 by Roger Alsing 3 Comments

I’ve added some more features to my toy language “Plastic”.

Partial application of function arguments.
This is now used for generators.
Yield is no longer a core function, instead, each generator takes a closure as its last argument which is then supplied by the foreach function.
This way the foreach body don’t have to be stored as a symbol, it is just passed as an argument to the generator.

func Range(low,high,yield)
{
    for(let i=low,i<=high,i++)
    {
        yield(i);
    };
};

// apply value to "low"
let From10 = Range(10);

// apply value to "high"
foreach(x in From10(20))
{ //this block is transformed to a closure and passed to yield
    print(x);
};

Break and Continue
Loop behavior can now be altered with break and continue.
I implemented those as special values that breaks any execution flow almost like exceptions.
The values are then bubbled up to the first loop which consumes the values and perform the appropriate action.

I guess exceptions and “return” could be implemented the same way.

[Edit]

I’ve added some basic one way coroutine support to support breaking out of generators that are constructed from nested loops.
Before, a break would only exit the most inner loop of the generator.

Now I can do things like this:

func primes(low,high,yield)
{
    foreach(i in range(low,high))
    {
         foreach(j in range(2,i/2))
         {
             if (i % j == 0)
             {
                break;
             };
         }
         else
         {
             yield(i);
         };
    };
};

foreach(prime in primes(2,100))
{
    print(prime);
    if (prime > 50,break);
}
else
{
    print(""done"");
};

Filed under .NET, Domain Specific Languages, F#

← Older posts