Solving the 0-1 Knapsack Problem with a Genetic Algorithm in Ruby

The Knapsack Problem

The Knapsack Problem is an NP combinatorial optimization problem in which items that have both value and weight are placed into a "knapsack" with a weight limit. The goal is to maximize the value of the items while keeping the total weight of the items below the weight limit threshold. A maximized solution can be approximated using a genetic algorithm.

Genetic Algorithm

Genetic algorithms are biologically inspired, using natural selection, reproduction, mutation, and other elements of evolution to obtain solutions. They are often used to solve optimization problems and model certain systems.

Solution

item.rb

 1class Item
 2
 3  attr_accessor :weight, :value
 4
 5  def initialize(weight, value)
 6    @weight = weight
 7    @value = value
 8  end
 9
10end

The Item class as both a weight and a value, which will be set randomly within a range.

knapsack.rb

 1class Knapsack
 2
 3  attr_accessor :chromosome, :total_weight, :total_value
 4
 5  def initialize(chromosome)
 6    @chromosome = chromosome
 7    total_weight = 0.0
 8    total_value = 0.0
 9  end
10
11end

The Knapsack class has a chromosome, or array of 0s and 1s representing whether a specific item is included in the knapsack, along with a total weight and a total value which will be calculated and stored based on its chromosome.

genetic.rb

 1require_relative('item.rb')
 2require_relative('knapsack.rb')
 3
 4if ARGV.length > 0
 5  num_items = ARGV[0].chomp.to_i
 6  num_knapsacks = ARGV[1].chomp.to_i
 7  num_generations = ARGV[2].chomp.to_i
 8  verbose = ARGV[3]
 9  if verbose == "true"
10    verbose = true
11  else
12    verbose = false
13  end
14end

Loads the Item and Knapsack classes and accepts user input for the number of items, the number of knapsacks in the population, the maximum number of generations, and whether the script should run in verbose mode or silently. Note that there isn't really any validation here, so the script assumes correct user input.

 1items = []
 2knapsacks = []
 3generation = 1
 4
 5# Generate random items
 6num_items.times do
 7  ran_weight = (rand * 10).round(2)
 8  ran_value = (rand * 100).round(2)
 9  items << Item.new(ran_weight, ran_value)
10end
11
12# Generate initial knapsacks
13num_knapsacks.times do 
14  ran_items = []
15  num_items.times do
16    if rand < 0.1
17      ran_items << 1
18    else
19      ran_items << 0
20    end
21  end
22  knapsacks << Knapsack.new(ran_items)
23end

The group of items is created with a pseudorandom weights between 0.0 and 10.0 and pseudorandom values between 0.0 and 100.0. then the initial generation of knapsacks is created each with a pseudorandom chromosome where each item has a 10% chance of being turned on.

 1# Main loop
 2until generation > num_generations
 3  
 4  puts "==================================" if verbose
 5  puts "Begin generation: " + generation.to_s if verbose
 6  puts "==================================" if verbose
 7
 8  sum_value = 0.0
 9  best_value = 0.0
10  best_knapsack = 0
11  max_weight = 50.0
12
13  # Calculate value and weight
14  knapsacks.each_with_index do |knapsack, index|
15    total_weight = 0.0
16    total_value = 0.0
17    knapsack.chromosome.each_with_index do |gene, gene_index|
18      if gene === 1
19        total_weight += items[gene_index].weight
20        total_value += items[gene_index].value
21      end
22    end
23    if total_weight <= max_weight
24      if total_value > best_value
25        best_value = total_value
26        best_knapsack = index
27      end
28    else 
29      total_value = 0.0
30    end
31    knapsack.total_weight = total_weight
32    knapsack.total_value = total_value
33    sum_value += total_value
34  end

As the main loop begins, we calculate the total weight and total value of each knapsack in order to determine its fitness. If a knapsack is over the weight limit, its value becomes 0.0 which effectively will remove it from the population. Note that the best overall knapsack is stored, and the sum_value of all knapsacks is calculated as well.

 1  # Use Roulette wheel algorithm to proportionately create next generation
 2  new_generation = []
 3  elitist = Knapsack.new(knapsacks[best_knapsack].chromosome.clone)
 4  puts 'Elitist: ' + best_knapsack.to_s if verbose
 5  p elitist if verbose
 6  (num_knapsacks-1).times do
 7    rnd = rand();
 8    rnd_sum = 0.0
 9    rnd_selected = 0;
10
11    knapsacks.each do |knapsack|
12      rel_value = knapsack.total_value / sum_value
13      rnd_sum += rel_value
14      if rnd_sum > rnd
15        break
16      else
17        rnd_selected += 1
18      end
19    end
20    new_generation << Knapsack.new(knapsacks[rnd_selected].chromosome.clone)
21  end
22
23  # Replace old generation with new
24  knapsacks = []
25  knapsacks = new_generation
26  generation += 1

Here a Roulette Wheel style algorithm is used to create a new generation. Essentially a random number is chosen between 0.0 and 1.0, then each knapsack is looped through and their relative value is summed. The knapsack whose relative value is the one that puts the sum over the random value becomes a parent in the next generation. This has the effect of each knapsack occupying its own "slice" of a Roulette wheel, with its size proportionate to its share of value in the population.

 1  # Randomly select two knapsacks
 2  rnd_knap_1 = (0...num_knapsacks-1).to_a.sample
 3  rnd_knap_2 = rnd_knap_1
 4  until (rnd_knap_2 != rnd_knap_1)
 5    rnd_knap_2 = (0...num_knapsacks-1).to_a.sample
 6  end
 7
 8  # Perform crossover
 9  split_point = (0...num_items-1).to_a.sample
10  front_1 = knapsacks[rnd_knap_1].chromosome[0, split_point];
11  front_2 = knapsacks[rnd_knap_2].chromosome[0, split_point];
12  back_1 = knapsacks[rnd_knap_1].chromosome[split_point, num_items-1];
13  back_2 = knapsacks[rnd_knap_2].chromosome[split_point, num_items-1];
14  new_chr_1 = front_1 + back_2
15  new_chr_2 = front_2 + back_1
16  new_1 = Knapsack.new(new_chr_1)
17  new_2 = Knapsack.new(new_chr_2)
18
19  knapsacks[rnd_knap_1] = new_1
20  knapsacks[rnd_knap_2] = new_2

Now it is time to expand the search space, so we randomly choose two knapsacks from the new generation and perform crossover. A randomly determined point in the chromosome separates each chromosome into a head and a tail. The heads and tails are swapped between the two chromosomes, which represents a large jump in the search space.

 1  # Perform mutation
 2  knapsacks.each do |knapsack|
 3    knapsack.chromosome.each_with_index do |gene, index|
 4      if rand < 0.01
 5        puts 'Successful mutation at gene: ' + index.to_s if verbose
 6        gene == 0 ? gene = 1 : gene = 0
 7        knapsack.chromosome[index] = gene
 8      end
 9    end
10  end

Mutation is performed to make smaller "tweaks" in the search space. For each knapsack and each gene in its chromosome there is a 1% chance that it will flip, either going from 0 to 1 or 1 to 0.

1  knapsacks << elitist
2
3  puts 'Last knapsack:' if verbose
4  p knapsacks[num_knapsacks-1] if verbose
5  puts 'Best value:'
6  p best_value
7
8end

Finally, the elitist knapsack is added back into the next population (after the crossover and mutations so that it is not effected) and the main loop ends with some useful output.

Conclusion

The solution provided by the genetic algorithm is not guaranteed to be an absolute maximum, but if it runs long enough to eventually cover the majority of the solution space then it will certainly provide a very good solution. There are lots of things that you can tweak in this algorithm as well, such as the percentage chance of mutation or the method used for crossover. You can remove the elitism if desired, or change it to include the best five. If you make any significant changes and want to share them, don't hesitate to contact me!

The full code is publicly available on GitHub, and may be more up to date than the code here although I will try to keep this post updated.