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 /files/fragments/PetPurchase1.php.txt.