การหาค่าเหมาะสุดอย่างตอบสนอง
การหาค่าเหมาะสุดอย่างตอบสนอง หรือ การค้นหาค่าเหมาะสุดอย่างตอบสนอง (อังกฤษ: reactive search optimization)
การค้นหาค่าเหมาะสุดอย่างตอบสนอง หมายถึงการศึกษาสำนึกด้วยการค้นเฉพาะที่(local-search heuristics)บนพื้นฐานของการเรียนรู้ของเครื่องจักร(machine learning) เป็นหนึ่งในขึ้นตอนวิธีการหาค่าเหมาะสุดที่เป็นการค้นเฉพาะที่ หรือเป็นรูปแบบหนึ่งของการศึกษาสำนึก(heuristics)ซึ่งปรับเปลี่ยนค่าในการทำงานในระหว่างขั้นตอนการหาค่าเหมาะสุด
ลักษณะโดยทั่วไป: การเรียนรู้ในขณะค้นหาค่าเหมาะสุด[แก้]
การค้นหาค่าเหมาะสุดอย่างตอบสนองก็เหมือนวิธีการค้นเฉพาะที่ทั่วๆไปที่ถูกนำมาใช้แก้ปัญหาจำพวกการหาโครงแบบที่เหมาะสมของระบบ โดยที่โครงแบบดังกล่าวมักจะประกอบด้วยตัวแปรที่เปลี่ยนแปลงไปมาทั้งในลักษณะที่ต่อเนื่องและไม่ต่อเนื่อง แต่ในขณะเดียวกันเกณฑ์ในการหาค่าเหมาะสุดนั้นเป็นเพียงตัวเลขตัวเดียว ส่วนใหญ่แล้วปัญหาการหาค่าเหมาะสุดนั้นมักจะถูกลดรูปไปสู่ปัญหาการหาค่าน้อยที่สุดของฟังก์ชันที่มีอากิวเมนต์ของฟังก์ชันคือตัวแปรโครงแบบที่ถูกมองว่าเป็นตัวแปรอิสระในโดเมนของฟังก์ชันนี้
การค้นหาค่าเหมาะสุดอย่างตอบสนองนั้นสนับสนุนการผสมผสานกันระหว่างวิธีการการเรียนรู้ของเครื่องจักรภายใต้วิธีทางสัญลักษญ์(sub-symbolic machine learning)และการศึกษาสำนึกด้วยวิธีการค้นหา(search heuristics) เพื่อร่วมกันแก้ปัญหาการค้นหาค่าเหมาะสุดที่ซับซ้อน คำว่า "อย่างตอบสนอง" นั้น หมายถึงพร้อมเสมอที่จะตอบสนองต่อเหตุการณ์ระหว่างการค้นหา ทั้งประวัติในการค้นหาและความรู้ต่างๆที่เก็บสะสมมาในขณะที่เคลื่อนตัวผ่านพื้นที่โครงแบบนั้นถูกใช้ในการปรับตัวเองอย่างอัตโนมัติ ซึ่งขั้นตอนวิธีการนี้ได้ถูกสร้างขึ้นมาเพื่อให้มีความยืนหยุ่นต่อการจัดการกับปัญหาที่แตกต่างในระหว่างการค้นหา หรือกล่าวโดยสรุปว่ามันมีความมสามารถในการปรับตัวอย่างอัตโนมัติโดยการตัดสินใจจากประสบการณ์ในอดีตนั่นเอง
ในโลกแห่งความเป็นจริงนั้น คนต้องพบเจอกับปัญหาในชีวิตประจำวันมากมาย เรามักเลือกตัดสินปัญหาหลายๆอย่างโดยยึดจากการสังเกตและเรียนรู้ประสบการณ์ที่ผ่านมาในอดีตเป็นแนวทางในการแก้ไขและพัฒนา นอกจากนี้สมองของคนมีการเรียนรู้ที่รวดเร็วทำให้ในบางครั้งที่ตัดสินใจทำอะไรไปแล้ว ก็สามารถต้องเปลี่ยนแผนกลางครันเมื่อเห็นว่าเราเดินมาผิดทางและมีทางที่น่าจะได้ผลดีกว่าทางปัจจุบัน ด้วยพฤติกรรมของคนนี้เองเป็นแบบอย่างให้เกิดขึ้นตอนวิธีนี้ขึ้น เพราะในโลกของการแก้ปัญหาทางคอมพิวเตอร์นั้นก็มีวิธีการค้นหาคำตอบมากมายผ่านปริภูมิการค้นหา(search space)เช่นเดียวกัน ทำให้เกิดการเพิ่มวิธีการเรียนรู้ของเครื่อง(machine learning)ไปสู่การค้นหาค่าเหมาะสุดอย่างตอบสนอง
ปัญหาการปรับค่าตัวแปรในกระบวนการศึกษาสำนึก[แก้]
การศึกษาสำนึกในปัญหาการค้นหาส่วนใหญ่เช่น กาค้นหาด้วยวิธีการทาบู (tabu search) และการหลอมลวง (simulated annealing) ได้ถูกนำมาใช้ในโปรแกรมคอมพิวเตอร์อย่างมีประสิทธภาพและมีประโยชน์ โดยการศึกษาสำนึกเหล่านี้มีลักษณะที่อ่อนไหวต่อตัวแปรภายในเป็นอย่างมาก ตัวอย่างเช่นปัญหาการหลอมลวงซึ่งขึ้นอยู่การตารางเวลาการหลอมบ่อยครั้งถูกอธิบายโดยตัวแปรอัตราการทำให้เย็นตัวลง(cooling rate) โดยค่าที่เหมาะที่สุดมีควาแตกต่างไปตามแต่ละกรณีซึ่งกำลังถูกแก้ไป ดังนั้นขึ้นตอนวิธีเดียวกันจึงต้องการค่าการเปลี่ยนที่ดีและแน่นอนเพื่อที่สามารถนำมาใช้กับปัญหาใหม่ได้ ในขั้นตอนการหาค่าเหมาะสุดโดยทั่วไปผู้ออกแบบมักจะใส่การปรับเปลี่ยนเพียงเล็กน้อยในขึ้นตอนวิธีนั้นเพื่อเพิ่มความเร็วของระบบ
เป็นที่สังเกตว่าผลการวิจัยจำนวนมากที่เกี่ยวกับการศึกษาสำนึกการค้นหาค่าเหมาะสุดมีความลำเอียงมาจากปัญหานี้ เพราะในบางครั้งประสิทธิภาพของขั้นตอนวิธีถูกคำนวณหลังจากที่ได้เปลี่ยนตัวแปรแล้ว ทั้งที่จริงแล้วกำลังทั้งหมดของการหาค่าเหมาะสุดรวมถึงเวลาในการปรับค่าตัวแปรควรที่จะถูกรวมเข้ามาคิดด้วย
การปรับค่าตัวแปรในฐานะองค์ประกอบหลักของการศึกษาสำนึก[แก้]
การค้นหาค่าเหมาะสุดอย่างตอบสนองให้วิธีการแก้ปัญหาโดยการบวกกลไกการปรับค่าตัวแปรลงไปในขึ้นตอนวิธีการค้นหาด้วยตัวมันเอง ซึ่งตัวแปรเหล่านี้จะถูกปรับด้วยวงวนการป้อนข้อมูลอัตโนมัติตัวหนึ่งซึ่งจะปรับตัวไปตามคุณภาพของวิธีแก้ปัญหาที่พบ โดยยึดจากประวัติการค้นหา และจากเกณฑ์อื่นๆ
ประโยชน์[แก้]
- ความอัตโนมัติของวิธีการหาค่าเหมาะสุดรวมถึงความอัตโนมัติของขึ้นตอนการปรับค่าตัวแปรที่เหมาะสม
- การปรับตัวพลวัตของตัวแปรการค้นหา ซึ่งอาจจะเกิดขึ้นในทุกๆก้าวของการค้นหา นำไปสู่เวลาในการหาค่าเหมาะสุดรวมที่เร็วขึ้น
- รูปแบบที่เพิ่มขึ้นของผลลัพธ์เพราะขั้นตอนวิธีที่สมบูรณ์แบบของการปรับค่าตัวแปร
การค้นหาค่าเหมาะสุดอย่างตอบสนองกับการค้นหาค่าเหมาะสุดอย่างชาญฉลาด[แก้]
การค้นหาค่าเหมาะสุดอย่างตอบสนองจัดอยู่ในพื้นที่การวิจัยที่ซ้อนทับกันหลายองค์ประกอบ ทั้งการวิจัยทางการจัดการ(การหาค่าเหมาะสุด) วิทยาศาสตร์คอมพิวเตอร์ การเรียนรู้ของเครื่องจักร รวมถึงเครือข่ายระบบประสาท(neural networks) จุดประสงค์หลักคือเพื่อที่จะศึกษารูปแบบการเรียนรุ้ที่สามารถประยุกต์ใช้ไปในการแก้ไขปัญหาและการหาค่าเหมาะสุด
สัญญาณการเรียนรู้ที่ส่งผลต่อการปรับค่าตัวแปรภายในของวิธีการการแก้ปัญหาได้มาจากสามแหล่ง คือ
- ลักษณะของปัญหาการค้นหาค่าเหมาะสุด ตัวอย่างเช่น ตัวแปรและตัวเลือกสำหรับการค้นหาที่ถูกประยุกต์ไปใช้กับปัญหา Travelling salesman problem(TSP) จะแตกต่างอย่างมากตัวแปรที่ใช้กับปัญหา Satisfiability
- กรณีที่เฉพาะเจาะจง ตัวอย่างเช่น การแก้ปัญหา TSP สำหรับเมืองในเทือกเขาแอลป์อาจจะต้องการตัวแปรการแก้ปัญหานี้สำหรับเมืองในพื้นราบ
- ลักษณะพิเศษในปริภูมิโครงแบบโดยรอบคำตอบที่ถูกเลือก ตัวอย่างเช่นถ้าคำตอบปัจจุบันถูกจำกัดอยู่ในอ่างน้ำรอบจุดเหมาะสุด(local optimum) ลักษณะของอ่างน้ำ เช่น เส้นผ่านศูนย์กลาง ความสูงของผนังอ่าง เป็นต้น สามารถถูกใช้เพื่อที่จะปรับแต่งวิธีการหลบหนีที่หลากหลาย
โปรแกรมที่เกี่ยวข้อง[แก้]
มีโปรแกรมมากมายที่เกี่ยวข้องกับการค้นหาอย่างตอบสนองเพราะเป็นหนึ่งในการค้นเฉพาะที่สนับสนุนโปรแกรมจำนวนมาก ต่อไปนี้คือโปรแกรมที่ได้ถูกตีพิมพ์มาไม่กี่ปีมานี้และมีความน่าสนใจที่เกี่ยวกับการค้นหาอย่างตอบสนอง
- quadratic assignment
- training neural nets and control problems
- vehicle-routing
- structural acoustic control
- special-purpose VLSI realizations
- graph partitioning
- electric power distribution
- maximum satisfiability
- constraint satisfaction
- optimization of continuous functions
- traffic grooming in optical networks
- maximum clique
- real-time dispatch of trams in storage yards
- roof truss design
- increasing internet capacity
- improving vehicle safety
- aerial reconnaissance simulations
สรุป[แก้]
การค้นหาค่าเหมาะสุดอย่างตอบสนองนั้นเป็นศาสตร์ที่มีความเกี่ยวข้องกับศาสตร์หลายแขนงมาก(ดูได้จากหัวข้อดูเพิ่ม) และมีความน่าสนใจมาก เพราะอย่างที่ทราบกันว่าปัญหาหลายๆปัญหานั้นมีความยากและต้องใช้เวลานานในการหาคำตอบ หรือการประมวลผลอุปกรณ์บางอย่างต้องทำอย่างต่อเนื่อง ยกตัวอย่างเช่นเทคโนโลยีทางด้านการเรียนรู้ของเครื่องจักร ที่ต้องการให้เครื่องจักรมีการเรียนรู้อยู่ตลอดเวลา มีการปรับเปลี่ยนวีธีการประมวลสิ่งต่างๆ และแก้ปัญหาต่างๆอยู่ตลอดเวลา ลองจินตนาการดูว่าอีกไม่นานเราก็จะมีสุนัขที่เป็นหุ่นยนต์ แรกเริ่มที่เราซื้อมามันก็ยังทำอะไรไม่เป็นแต่เมื่อเราสอน มันก็เรียนรู้ได้เฉกเช่นเดียวกับสุนัขจริงๆ คงจะดีไม่น้อยนะครับอีกต่อไปเราคงไม่คงไม่ต้องพามันไปหาสัตวแพทย์อยู่บ่อยๆเพราะป่วยเป็นโรคโน่นโรคนี่ หรืออย่างหนังทางวิทยาศาสตร์ที่หุ่นยนต์มายึดครองโลกก็ตาม ลากมาซะยาวก็เพื่อต้องการจะให้เห็นถึงความวิเศษของขั้นตอนวิธีการค้นหาค่าเหมาะสุดอย่างตอบสนองนี้ สิ่งเล็กๆแค่นี้อาจจะดูยิ่งใหญ่ไปซักหน่อย แต่เป็นก้าวย่างที่ดีที่จะนำเราไปสู่อีกหลายๆเทคโนโลยีที่กำลังมาในโลกปัจจุบัน
ดูเพิ่ม[แก้]
- การหาค่าเหมาะสุดโดยรวม Global optimization
- การค้นเฉพาะที่ Local search (optimization)
- การค้นเฉพาะที่ชี้นำ Guided local search
- การค้นเฉพาะที่ซ้อน Iterated local search
- การค้นหาแบบทาบู Tabu search
- การหลอมลวง Simulated annealing
- ขั้นตอนวิธีทางพันธุศาสตร์ Genetic algorithm
- ความฉลากทางด้านธุรกิจอย่างตอบสนอง Reactive Business Intelligence
อ้างอิง[แก้]
- Battiti, Roberto (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN 978-0-387-09623-0. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2012-03-16. สืบค้นเมื่อ 2011-09-28.
{{cite book}}
: ไม่รู้จักพารามิเตอร์|coauthors=
ถูกละเว้น แนะนำ (|author=
) (help) - Battiti, Roberto (2011). Reactive Business Intelligence. From Data to Models to Insight. Trento, Italy: Reactive Search Srl. ISBN 978-88-905795-0-9. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-03-15. สืบค้นเมื่อ 2011-09-28.
{{cite book}}
: ไม่รู้จักพารามิเตอร์|coauthors=
ถูกละเว้น แนะนำ (|author=
) (help) - Battiti, Roberto (1994). "The reactive tabu search" (PDF). ORSA Journal on Computing. 6 (2): 126–140.
{{cite journal}}
: ไม่รู้จักพารามิเตอร์|coauthors=
ถูกละเว้น แนะนำ (|author=
) (help)
แหล่งข้อมูลอื่น[แก้]
- The Reactive Search Community เก็บถาวร 2010-06-02 ที่ เวย์แบ็กแมชชีน
- LION Conference on Learning and Intelligent Optimization techniques เก็บถาวร 2010-11-08 ที่ เวย์แบ็กแมชชีน
- Reactive Search srl เก็บถาวร 2011-09-03 ที่ เวย์แบ็กแมชชีน