ขั้นตอนวิธีการแก้ไขปัญหาการปีนเขาของสโทแคสติก

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

รหัสเทียม

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 เก็บถาวร 2011-09-27 ที่ เวย์แบ็กแมชชีน
• The OneMax Problem