Skip to content

Instantly share code, notes, and snippets.

@NilsHaldenwang
Created May 14, 2011 12:08
Show Gist options
  • Save NilsHaldenwang/972159 to your computer and use it in GitHub Desktop.
Save NilsHaldenwang/972159 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment