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) یک مدل شبیه‌سازی محاسباتی مبتنی بر شبکه است که اولین بار توسط جان فون نویمان و استانیسلاو اولام در دهه‌های ۱۹۴۰-۱۹۵۰ فرموله شد و توسط بازی زندگی جان کانوی (۱۹۷۰) و طبقه‌بندی سیستماتیک استفن وولفرام (۲۰۰۲) به شهرت رسید، که در آن شبکه‌ای از سلول‌ها — هر کدام دارای یک حالت گسسته محدود — در گام‌های زمانی گسسته بر اساس قوانین تعامل همسایگی محلی تکامل می‌یابد و باعث می‌شود الگوهای پیچیده جهانی از مشخصات محلی ساده پدیدار شوند.

شهود پشت روش

یک صفحه شطرنج را تصور کنید که در آن هر مربع می‌تواند زنده یا مرده باشد. در هر تیک ساعت، هر مربع به همسایگان فوری خود نگاه می‌کند و یک قانون ساده را اعمال می‌کند — مثلاً، یک سلول زنده اگر دو یا سه همسایه زنده داشته باشد زنده می‌ماند، و یک سلول مرده اگر دقیقاً سه همسایه زنده داشته باشد زنده می‌شود. از هیچ چیز بیشتر از این دفترچه قوانین کوچک که به طور همزمان در سراسر هر سلول اعمال می‌شود، شما الگوهای موج‌دار، ساختارهای پایدار و اشکال در حال حرکت را مشاهده می‌کنید که از ابتدا پدیدار می‌شوند. هیچ سلول واحدی از الگوی جهانی اطلاعی ندارد؛ پیچیدگی از تکرار صرف تعاملات محلی ناشی می‌شود. این بینش سلولار اتوماتا است: رفتار جهانی غنی، اغلب غیرقابل پیش‌بینی که از سادگی محلی ناشی می‌شود.

تاریخ

مفهوم سلولار اتوماتا توسط جان فون نویمان و استانیسلاو اولام در اواخر دهه ۱۹۴۰ و اوایل دهه ۱۹۵۰ به عنوان چارچوبی برای مطالعه خودتکثیری در سیستم‌های پیچیده معرفی شد. فون نویمان یک CA قادر به محاسبه جهانی و خودتکثیری طراحی کرد و پایه‌های نظری آن را بنا نهاد. این ایده توسط بازی زندگی جان کانوی، که در سال ۱۹۷۰ معرفی شد، به توجه عمومی و علمی رسید، که نشان داد چگونه رفتار فوق‌العاده پیچیده و شبیه به زندگی می‌تواند از سه قانون ساده اعمال شده بر روی یک شبکه باینری پدیدار شود. استفن وولفرام فضای CAهای یک بعدی را در طول دهه ۱۹۸۰ به طور سیستماتیک کاوش کرد و یافته‌های خود را در کتاب «نوع جدید علم» (۲۰۰۲) تدوین کرد و استدلال کرد که فرآیندهای محاسباتی شبیه CA اساس بسیاری از پیچیدگی‌های مشاهده شده در طبیعت را تشکیل می‌دهند. در علوم کاربردی، وایت و انگلن (۲۰۰۰) پیشگام استفاده از CA برای مدل‌سازی رشد شهری با وضوح بالا بودند و نشان دادند که چارچوب‌های SLEUTH و CA مرتبط می‌توانند الگوهای مشاهده شده گسترش فضایی شهری را بازتولید کنند. امروزه، مدل‌های CA ابزارهای استانداردی در جغرافیا شهری، شبیه‌سازی کاربری زمین، اپیدمیولوژی و بوم‌شناسی هستند.

چه زمانی استفاده شود

سلولار اتوماتا زمانی مناسب است که پدیده مورد علاقه یک فرآیند فضایی باشد که توسط تعاملات همسایگی محلی هدایت می‌شود — گسترش شهری، گسترش آتش، انتقال اپیدمی در یک شبکه، جریان ترافیک، یا جانشینی اکولوژیکی. این روش به حداقل اندازه نمونه تجربی نیاز ندارد؛ حالت‌ها و قوانین توسط مدل‌ساز تعریف می‌شوند و در صورت وجود می‌توانند با داده‌های مرجع کالیبره شوند. CA به ویژه برای متغیرهای دسته‌ای با مقادیر باینری یا حالت‌های کوچک در یک شبکه منظم مناسب است. این روش برای پدیده‌هایی که توسط بازخوردهای جهانی بدون ساختار فضایی محلی هدایت می‌شوند (سیستم دینامیک ارجح است)، برای رفتار ناهمگن عامل با تصمیم‌گیری فردی (مدل‌سازی مبتنی بر عامل ارجح است)، یا برای میدان‌های فضایی با مقادیر پیوسته (معادلات دیفرانسیل جزئی یا کرینگ ارجح است) مناسب نیست. به‌روزرسانی همزمان یا غیرهمزمان باید با دقت انتخاب شود زیرا انتخاب، دینامیک را تغییر می‌دهد.

محدودیت‌ها و ملاحظات

  • کالیبراسیون مجموعه قوانین برای تطابق با یک الگوی فضایی مشاهده شده چالش‌برانگیز است و ممکن است مجموعه‌های قوانین متعددی که خروجی یکسانی را تولید می‌کنند (هم‌نظری) به دست دهد.
  • CA استاندارد فرض می‌کند که توپولوژی شبکه منظم است؛ هندسه‌های فضایی نامنظم نیازمند افزونه‌هایی مانند سلولار اتوماتا نامنظم یا اتصال با لایه‌های GIS هستند.
  • به‌روزرسانی همزمان فرض می‌کند که همه سلول‌ها به طور همزمان عمل می‌کنند، که ممکن است فرآیندهای متوالی یا غیرهمزمان واقعی را منعکس نکند.
  • تعاملات دوربرد یا بازخوردهای جهانی به طور طبیعی توسط قوانین همسایگی محلی مدیریت نمی‌شوند؛ چنین دینامیک‌هایی نیازمند افزونه‌های مدل هستند.
  • نتایج به انتخاب توپولوژی همسایگی و شرایط مرزی حساس هستند، که هر دو باید مستند شوند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • الگوهای فضایی پیچیده و واقع‌گرایانه را از مجموعه کوچکی از قوانین محلی شفاف تولید می‌کند — کل سیستم قوانین را می‌توان در چند خط بیان کرد.
  • به حداقل اندازه نمونه تجربی نیاز ندارد؛ مدل‌ساز حالت‌ها و قوانین را مشخص می‌کند، که سپس می‌توانند با داده‌های فضایی مشاهده شده کالیبره شوند.
  • ناهمگنی فضایی و اثرات مرزی را به طور طبیعی بر روی یک شبکه منظم نشان می‌دهد.
  • از نظر محاسباتی در مقیاس‌های فضایی بزرگ کارآمد است زیرا به‌روزرسانی هر سلول فقط به همسایگی محلی آن بستگی دارد.
  • در طیف گسترده‌ای از دامنه‌های فضایی قابل اجرا است: رشد شهری، اکولوژی، اپیدمیولوژی، ترافیک و فرآیندهای انتشار فیزیکی.

کاربردها

  • مدل‌سازی رشد شهری: شبیه‌سازی گسترش فضایی شهرها و تغییر کاربری زمین با استفاده از چارچوب‌هایی مانند SLEUTH.
  • گسترش آتش‌سوزی جنگل: مدل‌سازی اشتعال و انتشار در سراسر شبکه‌ای از سلول‌های پوشش گیاهی تحت شرایط مختلف باد و رطوبت.
  • انتقال اپیدمی: ردیابی گسترش عفونت در یک شبکه فضایی که در آن تماس با نزدیکی جغرافیایی تعیین می‌شود.
  • جریان ترافیک: نمایش حرکت وسایل نقلیه در شبکه‌های جاده‌ای که در آن قوانین پیروی محلی باعث ایجاد و پراکندگی ترافیک می‌شود.
  • جانشینی اکولوژیکی: مدل‌سازی تغییر پوشش گیاهی، تهاجم گونه‌ها و تکه‌تکه شدن زیستگاه در مقیاس منظره.

چگونه کار می‌کند

چگونه کار می‌کند

1

فضای شبیه‌سازی یک شبکه منظم است — بیشتر اوقات یک شبکه مستطیلی دو بعدی، اما آرایه‌های یک بعدی و حجم‌های سه بعدی نیز استفاده می‌شوند. هندسه شبکه و شرایط مرزی آن (پوشش دوره‌ای، لبه‌های ثابت، یا مرزهای جذب‌کننده) باید قبل از نوشتن هرگونه قانون مشخص شوند، زیرا انتخاب مرز مستقیماً بر الگوهایی که می‌توانند پدیدار شوند تأثیر می‌گذارد.

2

هر سلول می‌تواند یکی از مجموعه‌ای محدود از حالت‌ها را اشغال کند — ساده‌ترین حالت، باینری (۰ یا ۱) است. یک توپولوژی همسایگی انتخاب می‌شود: همسایگی مور (۸ سلول اطراف در ۲D) و همسایگی فون نویمان (۴ سلول متعامد) دو پیکربندی استاندارد هستند. قانون انتقال، حالت بعدی یک سلول را به عنوان تابعی قطعی (یا احتمالی) از حالت فعلی آن و حالت همسایگانش تعریف می‌کند. کالیبراسیون مجموعه قوانین برای بازتولید یک الگوی فضایی مشاهده شده، دشوارترین مرحله مدل‌سازی است و نیازمند کاوش سیستماتیک است.

3

شبکه با یک پیکربندی اولیه از حالت‌های سلولی بذرپاشی می‌شود. این بذر می‌تواند یک الگوی سبک‌دار (یک سلول زنده منفرد، یک میدان تصادفی، یا یک آرایش هندسی خاص) باشد یا می‌تواند از داده‌های فضایی مشاهده شده مشتق شود — به عنوان مثال، یک نقشه کاربری زمین که برای کالیبراسیون یک CA رشد شهری استفاده می‌شود. پیکربندی اولیه به شدت بر رفتار گذرا اولیه تأثیر می‌گذارد، بنابراین انتخاب باید مستند شود و در صورت امکان، با داده‌های واقعی توجیه شود.

4

در هر گام زمانی گسسته، قانون انتقال به هر سلول در شبکه اعمال می‌شود — یا به صورت همزمان (همه سلول‌ها به طور همزمان به‌روز می‌شوند) یا به صورت غیرهمزمان (سلول‌ها به ترتیب مشخص یا تصادفی به‌روز می‌شوند). انتخاب بین به‌روزرسانی همزمان و غیرهمزمان می‌تواند به طور کیفی دینامیک را تغییر دهد، و هر دو گزینه در حوزه‌های کاربردی رایج هستند. مدل معمولاً برای گام‌های زمانی زیادی اجرا می‌شود تا رفتار گذرا از بین برود و الگوهای فضایی پایدار تثبیت شوند.

5

پیکربندی‌های فضایی در حال تکامل ثبت و تجزیه و تحلیل می‌شوند. معیارهای مورد علاقه شامل پیچیدگی الگو، خودهمبستگی فضایی، توزیع اندازه خوشه‌ها، و مقایسه الگوهای کاربری زمین شبیه‌سازی شده یا الگوهای انتشار با نقشه‌های مرجع مشاهده شده با استفاده از معیارهایی مانند شاخص شایستگی یا آماره کاپا است. تحلیل حساسیت بر روی پارامترهای قانون، مشخص می‌کند که کدام قوانین باعث ایجاد الگوهای کلیدی نوظهور می‌شوند.

دام‌های رایج

  • انتخاب شرایط مرزی بدون توجیه — مرزهای دوره‌ای، ثابت و جذب‌کننده هر کدام می‌توانند رفتار لبه‌ای متفاوتی تولید کنند؛ انتخاب باید با سیستم فیزیکی یا مفهومی که مدل‌سازی می‌شود مطابقت داشته باشد.
  • گزارش تنها یک اجرا از یک CA تصادفی — اگر قوانین انتقال احتمالی باشند، تکرارهای متعدد لازم است و نتایج باید به صورت توزیع گزارش شوند.
  • در نظر گرفتن یک مجموعه قوانین کالیبره شده به عنوان منحصر به فرد تأیید شده بدون بررسی مجموعه‌های قوانین جایگزین که الگوهای مشابهی تولید می‌کنند (هم‌نظری)؛ آزمون‌های حساسیت ساختاری در میان طیف وسیعی از پیکربندی‌های قانون معقول ضروری است.
  • اعمال به‌روزرسانی همزمان زمانی که فرآیند مدل‌سازی شده ذاتاً متوالی است — به عنوان مثال، جریان ترافیک یا زنجیره‌های تماس اپیدمی — بدون تأیید اینکه طرح به‌روزرسانی مصنوعاتی را معرفی نمی‌کند.
  • نادیده گرفتن دوره گرمایش گذرا زمانی که پیکربندی اولیه به جای داده‌محور، سبک‌دار است؛ رفتار مراحل اولیه ممکن است بذر را منعکس کند، نه دینامیک واقعی سیستم.

پرسش‌های متداول

سلولار اتوماتا چگونه با مدل مبتنی بر عامل متفاوت است؟

سلولار اتوماتا عامل‌ها (سلول‌ها) را در موقعیت‌های روی یک شبکه منظم ثابت می‌کند؛ حالت و قانون به‌روزرسانی هر سلول در سراسر شبکه یکنواخت است و تعامل کاملاً محلی است. مدل مبتنی بر عامل به عامل‌ها اجازه می‌دهد تا متحرک، ناهمگن باشند و از طریق توپولوژی‌های انعطاف‌پذیر تعامل کنند. از CA زمانی استفاده کنید که فرآیند فضایی ذاتاً شبکه‌ای است و خود سلول‌ها حرکت نمی‌کنند یا تصمیمات پیچیده‌ای نمی‌گیرند؛ از ABM زمانی استفاده کنید که ناهمگنی فردی، تحرک و تصمیم‌گیری در پدیده مرکزی هستند.

آیا باید از به‌روزرسانی همزمان یا غیرهمزمان استفاده کنم؟

به‌روزرسانی همزمان قانون انتقال را به طور همزمان در هر گام زمانی به همه سلول‌ها اعمال می‌کند و فرمول‌بندی کلاسیک CA است. به‌روزرسانی غیرهمزمان قوانین را یکی یکی، به ترتیب مشخص یا تصادفی اعمال می‌کند. این انتخاب می‌تواند دینامیک نوظهور را به طور کیفی تغییر دهد. به‌روزرسانی همزمان برای فرآیندهای انتشار فیزیکی (آتش، انتشار) استاندارد است؛ غیرهمزمان اغلب برای فرآیندهای بیولوژیکی یا اجتماعی که در آن عاملان به صورت متوالی عمل می‌کنند، واقع‌گرایانه‌تر است. انتخاب باید توجیه و مستند شود.

چگونه یک CA را به داده‌های واقعی مشاهده شده کالیبره کنم؟

کالیبراسیون معمولاً شامل تعریف یک معیار سنجش نیکویی برازش — مانند شاخص شایستگی یا آماره کاپا که نقشه‌های کاربری زمین شبیه‌سازی شده و مشاهده شده را مقایسه می‌کند — و سپس جستجو در فضای پارامتر قانون برای به حداقل رساندن اختلاف است. از آنجایی که چندین مجموعه قانون می‌توانند خروجی مشابهی تولید کنند (هم‌نظری)، کالیبراسیون باید با تحلیل حساسیت در طیف وسیعی از پیکربندی‌های قانون معقول همراه باشد، نه فقط بهینه‌سازی به یک نقطه بهترین برازش منفرد.

آیا اجرای CA به داده‌های تجربی نیاز دارد؟

حداقل نمونه تجربی لازم نیست. حالت‌ها و قوانین را می‌توان به صورت نظری مشخص کرد و مدل را به عنوان یک شبیه‌سازی خالص اجرا کرد. با این حال، اگر هدف مدل‌سازی یک فرآیند فضایی خاص واقعی — رشد شهری در یک شهر خاص، گسترش آتش در یک منظره خاص — باشد، آنگاه کالیبراسیون مجموعه قوانین و پیکربندی اولیه به داده‌های مرجع مشاهده شده، اعتبار و سودمندی پیش‌بینی مدل را به طور قابل توجهی افزایش می‌دهد.

روش‌های مرتبط

منابع

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

    شابک: 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
    کپی شد.