Winter 2014 Challenge

This challenge is open to the students enrolled in Advanced Programming in .NET – COMP-10068 (Winter 2014) at Mohawk College.

This challenge is in no way part of the actual course itself, it is provided as a completely optional side project that is (hopefully) fun and challenging.

The challenge isn’t intended to be “Kobayashi Maru” hard. ;-) But it is intended to give you a chance to explore something completely new and different.

Due date

The challenge has to be completed and e-mailed to me at kevin.browne3@mohawkcollege.ca by Wednesday April 30th 2014.

Solutions can be sent as many times as is required to get it right, but I can only look over solutions and respond so quickly.

Reward

floppydisk

As a souvenir and reward in exchange for completing the challenge, you’ll receive a 3.5″ floppy disk, with a cover signed by me along with the year the challenge was completed, the name of the challenge you completed, and your name. I doubt these things will become like Knuth cheques, but it’s something!

Challenge

Create a Genetic Algorithm Solution to the Knapsack Problem

The knapsack problem is a combinatorial optimization problem with many real life applications related to allocating resources. The problem roughly stated is, given x items, each with v value and w weight, and a knapsack capable of holding max weight m, what is the maximum value of items that we can put in the knapsack without going over the max weight the knapsack is able to carry?

knapsack

One version of the problem is called the 0-1 knapsack problem, where we assume that we only have one of each item, and we can either put an item in the knapsack or not. Other variations of the problem allow you to put different numbers of each item into the knapsack, or a fraction of the item into the knapsack.

The knapsack problem is a type of problem that is difficult (i.e. very time consuming) to solve using a computer, these types of problems are called NP-Complete and NP-Hard. This is part of what makes it a particularly interesting problem – unlike other problems, we can’t write an algorithm that will quickly give us the correct answer every time.

xkcd

One way of finding solutions to the problem would be to use a genetic algorithm (GA). Genetic algorithms are a way to search for optimal solutions to a problem by mimicking the process of natural selection. An initial “population” of solutions is generated, these solutions are tested for “fitness”, the most fit solutions combine and “breed” to produce offspring (i.e. a new set of hopefully improved solutions), and the new offspring is tested for fitness and on and on. There are many different ways to write a genetic algorithm – how to produce the offspring, how to represent solutions, how to combine solutions to produce child solutions (should their be mutations, and how many mutations), how to decide which solutions make it on to the next generation, when to stop the algorithm, etc.

Problem

Write a genetic algorithm solution in C# to solve the 0-1 knapsack problem. Test it with different sizes of the knapsack problem in terms of the number of items, value and weight of the items, and maximum weight of the knapsack. Can your algorithm find the optimal solution? What if you keep increasing the number of items? How close does it get? You can experiment with different solution population sizes and other variations of your genetic algorithm too. Test it against another solution to the knapsack problem (perhaps the brute force solution or a dynamic programming solution). Document these tests and experiments in the comments of your code and explain what you have done.

Resources

Notes

  • Feel free to “explore”. If you aren’t sure you are doing things the “right” way, or if you want to know whether to do something one way or another way, try it out and see what happens. There is no one right answer here and there is room for exploration and experimentation. In fact, that’s what I’d be happy to see!
  • Don’t worry about any scary math you see in articles discussing this topic – it’s not that bad in practice, and you have enough knowledge of C# to code a solution.