In addition to exams, problem sets were used to test knowledge and give hands-on experience working with techniques covered in class. An example problem from one problem set is laid out here:

​

Description:

    You are going on a hiking trip, and there is a limit to the things you can bring. You have two things: a backpack with a size (the weight it can hold, that is) and a set of boxes with different weights and different importance values.

   Weight list:              [20, 30, 60, 90, 50, 70, 30, 30, 70, 20, 20, 60]     (12 items)

   Importance list:       [6, 5, 8, 7, 6, 9, 4, 5, 4, 9, 2, 1]

 

Goal:

The goal is to fill the backpack to make it as valuable as possible without exceeding the maximum weight (250).

    1) Define the problem in the context of genetic algorithms

    2)  Provide the genome for the problem

    3) Define fringe operations

    4) Cull your population by 50% at every generation

​

Solution:

My approach is laid out here:

​

The problem can be formalized as a genetic search process as follows: Let X be the set of possible items and let A = {x_1,...,x_n} be the power set of X. Then n = 2^{12}.

 

Define a genome/chromosome to be an element x_i of A, represented by binary sequence of 12 inclusion/exclusion variables.

 

Define the fitness function f to be:

     - f(x_i) = {sum of importance values ("precedence") of items in i} for sum <= limit. 0 for sum > limit.                 - Alternatively, the sum over precedences times kronecker delta which is equal to 1 if the element is in x_i         and zero otherwise

 

Initialize the population of size N < n

 

Cull the bottom 50% with the lowest fitness functions

 

Of the remaining population, take each chromosome and randomly permute whether or not it has an item in it

      Uniform distribution can be used, but also can randomly permute giving higher weights to common                items. I.e. if 9 of 10 of the strongest 50% all have item 4 in common, make this less likely to permute

 

Repeat for desired number of iterations or until a given efficiency is reached by at least 1 chromosome

​

Implementation:

I implemented the above solution in Python utilizing NumPy and PyPlot. Below, a chart of the fitness of each chromosome in each iteration can be seen, along with progress charts of the most/least fit chromosomes.