Class: Stochastic::HillClimbing

Inherits:
Object
  • Object
show all
Defined in:
lib/Algorithmically/Stochastic/hill_climbing.rb

Instance Method Summary collapse

Constructor Details

#initialize(max_iterations, num_bits) ⇒ HillClimbing

Returns a new instance of HillClimbing.



5
6
7
8
 
# File 'lib/Algorithmically/Stochastic/hill_climbing.rb', line 5

def initialize(max_iterations, num_bits)
  best = search(max_iterations, num_bits)
  puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].join}"
end

Instance Method Details

#onemax(vector) ⇒ Object 



10
11
12
 
# File 'lib/Algorithmically/Stochastic/hill_climbing.rb', line 10

def onemax(vector)
  vector.inject(0.0) { |sum, v| sum + ((v=="1") ? 1 : 0) }
end

#random_bitstring(num_bits) ⇒ Object 



14
15
16
 
# File 'lib/Algorithmically/Stochastic/hill_climbing.rb', line 14

def random_bitstring(num_bits)
  Array.new(num_bits) { |i| (rand<0.5) ? "1" : "0" }
end

#random_neighbor(bitstring) ⇒ Object 



18
19
20
21
22
23
 
# File 'lib/Algorithmically/Stochastic/hill_climbing.rb', line 18

def random_neighbor(bitstring)
  mutant = Array.new(bitstring)
  pos = rand(bitstring.size)
  mutant[pos] = (mutant[pos]=='1') ? '0' : '1'
  mutant
end

#search(max_iterations, num_bits) ⇒ Object 



25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/Algorithmically/Stochastic/hill_climbing.rb', line 25

def search(max_iterations, num_bits)
  candidate = {}
  candidate[:vector] = random_bitstring(num_bits)
  candidate[:cost] = onemax(candidate[:vector])
  max_iterations.times do |iter|
    neighbor = {}
    neighbor[:vector] = random_neighbor(candidate[:vector])
    neighbor[:cost] = onemax(neighbor[:vector])
    candidate = neighbor if neighbor[:cost] >= candidate[:cost]
    puts " > iteration #{(iter+1)}, best=#{candidate[:cost]}"
    break if candidate[:cost] == num_bits
  end
  candidate
end