การค้นหาแบบสุ่ม

จากวิกิพีเดีย สารานุกรมเสรี

การค้นหาแบบสุ่ม (อังกฤษ: random search: RS) เป็นหนึ่งในวิธีการเชิงตัวเลข ที่ใช้เพิ่มประสิทธิภาพ (อังกฤษ: Optimization) ในการแก้ปัญหาประเภทค้นหา โดยที่ปัญหาที่จะเพิ่มประสิทธิภาพในการแก้ด้วยวิธีการค้นหาแบบสุ่มนี้ ไม่จำเป็นว่าจะต้องเป็น ปัญหาเชิงเส้น หรือ ปัญหาที่มีความต่อเนื่องของคำตอบ (อังกฤษ: Continuous function) หรือ ปัญหาที่ใช้อนุพันธ์หาคำตอบได้ (อังกฤษ: differentiable function)

การค้นหาแบบสุ่ม นั้นถูกพิจารณาว่าเขียนโดย Rastrigin [1] ซึ่งเขาเป็นคนนำเสนอวิธีของการค้นหาแบบสุ่มคนแรก ที่ใช้ทฤษฐีทางด้านคณิตศาสตร์เข้ามาช่วยในการวิเคราะห์ทฤษฏี การค้นหาแบบสุ่มนั้น ทำงานโดยการหาในตำแหน่งที่ดีขึ้นจากตำแหน่งเก่า ซ้ำๆ เรื่อยๆ ในปริภูมิค้นหา

จากนั้นในปี 1991 คุณ Anatoly Zhigljavsky [2] ก็ได้ทำการตีพิมพ์ออกเป็นหนังสือ ชื่อ Theory of Global Random Search และเขาได้ทำการเขียนเอกสารทางวิชาการออกมาอีกมากมาย ในเรื่องที่เกี่ยวกับการค้นหาแบบสุ่มนี้ ยกตัวอย่างเช่น

  • ประมาณค่าต่ำสุดของฟังก์ชันในขั้นตอนวิธีการค้นหาแบบสุ่ม [3]
  • การอนุมานเชิงสถิติแบบกึ่งไม่เมตริกด้วยการค้นหาแบบสุ่ม [4]

ตัวอย่างวิธีการเพิ่มประสิทธิภาพการค้นหา เช่น การค้นหาแบบตรง (อังกฤษ: direct-search) การค้นหาโดยไม่ซ้ำทางเดิม (อังกฤษ: derivative-free) ขั้นตอนวิธีแบบกล่องดำ (อังกฤษ: black-box methods)

ขั้นตอนวิธีการทำงาน[แก้]

ให้ f : n → เป็นฟังก์ชันต้นทุน หรือ เป็นฟังก์ชันที่เหมาะสมในการประเมินความ ใกล้ ไกล ของคำตอบที่ต้องการ

เช่น (f (y)  < f (x) ) หมายความว่า คำตอบของ y นั้น ใกล้เคียงค่าผลที่ต้องการมากกว่าคำตอบของ x

ให้ x ∈ n เป็นตำแหน่ง หรือ คำตอบ ที่จะค้นหาได้จาก ปริภูมิค้นหา

การค้นหาแบบสุ่มอย่างง่าย จะมีขั้นตอนการทำต่อไปนี้[แก้]

  1. กำหนดค่าของ X ขึ้นมาอย่างสุ่มๆ บนปริภูมิค้นหา
  2. หาค่าตำแหน่งใหม่ชื่อ Y จากปริภูมิค้นหา ให้สัมพัทธ์กับค่าของ X แล้วเพิ่มเติมด้วย ค่าสุ่มๆรบกวนเล็กน้อย (อังกฤษ: random noise) (ยกตัวอย่างเช่น เทคนิคของคุณMarsaglia ในการสุ่มหาค่าในปริภูมิค้นหา)
  3. ถ้า (f (y)  < f (x) ) ให้เปลี่ยนค่าใหม่ X เสียใหม่โดยให้ x = y
  4. ตรวจสอบว่าค่าของ X ที่ได้มา เป็นค่าที่ถูกต้องกับที่เราต้องการแล้วหรือเปล่า ถ้าถูกแล้ว ให้หยุด ถ้ายังไม่ถูกต้อง ให้ทำตั้งแต่ข้อ 2 อีกครั้งหนึ่ง

สุดท้าย ตอนนี้ค่า x จะเป็นค่าของผลลัพธ์ที่ดีที่สุดที่หาเจอ

การนำไปปรับใช้งาน[แก้]

การค้นหาแบบสุ่ม ถูกนำไปปรับใช้ในวารสารทางวิชาการ เช่น

  • การค้นหาแบบสุ่มที่การสุ่มแต่ละครั้งมีค่าสัมพัทธ์ขนาดคงที่ (อังกฤษ: Fixed Step Size Random Search) เป็นของคุณ Rastrigin [1]

ที่เป็นขั้นตอนวิธีที่ค้นหา ตัวอย่างที่นำมาใช้ในการทดสอบ โดยการกำหนดค่าคงที่ค่าหนึ่ง และให้ตัวอย่างทดสอบ แต่ละการทดสอบนั้น มีความห่างกัน (มีค่าสัมพัทธ์) เป็นขนาดคงที่

  • การค้นหาแบบสุ่มที่การสุ่มแต่ละครั้งมีค่าสัมพัทธ์ที่คิดว่าเหมาะสมที่สุด (อังกฤษ: Optimum Step Size Random Search) เป็นของคุณ Schumer and Steiglitz [5]

เป็นทฤษฐีแรกที่อธิบายว่า การค้นหาแต่ละครั้ง เราควรจะเลือกค่าความต่างจากตัวอย่างอันเดิมป็นค่าเท่าใหร่ โดยที่ไม่เสียเวลาไปกับการเลือกค่าความต่างเหล่านั้นมากไปนัก ในการนำไปใช้งานจริงของขั้นตอนวิธีนี้ ทำการหาค่าของความต่างจากคำตอบเดิม โดยการสร้างค่าสัมพัทธ์ นี้ ทำโดยการทำการหาค่าสัมพัทธ์หลายๆครั้ง และด้วยเหตุผลของการหาค่าสัมพัทธ์หลายๆครั้ง ทำให้การทำงานจริงนั้น ใช้เวลาจำนวนมากในการหาค่าสัมพัทธ์ทีเหมาะสม

  • การค้นหาแบบสุ่มที่การสุ่มแต่ละครั้งมีค่าสัมพัทธ์ที่เปลี่ยนแปลงได้ (อังกฤษ: Adaptive Step Size Random Search) เป็นของคุณ Schumer and Steiglitz [5]

เขาได้ทำการศึกษาว่าเราควรจะเปลี่ยนแปลงค่าสัมพัทธ์อย่างไร เท่าใหร่ เมื่อใด แต่ว่า ขั้นตอนวิธีการหาค่าสัมพัทธ์นั้น มีความซับซ้อนเป็นอย่างมาก

  • การค้นหาแบบสุ่มที่การสุ่มแต่ละครั้งมีค่าสัมพัทธ์ที่เปลี่ยนแปลงแบบสัมพัทธ์กับค่าสัมพัทธิ์เดิม (อังกฤษ: Optimized Relative Step Size Random Search) เป็นของคุณ Schrack and Choit [6]

เป็นขั้นตอนวิธีที่ทำการประมาณค่าสัมพัทธ์ที่เหมาะสม โดยการทำการเพิ่มอย่างเป็นกราฟเอกโพแนนเชียล แต่อย่างไรก็ดี สูตรที่ใช้ในการคำนวณค่าที่เพิ่มขึ้นนั้นมีความซับซ้อนมากมาย

  • ขั้นตอนวิธีทางพันธุกรรม โดยใช้การแก้ปัญหาด้วยวิธีการค้นหาแบบสุ่ม ของคุณ Charles C. Peck & Atam P. Dhawan [7]

ลองค้นคำใกล้เคียง[แก้]

อ้างอิง[แก้]

  1. อ้างอิงผิดพลาด: ป้ายระบุ <ref> ไม่ถูกต้อง ไม่มีข้อความใดให้ไว้สำหรับอ้างอิงชื่อ rastrigin63convergence
  2. อ้างอิงผิดพลาด: ป้ายระบุ <ref> ไม่ถูกต้อง ไม่มีข้อความใดให้ไว้สำหรับอ้างอิงชื่อ zhigl1991
  3. อ้างอิงผิดพลาด: ป้ายระบุ <ref> ไม่ถูกต้อง ไม่มีข้อความใดให้ไว้สำหรับอ้างอิงชื่อ Estimatingtheminimalvalue
  4. อ้างอิงผิดพลาด: ป้ายระบุ <ref> ไม่ถูกต้อง ไม่มีข้อความใดให้ไว้สำหรับอ้างอิงชื่อ zhigljavskyStatistical
  5. อ้างอิงผิดพลาด: ป้ายระบุ <ref> ไม่ถูกต้อง ไม่มีข้อความใดให้ไว้สำหรับอ้างอิงชื่อ schumer68adaptive
  6. อ้างอิงผิดพลาด: ป้ายระบุ <ref> ไม่ถูกต้อง ไม่มีข้อความใดให้ไว้สำหรับอ้างอิงชื่อ schrack76optimized
  7. อ้างอิงผิดพลาด: ป้ายระบุ <ref> ไม่ถูกต้อง ไม่มีข้อความใดให้ไว้สำหรับอ้างอิงชื่อ GeneticAlgorithmsasGlobalRandomSearchMethods

อ้างอิงผิดพลาด: ป้ายระบุ <ref> ชื่อ "GeneticAlgorithmsasGlobalRandomSearchMethods" มีนิยามใน <references> แต่ไม่ถูกใช้ในข้อความก่อนหน้านี้
อ้างอิงผิดพลาด: ป้ายระบุ <ref> ชื่อ "zhigl1991" มีนิยามใน <references> แต่ไม่ถูกใช้ในข้อความก่อนหน้านี้
อ้างอิงผิดพลาด: ป้ายระบุ <ref> ชื่อ "Estimatingtheminimalvalue" มีนิยามใน <references> แต่ไม่ถูกใช้ในข้อความก่อนหน้านี้
อ้างอิงผิดพลาด: ป้ายระบุ <ref> ชื่อ "zhigljavskyStatistical" มีนิยามใน <references> แต่ไม่ถูกใช้ในข้อความก่อนหน้านี้
อ้างอิงผิดพลาด: ป้ายระบุ <ref> ชื่อ "schrack76optimized" มีนิยามใน <references> แต่ไม่ถูกใช้ในข้อความก่อนหน้านี้
อ้างอิงผิดพลาด: ป้ายระบุ <ref> ชื่อ "schumer68adaptive" มีนิยามใน <references> แต่ไม่ถูกใช้ในข้อความก่อนหน้านี้

อ้างอิงผิดพลาด: <ref> tag defined in <references> has group attribute "" which does not appear in prior text.