การศึกษาอัลกอริทึมการสืบค้น สำหรับการจำลองการทดลองด้วยคอมพิวเตอร์
Exploratory search algorithms for computer simulated experiments
Keywords:
การจำลองการทดลองด้วยคอมพิวเตอร์, แผนการทดลองแบบลาตินไฮเปอร์คิวบ์, อัลกอริทึมการสืบค้น, เกณฑ์การเลือกค่าที่เหมาะสม, Computer simulated experiments, Latin hypercube designs, Search algorithms, Optimality criteriaAbstract
เทคนิคการจำลองการทดลองด้วยคอมพิวเตอร์ถูกนำมาใช้อย่างแพร่หลายในการศึกษาระบบที่มีความซับซ้อนและไม่สามารถทำการทดลองทางกายภาพได้ การจำลองการทดลองประเภทนี้มักจะใช้เวลายาวนานมากในการประมวลผล โดยทั่วไปผลลัพธ์ที่ได้จากการจำลองการทดลองด้วยคอมพิวเตอร์จะมีลักษณะตรงแบบ กล่าวคือเมื่อทำการทดลองภายใต้เงื่อนไขเดิมของตัวแปรเข้าจะทำให้ได้ค่าผลลัพธ์คงที่เสมอดังนั้นแผนการทดลองที่เน้นการกระจายจุดทดลองเพื่อเติมเต็มปริภูมิของการทดลองให้มากที่สุด ซึ่งมีชื่อเรียกว่า แผนการทดลองแบบลาตินไฮเปอร์คิวบ์ (Latin hypercube design: LHD) จึงถูกนำมาใช้อย่างแพร่หลายในทางปฏิบัติการสร้างแผนการทดลองแบบ LHD ที่เหมาะสมที่สุดสามารถทำได้โดยใช้อัลกอริทึมการสืบค้นควบคู่กับเกณฑ์ในการเลือกค่าที่เหมาะสม ซึ่งกระบวนสืบค้นดังกล่าวนี้มักจะใช้เวลานานมากโดยเฉพาะอย่างยิ่งเมื่อมิติปัญหาของแผนการทดลองมีขนาดใหญ่ขึ้น ดังนั้นจึงมีงานวิจัยจำนวนมากที่ได้นำเสนออัลกอริทึมการสืบค้นแบบต่าง ๆ เพื่อการค้นหาแผนการทดลองแบบ LHD ที่มีประสิทธิภาพมากที่สุด บทความนี้จึงได้ทำการรวบรวมและทบทวนคุณลักษณะของอัลกอริทึมการสืบค้นเหล่านี้ รวมไปถึงเกณฑ์ที่ใช้ในการตัดสินใจเลือกค่าที่เหมาะสมประเภทต่าง ๆ เพื่อเป็นแนวทางในการเลือกใช้อัลกอริทึมการสืบค้นที่เหมาะสมสำหรับแต่ละมิติปัญหาของการทดลอง ส่วนทิศทางการวิจัยในงานด้านนี้ได้นำเสนอไว้ในตอนท้ายของบทความ Computer simulated experiments are often used to explore complex physical phenomena. They are usually time consuming and computationally expensive to run. Normally, the output responses from computer simulated experiments are deterministic. Consequently the space filling designs, which focus on spreading design points over a design space, are necessary. Latin hypercube designs (LHD) are normally practiced in the context of computer simulated experiments. The best LHD for a given dimensional problem is obtained by using a search algorithm under a pre-specified optimality criterion. Usually this searching process takes a long time to terminate, especially when the dimension of the problem is large. A number of search algorithms have been practiced along with the optimality criteria to search for the best LHD. In this paper we review the popular search algorithms and the optimality criteria that have been extensively used in the context of computer simulated experiments. The guidelines for the choice of best search algorithm and further study are also presented.References
Bates, R. A., Buck, R. J., Riccomagno, E., and Wynn, H.P. (1996). Experimental design and observation for large systems. Journal of the royal statistical society, Series B, 58, 77-94.
Butler, N.A. (2001). Optimal and orthogonal latin hypercube designs for computer experiments. Biometrika, 88(3),847-857.
Jin, R., Chen, W., and Sudjianto, A. (2005). An efficient algorithm for constructing optimal design of computer experiments. Journal of Statistical Planning and Inference, 134, 268-287.
Johnson, M. E., Moore, I.M., and Ylvisaker, D. (1990). Minimax and maximin distance designs. Journal of Statistical Planning and Inference, 26, 131-148.
Koehler, J. and Owen, A.B. (1996). Computer experiments. Handbook of Statistics, volume 13, Elsevier Science, New York, 261-308.
Leary, S., Bhaskar, A., and Keane, A. (2003). Optimal orthogonal-array-based latin hypercubes. Journal of Applied Statistics, 30(5), 585-598.
Li, W. and Wu, C.F.J. (1997). Columnwise-pairwise algorithms with applications to the construction of supersaturated designs. Technometrics, 39, 171-179.
Li, Z. and Shigeru, N. (2001). Maximin distance-lattice hypercube design for computer experiment based on genetic algorithm. IEEE explore, 2, 814-819.
Liefvandahl, M. and Stocki, R. (2006). Study on algorithms for optimization of latin hypercubes. Journal of Statistical Planning and Inference, 136, 3231-3247.
Mackay, M.D., Beckman, R.J., and Conover, W.J. (1979). A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 21, 239-246.
