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

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

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

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

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

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

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

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

เช่น (*f* (**y**) &nbsp;*n* เป็นตำแหน่ง หรือ คำตอบ ที่จะค้นหาได้จาก ปริภูมิค้นหา

#### การค้นหาแบบสุ่มอย่างง่าย จะมีขั้นตอนการทำต่อไปนี้
# กำหนดค่าของ X ขึ้นมาอย่างสุ่ม ๆ บนปริภูมิค้นหา
# หาค่าตำแหน่งใหม่ชื่อ Y จากปริภูมิค้นหา ให้สัมพัทธ์กับค่าของ X แล้วเพิ่มเติมด้วย ค่าสุ่ม ๆ รบกวนเล็กน้อย () (ยกตัวอย่างเช่น เทคนิคของคุณMarsaglia ในการสุ่มหาค่าในปริภูมิค้นหา)
# ถ้า (*f* (**y**) &nbsp;<&nbsp;*f* (**x**) ) ให้เปลี่ยนค่าใหม่ X เสียใหม่โดยให้ **x**&nbsp;=&nbsp;**y**
# ตรวจสอบว่าค่าของ X ที่ได้มา เป็นค่าที่ถูกต้องกับที่เราต้องการแล้วหรือเปล่า ถ้าถูกแล้ว ให้หยุด ถ้ายังไม่ถูกต้อง ให้ทำตั้งแต่ข้อ 2 อีกครั้งหนึ่ง
สุดท้าย ตอนนี้ค่า x จะเป็นค่าของผลลัพธ์ที่ดีที่สุดที่หาเจอ

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

* **การค้นหาแบบสุ่มที่การสุ่มแต่ละครั้งมีค่าสัมพัทธ์ขนาดคงที่** () เป็นของคุณ Rastrigin 

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

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

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

* **การค้นหาแบบสุ่มที่การสุ่มแต่ละครั้งมีค่าสัมพัทธ์ที่เปลี่ยนแปลงแบบสัมพัทธ์กับค่าสัมพัทธิ์เดิม** () เป็นของคุณ Schrack and Choit 

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

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

## ลองค้นคำใกล้เคียง
* การเพิ่มประสิทธิภาพแบบสุ่ม มีความใกล้เคียงกันกับวิธีการเพิ่มประสิทธิภาพด้วยกานค้นหาแบบสุ่ม เพียงแต่ว่า การเพิ่มประสิทธิภาพแบบสุ่มนั้น ใช้กับการหาคำตอบบนข้อมูลตัวอย่างบนกราฟการแจกแจงปกติ () ไม่ใช่ การค้นหาแบบสุ่มที่สามารถค้นหาใด้ในปริภูมิหลายมิติ
* Luus–Jaakola เป็นวิธีเพิ่มประสิทธิภาพที่มีความใกล้เคียงที่ใช้ในการค้นหาคำตอบที่อยู่บนการแจกแจงแบบสม่ำเสมอ () ที่คำตอบมีลักษณะการเพิ่มกันเป็นค่าเหมือนฟังก์ชันเอกซ์โพเนนเชียล
*  การค้นหาไปบนแกนพิกัดของพื้นที่ค้นหา ที่ใช้ค่าสัมพัทธ์ที่เพิ่มแบบฟังชันเอกซ์โพเนนเชียล

## อ้างอิง

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