بخشی از مقاله
مطالعه و مروری بر الگوریتم اتوماتای سلولی و کاربرد آن در مهندسی منابع آب
چکیده
شبیه سازی سیستم های منابع آب به دلیل پیچیدگی روابط حاکم بر معادله آنها گاه با روش های معمول قدیمی امکان پذیر نمی باشد و یا حل آنها مستلزم صر وقت و هزینه بسیار است. در این میان، است اده از روش های توانمند و نوین امری اجتناب ناپذیر است. از این رو در سال های اخیر الگوریتم اتوماتای سلولی مورد توجه و است اده محققان و کارشناسان قرار گر ته است. اتوماتای سلولی سیستم پویای گسسته و شامل اجزا با اتصال محلی می باشد که بصورت شبکه ای یکنواخت و منظم عمل می کند و مقدار هرجزء با توجه به مقادیر اجزاء اطرا آن تعیین می شود. از اینرو همگرایی و رسیدن به جواب بهینه در این روش با سرعت و دقت بیشتری انجام می شود؛ که این امر موجب تمایز این روش از دیگر روش های شبیه سازی و مدل های مبتنی بر روش های عددی شده است. در نتیجه چنین سیستمی پتانسیل اجرای محاسبات شبیه سازی پیچیده را دارد و بکارگیری آن در حل مسائل پیچیده علوم مهندسی آب در حال ا زایش است. در این بررسی، ضمن معر ی الگوریتم اتوماتای سلولی و کاربردهای آن، مزیت ها و محدودیت های آن در مدل کردن سیستم های منابع آب بیان شده است. همچنین ضرورت توجه بیشتر به این روش به عنوان ابزاری توانمند برای شبیه سازی و مدیریت سیستم های منابع آب و است اده از این روش در حل سایر مسائل توصیه شده است.
.1 مقدمه:
شبیه سازی سیستم های منابع آب به دلیل پیچیدگی روابط حاکم بر معادله آنها گاه با روش های معمول قدیمی امکان پذیر نمی باشد و یا حل آنها مستلزم صر وقت و هزینه بسیار است . در این میان، است اده از روش های توانمند و نوین امری اجتناب ناپذیر است. در سال های اخیر است اده از روش اتوماتای سلولی که مدلی ساده برای شبیه سازی سیستمهای پیچیده می باشد مورد توجه و است اده محققان و کارشناسان قرار گر ته است. اتوماتای سلولی سیستم های پویایی هستند که در زمان، مکان و حالت گسسته می باشند و همگرایی و رسیدن به جواب بهینه در این روش با سرعت و دقت بیشتری انجام می شود؛ که این امر موجب تمایز این روش از دیگر روش های شبیه سازی و مدل های مبتنی بر روشهای عددی شده است .[35]
دربهینه سازی به کمک اتوماتای سلولی چیزی به نام تابع هد تعری نمی شود و این الگوریتم تنها به کمک قوانین در سطح محلی کار می کند. مدل های مبتنی بر اتوماتای سلولی سازگار با برنامه های موازی هستند؛ بنابراین به سادگی در کامپیوترهای مدرن قابل است اده هستند. اتوماتای سلولی در مدلسازی پروسه های یزیکی و مهندسی که مدلسازی گسسته می باشد مناسب می باشد و به عنوان جایگزینی برای معادلات دی رانسیل جزئی است اده می شود. از اینرو بکارگیری آن در حل مسائل پیچیده علوم مهندسی آب در حال ا زایش است. بسیاری از کاربرد های اتوماتای سلولی در زمینه دینامیک جریان و شبیه سازی رسایش و رسوب، مدلسازی آب زیرزمینی، پخش آلودگی، بهینه سازی شبکه توزیع آب و ... موجود است. با توجه به اهمیت این الگوریتم و لزوم آشنایی و بکار گیری آن در حل مسائل پیچیده علوم مهندسی آب، در این تحقیق ضمن معر ی الگوریتم اتوماتای سلولی و کاربردهای آن در مهندسی آب، مزیتها و محدودیتهای آن در مدل کردن سیستم های منابع آب بیان شده است.
.2 الگوریتم اتوماتای سلولی
یکی از مدلهایی که در شبیه سازی و یا مدل کردن سیستمها مورد است اده قرار می گیرد، اتوماتای سلولی می باشد. اتوماتای سلولی سیستم های پویایی هستند که در زمان، مکان و حالت گسسته می باشند[16 ] و اولین بار توسط جان ون نیومن در سال 1966 میلادی به منظور مدلسازی ماهیت خود تکثیری در سیستم های بیولوژیکی مطرح شد.21 ]،25،12،28، 32 و [35 در این سیستم ها ضا به اجزا ئی مشابه به نام " سلول "با اتصال محلی تقسیم می شود و بصورت شبکه یکنواخت و منظم عمل می کند. هر کدام از این سلول ها میتوانند مقادیر مشخص و گسسته ای را اتخاذ کنند.[4]
اتوماتای سلولی براساس معیار بعد شبکه، به اتوماتای سلولی یک بعدی، دوبعدی و سه بعدی تقسیم می گردد.[3] متداولترین اتوماتای سلولی، اتوماتای سلولی دو بعدی می باشد. در اتوماتای سلولی قوانین ساده یکسانی حاکم است که همزمان برای تمام سلول ها اعمال می شود. این قوانین، قانون محلی یا تابع انتقال 1 نامیده می شود. قانون اتوماتای سلولی، نحوه تاثیر پذیر تن یک سلول از سلولهای همسایه خود را مشخص می کند. همسایه هر سلول، سلولهای مجاور آن هستند که با آن سلول تعامل دارند. یک سلول، همسایه سلول دیگر گ ته میشود اگر بتواند آن سلول را در یک مرحله و براساس قانون حاکم تحت تاثیر قرار دهد . برای سلولهای همسایه مدلهای مختل ی ارائه شده است که مهمترین مدلهای آن برای اتوماتای دو بعدی در شکل 1 نشان داده شده است:[2]
شکل -1 مدل های متداول همسایگی در اتوماتای دو بعدی
برای الگوریتم اتوماتای سلولی، قانون انتقال محلی عموما بسته به مساله مورد حل مت اوت می باشد و عموما به صورت اختصاصی برای هر مساله و با توجه به یزیک مساله محاسبه می شود و الگوی خاصی برای یا تن این معادله وجود ندارد18] و .[22
در همه سلول ها مقدار هر سلول بر اساس سلول های همسایه آن تعیین می شود. یعنی در هر گام زمانی مقدار هر سلول به مقدار سلول های همسایه در گام زمانی قبل وابسته است. بر طبق تعری ، هیچ گونه محدودیتی برای تعداد همسایگان شرکت کننده در قانون انتقال محلی وجود ندارد؛ اما باید به این نکته نیز توجه کرد که این انتخاب تاثیر زیادی بر روی قانون انتقال و در نتیجه بر روی جواب و سرعت همگرایی مساله دارد. هر سلول در اتوماتای سلولی بصورت 7 تایی (Q,d,V,Σ,Δ,δ,λ) می باشد که در آن:
Q -1 مجموعه حالاتی است که هر سلول می تواند اختیار کند.
d - 2 ابعاد ضای سلولی را مشخص می نماید. به ازای d=1 یک اتوماتای سلولی یک بعدی و به ازای d=2 یک اتوماتای سلولی دو-بعدی خواهیم داشت.
-3 برای هر سلول x در اتوماتای سلولی آرایه V(x) = {x + v0, x + v1,..., x + vk } مشخص کننده k+1 همسایه ای می باشد که بصورت مستقیم با سلول در ارتباطند.
Σ -4 شامل ورودی اتوماتای سلولی می باشد.
-5 شامل خروجی اتوماتای سلولی می باشد.
δ - 6 تابع انتقال است که ب رم δ : (Q× Σn )k +1 → Q می باشد. براساس تابع انتقال، حالت بعدی هر سلول به حالت و مقادیر حا ظه ای تمامی همسایگان آن سلول در مرحله علی بستگی دارد. n تعداد ثبات های هر سلول است.
λ - 7 رابطه مبدل است. این مبدل مقدار هر حا ظه سلول را با توجه به حالت و مقادیر حا ظه ای همسایگانش مشخص می سازد.[3]
دربهینه سازی به کمک اتوماتای سلولی چیزی به نام تابع هد تعری نمی شود و این الگوریتم تنها به کمک قوانین در سطح محلی کار می کند بهینه سازی، برپایه به روز رسانی جایگاه سلول ها بر اساس قانون انتقال محلی استوار است. این قانون به طور همزمان و یکسان بر روی تمام سلولها اعمال شده و مقادیر این سلولها را در جهت رسیدن به جواب بهینه هدایت می کند. نکته مهم، انتخاب درست قانون انتقال است که بر اساس جایگاه سلول و همسایگانش در یک تکرار قبل تعری میشود17 ]و.[18 قانون بهتر نتابج بهتری را بدست میدهد. الگوریتم اتوماتای سلولی قابلیت مدل کردن هد های مختل ی که در تقابل با هم هستند را به طور همزمان دارا می باشد علاوه بر آن است اده از قانون انتقال که یک رمول ساده است نیز از مزایای این الگوریتم به شمار می رود[4]
بطور کلی روش کار اتوماتای سلولی بدین صورت است که در ابتدای کار نوع سلولهای اتوماتای سلولی را مشخص کرده و مقادیر اولیه برای تمام سلولها بر اساس شرایط ابتدایی سیستم تعیین می شوند . سپس بطور همزمان هر سلول براساس وضعیت همسایه هایش محاسبه ای را انجام می دهد و بر اساس نتیجه آن محاسبه، وضعیت خود را تغییر دهد.[3 ] بدین صورت اتوماتای سلولی با تغییر مقدار(حالت) تمام سلول ها بر اساس قانون انتقال در یک زمان با گام زمانی گسسته نمو پیدا می کند. در نهایت تغییر و تکامل سراسری اتوماتای سلولی با تکامل تمام سلول ها حاصل می شود.[16]
.2-1 ویژگی های اتوماتای سلولی:
اتوماتای سلولی مدل ریاضی برای سیستم هایی است که در آنها چندین مؤل ه ساده برای الگوهای پیچیده با هم همکاری می کنند. مدل های مبنی بر اتوماتای سلولی سازگار با برنامه های موازی هستند بنابراین به سادگی در کامپیوترهای مدرن قابل است اده هستند. از اینرو برای شبیه سازی مسایل پیچیده بسیار خوب عمل می کند و بکارگیری آن در علوم طبیعی، ریاضیات و در علم کامپیوتر؛ به عنوان نمونه در جریان سیالات، آرایش کهکشان، زمین لرزه، شکل گیری الگوی زیستی و کارهای محاسباتی در حال ا زایش است.[24]
به طور کلی میتوان ویژگی های اتوماتای سلولی را به موارد زیر خلاصه کرد: .1 ر اتوماتای سلولی زمان و ضا گسسته میباشند.
.2 با توجه به قوانینی که دارد ر تار بسیار پیچیده ای از خود بروز می دهد.
.3 اتوماتای سلولی خاصیت محلی2دارد و در هر لحظه وضعیت و مقدار هر سلول با توجه به وضعیت و مقدار سلولهای همسایهاش تعیین میشود.
.4 اتوماتای سلولی بصورت همگن3 است بدین معنی که عمل بروزرسانی سلولها به طور همزمان و بر اساس یک قانون یکسان انجام میشود.
.5 اتوماتای سلولی خاصیت توازی4 دارد؛ بدین معنی که به روز رسانی جایگاه سلول ها به صورت موازی با هم انجام می شود.
.6 در اتوماتای سلولی تمام سلول ها یکسان می باشند و قانون یکسان در همه آنها اعمال می شود. 34]و[2
با وجود مزایای اتوماتای سلولی، یکی از محدودیت های آن تعیین رم قطعی قوانین مورد نیاز برای یک کاربرد خاص است. اتوماتای سلولی برای مدل کردن سیستمهایی مناسب است که قطعیت در تغییر حالات سیستم وجود داشته باشد؛ در صورتیکه برخی سیستمها دارای عدم قطعیت میباشند و وضع قوانین به صورت قطعی برای آنها منطقی به نظر نمی رسد. روشهای مت اوتی برای حل این مشکل پیشنهاد شده است. یکی از این روشها احتمالاتی کردن قوانین میباشد.[27]
مدل های تعمیم یا ته اتوماتای سلولی دارای خصوصیات ناهمگنی زمانی و مکانی در تابع انتقال، پیوستگی حالت، غیر همزمانی در تابع حالت، همسایگی های پیچیده وابسته به زمان و توابع انتقال احتمالاتی و مرتبه ای می باشند[16]
برای نمونه مدل "یادگیرنده Q سلولی "برای مشکل عدم قطعیت پیشنهاد شده است. یادگیرنده Q سلولی یک اتوماتای سلولی است که هر سلول آن به یک یا چند یادگیرنده Q که یکی از انواع یادگیری تقویتی میباشد مجهز است و وضعیت سلول را مشخص میکند. مانند اتوماتای سلولی، قانون محلی در محیط حاکم است و این قانون تعیین می کند که آیا عمل انتخاب شده توسط یک یادگیرنده Q در سلول باید پاداش داده شود ویا اینکه جریمه شود .دادن پاداش ویا جریمه منجربه بهروز درآوردن ساختار یادگیرنده Q سلولی به-منظور نیل به یک هد مشخص می گردد.[27]
.3 کاربردهای اتوماتای سلولی
همانطور که در بخش قبل اشاره شد، اتوماتای سلولی با وجود قوانین ساده پتانسیل اجرای محاسبات شبیه سازی پیچیده را دارند و در مدلسازی پروسه های یزیکی و مهندسی که مدلسازی گسسته می باشد مناسب می باشد و خوب عمل می کند و به عنوان جایگزینی برای معادلات دی رانسیل جزئی است اده می شود. از اینرو بکارگیری آن در حل مسائل پیچیده علوم مهندسی آب در حال ا زایش است. بسیاری از کاربرد های اتوماتای سلولی در زمینه دینامیک جریان موجود است.[13 ] در این صل به کاربردهای اتوماتای سلولی و مدل های ارائه شده در زمینه مدیریت منابع آب سطحی و آب زیرزمینی، مدیریت شبکه های شهری و حوضه آبخیز و نیز مزایا و محدودیت های آنها اشاره شده است.
.3-1 منابع آب سطحی:
ضیائیان یروز آبادی و همکاران((1382 با تل یق داده های سنجش از دور، به کارگیری مدل های هیدرولوژی موجود در زمینه برآورد سیلاب ناشی از بارش و به کار گیری مدل سلولهای خودکار، به شبیه سازی گسترش سیلاب برای دو حوضه کشور پرداختند . مقایسه نتایج این شبیه سازی با روش مدل ریاضی و داده های واقعی سیلاب نشان دهنده شبیه سازی سیلاب با دقت مطلوب تری می باشد.[6]
نادر((2005 از اتوماتای سلولی در شبیه سازی سیلاب های ناحیه حوضه تالاب های ساحلی کانادا است اده نمود و نشان داد که این روش نتایج دقیق تر و قابل قبول تری نسبت به سایر روشهای موجود، ارائه می دهد.[29]
داوینت و همکاران (2006) در تجزیه و تحلیل 3 بعدی جریان آبراهه به کمک ابزار مدلساز Ruicells بر پایه اتوماتای سلولی نشان دادند که اتوماتای سلولی به تعری بهتر سیستم های مور ولوژی کمک می کند و خروجی مدل در تعیین سهم شاخه ها وموقعیت صعود موج راهنمایی می کند. همچنین نتایج نشان دهنده تطبیق خوب نتایج شبیه سازی با رواناب های مشاهداتی می باشد.[14]
ایکسان گ (2006) به ارائه مدل مسیریابی رواناب درحوضه آبخیز لی آنه براساس قواعد پایه GIS و اتوماتای سلولی پرداخت. مقایسه نتایج شبیه سازی مدل HydroCA با مدل TOPMODEL (با است اده از نقشه توپوگرا یک (DEM نشان دهنده بهبود نتایج با است اده از اتوماتای سلولی می باشد. صر نظر از محدودیت های این مدل که محدود بودن مقیاس مدل برای حوضه هایی با مساحت 5000-500 کیلومتر مربع، عدم وجود نقشه های DEM با کی یت مطلوب به عنوان ورودی مدل و نیز تاخیر رواناب تولید شده که منبعی از خطا در مدل می باشد؛ این مدل مزیت هایی نسبت به روش های قدیمی مدلسازی از جمله مشخص تر بودن تغییرات در شکل و صورتبندی رواناب و جریان سطحی در یک زمان مشخص، راحت تر بودن شبیه سازی پروسه حرکت جریان از هر نقطه به سمت خروجی و نمایش مسیر معقولتری از پروسه جریان رواناب به سمت خروجی را داراست. بنابراین امکان علمی برای است اده از اتوماتای سلولی برای مدلسازی مسیریابی هیدرولوژیکی وجود دارد.[39]
