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

ขั้นตอนการแก้ไขปัญหาการปีนเขาของสโทแคสติก (อังกฤษ: 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