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:
(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.
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