24 July 2009

Watching simulated chromosomes mutate as they try to reach a "goal"

Hi -

What might a time-lapse of evolution look like, at the genetic level, watching genes win and lose on the basis of how well the organism was able to survive? In this blog post, we'll look at a really dumbed-down version of this that's still, I think, conceptually compelling.


How is a recipe different from an evolving organism? What if real-world problems, like designing bridges or electronic circuits, were solved by a computer that hunted around for a good solution rather than at the explicit, exacting direction of a team of engineers?

Genetic algorithms are computational "recipes" that function in this manner. Broadly, it's been possible to program a computer to program itself, using a technique that has some analogies with real-life evolution. This won't surprise any computer scientists, since the technique has been around since the 1950s and gained popularity in the 1970s. But I thought you might be interested in GAs because we can peer (diagrammatically) into an accelerated world of simulated, simplified "evolution" - and, also, it's a fun programming exercise that lets me get a little more experience with languages like Mathematica and C.

(If this is new to you, see the brief overview that I blogged about in 2007.)

In short, we give our evolution-simulating program a few things:
  • A population of organisms (usually called chromosomes), each chromosome being composed of a bunch of genes... and each gene can be as simple as a 0 or 1 -- or as complicated as a mathematical function like Sin(x). Usually the population is random, a bunch of Frankensteins.
  • A goal to achieve, like "figure out what math function best approximates this stock-ticker," or "figure out how to place 100 Lego blocks to make a really long bridge that doesn't collapse under its own weight." Usually the goal is presented in terms of a test called a fitness function. We test each organism (or chromosome's) ability to pass the test. The chromosomes that do better survive - pairs of chomosomes (parents) breed, make children, the kids are mutated, and the weaker parents are killed. Repeat.
  • And you need to let the simulation know how likely it is that genes will mutate or that breeding parents will swap chromosomal segments ("crossover").
As a prelude to a larger project, I put together a simple Mathematica notebook that would try out a problem in a textbook on the subject, Melanie Mitchell's An Introduction to Genetic Algorithms. The test?

Turning random "binary" chromosomes into a freaky population that loves the number 1

Start with a bunch of random chromosomes, like:

{0,0,1,0,1,1,1,0} (chromosome 1)
{1,0,0,1,1,0,0,0} (chromosome 2)

...and let them breed and mutate. The chromosomes that looked most like {1,1,1,1,1,1,1,1} were not killed off.

Our population had 40 chromosomes, each with 10 genes valued 0 or 1. The universe runs for 100 time-steps.

Here's a chromosome from the randomized primordial ooze, our friend chromosome 5:


And here is its universe, textually:


..and graphically (Mr. Five is in the fifth row from the top):


A few simple experiments: does it work?

Of course, I implemented the basic GA stuff, like a function for "fitness-proportionate selection using roulette wheel sampling," a fancy way of saying "a way to favor the parents that most look like a bunch of ones." At the end I'll link to the notebook so you can use it, laugh at my code, and offer suggestions.

Here I'll show you a few plots that show how the population's fitness improves (hopefully) over 100 sessions of selection, mating with crossover, and "honey, I mutated the kids."


Above, we use the recommended parameters for mutation (0.001 = 0.1% likely) and crossover (70%). As you can see, the population approaches the theoretical maximum fitness (400, which is the number of chromosomes multiplied by the number of genes each) at about step 20.

The curve goes up, meaning that the "fitness" of the chromosomes is improving.  A plot of the chromosomes at ten snapshots in their history are provided right under that.  They're getting more black - which means that they're becoming filled with 1s.  (Under that is what the first ten generations looked like.)

It bounces around, too. That's because the genes mutate now and then.

What if we go outside without sunblock?

What if we turn the mutation probability up to a whopping 10%?


Augh! The population never has a chance to improve its fitness; just as it tries to get healthy, we flip bits and really screw things up.

One other quick experiment: do what extent does the crossover probability matter? Let's turn it down to 0.5%, so that crossover happens about 1 in 200 matings. We'll increase the number of generations to 500:


Neat! Maybe I'm reading too much into this, but it's as if improvements in fitness happen in punctuated jumps.

Oh, what does the life of one chromosome over the whole history look like? Going back to our original parameters for mutation and crossover, Mr. Five indeed tends toward all ones (or "all black," reading downward.)




Well, that's it. If you find this interesting, you might want to code some of this stuff up on your own. I suggest a few video clips of neat stuff (e.g. synthetic organisms learning to crawl, Lego bridges...) and good books on these blog posts:

  • g-fav's first attempt to write a GA, in C (May 2007)
  • "virtual schadenfraude" - turn on your speakers! (Oct 2008)
  • Lego bridges and truck backer-uppers (May 2009)
The Mathematica notebook (do whatever you want with this, was written for fun and not error-tested, not responsible for damages...) max_ones.nb - free Wolfram Mathematica Player

Have a good weekend!

Gregg





3 comments:

hyipinvestor said...

Make Serious and fastest Money On The Internet

The Best Low Risk - High Return Investment I Made 7Millions Liberty reserve and perfectmoney profit in paying hyips

http://www.payinghyiponline.com

Make millions liberty reserve and perfectmoney in paying hyips fastest Real Investment
Payinghyiponline.com is an expert investment advisor and can help with investment services. Choose a Service: online investment, investment make money online, online investment advice, online stock investment, online investment service,

trading investment online, online investment magazine, online investment broker, online investment services, online investment banking, online investment club, online investment company, business introduction, online investment

opportunity, online investment calculator, online investment information, online investment bank
HYIP(High Yield Investment Program) is a investment program that anyone can join online and deposit fund, in return the member will earn high interest in short period of time. There are tons of HYIPs on the Internet and most of them are

closely monitored by HYIP rating sites and HYIP forums.You can find HYIPs from those HYIP rating and monitor sites. http://www.makecurrencyonline.com one of the biggest HYIP rating and monitor sites.
If you've searched around the Internet for different ways to make money online, there's no doubt that you've come across the term HYIP . You might have just skipped it and paid it no mind, but if you're reading this article right now,

you must have questioned what the term encompasses. HYIP stands for High Yield Investment Programs , which covers all programs, offline and online , that are used to invest money to receive a higher yield than you would normally get at a

bank . But that doesn't necessarily mean that it's a safe and solid investment. Look to HYIPs as more like gambling than an investment , and only use money that you can afford to lose.
If you don't have liberty reserve or perfectmoney account, please sign up a free account
https://www.libertyreserve.com/en/
http://www.perfectmoney.com/
Now you need fund your liberty reserve or perfectmoney account. We recommend some good e-currency exchange sites for you
http://ebuygold.com/
http://www.londongoldexchange.com/
http://www.wm-center.com/index.html?lang=eng
http://www.superchange.ru/en/
more exchange sites
https://www.libertyreserve.com/en/exchangers/index.aspx
https://www.perfectmoney.com/business-partners.html
I got paid and made serious profit from following hyips

http://www.fastlibertyreserve.com/?6016375 (Recommended)

http://www.seriousinvestorhome.com/?6016375 (Recommended)

http://www.libertyreserveinvestment.net/?6016375

http://www.libertyreserveinvesting.com/?6016375

http://www.deltalloydinvestmentsfund.com/?6016375

http://www.lrfund.com/?U6016375

http://www.richestinvestment.com/?6016375

http://www.perfectlite.org/?6016375

http://www.t5t.us/?6016375

You can choose some sites make your first deposits and become rich fast
mail to me if you made a deposit use my referral link.We will return 25% of your spend instant.100% guaranteed money back.
My email address: services@payinghyiponline.com
Our website
http://www.payinghyiponline.com

Make $50k libertyreserve money daily on forex trading
http://www.libertyreserveforex.net

Read news about hyips.make money fast and easy
http://libertyreserve-investment-hyip.blogspot.com/

More news about paying hyips
http://groups.google.com/group/make1milliondaily

Post Your AD on 1000+ Forums
The Best HYIP - High Yield Investment Programs Rating and Monitoring listing along with information, strategies and HYIP articles, news, advice on HYIP investments."
http://www.yahoomsngroup.com/

bullionsInvestor said...

Make Money Online From Investment(High Return Liberty reserve Investment Plans Without

risk)

Make Serious and fastest Money in Paying hyips
The Best Low Risk - High Return Investment I Made Several Millions Profit with Liberty

reserve and perfectmoney money in paying hyips
Make millions liberty reserve and perfectmoney in paying hyips fastest Real Investment
Many people today feel like they don't have enough money in their lives. These days

having only one stream of income isn't enough. People are always looking for more. Life

is getting expensive. People want to be able to go out and do what they want, take

vacations, have fun, and in general enjoy life. The problem is that they usually don't

have enough money or time to enjoy these things. This is where E-Currency Investment

comes in.
Becoming a HYIP Investment expert is not easy, but it can be very profitable, you can be

able to gain monthly interest as high as you will never find in any other investment

opportunity! See more information at HYIP Investments.
http://www.yahoomsngroup.com/
http://www.makecurrencyonline.com/
http://www.hyipfunding.com/
http://www.libertyreserveforex.net/
If you've been having a hard time keeping up with your bills, you feel like you want more

money, or you feel you need to grab a hold of your life, then I recommend checking out E

-Currency Investment.
First,You need to have one liberty reserve or perfectmoney account
If you don't have liberty reserve or perfectmoney account, please sign up a free account
https://www.libertyreserve.com/en/
http://www.perfectmoney.com/
Second, you need fund your liberty reserve or perfectmoney account. We recommend some

good e-currency exchange sites for you
http://ebuygold.com/
http://www.superchange.ru/en/
Last I got paid and made serious profit from following hyips
http://www.mountainmininginvestment.com/?6016375
http://www.fastlibertyreserve.com/?6016375
http://www.profitinparadise.net/?6016375
http://www.seriousinvestorhome.com/?6016375
http://www.libertyreserveinvestment.net/?6016375
http://www.libertyreserveinvesting.com/?6016375
http://www.richestinvestment.com/?6016375
http://www.perfectlite.org/?6016375
http://www.noriskinvestors.com/?ref=payinghyiponline
http://www.highreturnatinvestment.com/?6016375
http://www.perpetuityincome.com/?6016375
http://www.citrusfinance.net/?6016375
http://www.vividfinance.net/?6016375
http://www.sureprofits.net/?6016375
http://www.gleenmanagement.com/?6016375
http://www.workinglr.com/?6016375

You can choose some sites make your first deposits and become rich fast
mail to me if you made a deposit use my referral link.We will return 25% of your spend

instant.100% guaranteed money back.mailto:services@payinghyiponline.com
http://www.payinghyiponline.com is an expert investment advisor and can help with

investment services. Choose a Service: online investment, investment make money online,

online investment advice, online stock investment, online investment service, trading

investment online, online investment magazine, online investment broker, online

investment services, online investment banking, online investment club, online investment

company, business introduction, online investment opportunity, online investment

calculator, online investment information, online investment bank

Anonymous said...

you have a nice site. thanks for sharing this valuable resources. keep it up. you can also earn money from here

http://hutmoney.blogspot.com