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

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

Genetic Algorithm (GA)

• 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)

  $ java knapsack.KnapsackGaSolver1 problem.txt 8 100 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

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

  $ 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).

Note

• Since this assignment depends on randomness and the number of iterations, you program may not always get the optimal solution. Thus, we will run your program multiple times and will not take out any points if your answer is within 5% from the optimal solution. You can use KnapsackDpSolver.java (this is available in the provided zip file too) to get the optimal solution, which implements a Dynamic Programming algorithm. This program takes the same knapsack problem file as we use in Part 1 and Part 2 as follows:

    $ java knapsack.KnapsackDpSolver problem.txt
  

• You can include regular java files in your solution as long as the core actor related part is written in SALSA. Make sure those java files implement Serializable as required by SALSA.

Due Date

Submission Requirements