George Mason University

CS491 Great Principles Fall 2002

Design Problem ECD1 (5 points extra credit)

Due 12/1/02

Before doing these problems, re-read the essay on algorithms and machines. You may also find it helpful to read the book Computers, Ltd. by David Harel, Oxford, 2001 (listed in the course reference list).

Genetic algorithms were invented as a way to evolve good solutions to hard problems, rather than try to compute them by brute-force search over a large space of possibilities. These algorithms are based on an analogy with living systems, in which individuals with good genetic codes have greater fitness and can cross breed with others to proliferate more of their kind. An example of a genetic algorithm for solving an NP-hard combinatorial problem, the knapsack problem, is given in the essay. The purpose of this design problem is to help you fully understand the power and workings of genetic algorithms. You will be working with this knapsack problem:

Object    Size    Value   Knapsack capacity = 10
------    -----   -----
1          5       100
2          2        11
3          1         9
4          3        55
5          4        82
6          2        10
7          6       130
8          2        12
9          3        62
10         4        78

(1) Give at least two examples of real world problems that are modeled by the knapsack problem.

(2) A heuristic for solving the problem is to order the objects by their value/size ratios, then attempt to pack them in order of decreasing ratio. What packing(s) does this heuristic yield? What value is achieved?

(3) Write a program that finds the best solution by searching over all possible 10-bit vectors, where a bit vector indicates which objects are "in". Vectors that exceed knapsack capacity are considered "unfit". What is (are) the optimal packing(s)? Their value(s)? Record the running time of this program.

(4) Write a genetic algorithm that finds a solution. (See text for example.) Record its running time. What is (are) the best packings according to this program? What is the best value?

(5) Draw conclusions about the effectiveness of the three approaches.