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.