Skip to content
กลับไปยังผลการค้นหา

เซลลูลาร์ออโตมาตา — การเกิดจากกฎท้องถิ่นบนกริด

ผู้เสนอ
John von Neumann and Stanislaw Ulam (1940s–1950s); popularized by John Conway (1970) and Stephen Wolfram (1980s–2002)
ปี
1940s–1950s (formalized); 1970 (Conway's Game of Life); 2002 (Wolfram's systematic classification)
ประเภท
Grid-based computational simulation model

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

เซลลูลาร์ออโตมาตา (CA) เป็นแบบจำลองการจำลองด้วยคอมพิวเตอร์บนกริด ซึ่งถูกกำหนดรูปแบบขึ้นครั้งแรกโดย John von Neumann และ Stanislaw Ulam ในช่วงทศวรรษ 1940–1950 และได้รับความสนใจอย่างกว้างขวางจาก Game of Life ของ John Conway (1970) และการจำแนกประเภทอย่างเป็นระบบของ Stephen Wolfram (2002) โดยที่โครงข่ายของเซลล์ — ซึ่งแต่ละเซลล์มีสถานะไม่ต่อเนื่องแบบจำกัด — จะวิวัฒนาการไปตามช่วงเวลาที่ไม่ต่อเนื่องตามกฎการปฏิสัมพันธ์ของเพื่อนบ้านท้องถิ่น ทำให้เกิดรูปแบบทั่วโลกที่ซับซ้อนจากการระบุคุณสมบัติเฉพาะของท้องถิ่นที่เรียบง่าย

แนวคิดเบื้องหลังวิธีการ

ลองนึกภาพกระดานหมากรุกที่แต่ละช่องสามารถมีชีวิตอยู่หรือตายได้ ในทุกๆ การคลิกของนาฬิกา แต่ละช่องจะมองเพื่อนบ้านที่อยู่ติดกันและใช้กฎง่ายๆ — เช่น เซลล์ที่มีชีวิตจะอยู่รอดหากมีเพื่อนบ้านที่มีชีวิตสองหรือสามเซลล์ และเซลล์ที่ตายจะกลายเป็นเซลล์ที่มีชีวิตหากมีเพื่อนบ้านสามเซลล์ จากกฎเล็กๆ น้อยๆ เหล่านี้ที่นำไปใช้กับทุกเซลล์พร้อมกัน คุณจะเห็นรูปแบบที่แผ่กระจาย โครงสร้างที่เสถียร และรูปร่างที่เคลื่อนที่ปรากฏขึ้นจากศูนย์ ไม่มีเซลล์ใดเซลล์หนึ่งที่รู้เกี่ยวกับรูปแบบทั่วโลก ความซับซ้อนเกิดขึ้นจากการทำซ้ำของการปฏิสัมพันธ์ในท้องถิ่น นี่คือแนวคิดของเซลลูลาร์ออโตมาตา: พฤติกรรมทั่วโลกที่หลากหลายและมักจะคาดเดาไม่ได้ซึ่งเกิดขึ้นจากความเรียบง่ายในท้องถิ่น

ประวัติศาสตร์

แนวคิดของเซลลูลาร์ออโตมาตาถูกนำเสนอโดย John von Neumann และ Stanislaw Ulam ในช่วงปลายทศวรรษ 1940 และต้นทศวรรษ 1950 ในฐานะกรอบการทำงานสำหรับการศึกษาการสืบพันธุ์ตนเองในระบบที่ซับซ้อน Von Neumann ได้ออกแบบ CA ที่มีความสามารถในการคำนวณสากลและการสืบพันธุ์ตนเอง ซึ่งเป็นการวางรากฐานทางทฤษฎี แนวคิดนี้ได้รับความสนใจในวงกว้างทั้งในระดับสาธารณะและวิทยาศาสตร์จาก Game of Life ของ John Conway ซึ่งเปิดตัวในปี 1970 ซึ่งแสดงให้เห็นว่าพฤติกรรมที่ซับซ้อนและเหมือนสิ่งมีชีวิตอย่างยิ่งสามารถเกิดขึ้นได้จากกฎง่ายๆ สามข้อที่นำไปใช้กับกริดทวิภาค Stephen Wolfram ได้สำรวจพื้นที่ของ CA หนึ่งมิติอย่างเป็นระบบตลอดทศวรรษ 1980 และได้รวบรวมผลการค้นพบของเขาใน A New Kind of Science (2002) โดยโต้แย้งว่ากระบวนการคำนวณที่คล้าย CA เป็นพื้นฐานของความซับซ้อนส่วนใหญ่ที่สังเกตได้ในธรรมชาติ ในวิทยาศาสตร์ประยุกต์ White และ Engelen (2000) เป็นผู้บุกเบิกการใช้ CA สำหรับการสร้างแบบจำลองการเติบโตของเมืองที่มีความละเอียดสูง โดยแสดงให้เห็นว่า SLEUTH และกรอบการทำงาน CA ที่เกี่ยวข้องสามารถสร้างรูปแบบการขยายตัวเชิงพื้นที่ของเมืองที่สังเกตได้ ปัจจุบันแบบจำลอง CA เป็นเครื่องมือมาตรฐานในภูมิศาสตร์เมือง การจำลองการใช้ที่ดิน ระบาดวิทยา และนิเวศวิทยา

ควรใช้เมื่อใด

เซลลูลาร์ออโตมาตาเหมาะสมเมื่อปรากฏการณ์ที่สนใจเป็นกระบวนการเชิงพื้นที่ที่ขับเคลื่อนโดยการปฏิสัมพันธ์ของเพื่อนบ้านท้องถิ่น — การขยายตัวของเมือง, การแพร่กระจายของไฟ, การแพร่ระบาดของโรคบนกริด, การไหลของการจราจร, หรือการสืบทอดทางนิเวศวิทยา วิธีนี้ไม่ต้องการขนาดตัวอย่างเชิงประจักษ์ขั้นต่ำ; สถานะและกฎถูกกำหนดโดยผู้ออกแบบโมเดลและสามารถปรับเทียบกับข้อมูลอ้างอิงได้หากมี CA เหมาะอย่างยิ่งสำหรับตัวแปรหมวดหมู่ที่มีค่าเป็นทวิภาคหรือมีสถานะน้อยบนโครงข่ายปกติ ไม่เหมาะสมสำหรับปรากฏการณ์ที่ถูกควบคุมโดยการป้อนกลับทั่วโลกโดยไม่มีโครงสร้างเชิงพื้นที่ในท้องถิ่น (ควรใช้ system dynamics), สำหรับพฤติกรรมของเอเจนต์ที่หลากหลายพร้อมการตัดสินใจของแต่ละบุคคล (ควรใช้ agent-based modeling), หรือสำหรับสนามเชิงพื้นที่ที่มีค่าต่อเนื่อง (ควรใช้ partial differential equations หรือ kriging) การอัปเดตแบบพร้อมกันหรือแบบไม่พร้อมกันจะต้องถูกเลือกอย่างจงใจเนื่องจากทางเลือกนี้เปลี่ยนแปลงพลวัต

ข้อจำกัดและข้อควรพิจารณา

  • การปรับเทียบชุดกฎให้ตรงกับรูปแบบเชิงพื้นที่ที่สังเกตได้นั้นเป็นเรื่องท้าทายและอาจให้ชุดกฎหลายชุดที่สร้างผลลัพธ์เดียวกัน (equifinality)
  • CA มาตรฐานสมมติว่าโทโพโลยีกริดเป็นแบบปกติ รูปทรงเรขาคณิตเชิงพื้นที่ที่ไม่ปกติต้องการส่วนขยาย เช่น irregular cellular automata หรือการเชื่อมต่อกับชั้น GIS
  • การอัปเดตแบบพร้อมกันสมมติว่าเซลล์ทั้งหมดทำงานพร้อมกัน ซึ่งอาจไม่สะท้อนกระบวนการตามลำดับหรือแบบไม่พร้อมกันในโลกแห่งความเป็นจริง
  • การปฏิสัมพันธ์ระยะไกลหรือการป้อนกลับทั่วโลกไม่สามารถจัดการได้โดยธรรมชาติด้วยกฎเพื่อนบ้านท้องถิ่น พลวัตดังกล่าวต้องการส่วนขยายของโมเดล
  • ผลลัพธ์มีความไวต่อการเลือกโทโพโลยีเพื่อนบ้านและเงื่อนไขขอบเขต ซึ่งทั้งสองอย่างจะต้องได้รับการบันทึก

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • สร้างรูปแบบเชิงพื้นที่ที่ซับซ้อนและดูสมจริงจากชุดกฎท้องถิ่นที่เล็กและโปร่งใส — ระบบกฎทั้งหมดสามารถระบุได้ในไม่กี่บรรทัด
  • ไม่ต้องการขนาดตัวอย่างเชิงประจักษ์ขั้นต่ำ; ผู้ออกแบบโมเดลระบุสถานะและกฎ ซึ่งสามารถปรับเทียบกับข้อมูลอ้างอิงเชิงพื้นที่ที่สังเกตได้
  • แสดงความไม่สม่ำเสมอเชิงพื้นที่และผลกระทบของขอบเขตบนกริดปกติได้อย่างเป็นธรรมชาติ
  • มีประสิทธิภาพในการคำนวณในสเกลเชิงพื้นที่ขนาดใหญ่ เนื่องจากอัปเดตของแต่ละเซลล์ขึ้นอยู่กับเพื่อนบ้านท้องถิ่นเท่านั้น
  • สามารถนำไปใช้ได้ในโดเมนเชิงพื้นที่ที่หลากหลาย: การเติบโตของเมือง, นิเวศวิทยา, ระบาดวิทยา, การจราจร, และกระบวนการแพร่กระจายทางกายภาพ

การประยุกต์ใช้

  • การสร้างแบบจำลองการเติบโตของเมือง: การจำลองการขยายตัวเชิงพื้นที่ของเมืองและการเปลี่ยนแปลงการใช้ที่ดินโดยใช้กรอบการทำงานเช่น SLEUTH
  • การแพร่กระจายของไฟป่า: การสร้างแบบจำลองการจุดและการแพร่กระจายทั่วกริดของเซลล์พืชภายใต้สภาวะลมและความชื้นที่แตกต่างกัน
  • การแพร่ระบาดของโรค: การติดตามการแพร่กระจายของการติดเชื้อบนกริดเชิงพื้นที่ซึ่งการสัมผัสถูกกำหนดโดยความใกล้ชิดทางภูมิศาสตร์
  • การไหลของการจราจร: การแสดงการเคลื่อนที่ของยานพาหนะบนกริดถนนซึ่งกฎการติดตามในท้องถิ่นทำให้เกิดการก่อตัวและการสลายตัวของรถติด
  • การสืบทอดทางนิเวศวิทยา: การสร้างแบบจำลองการเปลี่ยนแปลงพืชพรรณ การรุกรานของชนิดพันธุ์ และการแตกกระจายของถิ่นที่อยู่ในระดับภูมิทัศน์

วิธีการทำงาน

วิธีการทำงาน

1

พื้นที่จำลองเป็นโครงข่ายปกติ — ส่วนใหญ่มักเป็นกริดสี่เหลี่ยมสองมิติ แต่ก็มีการใช้อาร์เรย์หนึ่งมิติและปริมาตรสามมิติด้วย รูปทรงเรขาคณิตของกริดและเงื่อนไขขอบเขต (การพันรอบแบบคาบ, ขอบคงที่, หรือขอบที่ดูดซับ) จะต้องถูกระบุไว้ก่อนที่จะเขียนกฎใดๆ เนื่องจากทางเลือกของขอบเขตส่งผลโดยตรงต่อรูปแบบที่สามารถเกิดขึ้นได้

2

แต่ละเซลล์สามารถอยู่ในสถานะใดสถานะหนึ่งจากชุดสถานะที่จำกัด — กรณีที่ง่ายที่สุดคือสถานะทวิภาค (0 หรือ 1) จะมีการเลือกโทโพโลยีเพื่อนบ้าน: เพื่อนบ้านแบบ Moore (เซลล์รอบข้าง 8 เซลล์ใน 2 มิติ) และเพื่อนบ้านแบบ von Neumann (เซลล์ตั้งฉาก 4 เซลล์) เป็นสองรูปแบบมาตรฐาน กฎการเปลี่ยนสถานะจะกำหนดสถานะถัดไปของเซลล์ให้เป็นฟังก์ชันที่แน่นอน (หรือเป็นไปได้) ของสถานะปัจจุบันและสถานะของเพื่อนบ้าน การปรับเทียบชุดกฎเพื่อสร้างรูปแบบเชิงพื้นที่ที่สังเกตได้ใหม่เป็นขั้นตอนการสร้างแบบจำลองที่ยากที่สุดและต้องมีการสำรวจอย่างเป็นระบบ

3

กริดจะถูกเริ่มต้นด้วยการกำหนดค่าเริ่มต้นของสถานะเซลล์ เมล็ดพันธุ์นี้อาจเป็นรูปแบบที่ออกแบบมา (เซลล์ที่มีชีวิตเพียงเซลล์เดียว, สนามสุ่ม, หรือการจัดเรียงทางเรขาคณิตเฉพาะ) หรืออาจได้มาจากข้อมูลเชิงพื้นที่ที่สังเกตได้ — ตัวอย่างเช่น แผนที่การใช้ที่ดินที่ใช้ในการปรับเทียบ CA การเติบโตของเมือง การกำหนดค่าเริ่มต้นส่งผลอย่างมากต่อพฤติกรรมชั่วคราวในช่วงต้น ดังนั้นทางเลือกจะต้องได้รับการบันทึกและหากเป็นไปได้ ให้มีเหตุผลจากข้อมูลจริง

4

ในแต่ละช่วงเวลาที่ไม่ต่อเนื่อง กฎการเปลี่ยนสถานะจะถูกนำไปใช้กับทุกเซลล์ในกริด — ไม่ว่าจะพร้อมกัน (เซลล์ทั้งหมดอัปเดตพร้อมกัน) หรือไม่พร้อมกัน (เซลล์อัปเดตตามลำดับที่กำหนดหรือสุ่ม) ทางเลือกระหว่างการอัปเดตแบบพร้อมกันและไม่พร้อมกันสามารถเปลี่ยนแปลงพลวัตได้อย่างมีคุณภาพ และทั้งสองตัวเลือกมีการใช้งานทั่วไปในโดเมนแอปพลิเคชัน แบบจำลองมักจะทำงานเป็นเวลาหลายช่วงเวลาเพื่อให้พฤติกรรมชั่วคราวสลายไปและรูปแบบเชิงพื้นที่ที่คงที่เสถียร

5

การกำหนดค่าเชิงพื้นที่ที่กำลังวิวัฒนาการจะถูกบันทึกและวิเคราะห์ ตัวชี้วัดที่น่าสนใจ ได้แก่ ความซับซ้อนของรูปแบบ, ความสัมพันธ์เชิงพื้นที่, การกระจายขนาดของกลุ่ม, และการเปรียบเทียบรูปแบบการใช้ที่ดินหรือการแพร่กระจายที่จำลองได้กับแผนที่อ้างอิงที่สังเกตได้ โดยใช้มาตรวัด เช่น figure-of-merit หรือสถิติคัปปา การวิเคราะห์ความไวต่อพารามิเตอร์กฎจะบันทึกว่ากฎใดขับเคลื่อนรูปแบบที่เกิดขึ้นหลัก

ข้อผิดพลาดที่พบบ่อย

  • การเลือกเงื่อนไขขอบเขตโดยไม่มีเหตุผล — ขอบเขตแบบคาบ, ขอบเขตคงที่, และขอบเขตที่ดูดซับแต่ละแบบสามารถสร้างพฤติกรรมขอบที่แตกต่างกันอย่างมีคุณภาพ; ทางเลือกจะต้องตรงกับระบบทางกายภาพหรือแนวคิดที่กำลังสร้างแบบจำลอง
  • การรายงานการทำงานเพียงครั้งเดียวจาก CA แบบสุ่ม — หากกฎการเปลี่ยนสถานะเป็นแบบสุ่ม จำเป็นต้องมีการจำลองซ้ำหลายครั้งและต้องรายงานผลลัพธ์เป็นค่าการกระจาย
  • การปฏิบัติต่อชุดกฎที่ปรับเทียบแล้วเสมือนว่าได้รับการตรวจสอบแล้วโดยไม่มีการตรวจสอบชุดกฎทางเลือกที่สร้างรูปแบบที่คล้ายกัน (equifinality); การทดสอบความไวเชิงโครงสร้างตลอดการเปลี่ยนแปลงกฎที่เป็นไปได้เป็นสิ่งจำเป็น
  • การใช้การอัปเดตแบบพร้อมกันเมื่อกระบวนการที่สร้างแบบจำลองเป็นแบบลำดับโดยธรรมชาติ — ตัวอย่างเช่น การไหลของการจราจรหรือห่วงโซ่การติดต่อของการแพร่ระบาด — โดยไม่ตรวจสอบว่ารูปแบบการอัปเดตไม่ได้สร้างสิ่งประดิษฐ์
  • การละเลยช่วงเวลาอุ่นเครื่องชั่วคราวเมื่อการกำหนดค่าเริ่มต้นถูกออกแบบมาแทนที่จะขับเคลื่อนด้วยข้อมูล; พฤติกรรมในช่วงต้นอาจสะท้อนถึงเมล็ดพันธุ์ ไม่ใช่พลวัตที่แท้จริงของระบบ

คำถามที่พบบ่อย

เซลลูลาร์ออโตมาตาแตกต่างจาก agent-based model อย่างไร?

เซลลูลาร์ออโตมาตาจะตรึงเอเจนต์ (เซลล์) ไว้กับตำแหน่งบนกริดปกติ; สถานะและกฎการอัปเดตของแต่ละเซลล์จะเหมือนกันทั่วทั้งกริด และการปฏิสัมพันธ์จะจำกัดอยู่แค่ในท้องถิ่นเท่านั้น Agent-based model อนุญาตให้เอเจนต์เคลื่อนที่ได้ มีความหลากหลาย และโต้ตอบกันผ่านโทโพโลยีที่ยืดหยุ่น ใช้ CA เมื่อกระบวนการเชิงพื้นที่มีลักษณะเป็นกริดโดยธรรมชาติและเซลล์เองไม่ได้เคลื่อนที่หรือทำการตัดสินใจที่ซับซ้อน ใช้ ABM เมื่อความหลากหลายของแต่ละบุคคล การเคลื่อนที่ และการตัดสินใจเป็นหัวใจสำคัญของปรากฏการณ์

ฉันควรใช้การอัปเดตแบบพร้อมกันหรือแบบไม่พร้อมกัน?

การอัปเดตแบบพร้อมกันนำกฎการเปลี่ยนสถานะไปใช้กับเซลล์ทั้งหมดพร้อมกันในแต่ละช่วงเวลา และเป็นรูปแบบ CA แบบดั้งเดิม การอัปเดตแบบไม่พร้อมกันนำกฎไปใช้ทีละเซลล์ ตามลำดับที่กำหนดหรือสุ่ม ทางเลือกนี้สามารถเปลี่ยนแปลงพลวัตที่เกิดขึ้นได้อย่างมีคุณภาพ การอัปเดตแบบพร้อมกันเป็นมาตรฐานสำหรับกระบวนการแพร่กระจายทางกายภาพ (ไฟ, การแพร่กระจาย); แบบไม่พร้อมกันมักจะสมจริงกว่าสำหรับกระบวนการทางชีววิทยาหรือสังคมที่เอเจนต์ดำเนินการตามลำดับ ทางเลือกนี้จะต้องมีเหตุผลและบันทึกไว้

ฉันจะปรับเทียบ CA กับข้อมูลจริงที่สังเกตได้อย่างไร?

การปรับเทียบโดยทั่วไปเกี่ยวข้องกับการกำหนดเมตริกวัดความเหมาะสม — เช่น figure-of-merit หรือสถิติคัปปาที่เปรียบเทียบแผนที่การใช้ที่ดินที่จำลองได้กับแผนที่ที่สังเกตได้ — จากนั้นจึงค้นหาปริภูมิพารามิเตอร์ของกฎเพื่อลดความคลาดเคลื่อน เนื่องจากชุดกฎหลายชุดสามารถสร้างผลลัพธ์ที่คล้ายคลึงกันได้ (equifinality) การปรับเทียบควรมาพร้อมกับการวิเคราะห์ความไวต่อการกำหนดค่ากฎที่เป็นไปได้หลากหลาย ไม่ใช่แค่การหาค่าที่เหมาะสมที่สุดเพียงจุดเดียว

CA ต้องการข้อมูลเชิงประจักษ์เพื่อทำงานหรือไม่?

ไม่จำเป็นต้องมีขนาดตัวอย่างเชิงประจักษ์ขั้นต่ำ สถานะและกฎสามารถกำหนดได้ตามทฤษฎีและแบบจำลองสามารถทำงานเป็นการจำลองบริสุทธิ์ อย่างไรก็ตาม หากเป้าหมายคือการสร้างแบบจำลองกระบวนการเชิงพื้นที่ในโลกแห่งความเป็นจริง — การเติบโตของเมืองในเมืองใดเมืองหนึ่ง การแพร่กระจายของไฟในภูมิทัศน์ใดภูมิทัศน์หนึ่ง — การปรับเทียบชุดกฎและการกำหนดค่าเริ่มต้นกับข้อมูลอ้างอิงที่สังเกตได้จะช่วยเพิ่มความน่าเชื่อถือและประโยชน์ในการทำนายของแบบจำลองได้อย่างมาก

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Wolfram, S. (2002). A New Kind of Science. Wolfram Media.

    ISBN: 978-1579550080
    คัดลอกแล้ว
  2. White, R. & Engelen, G. (2000). High-Resolution Integrated Modelling of the Spatial Dynamics of Urban and Regional Systems. Computers, Environment and Urban Systems, 24(5), 383–400.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว