ออโตมาตาเซลลูลาร์แบบอะซิงโครนัส
ออโตมาตาเซลลูลาร์เช่นเดียวกับ แบบจำลอง ระบบหลายเอเจนต์ อื่นๆ มักจะถือว่าเวลาเป็นแบบไม่ต่อเนื่องและ การอัปเดต สถานะเกิดขึ้นพร้อมกัน สถานะของทุกเซลล์ในแบบจำลองจะได้รับการอัปเดตพร้อมกัน ก่อนที่สถานะใหม่ใดๆ จะส่งผลต่อเซลล์อื่นๆ ในทางตรงกันข้ามออโตมาตาเซลลูลาร์ แบบอะซิงโค รนัสสามารถอัปเดตแต่ละเซลล์ได้อย่างอิสระ ในลักษณะที่สถานะใหม่ของเซลล์หนึ่งส่งผลต่อการคำนวณสถานะในเซลล์ข้างเคียง
การนำการอัปเดตแบบซิงโครนัสไปใช้สามารถวิเคราะห์ได้เป็นสองขั้นตอน ขั้นตอนแรกคือการโต้ตอบ ซึ่งจะคำนวณสถานะใหม่ของแต่ละเซลล์โดยอิงจากเซลล์ข้างเคียงและกฎการอัปเดต ค่าสถานะจะถูกเก็บไว้ในที่เก็บข้อมูลชั่วคราว ขั้นตอนที่สองคือการอัปเดตค่าสถานะโดยการคัดลอกสถานะใหม่ไปยังเซลล์ต่างๆ
ในทางตรงกันข้าม การอัปเดตแบบอะซิงโครนัสไม่จำเป็นต้องแยกสองขั้นตอนดังกล่าวออกจากกัน: ในกรณีที่ง่ายที่สุด (การอัปเดตแบบอะซิงโครนัสโดยสมบูรณ์) การเปลี่ยนแปลงสถานะจะถูกนำไปใช้ทันที
วิธีการแบบซิงโครนัสตั้งอยู่บนสมมติฐานว่ามีนาฬิกา สากล เพื่อให้แน่ใจว่าเซลล์ทั้งหมดได้รับการอัปเดตพร้อมกัน แม้ว่าจะเป็นวิธีสะดวกในการเตรียมระบบคอมพิวเตอร์แต่สมมติฐานนี้อาจไม่สมจริงหากแบบจำลองนั้นมีจุดประสงค์เพื่อแสดงถึงระบบสิ่งมีชีวิต เป็นต้น ซึ่งไม่มีหลักฐานการมีอยู่ของอุปกรณ์ดังกล่าว
วิธีการทั่วไปที่ถูกค้นพบซ้ำแล้วซ้ำเล่าโดยอิสระ (โดย K. Nakamura ในทศวรรษ 1970 โดย T. Toffoli ในทศวรรษ 1980 และโดย CL Nehaniv ในปี 1998) ช่วยให้สามารถจำลองพฤติกรรมของออโตมาตาเซลลูลาร์แบบซิงโครนัสได้อย่างแม่นยำผ่านออโตมาตาเซลลูลาร์แบบอะซิงโครนัสที่สร้างขึ้นจากการดัดแปลงอย่างง่ายของออโตมาตาเซลลูลาร์แบบซิงโครนัส (Nehaniv 2002) อย่างไรก็ตาม ความถูกต้องของวิธีการนี้เพิ่งได้รับการพิสูจน์อย่างเข้มงวดเมื่อไม่นานมานี้ (Nehaniv, 2004) ด้วยเหตุนี้ จึงสรุปได้ทันทีจากผลลัพธ์เกี่ยวกับออโตมาตาเซลลูลาร์แบบซิงโครนัสว่า ออโตมาตาเซลลูลาร์แบบอะซิงโครนัสสามารถจำลองได้ เช่นเกมชีวิตของ คอนเวย์ การคำนวณแบบสากลและการจำลองตัวเอง (เช่น ในตัวสร้างสากลของฟอน นอยมันน์ ) ยิ่งไปกว่านั้น โครงสร้างทั่วไปและการพิสูจน์ยังสามารถนำไปใช้กับเครือข่ายออโตมาตาแบบซิงโครนัสในกลุ่มที่กว้างกว่า (เครือข่ายออโตมาตาที่ไม่เป็นเนื้อเดียวกันบนกราฟแบบมีทิศทาง ซึ่งอนุญาตให้มีอินพุตภายนอก –ซึ่งรวมถึงออโตมาตาเซลลูลาร์เป็นกรณีพิเศษ) โดยแสดงให้เห็นอย่างสร้างสรรค์ว่าพฤติกรรมของเครือข่ายเหล่านี้สามารถเกิดขึ้นได้แบบอะซิงโครนัสโดยเครือข่ายออโตมาตาแบบอะซิงโครนัสที่สอดคล้องกัน
อัปเดตแผนงาน
งานวิจัยหลายชิ้นได้นำแบบจำลองแบบอะซิงโครนัสมาใช้และพบว่าพฤติกรรมของแบบจำลองเหล่านั้นแตกต่างจากแบบจำลองแบบซิงโครนัส Bersini และ Detours (1994) ได้แสดงให้เห็น ว่า เกมชีวิตของคอนเวย์ มีความไว ต่อรูปแบบการอัปเดตมากเพียงใด พฤติกรรมที่น่าสนใจใดๆ ก็หายไปในกรณีอะซิงโครนัส Harvey และ Bossomaier (1997) ชี้ให้เห็นว่าการอัปเดตแบบสุ่มในเครือข่ายบูลีนแบบสุ่มส่งผลให้เกิดการแสดงออกของจุดดึงดูดเท่านั้น ไม่มีพฤติกรรมแบบวงจรที่ทำซ้ำได้ แม้ว่าพวกเขาจะแนะนำแนวคิดของจุดดึงดูดแบบวงจรที่ไม่แน่นหนา Kanada (1994) ได้แสดงให้เห็นว่าแบบจำลอง CA แบบหนึ่งมิติบางแบบที่สร้างรูปแบบที่ไม่วุ่นวายเมื่ออัปเดตแบบซิงโครนัสจะสร้างรูปแบบขอบแห่งความวุ่นวายเมื่อสุ่ม Orponen (1997) ได้แสดงให้เห็นว่าเครือข่ายของหน่วยตรรกะเกณฑ์ที่อัปเดตแบบซิงโครนัสใดๆ (ดูเซลล์ประสาทเทียม ) สามารถจำลองได้โดยเครือข่ายที่ไม่มีข้อจำกัดเกี่ยวกับลำดับของการอัปเดต Sipper และคณะ (1997) ได้ตรวจสอบวิวัฒนาการของ CA ที่ไม่สม่ำเสมอซึ่งทำงานคำนวณเฉพาะอย่าง แบบจำลองเหล่านี้ผ่อนคลายข้อกำหนดปกติที่ว่าโหนดทั้งหมดต้องมีกฎการอัปเดตเดียวกัน ในแบบจำลองของพวกเขา โหนดต่างๆ ถูกจัดระเบียบเป็นบล็อก โหนดภายในบล็อกจะได้รับการอัปเดตแบบซิงโครนัส แต่บล็อกจะได้รับการอัปเดตแบบอะซิงโครนัส พวกเขาได้ทดลองกับแผนการสามแบบ: (1) ในแต่ละขั้นตอนเวลา บล็อกจะถูกเลือกแบบสุ่มโดยมีการแทนที่ (2) ในแต่ละขั้นตอนเวลา บล็อกจะถูกเลือกแบบสุ่มโดยไม่มีการแทนที่ (3) ในแต่ละขั้นตอนเวลา บล็อกจะถูกเลือกตามลำดับการอัปเดตที่กำหนดไว้
การอัปเดตแบบอะซิงโครนัสมีหลายประเภท และผู้เขียนหลายท่านได้อธิบายไว้ในรูปแบบที่แตกต่างกัน แผนผังที่แสดงในภาพด้านล่างมีดังนี้ (Cornforth et al. 2005):
- รูปแบบการทำงานแบบซิงโครนัส - เซลล์ทั้งหมดจะได้รับการอัปเดตพร้อมกันในแต่ละช่วงเวลา นี่คือแบบจำลองแบบดั้งเดิมที่กล่าวถึงไว้ที่นี่เพื่อใช้ในการเปรียบเทียบ
- วิธีการสุ่มแบบอิสระ - ในแต่ละช่วงเวลา จะเลือกเซลล์หนึ่งเซลล์แบบสุ่มโดยมีการแทนที่ และทำการอัปเดต
- รูปแบบการเรียงลำดับแบบสุ่ม - ในแต่ละช่วงเวลา โหนดทั้งหมดจะได้รับการอัปเดต แต่ในลำดับแบบสุ่ม
- รูปแบบวัฏจักร - ในแต่ละช่วงเวลา จะมีการเลือกโหนดตามลำดับการอัปเดตที่กำหนดไว้ ซึ่งถูกกำหนดแบบสุ่มในระหว่างการเริ่มต้นโมเดล
- ระบบ การ ทำงานแบบตั้งเวลาเอง – แต่ละเซลล์มีตัวจับเวลาอิสระ ซึ่งเริ่มต้นด้วยช่วงเวลาและเฟสแบบสุ่ม เมื่อหมดช่วงเวลาแล้ว เซลล์จะได้รับการอัปเดตและตัวจับเวลาจะถูกรีเซ็ต การอัปเดตเป็นไปโดยอัตโนมัติและดำเนินไปในอัตราที่แตกต่างกันสำหรับแต่ละเซลล์
- ระบบการซิงค์ด้วยตนเอง - เหมือนกับระบบที่ใช้สัญญาณนาฬิกา แต่เฟสของตัวจับเวลาจะได้รับผลกระทบจากการเชื่อมต่อในพื้นที่กับอุปกรณ์ข้างเคียง จึงสามารถบรรลุการซิงค์ในพื้นที่ได้
แผนภาพสถานะเวลาด้านล่างแสดงความแตกต่างที่เกิดจากการเปลี่ยนรูปแบบการอัปเดตของแบบจำลองออโตมาตาเซลลูลาร์โดยไม่เปลี่ยนแปลงพารามิเตอร์อื่นใด กฎที่ใช้คือกฎ 30ซึ่งเหมือนกันสำหรับทุกแผนภาพ
| กฎข้อที่ 30 เดิม | กฎข้อที่ 30 ได้รับการอัปเดตแบบสุ่ม |
| กฎข้อที่ 30 ได้รับการอัปเดตในลำดับแบบสุ่ม | กฎข้อที่ 30 ได้รับการปรับปรุงตามลำดับแบบวนรอบ |
| กฎการตั้งเวลาอัตโนมัติข้อที่ 30 | กฎการซิงโครไนซ์อัตโนมัติข้อ 30 |
ผลกระทบ
บ่อยครั้งที่แบบจำลองอย่างเช่น ออโตมาตาเซลลูลาร์ ถูกนำมาใช้เพื่อช่วยให้เข้าใจกระบวนการที่เกิดขึ้นในชีวิตจริง การสร้างแบบจำลองที่เรียบง่ายช่วยให้ได้ข้อมูลเชิงลึกใหม่ๆ คำถามที่มักเกิดขึ้นเสมอคือ แบบจำลองเหล่านี้ควรเรียบง่ายแค่ไหนจึงจะสามารถอธิบายสิ่งที่กำลังจำลองได้อย่างเพียงพอ การใช้แบบจำลองแบบอะซิงโครนัสสามารถเพิ่มความสมจริงให้กับแบบจำลองได้อีกระดับ แผนการทั้งหมดที่กล่าวมาข้างต้นมีบทบาทในชีวิตจริง แผนการแบบสุ่มอิสระอาจเหมาะสมสำหรับการจำลองเครือข่ายสังคมหรือการสื่อสารในเครือข่ายคอมพิวเตอร์แผนการแบบมีจังหวะอาจเหมาะสมสำหรับการจำลองอาณานิคมของแมลงในขณะที่แผนการแบบซิงโครนัสด้วยตนเองอาจนำไปใช้กับเนื้อเยื่อประสาทได้





