Quantcast

Goal seeking code

Get the WebProNews Newsletter:


[ Business]

This is an extremely unsophisticated program that demonstrates evolutionary DNA. You start by passing it a string:

./goal.pl Goal

The goal, starting from two strings “abcdefg” and “gfedcba”, is to end up with your string duplicated four times: “GoalGoalGoalGoal”. It does this by having children that are produced by mating with other strings in its memory. The child produced is just position one from string1, position two from string two, etc. So starting with “abcdefg” and “gfedcba”, the first “child” would be “afcdebg”. However, random mutations are introduced to the children. Each string is then scored, and the highest scores get to reproduce again. This reproduction pattern tends toward similar parents producing similar children – much like real life.

Mutations here are more apt to change the case of a letter than change it outright, but they are aggressive. You can easily change these factors to see how they affect the results. So that the string can grow, letters can be doubled, though they can also be taken away. The strings are held to a maximum size of four times the length of your goal string, and the total number of strings is trimmed to a small number so that this doesn’t grind away for hours and hours sucking up cpu and memory..

It also does a little Permian Extinction now and then – which brings some fresh faces into the gene pool. Simply, we just randomly wipe out up to 75% of the strings on each generation, thus giving the new strings more chance to mate.

It doesn’t take long for the first patterns to appear. It’s interesting that “bad” strings often hold good positions for quite a while, but by a few thousand generations, the top scoring strings have at least one correctly anchored pattern.

It may take quite a while for better patterns to emerge. People who prefer to believe that life came from “intelligent design” sometimes forget how much time the primitive life of this planet had for its patterns to emerge. For hundreds of millions of years, simple living things reproduced over billions and billions of generations, gathering improvements as mutations failed and succeeded or made no difference at all. Bacteria might reproduce every twenty minutes. How many generations is that over a few hundred million years? What improvements can come about? Well, we are the results of just that. Life on this planet had many more generations available than you are likely to have the patience or time for on your computer.

I’ve recently been re-reading John McPhee’s Annals of the Former World. I have to keep a large dictionary beside me while reading this, which amuses my wife greatly as she doesn’t often see me nonplussed by mere words. Nevertheless, it’s a great read, and while it is starting to get a bit out of date with current knowledge, I still enjoy it. McPhee notes that for most of us, the concept of geographic time is beyond real comprehension – 100 million years or so is just a number, it’s nothing that we can really appreciate. Analogies like “if all of the earth’s history were the length of your arm, all of human history could be erased by a fingernail file” don’t really help, but it is these incredible lengths of time that made complex life possible.

The scoring here rewards simple goals, and gives higher scores for better matches. The scoring is deliberately imperfect – though it is programatically interesting:

sub score {
my $trg=shift;
my $len=length($Goal);
my $lct=lc($trg);
my $s=0;
my $G=$Goal;
my $g=lc($Goal);

# This looks for matches in position. If the goal is "Abc" and the
# target is "Xyz-Mno-123-456", this compares "abc" to "xyz", then
# "Abc" to "Xyz, then "ab" to "xy" (and "Ab" to "Xy"),
# "a" to "x", "bc" to "yz", "b" to "y", and "c" to "z".
#
# It then moves to "abc" compared to "mno", "ab" to "mn", etc.
#
# The longer the comparison, the more score for a match. "Abc"
# compared to "abc-xyz-mno-sdf" will match all of the case insensitive cases
# for "Abc" to "abc" and will match "bc" to "bc" and "c" to "c"
# for both insensitive and case sensitive tests.

for ($y=0;$y< length($trg);$y+=$len) {
&nbsp&nbsp&nbsp for ($z=0;$z<$len;$z++) {
&nbsp&nbsp&nbsp for ($zz=$len-$z;$zz>0;$zz--) {
&nbsp&nbsp&nbsp&nbsp&nbsp $s+=(10 * $zz) if substr($g,$z,$zz) eq substr($lct,$y+$z,$zz);
&nbsp&nbsp&nbsp&nbsp&nbsp $s+=(20 * $zz) if substr($G,$z,$zz) eq substr($trg,$y+$z,$zz);
&nbsp&nbsp&nbsp&nbsp&nbsp }
&nbsp&nbsp }
&nbsp }
if ( $trg eq "$Goal$Goal$Goal$Goal") {
&nbsp&nbsp print "$s $trg - DONE!\n";
&nbsp&nbsp exit 0;
}
return $s;
}

Crude as it is, the strings slowly get closer to the desired result. Just leave it alone for a few hours, and you should see the strings building toward the goal. There will be imperfect versions along the way; for example this has “Fog” as its target:

After just 550 generations, this is off to a good start.

Shorter strings of course get good patterns early.

This has more partial matches, and is well on its way to perfection. As it gets closer, though, changing becomes harder, because most changes won’t score well enough to beat these already good scores. The change has to be more beneficial, which is just as it works in the real world: succesful organisms tend not to evolve quickly.
Of course, we get much quicker results for a single letter goal:

It is is fun to play with various mutation/extinction schemes just to see what happens, though I don’t think we have any scientific validity here. This was fun to write, and fun to play with, but it’s not anything like the Avida project.

Perl source at ftp://ftp.aplawrence.com/pub/goal.pl for all the other off-balance folks.

*Originally published at APLawrence.com

A.P. Lawrence provides SCO Unix and Linux consulting services http://www.pcunix.com

Goal seeking code
Comments Off
Top Rated White Papers and Resources

Comments are closed.

  • Join for Access to Our Exclusive Web Tools
  • Sidebar Top
  • Sidebar Middle
  • Sign Up For The Free Newsletter
  • Sidebar Bottom