การปรับปรุงวิธีลอตโตเมตาฮิวริสติกสำหรับการแก้ปัญหาลอตเตอรี่
Article Sidebar
Main Article Content
บทคัดย่อ
ปัญหาลอตเตอรี่ เป็นปัญหาการสุ่มเลือกตัวเลข k หมายเลขจากหมายเลขทั้งหมด n หมายเลขโดยในลอตเตอรี่หนึ่งใบสามารถกรอกหมายเลข k หมายเลข และผลรางวัลจะถูกสุ่มหมายเลข p หมายเลขจากทั้งหมด n หมายเลข ซึ่งเป้าหมายของปัญหานี้คือ จะต้องซื้อลอตเตอรี่จำนวนน้อยที่สุดเพื่อให้ตรงกับผลรางวัลอย่างน้อย t หมายเลข โดยปัญหานี้สามารถหาคำตอบด้วยการสร้างตัวแบบกำหนดการเชิงจำนวนเต็ม อย่างไรก็ตามการหาคำตอบของปัญหานี้ด้วยวิธีแม่นตรงค่อนข้างใช้เวลานาน ดังนั้นในบทความวิจัยนี้ ผู้วิจัยได้นำเสนอวิธีการหาคำตอบของปัญหาลอตเตอรี่โดยปรับปรุงวิธีลอตโตเมตาฮิวริสติก (Lotto-Meta heuristic) ซึ่งเป็นวิธีฮิวริสติกสำหรับการแก้ปัญหาลอตเตอรี่จากผลการทดลองแก้ปัญหาลอตเตอรี่ขนาดเล็กพบว่าจำนวนลอตเตอรี่ที่ต้องซื้อมีค่าน้อยกว่าหรือเท่ากับจำนวนลอตเตอรี่ที่ได้จากวิธีเดิม
Article Details
เอกสารอ้างอิง
Burger, A., Gründlingh, W.R. and Vuuren, Jan. 2003. The lottery problem. Available at: https://www.researchgate.net/publication/228998461_The_lottery_problem. Retrieved December 2, 2019.
Jans, R. 1997. Analysis of a symmetrical set covering problem: The lottery problem. Master’s Thesis, Department of Applied Economics, K.U. Leuven, Belgium.
Li, P.C. and ven Rees, G.H.J. 2000. New constructions of lotto designs. Utilitas Mathematica, 58, 45-64.
Beasley, J.E. and Chu, P.C. 1996. A genetic algorithm for the set covering problem. European Journal of Operation Research, 94, 392-404.
Lan, G., Depuy, G.W. and Whitehouse, G.E. 2007. An effective and simple heuristic for the set covering problem. European Journal of Operation Research, 176, 1387-1403.
Aickelin, U. 2002. An indirect genetic algorithm for set covering problems. Journal of the Operation Research Society, 53, 1118-1126.
Bautisa, J. and Pereira, J. 2007. A GRASP algorithm to solve the unicost set covering problem, Computer & Operations Research, 34, 3162-3173.
Li, P.C. and van Rees, G.H.J. 2002. Lotto design tables. Journal of Combinatorial Designs, 10, 335-359.
Li, P.C. 1999. Some results on lotto design. Ph.D. Thesis, University of Manitoba.
Li, P.C. and van Rees, G.H.J. 1999. Lower bounds on lotto designs. Congressus Numerantium, 141, 5-30.
Jans, R. and Degrave, Z. 2008. A note on a symmetrical set covering problem: the lottery problem. European Journal of Operational Research, 186, 104-110.
Mohammadi, A. 2012. Heuristic algorithm for solving the integer programming of the lottery problem. Scientia Iranica. 19. 895-901.
