{"id":38,"date":"2008-12-11T01:20:19","date_gmt":"2008-12-11T09:20:19","guid":{"rendered":"http:\/\/sethjust.wordpress.com\/?p=38"},"modified":"2010-11-11T15:23:45","modified_gmt":"2010-11-11T23:23:45","slug":"genetic-algorithms-in-perl","status":"publish","type":"post","link":"https:\/\/sethjust.com\/2008\/12\/11\/genetic-algorithms-in-perl\/","title":{"rendered":"Genetic Algorithms in Perl"},"content":{"rendered":"<p>Inspired by <a href=\"http:\/\/hackaday.com\/2008\/12\/08\/genetic-programming\/\">recent<\/a> <a href=\"http:\/\/rogeralsing.com\/2008\/12\/07\/genetic-programming-evolution-of-mona-lisa\/\" class=\"broken_link\">genetic<\/a> algorithms floating around, I decided to try my hand at implementing one in perl. I&#8217;d thought for a long time that it would be quite difficult, but really it&#8217;s quite easy. My biggest hangup was dealing with data structures, but once I did that, it turns out that all you really need is a few functions:<\/p>\n<ul>\n<li>A fitness function, that determines which individuals are most fit to reproduce<\/li>\n<li>A mutate function, that will add random chance into each generation<\/li>\n<li>A breed function that allows the best individuals to reproduce.<\/li>\n<\/ul>\n<p>I ended up implementing a very simple algorithm, but it&#8217;s fairly fast and very generic \u00e2\u20ac\u201c it can be easily adapted to just about any task. Sadly, I have no fascinating application just yet, but if I stumble across one, I&#8217;ll be sure to post about it.<\/p>\n<p>After the jump, I&#8217;ll put up some of the code I used and a link to the script, all for your viewing pleasure.<br \/>\n<!--more--><\/p>\n<p>The heart of the algorithm is the mutate and breed functions:<\/p>\n<pre lang=\"perl\">sub mutate{     # Mutates each allele of an individual by a random, weighted amount,\r\n                #    controlled by certain parameters. It re-initializes if the allele\r\n                #    is zero, and takes abs()\r\n    my $ind = shift;\r\n\r\n    for (@$ind) {\r\n        $_ = eval($init_string) unless ($_);\r\n        $_ += (rand(2) - 1)*($mut_weight*($_)+$mut_offset);\r\n        $_ = -$_ unless ($_>0);\r\n    }\r\n\r\n    return 0;\r\n}\r\n\r\nsub breed{      # Breeds each individual with the top 20 percent of the population randomly\r\n                #    by averaging each allele of the individual with the corresponding allele\r\n                #    of a random individual in the top quintile. Note that this means that\r\n                #    each individual breeds with, at most (and ideally), as many individuals\r\n                #    as it has alleles, which breaks down the parent \/ child model slightly.\r\n    my $indvs = shift;\r\n    my @list;\r\n    ($minimize) || (@list = sort {fitness($b)  fitness($a)} @$indvs);  # Sort asc. vs. desc.\r\n    ($minimize) && (@list = sort {fitness($a)  fitness($b)} @$indvs);\r\n\r\n    @list = @list[1..(int(scalar(@list)\/5)+1)];\r\n\r\n    for (@$indvs) {              # Iterate through individuals\r\n        my $ind_ref = $_;\r\n        my $i = 0;\r\n        for (@$ind_ref) {        # Iterate through alleles\r\n            $_ = ((@list[int(rand(length(@list)-1))])->[$i] + $_)\/2;      # Average given allele with\r\n                                                                          #    a random, fit,\r\n                                                                          #    corresponding allele\r\n            $_ = (rand(1)<$reset_prob?eval($init_string):$_);             # Re-init the allele some\r\n                                                                          #    percent of the time\r\n            $i++;\r\n        }\r\n    }\r\n\r\n    return 0;\r\n}<\/pre>\n<p>Between the comments and the code, it should be pretty clear what's going on in here, although some of the data structures are kinda hard to get from this section. As I explain in the <a href=\"http:\/\/people.reed.edu\/~justs\/genes.pl\" class=\"broken_link\">code<\/a>:<\/p>\n<blockquote><p>A randomized population is created. An array holds references to the specified number of \"individuals\". Each individual is an array of alleles (scalar values) that are chosen by evaluating a specified string. These are currently positive real numbers.<\/p><\/blockquote>\n<p>These references (or references to the population array) are passed as arguments to the functions each iteration.<\/p>\n<p>If you're interested, be sure to check out the <a href=\"http:\/\/people.reed.edu\/~justs\/genes.pl\" class=\"broken_link\">code<\/a> and please give me some feedback!<\/p>\n<p>UPDATE: Ivan in the comments made the recommendation of using an anonymous function to intialize individuals. I made that change he recommended and updated the code.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Inspired by recent genetic algorithms floating around, I decided to try my hand at implementing one in perl. I&#8217;d thought for a long time that it would be quite difficult, but really it&#8217;s quite easy. My biggest hangup was dealing with data structures, but once I did that, it turns out that all you really [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,6],"tags":[14,36,45,46,156,158],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/posts\/38"}],"collection":[{"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/comments?post=38"}],"version-history":[{"count":3,"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/posts\/38\/revisions"}],"predecessor-version":[{"id":208,"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/posts\/38\/revisions\/208"}],"wp:attachment":[{"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/media?parent=38"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/categories?post=38"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sethjust.com\/wp-json\/wp\/v2\/tags?post=38"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}