Genetic Algorithm vs. 0-1-KNAPSACK

brute_force.rb

# taken from http://rosettacode.org/wiki/Knapsack_problem/0-1#Brute_force
class Array
  # do something for each element of the array's power set
  def power_set
    yield [] if block_given?
    self.inject([[]]) do |ps, elem|
      r = []
      ps.each do |i|
        r << i
        new_subset = i + [elem]
        yield new_subset if block_given?
        r << new_subset
      end
      r
    end
  end
end

def brute_force(problem)
  potential_items = problem.items
  knapsack_capacity = problem.max_cost

  maxval = 0
  solutions = []

  potential_items.power_set do |subset|
    cost = subset.inject(0) {|w, elem| w += elem.cost}
    next if cost > knapsack_capacity

    value = subset.inject(0) {|v, elem| v += elem.value}
    if value == maxval
      solutions << subset
    elsif value > maxval
      maxval = value
      solutions = [subset]
    end
  end

  solutions.each do |set|
    items = []
    wt = 0
    set.each {|elem| wt += elem.cost; items << elem.name}
    #puts "cost: #{wt}"
    puts "Found solution: #{items.sort.join(', ')}"
    puts "With value: #{maxval}"
  end
end

dynamic_programming.rb

# translated from http://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p
def dynamic_programming_knapsack(problem)
  num_items = problem.items.size
  items = problem.items
  max_cost = problem.max_cost

  cost_matrix = zeros(num_items, max_cost+1)

  num_items.times do |i|
    (max_cost + 1).times do |j|
      if(items[i].cost > j)
        cost_matrix[i][j] = cost_matrix[i-1][j]
      else
        cost_matrix[i][j] = [cost_matrix[i-1][j], items[i].value + cost_matrix[i-1][j-items[i].cost]].max
      end
    end
  end

  cost_matrix
end

def get_used_items(problem, cost_matrix)
  i = cost_matrix.size - 1
  currentCost = cost_matrix[0].size - 1
  marked = Array.new(cost_matrix.size, 0) 

  while(i >= 0 && currentCost >= 0)
    if(i == 0 && cost_matrix[i][currentCost] > 0 ) || (cost_matrix[i][currentCost] != cost_matrix[i-1][currentCost])
      marked[i] = 1
      currentCost -= problem.items[i].cost
    end
    i -= 1
  end
  marked
end

def get_list_of_used_items_names(problem, cost_matrix)
  items = problem.items
  used_items = get_used_items(problem, cost_matrix)

  result = []

  used_items.each_with_index do |item,i|
    if item > 0
      result << items[i].name
    end
  end

  result.sort.join(', ')
end

def zeros(rows, cols)
  Array.new(rows) do |row|
    Array.new(cols, 0)
  end
end

genetic_algorithm.rb

class KnapsackSolution
  include Comparable

  attr_reader :genome

  def initialize(problem, bit_string=nil)
    @problem = problem 

    if bit_string # use given bit string if it exists
      @genome = bit_string
    else # pick random bit string
      tmp = rand(2**problem.items.size).to_s(2)
      @genome = "0" * (problem.items.size - tmp.length) + tmp # fill up with leading zeros
    end

    update_fitness
  end

  def fitness 
    # cache fitness value
    @fitness ||= calc_fitness
  end

  def mutate(mutation_probability)
    # flip bits according to mutation probability
    0.upto @genome.length - 1 do |i|
      if rand < mutation_probability
        @genome[i] = @genome[i] == '0' ? '1' : '0'
      end
    end
    update_fitness
  end

  def <=>(other)
    fitness <=> other.fitness
  end

  def calc_fitness
    result = @problem.items.inject({:value => 0, :cost => 0}) do |mem, item|

      # find index of bit for current item
      corresponding_bit_as_fixnum = @genome[@problem.items.find_index(item)].to_i
      # add the item's cost (If bit is zero nothing happens)
      mem[:cost] += item.cost * corresponding_bit_as_fixnum 

      # if cost is still lower then the maximal cost
      if mem[:cost] <= @problem.max_cost
        # add the item's value (If bit is zero nothing happens)
        mem[:value] += item.value * corresponding_bit_as_fixnum 
      end
      # otherwise ignore the item

      mem
    end
    result[:value]
  end

  def update_fitness
    @fitness = calc_fitness
  end
end

class KnapsackSolver
  attr_reader :opts, :population, :generation_count

  def initialize(problem, opts = {})
    @opts = {
      :population_size => 500,
      :recombination_probability => 0.7,
      :mutation_probability => 2 / problem.items.size,
      :max_generations => 100,
      :verbose => false,
      :max_generations_without_improvement => 25,
      :two_point_crossover => false
    }.merge! opts

    @problem = problem
    @population = Array.new(@opts[:population_size]) {|i| KnapsackSolution.new problem}
  end

  def run
    best_avg_worst_mem = [] # Keep lines for csv of each generation
    best = current_best # store the best item
    i = 0
    no_change = 0 
    @generation_count = 0
    while no_change < @opts[:max_generations_without_improvement] && i <= @opts[:max_generations] do

      if @opts[:verbose]
        puts "Starting Generation #{i}"
        puts "Current best: #{best.genome} with fitness: #{best.fitness}"
        #puts "Average: #{@population.inject(0) {|mem, obj| mem + obj.value}}
        puts
      end

      new_best = evolve # create new generation
      no_change += 1

      if new_best > best
        best = new_best 
        no_change = 0 
      end

      avg = @population.inject(0) {|mem, item| mem + item.fitness } / @population.size
      worst = current_worst

      best_avg_worst_mem[i] = [best.fitness, avg, worst.fitness] #"#{best.fitness}, #{avg}, #{worst.fitness}"

      i += 1
      @generation_count += 1
    end
    [best, best_avg_worst_mem]
  end

  def evolve
    @population = next_generation
    @population.each {|p| p.mutate @opts[:mutation_probability]} 
    current_best
  end

  def current_best
    @population.sort.last
  end

  def current_worst
    @population.sort.first
  end

  def next_generation 
    @new_population = []
    while @new_population.size < @opts[:population_size] do
      @new_population.concat get_offspring
    end
    @new_population[0..(@opts[:population_size] - 1)]
  end

  def get_offspring
    parent_1 = select_parent
    parent_2 = select_parent

    if rand < @opts[:recombination_probability]
      do_crossover parent_1, parent_2
    else
      [parent_1, parent_2]
    end
  end

  def do_crossover(parent_1, parent_2)
    rand_range = parent_1.genome.length - 1

    offspring_1, offspring_2 = nil, nil

    if(@opts[:two_point_crossover])
      crossover_points = [rand(rand_range), rand(rand_range)].sort
      genome1 = parent_1.genome
      genome2 = parent_2.genome
      offspring_1 = genome1[0..crossover_points[0]] + genome2[(crossover_points[0]+1)..crossover_points[1]] + genome1[(crossover_points[1]+1)..-1]
      offspring_2 = genome2[0..crossover_points[0]] + genome1[(crossover_points[0]+1)..crossover_points[1]] + genome2[(crossover_points[1]+1)..-1]
    else
      crossover_point = rand(rand_range)  
      offspring_1 = parent_1.genome[0..crossover_point] + parent_2.genome[(crossover_point + 1)..-1] 
      offspring_2 = parent_2.genome[0..crossover_point] + parent_1.genome[(crossover_point + 1)..-1] 
    end

    [KnapsackSolution.new(@problem, offspring_1), KnapsackSolution.new(@problem, offspring_1)]
  end

  def select_parent 
    opponent_1 = @population[rand @population.size]  
    opponent_2 = @population[rand @population.size]  
    opponent_1 >= opponent_2 ? opponent_1 : opponent_2
  end
end

knapsack_setup.rb

require "benchmark"
require 'genetic_algorithm'
require 'brute_force'
require 'dynamic_programming'

KnapsackItem = Struct.new(:name, :cost, :value)
KnapsackProblem = Struct.new(:items, :max_cost)

def get_problem(size=nil,max_cost=500)
  problem = nil

  if size
    items = Array.new(size) do |i|
      KnapsackItem.new("Item_#{i}", rand(500), rand(500))
    end
    problem = KnapsackProblem.new(items, max_cost)
  else
    items = [
      KnapsackItem.new('map'                    , 9   , 150) , KnapsackItem.new('compass'             , 13  , 35)  , 
      KnapsackItem.new('water'                  , 153 , 200) , KnapsackItem.new('sandwich'            , 50  , 160) , 
      KnapsackItem.new('glucose'                , 15  , 60)  , KnapsackItem.new('tin'                 , 68  , 45)  , 
      KnapsackItem.new('banana'                 , 27  , 60)  , KnapsackItem.new('apple'               , 39  , 40)  , 
      KnapsackItem.new('cheese'                 , 23  , 30)  , KnapsackItem.new('beer'                , 52  , 10)  , 
      KnapsackItem.new('suntan cream'           , 11  , 70)  , KnapsackItem.new('camera'              , 32  , 30)  , 
      KnapsackItem.new('t-shirt'                , 24  , 15)  , KnapsackItem.new('trousers'            , 48  , 10)  , 
      KnapsackItem.new('umbrella'               , 73  , 40)  , KnapsackItem.new('waterproof trousers' , 42  , 70)  , 
      KnapsackItem.new('waterproof overclothes' , 43  , 75)  , KnapsackItem.new('note-case'           , 22  , 80)  , 
      KnapsackItem.new('sunglasses'             , 7   , 20)  , KnapsackItem.new('towel'               , 18  , 12)  , 
      KnapsackItem.new('socks'                  , 4   , 50)  , KnapsackItem.new('book'                , 30  , 10)  , 
      KnapsackItem.new('notebook'               , 90  , 1)   , KnapsackItem.new('tent'                , 200 , 150) ,
    ]
    problem = KnapsackProblem.new(items, max_cost)
  end
  problem
end

plotLog.m

function plotLog(logFileName)
    data = csvread(logFileName);

    hold on;
    plot(data);
    ylabel('Fitness (=value)');
    xlabel('# of Generation');
    text(8, 600, ['Best value: ' num2str(max(data(:,1)))]);
    legend('Overall best', 'Average', 'Worst');
    plot(1:size(data,1), 1130);
    hold off;
end

plotPopSizeInvestigationLog.m

function plotPopSizeInvestigationLog(logDataFileName)
    data = csvread(logDataFileName);
    
    subplot(3,1,1);
    hold on;
    plot(data(:,1));
    xlabel('population size');
    ylabel('fitness');
    title('Best solution');
    plot(1:size(data,1), 1130);
    hold off;

    subplot(3,1,2);
    hold on;
    plot(data(:,2));
    xlabel('population size');
    ylabel('fitness');
    title('Average fitness');
    plot(1:size(data,1), 1130);
    hold off;

    subplot(3,1,3);
    hold on;
    plot(data(:,3));
    xlabel('population size');
    ylabel('number of runs with optimal solution');
    title('Runs out of 100 with optimal solution');
    hold off;
end

pop_size_log

best,avg,optimum_count
940,570,0
950,688,0
1005,757,0
1045,779,0
1080,822,0
962,820,0
1080,851,0
1045,861,0
1065,883,0
1082,884,0
1057,887,0
1030,892,0
1057,907,0
1052,909,0
1110,923,0
1105,922,0
1112,942,0
1082,948,0
1082,949,0
1110,956,0
1110,971,0
1085,962,0
1105,970,0
1110,974,0
1115,988,0
1082,982,0
1115,991,0
1115,1000,0
1130,996,2
1130,1002,1
1107,993,0
1100,1000,0
1117,1004,0
1115,1005,0
1105,1009,0
1115,1015,0
1115,1011,0
1115,1001,0
1112,1011,0
1127,1005,0
1127,1024,0
1127,1024,0
1130,1032,1
1117,1028,0
1127,1043,0
1130,1024,1
1130,1031,1
1130,1036,1
1130,1036,1
1130,1037,1
1127,1042,0
1127,1044,0
1130,1043,1
1130,1050,2
1127,1052,0
1130,1056,2
1115,1052,0
1130,1051,1
1130,1060,3
1127,1053,0
1130,1049,1
1130,1055,2
1130,1058,1
1130,1061,2
1130,1064,4
1130,1057,2
1130,1061,2
1127,1068,0
1130,1070,2
1130,1068,4
1130,1070,5
1130,1065,3
1130,1073,3
1130,1068,1
1130,1069,3
1130,1073,3
1130,1082,4
1130,1079,4
1130,1076,5
1130,1068,2
1130,1078,3
1130,1080,7
1130,1077,3
1130,1078,3
1130,1082,4
1130,1089,7
1130,1086,4
1130,1085,3
1130,1087,2
1130,1086,5
1130,1084,5
1130,1084,4
1130,1083,4
1130,1092,7
1130,1088,7
1130,1090,6
1130,1085,7
1130,1088,11
1130,1080,4
1130,1086,7
1130,1092,10
1130,1091,9
1130,1089,5
1130,1097,17
1130,1094,11
1130,1092,7
1130,1094,10
1130,1093,11
1130,1094,7
1130,1094,10
1130,1093,10
1130,1097,6
1130,1097,14
1130,1099,5
1130,1100,14
1130,1093,11
1130,1097,9
1130,1095,8
1130,1101,13
1130,1101,12
1130,1096,7
1130,1098,15
1130,1101,14
1130,1099,14
1130,1096,8
1130,1102,10
1130,1099,14
1130,1098,9
1130,1105,11
1130,1102,13
1130,1101,10
1130,1105,20
1130,1102,11
1130,1101,12
1130,1102,13
1130,1108,17
1130,1103,11
1130,1103,9
1130,1105,13
1130,1102,10
1130,1103,15
1130,1107,15
1130,1106,18
1130,1107,17
1130,1109,20
1130,1109,18
1130,1105,17
1130,1110,23
1130,1106,14
1130,1108,22
1130,1102,14
1130,1107,17
1130,1110,24
1130,1108,15
1130,1109,19
1130,1107,17
1130,1111,27
1130,1109,17
1130,1108,16
1130,1109,18
1130,1111,17
1130,1109,18
1130,1109,21
1130,1110,20
1130,1109,18
1130,1110,22
1130,1113,23
1130,1109,15
1130,1111,18
1130,1114,19
1130,1114,27
1130,1113,26
1130,1113,26
1130,1112,21
1130,1112,22
1130,1113,20
1130,1109,14
1130,1114,30
1130,1112,22
1130,1115,32
1130,1112,24
1130,1114,23
1130,1114,33
1130,1115,32
1130,1114,26
1130,1112,21
1130,1112,27
1130,1115,25
1130,1117,30
1130,1114,24
1130,1114,28
1130,1114,25
1130,1116,29
1130,1118,32
1130,1118,35
1130,1116,33
1130,1113,27
1130,1115,27
1130,1118,34
1130,1117,34
1130,1118,34
1130,1117,39
1130,1120,39
1130,1117,32
1130,1120,33
1130,1120,38
1130,1117,32
1130,1118,32
1130,1117,31
1130,1116,36
1130,1116,29
1130,1119,38
1130,1119,37
1130,1115,22
1130,1117,35
1130,1116,28
1130,1122,41
1130,1115,31
1130,1119,33
1130,1118,32
1130,1119,30
1130,1119,29
1130,1116,31
1130,1120,37
1130,1119,44
1130,1118,29
1130,1120,35
1130,1117,34
1130,1117,32
1130,1120,38
1130,1120,35
1130,1118,41
1130,1120,40
1130,1120,32
1130,1119,26
1130,1120,29
1130,1117,29
1130,1120,34
1130,1116,34
1130,1119,33
1130,1119,32
1130,1121,40
1130,1119,33
1130,1121,34
1130,1121,42
1130,1120,39
1130,1122,46
1130,1119,40
1130,1121,43
1130,1123,50
1130,1120,38
1130,1120,34
1130,1122,46
1130,1121,42
1130,1120,42
1130,1120,36
1130,1120,38
1130,1122,45
1130,1121,42
1130,1122,44
1130,1121,40
1130,1122,43
1130,1121,35
1130,1122,50
1130,1123,48
1130,1120,28
1130,1122,40
1130,1122,42
1130,1122,46
1130,1123,48
1130,1121,40
1130,1123,47
1130,1124,47
1130,1123,44
1130,1122,46
1130,1124,52
1130,1124,57
1130,1123,42
1130,1123,54
1130,1124,53
1130,1123,49
1130,1124,50
1130,1124,46
1130,1123,37
1130,1124,51
1130,1123,42
1130,1123,47
1130,1123,44
1130,1124,57
1130,1124,51
1130,1124,49
1130,1122,47
1130,1124,53
1130,1125,49
1130,1123,51
1130,1123,47
1130,1122,46
1130,1124,53
1130,1125,51
1130,1123,53
1130,1124,53
1130,1124,48
1130,1122,44
1130,1123,48
1130,1124,55
1130,1124,53
1130,1124,51
1130,1123,48
1130,1124,54
1130,1125,55
1130,1125,56
1130,1124,52
1130,1124,55
1130,1125,55
1130,1124,49
1130,1124,46
1130,1124,51
1130,1124,60
1130,1124,54
1130,1125,58
1130,1125,63
1130,1124,54
1130,1125,55
1130,1126,58
1130,1125,57
1130,1124,52
1130,1123,49
1130,1124,54
1130,1124,48
1130,1124,55
1130,1124,52
1130,1125,54
1130,1124,49
1130,1125,56
1130,1125,48
1130,1124,60
1130,1123,53
1130,1124,54
1130,1126,58
1130,1125,53
1130,1125,54
1130,1126,57
1130,1127,64
1130,1125,54
1130,1125,60
1130,1126,58
1130,1125,58
1130,1126,62
1130,1126,66
1130,1126,65
1130,1126,62
1130,1125,57
1130,1127,68
1130,1125,52
1130,1126,53
1130,1125,64
1130,1125,60
1130,1126,62
1130,1125,57
1130,1126,61
1130,1125,55
1130,1126,62
1130,1125,59
1130,1125,56
1130,1126,62
1130,1125,55
1130,1125,60
1130,1126,61
1130,1127,64
1130,1126,56
1130,1126,57
1130,1125,63
1130,1125,60
1130,1125,61
1130,1127,66
1130,1126,67
1130,1126,54
1130,1126,61
1130,1127,72
1130,1125,54
1130,1127,67
1130,1126,61
1130,1124,51
1130,1127,59
1130,1126,64
1130,1126,69
1130,1126,57
1130,1126,72
1130,1125,60
1130,1126,61
1130,1127,67
1130,1126,62
1130,1126,55
1130,1127,67
1130,1126,63
1130,1127,67
1130,1127,66
1130,1126,63
1130,1126,58
1130,1126,62
1130,1127,70
1130,1127,69
1130,1127,73
1130,1128,74
1130,1127,70
1130,1127,75
1130,1127,73
1130,1126,67
1130,1128,71
1130,1127,67
1130,1127,64
1130,1127,69
1130,1127,75
1130,1127,71
1130,1126,63
1130,1127,69
1130,1127,64
1130,1127,70
1130,1127,68
1130,1126,63
1130,1127,60
1130,1127,68
1130,1127,69
1130,1127,70
1130,1128,77
1130,1126,62
1130,1128,81
1130,1127,65
1130,1127,70
1130,1127,75
1130,1127,67
1130,1127,70
1130,1127,72
1130,1127,63
1130,1128,69
1130,1128,76
1130,1127,69
1130,1127,73
1130,1128,71
1130,1127,75
1130,1127,66
1130,1127,68
1130,1127,67
1130,1127,72
1130,1127,75
1130,1127,66
1130,1128,68
1130,1127,67
1130,1127,73
1130,1127,67
1130,1127,73
1130,1127,70
1130,1128,77
1130,1128,65
1130,1128,78
1130,1128,74
1130,1127,71
1130,1127,63
1130,1128,78
1130,1127,72
1130,1127,72
1130,1126,61
1130,1128,74
1130,1127,66
1130,1128,76
1130,1128,79
1130,1128,76
1130,1127,67
1130,1127,74
1130,1127,69
1130,1127,64
1130,1128,73
1130,1127,71
1130,1128,73
1130,1128,79
1130,1128,79
1130,1129,88
1130,1128,72
1130,1127,74
1130,1127,74
1130,1128,74
1130,1127,70
1130,1127,73
1130,1128,72
1130,1127,68
1130,1127,71
1130,1128,77
1130,1128,78
1130,1128,82
1130,1128,81
1130,1128,73
1130,1128,75
1130,1128,79
1130,1128,72
1130,1127,71
1130,1128,73
1130,1127,73
1130,1129,81
1130,1128,78

test_file.rb

$:.unshift File.expand_path(File.dirname(__FILE__))
require 'knapsack_setup'

pop_size = 500
pop_size = ARGV[0].to_i if ARGV[0]
problem = get_problem

puts "Problem size: #{problem.items.size}"
puts

time = Benchmark.measure do
  cost_matrix = dynamic_programming_knapsack problem
  puts
  puts 'Dynamic Programming:'
  puts
  puts 'Found solution: ' + get_list_of_used_items_names(problem, cost_matrix)
  puts 'With value: ' + cost_matrix.last.last.to_s
end

puts "Time for dynamic programming solution:"
puts time
puts

time = Benchmark.measure do
  ga = KnapsackSolver.new problem, :population_size => pop_size, :max_generations_without_improvement => 25, :mutation_probability => 1 / problem.items.size, :recombination_probability => 0.7
  result = ga.run
  solution = result.first
  log = result.last

  File.open("logs/test_log.csv", 'w') do |f| 
    log.each {|l| f.puts l.join(',')}
  end

  used_items = []
  tmp = 0
  0.upto(solution.genome.length - 1) do |i|
    tmp += solution.genome[i].to_i * problem.items[i].cost
    if(solution.genome[i] == '1' && tmp <= problem.max_cost)
      used_items << problem.items[i].name
    end
  end

  puts
  puts 'Genetic Algorithm:'
  puts
  puts 'Found solution: ' + used_items.sort.join(', ')
  puts 'with value: ' + solution.fitness.to_s
  puts 'and with ' << ga.generation_count.to_s << ' generations'
end

puts "Time for Genetic Algorithm:"
puts time
puts


if(problem.items.size < 24 )
  puts
  puts "Brute Force:"
  puts
  time = Benchmark.measure do
    brute_force(problem)
  end

  puts "Time for brute force solution:"
  puts time
end