ขั้นตอนวิธีการปีนเขาแบบเฟ้นสุ่ม

ขั้นตอนวิธีการปีนเขาแบบเฟ้นสุ่ม () เป็นการแก้ไขปัญหาที่ต้องการผลเฉลยที่เป็นที่สุด คือ ดีที่สุดหรือน้อยที่สุด โดยมีหลักการในการแก้ไขปัญหาคือการเลือกแนวทางในการไปสู่คำตอบของปัญหานับจากตำแหน่งปัจจุบันที่ดีที่สุดอย่างสุ่ม แล้วจึงย้ายการหาแนวทางการไปสู่ผลเฉลยที่เป็นที่สุดไปที่จุดล่าสุดที่เลือกไว้ ซึ่งแนวความคิดของการเฟ้นสุ่มเกี่ยวกับขั้นตอนในการแก้ไขปัญหาการปีนเขานี้มีลักษณะคล้ายกันกับการแก้ไขปัญหาการปีนเขาโดยทั่วไป แต่ต่างกันตรงที่วิธีการแบบเฟ้นสุ่มนั้นอาศัยหลักในการเลือกเส้นทางในการปีนเขาอย่างสุ่ม ขณะที่แบบทั่วๆ ไปนั้นอาศัยหลักในการเลือกเส้นทางที่มีความชันมากที่สุดเพื่อมาประกอบกันเป็นส่วนหนึ่งของคำตอบในการแก้ไขปัญหา

 รหัสเทียม 
 Input: , ProblemSize
 Output: Current
 Current  RandomSolution(ProblemSize)
 For ( )
  Candidate  RandomNeighbor(Current)
  If (Cost(Candidate)  Cost(Current))
   Current  Candidate
  End
 End
 Return (Current)

 ตัวอย่างโค้ดภาษารูบี้เพื่อแก้ปัญหาวันแมกซ์ 

ปัญหาวันแมกซ์ (one max) คือปัญหาการหาสายอักขระที่อนุญาตให้มีอักขระที่เป็นไปได้คือ ศูนย์ และ หนึ่ง เท่านั้น เพื่อให้ผลรวมของอักขระที่อยู่ในสายอักขระมีค่ามากที่สุด

 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

 ดูเพิ่ม 
 ปัญหาที่ต้องการผลเฉลยที่เป็นที่สุด (Optimal solution)
 ขั้นตอนวิธีการปีนเขา (Hill climbing)

 อ้างอิง 

 Stochastic Hill Climbing 
 The OneMax Problem 

หมวดหมู่:ขั้นตอนวิธี