{{ message }}

Instantly share code, notes, and snippets.

# NilsHaldenwang/brute_force.rb

Created May 14, 2011
Genetic Algorithm vs. 0-1-KNAPSACK
 # 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
 # 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
 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
 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
 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
 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
 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
 \$:.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