CSCI.4430/6969 Programming Languages Spring 2012
Programming Assignment #3

This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get help from the TAs or the instructor. You are encouraged to use the RPILMS Discussions page to post problems so that other students can also answer/see the answers.

Solving Knapsack Problem with Genetic Algorithm

In this assignment, you will develop SALSA code to solve a knapsack problem in an evolutionary manner.


Knapsack Problem

Given a maximum weight you can carry in a knapsack and items, each with a weight and a value, find a set of items you can carry in the knapsack so as to maximize the total value. See here for a formal definition.


Imagine a thief with a knapsack who wants to maximize his earnings...

Your program has to take a problem file in the following format:

  1st line: the maximum weight of the knapsack
  2nd line: the number of items
  3rd line ... last line : an item ID followed by the weight and value of an item
An example problem file is here.

Genetic Algorithm (GA)

GA is a useful algorithm to find approximate solutions. Like the evolutionary process of species, first it creates a set of solutions randomly and tries to evolve them over time. Typical steps of GA looks like the following:


Problem Part 1 - Concurrent Solution (80/100 points)

Write a concurrent solution of the knapsack problem in SALSA using Genetic Algorithm. There should be M worker actors and one coordinator actor, where each worker actor is responsible for evaluating N/M individuals that are given from the coordinator actor. Essentially, the worker actors do only Step 2 in the above steps of GA, whereas the coordinator actor does all the other steps. All the actors run locally in a single theater in Part 1.

For your convenience, we provide you a sequential version of knapsack GA solver source code written in Java (knapsack.zip). Most of the code can be used in your solution, but you have to write the above coordinator-worker pattern in SALSA.

Your program is required to take four arguments in the order of: a knapsack problem file, the number of worker actors, the number of iterations, and the number of individuals. The command to execute the program should look like the following:
  $ java knapsack.KnapsackGaSolver1 problem.txt 8 100 1000
(the problem file: problem.txt, the number of worker actors: 8, the number of iterations: 100, the number of individuals: 1000)

Also, your coordinator actor should output messages like the following:

  Iteration = 1, Fitness (best = 0.555, avrg = 0.444, worst = 0.111)
  Iteration = 2, Fitness (best = 0.580, avrg = 0.476, worst = 0.222)
    ...
  Iteration = 100, Fitness (best = 1.000, avrg = 0.980, worst = 0.953)

  Maximum Knapsack Weight: XXX
  Total Item Weight: YYY
  Total Item Value: ZZZ
  Selected Items (item ID, weight, value):
  1, w1, v1
  3, w3, v3
  10, w10, v10
    ....
  88, w88, v88
Hint: this example uses a similar worker-coordinator design pattern.

Problem Part 2 - Distributed Solution (20/100 points)

Write a distributed version of the solution in SALSA based on Part 1. That is, you should use multiple theaters and distribute worker actors on each theater. In addition to the arguments used in Part 1, your program must accept another argument to specify theaters and a nameserver as follows:
  $ java knapsack.KnapsackGaSolver2 problem.txt 8 100 1000 theaters.txt

The theaters.txt is a text file, the first line of which is the location of the nameserver and the rest are locations of theaters. An example of theaters.txt is here.

Extra Credit (up to 25% bonus)

Note


Due Date

Received Time Grade Modification
before Thursday, 04/26, 11:59PM +10%
before Friday, 04/27, 11:59PM no modification (on time)
before Saturday, 04/28, 11:59PM -10%
before Monday, 04/30, 11:59PM -25%
after Tuesday, 05/01, 12:00AM not accepted

Submission Requirements

Please submit a ZIP file with your code, including a README file. In the README file, place the names of each group member (up to two). Your README file should also have a list of specific features / bugs in your solution. Your ZIP file should be named with your RPILMS user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair via RPILMS.


Last Updated -- April 24th, 2012.