{"id":455,"date":"2010-01-11T12:08:13","date_gmt":"2010-01-11T10:08:13","guid":{"rendered":"http:\/\/mariusbancila.ro\/blog\/?p=455"},"modified":"2011-05-19T15:44:09","modified_gmt":"2011-05-19T13:44:09","slug":"weasel-implementation-in-csharp","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2010\/01\/11\/weasel-implementation-in-csharp\/","title":{"rendered":"Weasel Implementation in C#"},"content":{"rendered":"

In the book The Blind Watchmaker<\/a>, Richard Dawkins<\/a> explains how evolution happens through accumulated small random variations (or mutations) filtered by the natural selection, as opposed to the mainstream misinterpretation that evolution happens in big leaps. He proposes a computer program, called weasel<\/a>, to demonstrate how the accumulated small improvements (mutations that bring a benefit to the individual so that it is “chosen” by the natural selection) produce faster results.<\/p>\n

\nI don’t know who it was first pointed out that, given enough time, a monkey bashing away at random on a typewriter could produce all the works of Shakespeare. The operative phrase is, of course, given enough time. Let us limit the task facing our monkey somewhat. Suppose that he has to produce, not the complete works of Shakespeare but just the short sentence ‘Methinks it is like a weasel’, and we shall make it relatively easy by giving him a typewriter with a restricted keyboard, one with just the 26 (capital) letters, and a space bar. How long will he take to write this one little sentence?<\/p>\n

[…]<\/p>\n

We again use our computer monkey, but with a crucial difference in its program. It again begins by choosing a random sequence of 28 letters, just as before … it duplicates it repeatedly, but with a certain chance of random error \u2013 ‘mutation’ \u2013 in the copying. The computer examines the mutant nonsense phrases, the ‘progeny’ of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL.\n<\/p><\/blockquote>\n

The phrase “METHINKS IT IS LIKE A WEASEL” is from Hamlet:<\/p>\n

\nHamlet<\/strong>: Do you see yonder cloud that’s almost in shape of a camel?
\nPolonius<\/strong>: By the mass, and ’tis like a camel, indeed.
\nHamlet<\/strong>: Methinks it is like a weasel.\n<\/p><\/blockquote>\n

The algorithm as described on Wikipedia, is as follows: <\/p>\n

    \n
  1. Start with a random string of 28 characters.<\/li>\n
  2. Make 100 copies of this string, with a 5% chance per character of that character being replaced with a random character.<\/li>\n
  3. Compare each new string with the target “METHINKS IT IS LIKE A WEASEL”, and give each a score (the number of letters in the string that are correct and in the correct position).<\/li>\n
  4. If any of the new strings has a perfect score (28), halt.<\/li>\n
  5. Otherwise, take the highest scoring string, and go to step 2.<\/li>\n<\/ol>\n

    A character is an upper case letter or space, the number of copies per iteration could be 100 and the mutation rate 5%. <\/p>\n

    The following C# code is an implementation of the algorithm.<\/p>\n

    \r\nclass Weasel1\r\n{\r\n   private const string ALLOWED_CHARS = \"ABCDEFGHIJKLMNOPQRSTUVXYWZ \";\r\n   private const string TARGET = \"METHINKS IT IS LIKE A WEASEL\";\r\n   Random rand = new Random();\r\n\r\n   private int Fitness(string candidate)\r\n   {\r\n      int score = 0;\r\n      for (int i = 0; i < candidate.Length; ++i)\r\n      {\r\n         if (candidate[i] == TARGET[i])\r\n            score++;\r\n      }\r\n\r\n      return score;\r\n   }\r\n\r\n   private string Mutate(string parent)\r\n   {\r\n      StringBuilder builder = new StringBuilder();\r\n      for (int i = 0; i < parent.Length; ++i)\r\n      {\r\n         bool mutate = rand.Next(20) == 10;\r\n         builder.Append(\r\n            mutate ? \r\n            ALLOWED_CHARS[rand.Next(ALLOWED_CHARS.Length)] : parent\r\n            [i]);\r\n      }\r\n      return builder.ToString();\r\n   }\r\n\r\n   public void Run(int copies)\r\n   {\r\n      StringBuilder builder = new StringBuilder();\r\n      for (int i = 0; i < TARGET.Length; ++i)\r\n      {\r\n         builder.Append(ALLOWED_CHARS[rand.Next(ALLOWED_CHARS.Length)]);\r\n      }\r\n      string parent = builder.ToString();\r\n\r\n      int step = 1;\r\n      Console.WriteLine(\"{0:D3} {1}\", step, parent);\r\n\r\n      do\r\n      {\r\n         step++;\r\n\r\n         string[] children = new string[copies];\r\n         for (int i = 0; i < copies; ++i)\r\n         {\r\n            children[i] = Mutate(parent);\r\n         }\r\n\r\n         int indexMax = 0;\r\n         int scoreMax = 0;\r\n         for (int i = 0; i < copies; ++i)\r\n         {\r\n            int score = Fitness(children[i]);\r\n\r\n            if (score > scoreMax)\r\n            {\r\n               scoreMax = score;\r\n               indexMax = i;\r\n            }\r\n         }\r\n\r\n         parent = children[indexMax];\r\n\r\n         Console.WriteLine(\"{0:D3} {1}\", step, parent);\r\n\r\n      } while (parent != TARGET);\r\n   }\r\n}\r\n\r\nclass Program\r\n{\r\n   static void Main(string[] args)\r\n   {\r\n      Weasel1 weasel = new Weasel1();\r\n      weasel.Run(100);\r\n   }\r\n}\r\n<\/pre>\n
    Function Fitness() computes how similar an offspring is to the parent, function Mutate() makes a copy of the parent with a 5% chance for each character to mutate. Function Run() runs the algorithm until the target string is reached. A possible output of the program is shown below. Different runs require different number of iterations (even more than 100).<\/p>\n
    \r\n001 E PVBQVRYRNQSRBCDLOCFOGEIB J\r\n002 E PVBQVRYRNQSRBCDLOCFOWEIB J\r\n003 E PVIQVRYRNQSRBCDLOCFOWEIB J\r\n004 EEPLIQVUYRNQSRBCDLOCFOWEIB J\r\n005 EEPLIQVU RNQSRBCDLOCFOWEIB J\r\n006 EEPHIQLU RNQSRBCDLOCFKWEIB J\r\n007 EEPHIQLU RNQSRHCDKOCFKWEIB J\r\n008 EEPHIQLU RNQSSHCDKOCFKWEIB J\r\n009 EEPHIQLU RNQSS CDKOCFKWEIB J\r\n010 EEPHIQLU RNQSS CDKOCWKWEKB L\r\n011 EEPHIQLU RNQSS CDKOCOKWEKB L\r\n012 EEPHIQLU RN SS CDKOGOKWEKB L\r\n013 EEPHIQLU RN SS LDKOGOKWEKB L\r\n014 EEPHIQLU RT SS LDKOGOKWEKB L\r\n015 EEPHIQLU RT SS LDKOGOKWEKBEL\r\n016 EEPHIQLU RT SS LPKOGOKWEKBEL\r\n017 EEPHIQLU RT SS LPKOGOKWEKSEL\r\n018 EEPHIQLU IT SS LPKOGOKWEKSEL\r\n019 EEPHIQLU IT SS LIKOGOKWEKSEL\r\n020 EEPHIQLU IT SS LIKOGOKWEKSEL\r\n021 EEKHIQLS IT SS LIKOGOKWEKSEL\r\n022 EEKHIQLS IT SS LIKOGOKWEKSEL\r\n023 EEKHIQLS IT SS LIKO OKWEKSEL\r\n024 EEKHIQLS IT SS LIKO OFWEKSEL\r\n025 EEKHIQLS IT ES LIKO OFWENSEL\r\n026 EEKHINLS IT ES LIKO OFWENSEL\r\n027 EEKHINLS IT ES LIKO O WENSEL\r\n028 EEKHINLS IT ES LIKO O WECSEL\r\n029 EEKHINLS IT BS LIKO O WEHSEL\r\n030 EEKHINLS IT QS LIKO O WEASEL\r\n031 EETHINSS IT QS LIKO O WEASEL\r\n032 EETHINSS IT QS LIKO O WEASEL\r\n033 EETHINSS IT IS LIKO O WEASEL\r\n034 EETHINSS IT IS LIKO O WEASEL\r\n035 EETHINBS IT IS LIKO O WEASEL\r\n036 XETHINBS IT IS LIKO O WEASEL\r\n037 XETHINBS IT IS LIKO O WEASEL\r\n038 XETHINBS IT IS LIKO O WEASEL\r\n039 XETHINBS IT IS LIKO O WEASEL\r\n040 XETHINBS IT IS LIKK O WEASEL\r\n041 XETHINBS IT IS LIKK O WEASEL\r\n042 XETHINBS IT IS LIKK O WEASEL\r\n043 XETHINKS IT IS LIKK O WEASEL\r\n044 XETHINKS IT IS LIKK   WEASEL\r\n045 XETHINKS IT IS LIKK   WEASEL\r\n046 XETHINKS IT IS LIKK   WEASEL\r\n047 XETHINKS IT IS LIKE   WEASEL\r\n048 XETHINKS IT IS LIKE   WEASEL\r\n049 METHINKS IT IS LIKE   WEASEL\r\n050 METHINKS IT IS LIKE   WEASEL\r\n051 METHINKS IT IS LIKE A WEASEL\r\n<\/pre>\n
    We can change this algorithm to randomize the chance of mutation. The changes to the code are small (basically function Mutate changes to take not only the parent string but only the chance for the mutation rate), but this increases the number of iterations needed to reach the target string.<\/p>\n
    \r\nclass Weasel2\r\n{\r\n   const string TARGET = \"METHINKS IT IS LIKE A WEASEL\";\r\n   const string ALLOWED_CHARS = \"ABCDEFGHIJKLMNOPQRSTUVWXYZ \";\r\n   Random rand = new Random();\r\n\r\n   private double Fitness(string candidate)\r\n   {\r\n      int score = 0;\r\n      for (int i = 0; i < candidate.Length; ++i)\r\n      {\r\n         if (candidate[i] == TARGET[i])\r\n            score++;\r\n      }\r\n\r\n      return score;\r\n   }\r\n\r\n   private string Mutate(string parent, double rate)\r\n   {\r\n      StringBuilder builder = new StringBuilder();\r\n      foreach(char c in parent)\r\n      {\r\n         builder.Append(\r\n            rand.NextDouble() < rate ? \r\n            c:\r\n            ALLOWED_CHARS[rand.Next(ALLOWED_CHARS.Length)]);\r\n      }\r\n\r\n      return builder.ToString();\r\n   }\r\n\r\n   public void Run(int copies)\r\n   {\r\n      StringBuilder builder = new StringBuilder();\r\n      for (int i = 0; i < TARGET.Length; ++i)\r\n      {\r\n         builder.Append(ALLOWED_CHARS[rand.Next(ALLOWED_CHARS.Length)]);\r\n      }\r\n      string parent = builder.ToString();\r\n\r\n      int step = 1;\r\n      Console.WriteLine(\"{0:D4} {1}\", step, parent);\r\n\r\n      do \r\n      {\r\n         string[] children = new string[copies];\r\n         for(int i = 0; i < copies; ++i)\r\n         {\r\n            children[i] = Mutate(parent, rand.NextDouble());\r\n         }\r\n\r\n         int indexMax = 0;\r\n         double scoreMax = 0;\r\n         for (int i = 0; i < copies; ++i)\r\n         {\r\n            double score = Fitness(children[i]);\r\n\r\n            if (score > scoreMax)\r\n            {\r\n               scoreMax = score;\r\n               indexMax = i;\r\n            }\r\n         }\r\n\r\n         parent = children[indexMax];\r\n\r\n         Console.WriteLine(\"{0:D4} {1}\", step, parent);\r\n         step++;\r\n\r\n      } while (parent != TARGET);\r\n   }\r\n}\r\n<\/pre>\n
    Here is the output, but because of the bigger number of iterations, only every 20th iteration is shown:<\/p>\n
    \r\n0001 BXZZBDJSZTVYFWRSGNKYEULISWRK\r\n0020 MSTCFNBSTITVIS L KPLEDBRASEC\r\n0040 METCINQSDITVIS LIKW A IRISEW\r\n0060 METLINKSOITJIS LJKW A IGASEW\r\n0080 METLINKSOITJIS LJKX A WEAUEL\r\n0100 METLINKSTKTXIS LIKK A WEAOEL\r\n0120 METHINKS KTXIS LIKH A WEAOEL\r\n0140 METHINKSDKTXIS LIKA A WEASEL\r\n0160 METHINKSEGTXIS LIKA A WEASEL\r\n0180 METHINKSEGTEIS LIKE A WEASEL\r\n0200 METHIMKSEGTMIS LIKE A WEASEL\r\n0220 METHIMKSTITNIS LIKE A WEASEL\r\n0240 METHIAKSTIT IS LIKE A WEASEL\r\n0260 METHIPKSTIT IS LIKE A WEASEL\r\n0280 METHJKKSTOT IS LRKE A WEASEL\r\n0300 METHYQKSCOT IS LRKE A WEASEL\r\n0320 METHFPKSCOT IS LRKE A WEASEL\r\n0340 METHFPKSCGT IS LRKE A WEASES\r\n0360 METHINKS XT IS LMOE A WEAIEL\r\n0380 METHINKS YT IS LMZE A WEAIEL\r\n0400 METHINKS IT IS LMHE A WEAIEL\r\n0420 METHINKS IT IS LEDE A WEANEL\r\n0440 METHINKS IT IS LIPE A WEANYL\r\n0460 METHINKS IT IS LIPE A WEAOYL\r\n0480 METHINKS IT IS LIWE A WEARWL\r\n0500 METHINKS IT IS LIWEDA WEAFWT\r\n0520 METVINKS IT IS LILE A WEABBG\r\n0540 METVINKS IT IS LIJE A WEABTG\r\n0560 METHINKS IT IS LIJE A WEAMRV\r\n0580 METHINKS IT IS LIZE A WEAMRV\r\n0600 METHINKS IT IS LIZE A WEA OV\r\n0620 METHINKS IT IS LIZE A WEAHE\r\n0640 METHINKS IT IS LIJE A WEAHEH\r\n0660 METHINKS IT IS LIFE A WEAHEH\r\n0680 M THINKS IT IS LINE I WXAHEL\r\n0700 MQTHINKS IT IS LIAE I WXASEL\r\n0720 MZTHIRKS IT IS LIKE T WXASEL\r\n0740 METHINKR IT IS LIKE T WRASEL\r\n0760 METOINKI IT IS LIKE T WRASEL\r\n0780 METMINKM IT IS LIKE A WQASEL\r\n0800 METMINKS IT IS LIKE A WQASEL\r\n0820 METJIXKS IT IS LIKE A WQASEL\r\n0840 METJILKS IT IS LIKE A WUASEL\r\n0860 METJIPKS IP IS LIKE A WAASEL\r\n0880 METJIPKS IW IS LIKE A WLASEL\r\n0900 METIIBKS QT IS LIKE A SEASEL\r\n0920 METIIPKS PT IS LIKE A SEASEL\r\n0940 METKINKS PT IS LIKE A TEASEL\r\n0960 METKINKS BT IS LIKE A QEASEL\r\n0980 METWINKS IT IS LIKE A QEASEL\r\n1000 METOINKS IT IS LIKE ANQEASEL\r\n1020 METUINKS IT IS LIKE AHTEASEL\r\n1040 METUINKS IT IS LIKE AMWEASEO\r\n1060 METQINKS IT IS LIKE AMWEASEO\r\n1080 MZTYINKS IT ISULIKE AKWEASEL\r\n1100 MZTYINKS IT ISULIKE APWEADEL\r\n1120 MJTHINKS IT ISULIKE AEWEAQEL\r\n1140 MJTHINKS IT ISULIKE AFWEAUEL\r\n1160 MJTHINKS IT ISCLIKP AVWEABEL\r\n1180 MJTHINKS IT IS LIKP AVWEAGEG\r\n1200 MNTHINKS IT IS LIKM AVWEACE\r\n1220 MNTHINKS IT IS LIKM AQWEACEL\r\n1240 MNTHINKS IT IS LIKMXAKWEAAEL\r\n1260 MNTHINKS CT IS LIKMGAPWEASEL\r\n1280 MPTHINKS IX IS EIK GA WEASEL\r\n1300 METHINKS IX IS LIK RA WEASEL\r\n1320 METHINKS IZ IS LIKEWA WEASEL\r\n1340 METHINKS IZ ISILIKEWA WEASEL\r\n1360 METHINKS IJ ISILIKE A WEASEL\r\n1380 METHINKS IM ISELIKE A WEASEL\r\n1400 METHINKS IM ISELIKE A WEASEL\r\n1420 METHINKS IU ISELIKE A WEASEL\r\n1440 METHINKS IY ISELIKE A WEASEL\r\n1460 METHINKS IT ISVLIKE A WEASEL\r\n1480 METHINKS IT ISCLIKE A WEASEL\r\n1500 METHINKS IT ISCLIKF A WEASEL\r\n1520 METHINKS IT ISTLIKF A WEASEL\r\n1540 METXINKS IT ISOLIKF A WEASEL\r\n1560 MZTXINKS IT ISOLIKC A WEASEL\r\n1580 MATXINKS IT IS LIKC A WEASEL\r\n1600 MATXINKS IT IS LIKE A WEDSEL\r\n1620 METHINKSGITVIC LIKE A WEASEL\r\n1640 METHINKSGITQIC LIKE A WEASEL\r\n1660 METHINLSAITQIC LIKE A WEASEL\r\n1680 METHINLSAITQIH LIKE A WEASEL\r\n1700 METHINGS ITAIH LIKE A WEASEL\r\n1720 METHINGS ITRIS LIKE W WEASEL\r\n1740 METHINVS IT IS LIJE A WEASEL\r\n1760 METHINVS IT IS LIGE A WEASEL\r\n1780 METHINVS IT IS LIGE A WEASEL\r\n1800 METHINVS IT IS LI E A WEASYL\r\n1820 METHIN S IT IS LIKE A WTASYT\r\n1840 METHINQS IT IS LIKE A STASYT\r\n1860 METHINWA IT IS LIKE A IFASES\r\n1880 METHINKA IT IS LIKE A IFASEJ\r\n1900 METHINKA IT YS LIKE O IEAAEL\r\n1920 METHINKU IT YS LIKE O WEAAEL\r\n1940 METHOJKM IT JS LIKE O WEAPEL\r\n1960 METHOJKF IT IS LIKE  RWEATEL\r\n1980 METHFGKF IT IS LIKE ARWBATEL\r\n2000 METHYNKG IT IS LIKE ARWEALEL\r\n2020 METHUNKD IT IS LIKE AAWEAWEL\r\n2040 METHIWKN IT IS LIKE AYWEADEL\r\n2060 METHIUKN IT IS LIKE AKWEAQEL\r\n2080 METHIUKN IT IS LIKE A WEAQEL\r\n2100 METHIAKN IT IS LIKE N WEAQEL\r\n2120 METHINKK IT IS LIKE N WEEQEL\r\n2140 METHDNKQ IT IS LIKE A WEBSEL\r\n2160 METHDNKQ IT IS LIKE A WEBSEL\r\n2180 METHDNKQ IT IS LIKE A WEBSEL\r\n2200 METHMNKQ IT IS LIKE A WEBSEL\r\n2220 MEKHBNKX IT IS LIKE A WEBSEL\r\n2240 MEBHQNKS IT IS LIKE A WEBSEL\r\n2260 METHQNKS IT IS LIKEZA WEFSEL\r\n2280 METHGNKS IT IS LIKEZA WESSEL\r\n2300 METHGNKS IT IS LIKEZA WEWSEL\r\n2320 METHLNKS IT IP BIKE A WEOSEL\r\n2340 METHYNKS IT IB SIKE A WEQSEL\r\n2360 METHINKS ITQIJ LIKE A WEQSEL\r\n2380 METHINKS ITIIJ LIKE A WEYSTL\r\n2400 METQINKS ITIIJ LIKE A WEASGL\r\n2420 METHINKS ITIIJJLIKE A WEASGL\r\n2440 METHINKS ITQIWJLIKE A WEAS L\r\n2460 METHINKS ITZIWJLIKE A WEASCL\r\n2480 METHINKS IT IDLLIZE A UEASCL\r\n2500 METHINKS IT ID LIZE A IEASZL\r\n2520 METHINKS IT ID LIZE A IEASZL\r\n2540 METHINKS IT IB LIZE A XEASOL\r\n2560 METHINKS IT IB LIAE A  EASOL\r\n2580 METHINKS IT IBVLICE A  EASEL\r\n2600 METHINKS IT IBVLIKE A  EASEL\r\n2620 METHINKS IT IKDLIKE A  EASEL\r\n2640 METHINKS IT IKNLIKE A HEASEL\r\n2660 METHINKS IT IKNLIKE A HIASEL\r\n2680 METHINKS IT IZNLIKE A HIASEL\r\n2700 METHINKS IT IZNLIKE A WOASEL\r\n2720 METHINKS IT ISNLIKE A WOASEL\r\n2740 METHINKS IT ISNLIKE M WSASEL\r\n2760 METHINKS IT ISVLIKE M WXASEL\r\n2780 METHINKS IT IS LIKE S WEASEL\r\n2785 METHINKS IT IS LIKE A WEASEL\r\n<\/pre>\n
    Notice that matching letters are not immutable. A letter, even if it matches one in the target string can change at any time.<\/p>\n
    You can find similar implementations in several programming languages on the Rosetta Code website<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
    In the book The Blind Watchmaker, Richard Dawkins explains how evolution happens through accumulated small random variations (or mutations) filtered by the natural selection, as opposed to the mainstream misinterpretation that evolution happens in big leaps. He proposes a computer program, called weasel, to demonstrate how the accumulated small improvements (mutations that bring a benefit … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[11],"tags":[187,189,188,186],"class_list":["post-455","post","type-post","status-publish","format-standard","hentry","category-csharp","tag-dawkins","tag-evolution","tag-simulation","tag-weasel"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t