پروژه سوم: اتوماتای سلولی

[sarevan 9753]

سیستم‌های دینامیکی گسسته‌ای هستند که رفتارشان کاملا بر اساس ارتباط محلی استوار است.

در اتوماتای سلولی فضا بصورت یک شبکه تعریف می‌گردد که به هر خانه آن یک سلول گفته می‌شود.

سلول‌ها می‌توانند تنها یک حالت از مجموعه‌ای از حالات متناهی را دارا باشند.

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

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

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

در اتوماتای سلولی همگام (Synchronous Cellular Automata) عمل بروز درآوردن سلولها به صورت همگام و در اتوماتای سلولی ناهمگام (Asynchronous Cellular Automata) عمل بروز درآوردن سلولها به بصورت ناهمگام انجام میگیرد.

[sarevan 9753]

آتوماتاي سلولي در واقع يك مدل گسسته رياضي است كه در زمينه هاي مختلفي همچون تئوري محاسبات، رياضيات، فيزيك و ... كاربرد دارد.

آتوماتاي سلولي در اواخر دهه 1940 توسط John von Neumann مطرح و پس از او توسط رياضيداني بنام Ulam به عنوان مدلي براي بررسي رفتار سيستم‌هاي پيچيده پيشنهاد شد.

نامهاي ديگر آتوماتاي سلولي عبارتند از:

-cellular structures

-homogeneous structures

- tessellation structure

- iterative arrays

[sarevan 9753]

—چرا ca؟

 

• شبيه سازي سيستم هاي پيچيده نيازمند معادلات پيچيده مي باشد.
  
• —
  
  
• —ارائه معادلات پيچيده نيازمند شناخت قوانين و وجود دانش کامل در مورد سيستم مورد بررسي است.
  
  
• —از معادلات پيچيده براي توصيف يک سيستم پيچيده استفاده نکنيد و بجاي آن اجازه دهيد اين پيچيدگي در قالب تعامل بين قوانين ساده بررسي گردد.
  
  
• —
  
  

 

• —ايده : استفاده از تعاملات ساده بين سلولها در آتوماتاي سلولي براي شبيه سازي سيستمهاي پيچيده
  

 

مفاهيم اساسي در يك آتوماتاي سلولي

• —سلول
  
  
• —حالت
  
  
• —شبكه
  
• —تغيير و تحول (گسسته از لحاظ زماني)
  
• —همسايگي
  
• —قوانين تغيير حالت
  
• —وضعيت اوليه
  
  

 

[sarevan 9753]

قوانين تغيير حالت:

 

در آتوماتاي سلولي زمان گسسته است و در هر مرحله هر سلول، وضعيت جديد خود را با در نظر گرفتن حالت همسايه‌هاي مجاور خود بر اساس يكسري از قوانين بدست مي‌آورد.

قانونها به سه دسته قابل تقسيم مي باشند:

 

1-قانون عمومي: در اين قانون مقدار يک سلول در مرحله بعدي، به مقدار تک تک سلولهاي همسايه در حالت فعلي وابسته است.

2- قانون totalistic: در اين قانون مقدار يک سلول در مرحله بعدي، به تعداد سلولهاي همسايه که در حالتهاي مختلف مي باشند، وابسته است. در اين نوع قانون برخلاف قانون عمومي، توجه اي به تک تک سلولها نمي شود.

3- قانون outer totalistic: تنها تفاوتي که اين قانون با totalistic دارد در اين است که در تعيين حالت بعدي سلول، حالت فعلي نيز موثر است.

 

 

[sarevan 9753]

—در اين آتوماتا هر سلول داراي دو حالت صفر يا يك مي باشد.

—همسايه هاي هر سلول دو سلول كناري آن مي باشند.

 

—هر سلول بهمراه دو همسايه كناري آن مي توانند هشت مقدار مختلف داشته باشند.

—

—هر سلول با توجه به وضعيت فعلي خود و دو همسايه اش يكي از حالات زير را خواهد داشت:

[sarevan 9753]

—هر سلول داراي يکي از چهار حالت زير مي باشد:

—حالت Blank

—حالت Copper

—حالت Head

—حالت Tail

—قوانين بصورت زير هستند:

—يک سلول در حالت Blank همواره در همان حالت باقي مي ماند.

—

—حالت بعدي يک سلول که داراي حالت head است، tail مي باشد.

—

—حالت بعدي يک سلول که داراي حالت tail است، Copper مي باشد.

—

—سلول داراي حالت Copper در همان حال باقي مي ماند مگر اينکه يک يا دو همسايه آن در حالت head باشند. در اينصورت حالت آن به head تغيير خواهد کرد.

—

—هر الگو يا قالب معيني را مي توان در شبکه سلولي در نظر گرفت و تکامل آنرا با استفاده از قانون هاي ذکر شده مشاهده نمود.

[sarevan 9753]

کاربردها:

• —شبيه سازي مدل انتشار شايعه
  
  
• 
  
• —تنظيم بار در گريدهاي محاسباتي
  
  
• 
  
• —تخصيص كانال در شبكه‌هاي سلولي
  
• 
  
• —جايابي مدارات مجتمع متراكم
  
• 
  
• —شبيه‌سازي تكامل ماقبل حيات
  
• 
  
• —مدل‌سازي شبكه‌هاي تجاري
  
• 
  
• —پردازش تصاوير
  
• 
  
• —قطعه‌بندي
  
• 
  
• —تشخيص لبه
  
• 
  
• —رفع نويز
  
• 
  
• —واضح‌سازي تصوير
  
• 
  
• —خوشه‌بندي شبكه‌هاي حسگر بي‌سيم
  
• 
  

[sarevan 9753]

منابع:ویکی پدیا..برنامه نویس...

اطلاعات عمومی و کاربری

[afsanehn 11]

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