การหาค่าเหมาะที่สุดแบบเฟ้นสุ่ม

การหาค่าเหมาะที่สุดแบบเฟ้นสุ่ม (อังกฤษ:Stochastic Optimization) เป็นวิธีการหาค่าเหมาะที่สุดโดยการสร้างและใช้ตัวแปรสุ่ม
สำหรับปัญหาในกลุ่มนี้ จะใช้ตัวแปรสุ่มในขั้นตอนการคำนวณหาค่าเหมาะที่สุดสำหรับปัญหานั้นๆ
การแก้ปัญหาโดยวิธิการเฟ้นสุ่มนั้นได้ถูกใช้กันอย่างแพร่หลายในหลายวงการ อาทิเช่น ทางด้านอากาศยาน ทางการแพทย์ การขนส่ง และทางด้านการเงิน เป็นต้น เพื่อใช้ช่วยในการออกแบบจรวจมิสไซล์และอากาศยาน การคำนวณกำหนดประสิทธิภาพของยาตัวใหม่ ช่วยในการพัฒนาประสิทธิภาพของการควบคุมสัญญาณจราจร หรือแม้กระทั่งใช้เป็นเครื่องมือในการช่วยตัดสินใจเพื่อผลประโยชน์สูงสุดในการลงทุน โดยวิธีการแบบเฟ้นสุ่มนี้เป็นขั้นตอนวิธีที่จะช่วยให้สามารถตัดสินใจเลือกหนทางที่เหมาะที่สุดในการลดทอนปัญหาต่างๆในโลกความเป็นจริงลง
== การหาค่าที่เหมาะสมที่สุดภายใต้ความไม่แน่นอน ==
เพื่ออธิบายปัญหาบางอย่างที่เกี่ยวข้องในการหาค่าที่เหมาะสมที่สุดภายใต้ความไม่แน่นอน เราจะใช้การอธิบายผ่านการยกตัวอย่างปัญหา สมมติว่าเราต้องการหาค่าที่มากที่สุดของ G (x, ω) โดยที่ขอนิยามค่าต่างๆ ดังนี้
x หมายถึงการตัดสินใจที่จะทำ
X หมายถึงจำนวนชุดของการตัดสินใจที่เป็นไปได้ทั้งหมด
ω หมายถึงผลลัพธ์ที่ไม่สามารถรู้ได้ระหว่างการตัดสินใจ และ
Ω หมายถึงชุดของผลลัพธ์ที่เป็นไปได้ทั้งหมด
จากปัญหาดังกล่าว มีการหาค่าที่เหมาะสมที่สุดภายใต้ความไม่แน่นอนอยู่หลายวิธี ซึ่งบางส่วนจะแสดงในตัวอย่างต่อไป
== ตัวอย่างปัญหา ==
ตัวอย่างปัญหา Newsvendor หลายบริษัทขายสินค้าตามฤดูกาล เช่น บทความแฟชั่น ที่นั่งของสายการบิน ของประดับตกแต่งวันคริสต์มาส นิตยสารและหนังสือพิมพ์ ผลิตภัณฑ์เหล่านี้มีลักษณะการขายที่ค่อนข้างสั้น หลังจากหมดฤดูกาล มูลค่าของผลิตภัณฑ์ก็จะลดลงอย่างมากมาย บ่อยครั้งที่มีการตัดสินใจผลิต หรือซื้อผลิตภัณฑ์ ก่อนที่ฤดูกาลขายจะเริ่มต้น เพราะเมื่อฤดูกาลขายเริ่มต้นแล้ว จะไม่มีเวลามานั่งเปลี่ยนแปลงหรือดำเนินการการตัดสินใจนั้น เนื่องจากจะทำให้ปริมาณของผลิตภัณฑ์ที่จะได้รับไม่ตรงตามเป้าหมาย แต่ในระหว่างฤดูกาล ผู้ที่ตัดสินใจสามารถตัดสินใจแบบอื่นๆที่ทำให้เกิดผลดีมากขึ้นได้ เช่น ปรับเปลี่ยนราคาและยอดขายของผลิตภัณฑ์ที่มีช่วงฤดูกาลยาว พฤติกรรมดังกล่าว เป็นที่คุ้นเคยในหลายๆอุตสาหกรรม ซึ่งสถานการณ์ดังกล่าวก็คือการตัดสินใจทำก่อนสินค้าติดตลาด ดังนั้นการตัดสินใจต้องทำโดยไม่ทราบถึงผลที่จะเกิดขึ้น
สมมติว่า ผู้จัดการมีการตัดสินใจผลิตสินค้าตามฤดูกาล ตามการสั่งซื้อสินค้า ดังนั้นการตัดสินใจตัวแปร x คือตัวเลขค่าลบแทนปริมาณการสั่งซื้อ ค่าใช้จ่ายสำหรับผลิตภัณฑ์ของบริษัท c คือต้นทุนต่อหน่วยของผลิตภัณฑ์ ให้ R คือราคาต่อหน่วยของผลิตภัณฑ์ที่สามารถขายในฤดูกาล(รายได้) หลังจากฤดูกาลขาย ผลิตภัณฑ์ที่เหลือสามารถจำหน่ายในราคาค่าซาก คือ s และโดยปกติ s  RX และ RX - CX = (r - C) x  ตามลำดับ ถ้า D หรือค่าความต้องการน้อยกว่าปริมาณการสั่งซื้อ x แล้ว ปริมาณของผลิตภัณฑ์ที่มีเหลือเมื่อหมดฤดูกาลคือ x – D ดังนั้น เมื่อรวมรายได้แล้ว จะได้กำไรคือ
RD + S (x -- D) และ RD + S (x -- D) -- CX = (s -- c) x + (R -- S) D ตามลำดับ
ดังนั้นจะได้กำไร
ผู้จัดการต้องการตัดสินใจ x เพื่อเพิ่มกำไร G (x, D) แต่ไม่รู้ว่า D เป็นอย่างไร หรืออาจบอกได้ว่าไม่แน่นอนในตอนนี้
สังเกตว่า ถ้า r ≤ c และ s ≤ c แล้ว บริษัทจะไม่ได้กำไรจากการซื้อและขายผลิตภัณฑ์ กำหนดปริมาณการสั่งซื้อที่ดีที่สุดคือ x* = 0 โดยไม่คำนึงถึง D นอกจากนี้ถ้า s ≥ c แล้ว ผลิตภัณฑ์ที่ยังไม่ได้ขายเมื่อหมดฤดูกาล สามารถขายในราคาอย่างน้อยเท่ากับต้นทุนของผลิตภัณฑ์ เพื่อที่จะได้ปริมาณการสั่งซื้อที่เหมาะสมที่สุดโดยไม่คำนึงถึง D นี่เป็นตัวอย่างที่ถูกต้องและชัดเจน ดังนั้นเราจึงสมมติได้ว่าส่วนที่เหลือคือ s  D ดังนั้นถ้าทราบความต้องการของ D จะได้การตัดสินใจที่ดีที่สุดในการเลือกปริมาณการสั่งซื้อ x * = D
อย่างไรก็ตาม ถ้าไม่รู้ D แล้ว จะทำให้ปัญหายากขึ้น บางครั้งผู้จัดการอาจต้องการป้องกันผลที่เลวร้ายที่สุด สมมติว่าผู้จัดการคิดว่า D จะอยู่ในช่วง [a, b] โดย a g* (D) - G (x, D) ผู้จัดการอาจกำหนดค่าของ x ที่ช่วยลดส่วนของกำไรที่เสียไป สำหรับ x ใดๆ เนื่องจากผู้จัดการฝ่ายต้องการที่จะกำหนดค่าของ x ที่ช่วยลดส่วนของกำไรที่เสียไป จึงนำไปสู่ปัญหา min - max ต่อไปนี้
ค่าที่เหมาะสมที่สุดของปัญหานี้คือ  x* = [(c - s) a + (r - c) b] / (r - s) กำหนดให้ x* เป็นการรวมของ a และ b และทำให้ a  \operatorname{E}[G(x,D)] = \int_{0}^{\infty} G(x,w )\,\operatorname {d}F(w) . ซึ่งนำไปสู่โปรแกรมการสุ่ม
การแก้ปัญหาค่าที่เหมาะสมไม่ใช่เรื่องยากในปัจจุบัน กำหนดให้ D ≥ 0 ฟังก์ชัน G(•,D) มีลักษณะเว้า (ตัวแบบเชิงเส้นเป็นช่วง) ดังนั้นมูลค่าที่คาดหวัง g (.) ก็ต้องเว้าด้วย สมมติว่าในขณะที่ F (.) ต่อเนื่องที่จุด x > 0 นั่นคือ  เมื่อใช้การอินทิเกรดแยกส่วนจะคำนวณได้ว่า
ฟังก์ชัน g (.) ลักษณะกราฟเว้าอย่างต่อเนื่อง จากสมการ (5) ถ้า F (°) ต่อเนื่องที่ x จะเป็นไปได้ว่า g (.) เป็นอนุพันธ์ที่ x iff F (.) อย่างต่อเนื่องที่ x ซึ่งในกรณีนี้
ในทางกลับกัน เป็นฟังก์ชันการแจกแจงสะสม (CDF) ของ F ซึ่งถูกกำหนดว่า
เนื่องจากฟังก์ชัน g(.) มีลักษณะเว้า ซึ่งสอดคล้องกับ x* > 0 เป็นการหาค่าที่ดีที่สุดของสมการที่ (4) นั่นคือ g’ (x*) = 0 โดยมีเงื่อนไขว่า g(.) เป็นอนุพันธ์ที่ x* กำหนดให้ s 
ค่าสัมประสิทธิ์ β ≥ 0 หมายถึงค่าน้ำหนักที่ให้กับการตัดสินใจ ถ้า β มีขนาดใหญ่ ปัญหาดังกล่าวข้างต้นจะมีความแปรปรวนของกำไรน้อยที่สุด ในขณะที่ β = 0 นั่นคือสมการ (8) เกิดขึ้นพร้อมกับสมการ (4) เนื่องจากมีการกำหนดค่าความแปรปรวนเป็น Var [G (x, D)] ≡ IE [(g (x, D) - IE [G (x, D)]) 2] ซึ่งเท่ากับค่าคาดหวังของมัน ค่าที่ได้จาก (8) จะคล้ายกับ ค่าที่คาดหวังที่ได้จาก (4) ดังนั้นการหาค่าคาดหวังที่ดีที่สุดคือ G (x, D) ซึ่งใช้ได้กับ การหาค่าเฉลี่ย ค่าความแปรปรวน ตำแหน่งของข้อมูล และเกือบทุกๆด้านของตัวแปรสุ่มที่น่าสนใจ
จากตัวอย่างการหาค่าที่ดีที่สุดนี้ สามารถนำไปใช้ได้กับการตัดสินใจภายใต้สภาวะการที่ไม่แน่นอนได้ ตัวแปรสุ่ม D ใช้แทนความหมายของค่าเฉลี่ย μ = IE [D] แล้วทำการกำหนดปัญหาดังนี้
== กำหนดการเฟ้นสุ่ม ==
กำหนดการเฟ้นสุ่ม (อังกฤษ:Stochastic programming) คือการโปรแกรมทางคณิตศาสตร์อาจจะอยู่ในรูปของกำหนดการเชิงเส้น กำหนดการไม่เชิงเส้น กำหนดการจำนวนเต็ม กำหนดการเชิงผสมผสานเชิงจำนวนเต็ม โดยที่ข้อมูลนั้นเป็นแบบเฟ้นสุ่ม นั่นหมายถึงเราไม่ทราบค่าสัมประสิทธิ์ ที่แน่นอนของข้อมูลแต่จะทราบลักษณะการแจกแจงของข้อมูลแทนในขณะที่ข้อมูลที่เป็นแบบเชิงกำหนด เราจะทราบค่าของสัมประสิทธิ์ ดังนั้นกำหนดการเฟ้นสุ่มจึงเกี่ยวข้องกับสถานการณ์ที่มีความไม่แน่นอน
== วิธีการค้นหาแบบสุ่ม ==
ในทางกลับกันหากเรามีชุดของข้อมูลที่ประกอบด้วยค่าที่วัดมาอย่างแม่นยำแล้ว ก็จะมีวิธีการบางอย่างที่จะนำไปสู่ขั้นตอนการสุ่มที่น้อยลง แล
ในความเป็นจริงแล้วหลักการต่างๆของวิธีการสุ่มเป็นที่รู้กันว่าเป็นหนทางที่ง่ายและมีประสิทธิภาพในการนำมาซึ่งขั้นตอนวิธีที่เกือบจะมีประสิทธิภาพดีที่สุด และสำหรับปัญหามากมายหลากหลายประเภทวิธีการหาค่าเหมาะที่สุดแบบเฟ้นสุ่มนี้ ประกอบไปด้วย
simulated annealing|Simulated annealing by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi (1983)
Reactive search optimization (RSO) by Roberto Battiti, G. Tecchiolli (1994), recently reviewed in the reference book
วิธีการครอส-เอนโทรปี: Cross-entropy method by Rubinstein and Kroese (2004)
Random search by Anatoly Zhigljavsky (1991)
Stochastic tunneling
Parallel tempering a.k.a. replica exchange
Stochastic hill climbing
Swarm algorithms
Evolutionary algorithms
* Genetic algorithms by Holland (1975)
* Evolution strategies
== อ้างอิง ==
http://www2.isye.gatech.edu/~anton/stochoptiebook.pdf 
http://www.jhuapl.edu/spsa/PDF-SPSA/Handbook04_StochasticOptimization.pdf
http://www.ima.umn.edu/talks/workshops/9-9-13.2002/birge/birge.pdf
http://www.math.uwaterloo.ca/~cswamy/talks/stochopt-short.ppt
http://stoprog.org/index.html?spintroduction.html 
ทฤษฎีความน่าจะเป็น
ทฤษฎีการประมาณค่า
ขั้นตอนวิธี
การสุ่ม
ความน่าจะเป็น