Tag Archives: Genetic Algorithms

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

This week, we’ll wrap up our genetic algorithm solution to our recent pet store problem:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15, cats cost $1, and mice are 25 cents each.  Finish implementing our genetic algorithm solution by doing the natural selection and termination.

To play along, post your code as a comment or send it via email.  If you’d like, you can build atop my current PetPurchase class; I put in placeholders for the next steps.

Last Week’s Fragment – Solution

Last week we continued our genetic algorithm solution to our recent pet store problem:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15, cats cost $1, and mice are 25 cents each.  Continue implementing our genetic algorithm solution.  Write code to create an initial generation (random population) of PetPurchases and create (“breed”) subsequent generations by crossover and, if desired, mutation.

We can create the initial population by adding these methods:

     /**
      * Generate a random set of counts, within reasonable constraints.
      */
     public function randomize() {
         $this->setDogCount(rand(1,6));
         $this->setCatCount(rand(1,85));
         $this->setMouseCount(rand(1,336));        
     }
     /**
      * Create a population of the given size with random individuals.
      */
     public static function createPopulation($size) {
         $population = array();
         for ($i=0; $i<$size; $i++) {
             $purchase = new PetPurchase();
             $purchase->randomize();
             array_push($population, $purchase);
         }
         return $population;
      }

And combination and mutation is done with these new methods:

     /**
      * Set my attributes from those of my parents.
      * This is also known as breeding, crossover, or recombination.
      */
     public function combine($dad, $mom) {
         $this->setDogCount(rand(0,1) == 0 ?
                             $dad->getDogCount() : $mom->getDogCount());
         $this->setCatCount(rand(0,1) == 0 ?
                             $dad->getCatCount() : $mom->getCatCount());
         $this->setMouseCount(rand(0,1) == 0 ?
                               $dad->getMouseCount() : $mom->getMouseCount());
      }
 
      /**
       * Mutate my attributes so that I'm not an exact clone of my parents.
       */
      public function mutate() {
          $this->setDogCount(rand(0,2) == 0 ?
                              rand(1,6) : $this->getDogCount());
          $this->setCatCount(rand(0,2) == 0 ?
                              rand(1,85) : $this->getCatCount());
          $this->setMouseCount(rand(0,2) == 0 ?
                              rand(1,336) : $this->getMouseCount());
      }

There are the many possible ways to go about this; breeding techniques can be quite different, but still result in a population that contains a correct (best fit) solution.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

This week, we continue our genetic algorithm solution to our recent pet store problem:

Write code to create an initial generation (random population) of PetPurchases and create (“breed”) subsequent generations by crossover and, if desired, mutation. We’ll finish by doing the natural selection and termination next week.

To play along, post your code as a comment or send it via email.  If you’d like, you can build atop my initial PetPurchase class; I put in placeholders for the next steps.

Last Week’s Fragment – Solution

Genetic algorithms have received new attention lately with interesting things like BoxCar 2D.  So with last week’s puzzle, we began looking at a genetic algorithm approach to solving a recent Friday Fragment:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15.  Cats cost $1, and mice are 25 cents each.  Start implementing a genetic algorithm solution – determine how to encode candidate solutions (individuals) and code the fitness function.

We could encode candidate solutions using a simple associative array with the number of dogs, cats, and mice, but I decided to create a class (PetPurchase) and use instance variables, like so:

     class PetPurchase {
         private $dogCount, $catCount, $mouseCount;

Here’s a very simple fitness function I wrote – a method on PetPurchase.  There are many possible answers.

     public function getFitness() {

         // There must be at least one of each animal:
         if ($this->getDogCount() == 0 ||
             $this->getCatCount() == 0 ||
             $this->getMouseCount() == 0)
              return 0;

         $countError = abs(100 - $this->getTotalCount());
         $amountError = abs(100 - $this->getTotalCost());

         if ($countError > 50 || $amountError > 50)
             return 0;
         else
             return 100 - ($countError + $amountError);
     }

For the rest of this initial code, see http://derekwilliams.us/fragments/PetPurchase1.php.txt.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Genetic algorithms have received new attention lately with interesting things like BoxCar 2D.  And while some of the research around them may seem mysterious, the basic approach is quite simple.  Let’s revisit a recent Friday Fragment and apply evolutionary techniques to solve it:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15.  Cats cost $1, and mice are 25 cents each.  Start implementing a genetic algorithm solution – determine how to encode candidate solutions (individuals) and code the fitness function.

To play along, post your code as a comment or send it via email.  You can refer back to Joe’s conventional programming solution if you’d like; the point here is to re-structure it into a genetic algorithm in order to learn this approach first-hand.

Last Week’s Fragment – Solution

Last week’s puzzle continued our team ranking system based on win/loss records and strength of schedule (SOS):

Write code to calculate the RPI (Ratings Percentage Index) for a set of teams using the basic Wikipedia calculation.  Present the teams ordered by RPI.

I updated my PHP Team class (now TeamRPI) to calculate RPI and sort the results. Here are the changes:

     public function computeRPI() {
         ... // (code up to here is the same as last week)
         $this->setRPI((0.25 * $this->getWinPercent())
                         + (0.5 * $or) + (0.25 * $oor));
     }
     public static function sortByRPI() {
         usort(self::$allTeams, array('TeamRPI', 'compareRPI'));
     }
     public function compareRPI($team1, $team2) {
        if ($team1->getRPI() == $team2->getRPI())
           return 0;
        return ($team1->getRPI() > $team2->getRPI()) ? -1 : 1;
     }

While at it, I improved performance by using an associative array:

     private static function addTeam($team) {
        self::$allTeams[$team->getName()] = $team;
     }
     public static function getTeam($name) {
         return self::$allTeams[$name];
     }

You can run this at  http://derekwilliams.us/fragments/rpi.html, which also includes links to the source code and 2010 NCAA Football data.

Here are the top 15 RPI rankings it calculates from this data, which is similar to other pure RPI rankings.

Rank Name Record Win % RPI
1 Auburn 14-0-0 1.000 0.694
2 LSU 11-2-0 0.846 0.660
3 Oklahoma 12-2-0 0.857 0.652
4 Arkansas 10-3-0 0.769 0.646
5 Alabama 10-3-0 0.769 0.638
6 Texas A&M 9-4-0 0.692 0.633
7 Stanford 12-1-0 0.923 0.632
8 TCU 13-0-0 1.000 0.631
9 Missouri 10-3-0 0.769 0.629
10 Ohio St. 12-1-0 0.923 0.628
11 Oregon 12-1-0 0.923 0.627
12 Michigan St. 11-2-0 0.846 0.622
13 Boise St. 12-1-0 0.923 0.621
14 Oklahoma St. 11-2-0 0.846 0.620
15 Florida St. 10-4-0 0.714 0.616

This shows some interesting things when compared to polls and other ranking systems, such as one reason why TCU is moving to the Big East.