การเขียนโปรแกรมเป้าหมายแบบอิงเอเจนต์ — การจำลองและการหาค่าเหมาะที่สุดแบบผสมผสานด้วยเอเจนต์แบบกระจายศูนย์และการบรรลุเป้าหมายหลายประการ
- ผู้เสนอ
- Charnes, Cooper (GP); Schelling, Holland (ABM foundations)
- ปี
- 1990s-2000s (hybrid integration)
- ประเภท
- Hybrid simulation-optimization
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การเขียนโปรแกรมเป้าหมายแบบอิงเอเจนต์ (Agent-Based Goal Programming หรือ ABGP) เป็นการบูรณาการการจำลองแบบอิงเอเจนต์เข้ากับการหาค่าเหมาะที่สุดด้วยการเขียนโปรแกรมเป้าหมาย เพื่อสร้างแบบจำลองระบบที่มีผู้ตัดสินใจอิสระหลายรายดำเนินตามเป้าหมายที่มีลำดับความสำคัญและมีการแข่งขันกัน วิธีนี้ช่วยให้นักวิจัยสามารถศึกษาว่าพฤติกรรมแบบกระจายศูนย์และปรับตัวได้ในระดับเอเจนต์นำไปสู่ผลลัพธ์ระดับระบบที่วัดเทียบกับเป้าหมายที่กำหนดไว้ล่วงหน้าได้อย่างไร โดยสามารถจับภาพทั้งปรากฏการณ์เชิงอุบัติและผลลัพธ์ที่ตอบสนองหลายเกณฑ์พร้อมกัน
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงห่วงโซ่อุปทานที่ซัพพลายเออร์ ผู้ผลิต และผู้ค้าปลีกแต่ละรายตัดสินใจอย่างอิสระตามกฎเกณฑ์ท้องถิ่น แต่ระบบทั้งหมดต้องบรรลุเป้าหมายด้านต้นทุน ระดับการบริการ และการปล่อยมลพิษ การหาค่าเหมาะที่สุดแบบมาตรฐานจะสมมติว่ามีผู้วางแผนกลางเพียงคนเดียว ส่วนการจำลองแบบบริสุทธิ์จะบอกว่าเกิดอะไรขึ้นแต่ไม่บอกวิธีปรับปรุง ABGP ผสมผสานทั้งสองอย่างเข้าด้วยกัน: เอเจนต์จำลองพฤติกรรมแบบกระจายศูนย์ที่สมจริง ในขณะที่การเขียนโปรแกรมเป้าหมายจะประเมินและนำพาระบบไปสู่การบรรลุเป้าหมายหลายประการโดยมีการเบี่ยงเบนน้อยที่สุด นักวิเคราะห์จะระบุเป้าหมายและน้ำหนักลำดับความสำคัญ เอเจนต์จะโต้ตอบกันตลอดเวลา และวิธีนี้จะติดตามว่าผลลัพธ์จริงเบี่ยงเบนจากแต่ละเป้าหมายไปมากน้อยเพียงใด ซึ่งช่วยให้สามารถวิเคราะห์และหาค่าเหมาะที่สุดของระบบปรับตัวที่ซับซ้อนได้
ประวัติศาสตร์
การเขียนโปรแกรมเป้าหมายถูกนำเสนอโดย Charnes และ Cooper ในทศวรรษ 1950 ในฐานะส่วนขยายของการเขียนโปรแกรมเชิงเส้นสำหรับการบรรลุวัตถุประสงค์หลายประการ การสร้างแบบจำลองแบบอิงเอเจนต์เกิดขึ้นเป็นระเบียบวิธีที่แตกต่างกันในทศวรรษ 1990 จากผลงานของนักวิชาการเช่น Holland และ Epstein การบูรณาการ ABM เข้ากับการเขียนโปรแกรมเชิงคณิตศาสตร์ รวมถึงการเขียนโปรแกรมเป้าหมาย ได้รับความสนใจในทศวรรษ 2000 ในชุมชนการวิจัยดำเนินงาน ห่วงโซ่อุปทาน และการจำลองนโยบาย เนื่องจากพลังการคำนวณทำให้วงจรการจำลองและการหาค่าเหมาะที่สุดแบบวนซ้ำเป็นไปได้
ควรใช้เมื่อใด
ใช้ ABGP เมื่อระบบเกี่ยวข้องกับผู้แสดงอิสระหลายรายที่มีกฎพฤติกรรมที่แตกต่างกัน และนักวิเคราะห์จำเป็นต้องบรรลุหรือหาค่าเหมาะที่สุดสำหรับเป้าหมายที่แข่งขันกันหลายประการพร้อมกัน ซึ่งเป็นเรื่องปกติในการจัดการห่วงโซ่อุปทาน นโยบายสาธารณะ การจัดสรรทรัพยากรด้านสุขภาพ และการวางแผนสิ่งแวดล้อม วิธีนี้เหมาะสมเมื่อพฤติกรรมรวมเชิงอุบัติเป็นหัวใจสำคัญของปัญหา และแบบจำลองการหาค่าเหมาะที่สุดแบบรวมศูนย์เพียงแบบเดียวจะแสดงถึงความเป็นอิสระของเอเจนต์ผิดพลาด หลีกเลี่ยง ABGP เมื่อระบบมีลักษณะเฉพาะที่ดีโดยผู้ตัดสินใจเพียงคนเดียว เมื่อทรัพยากรการคำนวณมีจำกัดมาก (ต้องมีการจำลองหลายครั้ง) เมื่อเป้าหมายสามารถลดลงเหลือวัตถุประสงค์เดียวโดยไม่สูญเสียความถูกต้อง หรือเมื่อการโต้ตอบของเอเจนต์มีน้อยมากและแบบจำลองการเขียนโปรแกรมเชิงคณิตศาสตร์แบบบริสุทธิ์ก็เพียงพอแล้ว
ข้อจำกัดและข้อควรพิจารณา
- ต้องใช้การคำนวณอย่างเข้มข้น: การประเมินแต่ละครั้งต้องเรียกใช้การจำลองแบบอิงเอเจนต์ทั้งหมด ทำให้วงจรการหาค่าเหมาะที่สุดขนาดใหญ่มีค่าใช้จ่ายสูง
- การปรับเทียบและการตรวจสอบแบบจำลองเป็นเรื่องที่ท้าทาย พารามิเตอร์พฤติกรรมของเอเจนต์มักจะประเมินได้ยากจากข้อมูลเชิงประจักษ์
- ผลลัพธ์อาจมีความอ่อนไหวต่อการเลือกการออกแบบการจำลอง (ช่วงเวลา, โครงสร้างเอเจนต์, เงื่อนไขเริ่มต้น) ซึ่งนำไปสู่ความเสี่ยงของแบบจำลอง
- การเขียนโปรแกรมเป้าหมายกำหนดให้นักวิเคราะห์ต้องระบุระดับความปรารถนาและน้ำหนักล่วงหน้า ซึ่งอาจเป็นอัตวิสัยหรือมีการโต้แย้งระหว่างผู้มีส่วนได้ส่วนเสีย
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- จับภาพพฤติกรรมระบบเชิงอุบัติที่เกิดจากการโต้ตอบของเอเจนต์แบบกระจายศูนย์ ซึ่งแบบจำลองการหาค่าเหมาะที่สุดแบบรวมไม่สามารถแสดงได้
- จัดการกับเป้าหมายที่แข่งขันกันหลายประการด้วยโครงสร้างลำดับความสำคัญหรือน้ำหนักที่ชัดเจน ทำให้นักตัดสินใจมีความโปร่งใสในการแลกเปลี่ยน
- รองรับเอเจนต์ที่แตกต่างกันด้วยกฎพฤติกรรม ชุดข้อมูล และการเรียนรู้แบบปรับตัวที่แตกต่างกัน โดยไม่จำเป็นต้องมีฟังก์ชันอรรถประโยชน์ที่เป็นหนึ่งเดียว
- อนุญาตให้มีการวิเคราะห์นโยบายแบบ "ถ้า...แล้ว" (what-if): การเปลี่ยนกฎของเอเจนต์หรือน้ำหนักเป้าหมาย และสังเกตผลกระทบระดับระบบโดยไม่ต้องทำการทดลองทางกายภาพ
- มีความยืดหยุ่นเพียงพอที่จะบูรณาการกับการจำลองเชิงสุ่ม โดยให้การกระจายการบรรลุเป้าหมายแทนที่จะเป็นค่าประมาณแบบจุด
การประยุกต์ใช้
- การประสานงานห่วงโซ่อุปทานที่ซัพพลายเออร์ ผู้ผลิต และผู้ค้าปลีกแต่ละรายหาค่าเหมาะที่สุดในระดับท้องถิ่น ในขณะที่ระบบมีเป้าหมายด้านต้นทุน ระดับการบริการ และความยั่งยืนพร้อมกัน
- การสร้างแบบจำลองการจัดสรรทรัพยากรสาธารณสุขโดยจำลองเอเจนต์โรงพยาบาลและการไหลของผู้ป่วยเพื่อลดการเบี่ยงเบนจากเป้าหมายด้านความครอบคลุม ความเท่าเทียม และงบประมาณ
- การจำลองตลาดพลังงานที่เอเจนต์ผู้ผลิตและผู้บริโภคโต้ตอบกัน และนโยบายพยายามบรรลุเป้าหมายด้านการเจาะตลาดพลังงานหมุนเวียน เสถียรภาพราคา และการปล่อยมลพิษ
- การวางแผนการใช้ที่ดินในเมืองด้วยเอเจนต์ครัวเรือนและผู้พัฒนา โดยนักวางแผนลดการเบี่ยงเบนจากเป้าหมายด้านความสามารถในการจ่าย ความหนาแน่น และพื้นที่สีเขียว
- การทดสอบความเครียดของตลาดการเงินที่เอเจนต์ผู้ค้าสร้างพลวัตภายในที่ประเมินเทียบกับเป้าหมายด้านเงินทุนตามกฎระเบียบและสภาพคล่อง
วิธีการทำงาน
วิธีการทำงาน
กำหนดเอเจนต์ (ประเภท, กฎพฤติกรรม, โครงสร้างการโต้ตอบ) และระบุชุดของเป้าหมาย g_i พร้อมระดับความปรารถนา แต่ละเป้าหมายแสดงถึงเป้าหมายที่ระบบควรบรรลุ เช่น ต้นทุนต่ำกว่าเกณฑ์ ปริมาณงานสูงกว่าค่าต่ำสุด หรือความเท่าเทียมกันสูงกว่าค่าพื้นฐาน กำหนดน้ำหนักลำดับความสำคัญ w_i หรือระดับลำดับความสำคัญแบบพจนานุกรมให้กับตัวแปรการเบี่ยงเบนเชิงบวก (เกินเป้าหมาย) และเชิงลบ (ต่ำกว่าเป้าหมาย) ของแต่ละเป้าหมาย
กำหนดวัตถุประสงค์การเขียนโปรแกรมเป้าหมายแบบถ่วงน้ำหนัก: ลดผลรวมถ่วงน้ำหนักของการเบี่ยงเบน Z = sum(w_i^+ * d_i^+ + w_i^- * d_i^-) โดยที่ d_i^+ และ d_i^- คือตัวแปรการเกินเป้าหมายและการต่ำกว่าเป้าหมายสำหรับเป้าหมาย i ตามลำดับ ฟังก์ชันวัตถุประสงค์นี้จะนำทางว่าควรประเมินการกำหนดค่าการจำลองหรือพารามิเตอร์เอเจนต์ใด
สูตร
\min Z = \sum_{i=1}^{k} (w_i^+ d_i^+ + w_i^- d_i^-)เรียกใช้การจำลองแบบอิงเอเจนต์สำหรับขอบเขตเวลาที่กำหนด เอเจนต์ปฏิบัติตามกฎพฤติกรรม (เช่น ความมีเหตุผลแบบจำกัด, ข้อมูลท้องถิ่น, การเรียนรู้แบบปรับตัว) และโต้ตอบกันผ่านตลาด เครือข่าย หรือสภาพแวดล้อมเชิงพื้นที่ บันทึกผลลัพธ์ระดับระบบในแต่ละช่วงเวลาหรือเมื่อสิ้นสุดการจำลอง ทำซ้ำหลายครั้งเพื่อพิจารณาความแปรปรวนเชิงสุ่มในพฤติกรรมของเอเจนต์
จับคู่ผลลัพธ์การจำลองกับสมการข้อจำกัดของเป้าหมาย: f_i(x) + d_i^- - d_i^+ = g_i คำนวณค่าการเบี่ยงเบน d_i^+ และ d_i^- สำหรับแต่ละเป้าหมาย i โดยอิงตามผลลัพธ์การจำลอง x คำนวณวัตถุประสงค์โดยรวม Z การประเมินนี้จะเปิดเผยว่าเป้าหมายใดบรรลุผล เป้าหมายใดเกินเป้าหมาย และเป้าหมายใดต่ำกว่าเป้าหมาย และมากน้อยเพียงใด
สูตร
f_i(x) + d_i^- - d_i^+ = g_i, \quad d_i^+, d_i^- \geq 0
ใช้ข้อมูลการเบี่ยงเบนเพื่ออัปเดตพารามิเตอร์เอเจนต์ กฎนโยบาย หรือการกำหนดค่าโครงสร้าง (ผ่านวงจรการหาค่าเหมาะที่สุด, การออกแบบการทดลอง, หรือการค้นหาแบบเมตาฮิวริสติก) และจำลองซ้ำ ดำเนินการวนซ้ำต่อไปจนกว่า Z จะถูกลดให้เหลือน้อยที่สุดในระดับที่ยอมรับได้ หรือเป็นไปตามเกณฑ์การหยุด รายงานการกำหนดค่าเอเจนต์สุดท้าย โปรไฟล์การบรรลุเป้าหมาย และการวิเคราะห์การแลกเปลี่ยนระหว่างวัตถุประสงค์ที่มีลำดับความสำคัญ
ข้อผิดพลาดที่พบบ่อย
- การถือว่าแบบจำลองแบบบูรณาการเป็นกล่องดำโดยไม่ตรวจสอบส่วนประกอบแบบอิงเอเจนต์แยกต่างหากก่อน อาจนำไปสู่ข้อผิดพลาดในการสร้างแบบจำลองที่ไม่ถูกตรวจพบซึ่งแพร่กระจายไปยังชั้นการหาค่าเหมาะที่สุด
- การใช้การจำลองน้อยเกินไปต่อจุดออกแบบทำให้เกิดการประมาณค่าการเบี่ยงเบนที่มีสัญญาณรบกวน ซึ่งทำให้การหาค่าเหมาะที่สุดด้วยการเขียนโปรแกรมเป้าหมายเข้าใจผิดไปสู่การกำหนดค่าที่ไม่เหมาะสม
- การกำหนดระดับความปรารถนาของเป้าหมายโดยพลการ แทนที่จะอิงตามเกณฑ์มาตรฐานเชิงประจักษ์หรือข้อมูลจากผู้มีส่วนได้ส่วนเสีย จะบ่อนทำลายความหมายของการลดการเบี่ยงเบน
- การละเลยความแปรปรวนเชิงสุ่มโดยใช้เฉพาะผลลัพธ์การจำลองเฉลี่ย อาจทำให้การบรรลุเป้าหมายผิดพลาดอย่างเป็นระบบ โดยเฉพาะอย่างยิ่งสำหรับเป้าหมายที่อ่อนไหวต่อความเสี่ยง
คำถามที่พบบ่อย
ABGP แตกต่างจากการเรียกใช้แบบจำลองแบบอิงเอเจนต์แล้วทำการเขียนโปรแกรมเป้าหมายแยกต่างหากอย่างไร?
ใน ABGP ส่วนประกอบทั้งสองเชื่อมโยงกันในวงจรป้อนกลับ: ค่าการเบี่ยงเบนเป้าหมายจากการจำลองแต่ละครั้งจะแจ้งการเปลี่ยนแปลงพารามิเตอร์ที่ป้อนกลับเข้าสู่การจำลองครั้งถัดไป การเรียกใช้แยกกันหมายความว่าการหาค่าเหมาะที่สุดไม่สามารถพิจารณาได้ว่าพฤติกรรมของเอเจนต์เปลี่ยนแปลงไปอย่างไรเพื่อตอบสนองต่อการปรับนโยบาย ซึ่งทำให้สูญเสียพลวัตเชิงอุบัติที่เป็นแรงจูงใจในการใช้ ABM ตั้งแต่แรก
มีเครื่องมือซอฟต์แวร์มาตรฐานสำหรับการนำ ABGP ไปใช้หรือไม่?
ไม่มีเครื่องมือเฉพาะเจาะจงเพียงเครื่องมือเดียว ผู้ปฏิบัติงานมักจะสร้างชั้นแบบอิงเอเจนต์ในแพลตฟอร์มเช่น NetLogo, Repast หรือ Mesa จากนั้นเชื่อมโยงกับตัวแก้ปัญหาการเขียนโปรแกรมเชิงคณิตศาสตร์ (เช่น CPLEX, Gurobi, PuLP) หรือตัวห่อหุ้มเมตาฮิวริสติกสำหรับวงจรการหาค่าเหมาะที่สุด การเชื่อมโยงมักจะเขียนโค้ดเองใน Python หรือ Java
ต้องมีการจำลองกี่ครั้งต่อจุดออกแบบเพื่อให้ได้ค่าประมาณการเบี่ยงเบนเป้าหมายที่เชื่อถือได้?
ไม่มีกฎสากล แต่การทดลองนำร่องด้วยการวิเคราะห์ความแปรปรวนเป็นสิ่งสำคัญ สำหรับ ABM แบบสุ่ม การจำลองซ้ำ 30-100 ครั้งต่อจุดออกแบบเป็นจุดเริ่มต้นทั่วไป ระบบที่มีความแปรปรวนทางพฤติกรรมสูงหรือเหตุการณ์ที่หายากอาจต้องใช้หลายร้อยครั้ง วิธีพื้นผิวตอบสนองหรือตัวเลขสุ่มร่วมสามารถลดจำนวนการเรียกใช้ทั้งหมดได้
ABGP สามารถจัดการลำดับความสำคัญแบบพจนานุกรม (pre-emptive) ระหว่างเป้าหมายได้หรือไม่ หรือเฉพาะเป้าหมายแบบถ่วงน้ำหนักเท่านั้น?
โครงสร้างลำดับความสำคัญทั้งสองแบบเข้ากันได้ ABGP แบบถ่วงน้ำหนักจะลดวัตถุประสงค์การเบี่ยงเบนรวมเพียงหนึ่งเดียว ABGP แบบพจนานุกรมจะหาค่าเหมาะที่สุดของเป้าหมายตามลำดับ — ขั้นแรกให้ลดการเบี่ยงเบนในเป้าหมายที่มีลำดับความสำคัญสูงสุด จากนั้นในเป้าหมายที่สองโดยที่ระดับการบรรลุเป้าหมายแรกถูกกำหนดไว้ และต่อไปเรื่อยๆ การเลือกควรสะท้อนถึงโครงสร้างความชอบที่แท้จริงของผู้มีส่วนได้ส่วนเสีย
เมื่อใดที่การเขียนโปรแกรมเป้าหมายแบบแข็งแกร่งหรือแบบสุ่มดีกว่า ABGP?
เมื่อความแตกต่างในระดับเอเจนต์และผลกระทบจากการโต้ตอบเชิงอุบัติไม่ใช่ปัจจัยหลักของความไม่แน่นอน — ตัวอย่างเช่น เมื่อความไม่แน่นอนส่วนใหญ่เกิดจากการกระจายพารามิเตอร์มากกว่าจากการตัดสินใจแบบกระจายศูนย์ — การเขียนโปรแกรมเป้าหมายแบบสุ่มหรือแบบแข็งแกร่งจะให้ความสามารถในการวิเคราะห์ที่ชัดเจนกว่าด้วยต้นทุนการคำนวณที่ต่ำกว่า
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Charnes, A., Cooper, W. W., & Ferguson, R. O. (1955). Optimal estimation of executive compensation by linear programming. Management Science, 1(2), 138-151.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วMacal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3), 151-162.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว