CSCI.4430/6969 Programming Languages Spring 2012
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.
Programming Assignment #3
Solving Knapsack Problem with Genetic Algorithm
In this assignment, you will develop SALSA
code to solve a knapsack problem in an evolutionary manner.
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:
- Step 1: Randomly create a population of N individuals (each individual represents a solution to the problem)
- Each individual is encoded as a string (called chromosome)
- Ex.) Binary encoding for the knapsack problem: 0010101...11 (1:item is chosen, 0:item is not chosen)
- Step 2: Evaluate the fitness of each individual
- Decode the chromosome into a solution, evaluate it by a fitness function, and determine how good the solution is
- Step 3: If one of the solutions is good enough or the algorithm reaches the maximum iteration, exit
- Step 4: Otherwise, create a new generation of the population
- For X% of the new N individuals, preserve "elite" individuals from the previous generation
- For (100-X)% of the new N individuals, create new offspring through crossover and mutation
- crossover: select two parents from the previous generation, randomly choose a certain position of the chromosomes,
and swap them after the chosen position
- Ex.) parents (111111, 000000) -> offspring (111000, 000111) (crossover occurred at the 4th position)
- mutation: randomly choose Y% of N individuals and modify a randomly chosen position on their chromosomes
- Ex.) 111111 -> 111101 (mutation occurred at the 5th position)
- Step 5: Go to Step 2
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)
- Add a load balancing capability to your program. Instead of creating the same number of worker actors on each theater, create all workers on a single theater.
Then, have other theaters steal some worker actors from the theater with many worker actors. Include the test code and an explanation of the results in your submission.
- See the professor if you have ideas for other extensions to this assignment and would like extra credit for implementing them (Added on April 24th).
|before Thursday, 04/26, 11:59PM
|before Friday, 04/27, 11:59PM
||no modification (on time)
|before Saturday, 04/28, 11:59PM
|before Monday, 04/30, 11:59PM
|after Tuesday, 05/01, 12:00AM
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.