Stochastic Hill ClimbingStochastic Hill Climbing, SHC, Random Hill Climbing, RHC, Random Mutation Hill Climbing, RMHC. TaxonomyThe Stochastic Hill Climbing algorithm is a Stochastic Optimization algorithm and is a Local Optimization algorithm (contrasted to Global Optimization). It is a direct search technique, as it does not require derivatives of the search space. Stochastic Hill Climbing is an extension of deterministic hill climbing algorithms such as Simple Hill Climbing (firstbest neighbor), SteepestAscent Hill Climbing (best neighbor), and a parent of approaches such as Parallel Hill Climbing and RandomRestart Hill Climbing. StrategyThe strategy of the Stochastic Hill Climbing algorithm is iterate the process of randomly selecting a neighbor for a candidate solution and only accept it if it results in an improvement. The strategy was proposed to address the limitations of deterministic hill climbing techniques that were likely to get stuck in local optima due to their greedy acceptance of neighboring moves. ProcedureAlgorithm (below) provides a pseudocode listing of the Stochastic Hill Climbing algorithm for minimizing a cost function, specifically the Random Mutation Hill Climbing algorithm described by Forrest and Mitchell applied to a maximization optimization problem [Forrest1993]. Input :
$Iter_{max}$, ProblemSize
Output :
Current
Current $\leftarrow$ RandomSolution (ProblemSize )For ($iter_i \in$ $Iter_{max}$)Candidate $\leftarrow$ RandomNeighbor (Current )If (Cost (Candidate ) $\geq$ Cost (Current ))Current $\leftarrow$ Candidate End End Return (Current )Heuristics
Code ListingListing (below) provides an example of the Stochastic Hill Climbing algorithm implemented in the Ruby Programming Language, specifically the Random Mutation Hill Climbing algorithm described by Forrest and Mitchell [Forrest1993]. The algorithm is executed for a fixed number of iterations and is applied to a binary string optimization problem called 'One Max'. The objective of this maximization problem is to prepare a string of all '1' bits, where the cost function only reports the number of bits in a given string. def onemax(vector) return vector.inject(0.0){sum, v sum + ((v=="1") ? 1 : 0)} end def random_bitstring(num_bits) return Array.new(num_bits){i (rand<0.5) ? "1" : "0"} end def random_neighbor(bitstring) mutant = Array.new(bitstring) pos = rand(bitstring.size) mutant[pos] = (mutant[pos]=='1') ? '0' : '1' return mutant end 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 return candidate end if __FILE__ == $0 # problem configuration num_bits = 64 # algorithm configuration max_iterations = 1000 # execute the algorithm best = search(max_iterations, num_bits) puts "Done. Best Solution: c=#{best[:cost]}, v=#{best[:vector].join}" end Download: stochastic_hill_climbing.rb.
ReferencesPrimary SourcesPerhaps the most popular implementation of the Stochastic Hill Climbing algorithm is by Forrest and Mitchell, who proposed the Random Mutation Hill Climbing (RMHC) algorithm (with communication from Richard Palmer) in a study that investigated the behavior of the genetic algorithm on a deceptive class of (discrete) bitstring optimization problems called 'royal road' functions [Forrest1993]. The RMHC was compared to two other hill climbing algorithms in addition to the genetic algorithm, specifically: the SteepestAscent Hill Climber, and the NextAscent Hill Climber. This study was then followed up by Mitchell and Holland [Mitchell1993]. Jules and Wattenberg were also early to consider stochastic hill climbing as an approach to compare to the genetic algorithm [Juels1994]. Skalak applied the RMHC algorithm to a single long bitstring that represented a number of prototype vectors for use in classification [Skalak1994]. Learn MoreThe Stochastic Hill Climbing algorithm is related to the genetic algorithm without crossover. Simplified version's of the approach are investigated for bitstring based optimization problems with the population size of the genetic algorithm reduced to one. The general technique has been investigated under the names Iterated Hillclimbing [Muhlenbein1991], ES(1+1,m,hc) [Muhlenbein1992], Random Bit Climber [Davis1991], and (1+1)Genetic Algorithm [Back1993]. This main difference between RMHC and ES(1+1) is that the latter uses a fixed probability of a mutation for each discrete element of a solution (meaning the neighborhood size is probabilistic), whereas RMHC will only stochastically modify one element. Bibliography

Free CourseGet one algorithm per week...
Own A CopyThis 438page ebook has...


Please Note: This content was automatically generated from the book content and may contain minor differences. 

Do you like Clever Algorithms? Buy the book now. 