پروژه شبیه سازی آموزشی الگوریتم کرم شب تاب در متلب

توضیحات

پروژه شبیه سازی الگوریتم کرم شب تاب در متلب

چکیده

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

کلمات کلیدی: بهینه سازی– سیستم های بیولوژیک– الگوریتم کرم شب تاب

1-مقدمه

کرم شب تاب به انگلیسی:( Firefly)‏ بر خلاف نامش از خانواده حشرات و زیرمجموعه سوسک‌ها و زیرشاخه غلاف پران یا قاب بالان می‌باشد. کرم‌های شب تاب نور سرد تولید می‌کنند که فاقد طیف‌های فروسرخ و فرابنفش می‌باشد. این نور که طول موج آن از ۵۱۰ تا ۶۷۰ نانومتر متغییر است می‌تواند به رنگ‌های زرد، سبز یا قرمز کم‌رنگ دیده شود. دانشمندان پیشتر بر این عقیده بودند که این حشرات با نور شفقی فسفری شان موجب جلب توجه جنس مخالف برای جفتگیری و یا صید برای شکار می‌شوند. اما تحقیقاتی که اخیرا توسط گروهی از محققین با سرپرستی دانشمند بلژیکی، رافائل دی کاک انجام شده است نشان می‌دهد که کرم‌های شب تاب از نوردهی به عنوان یک سیستم دفاعی برای مقابله با شکارچیان استفاده می‌کنند. تاکنون در حدود ۲۰۰۰ گونه از این نوع حشرات در نواحی معتدل و گرمسیری شناسایی شده است. بسیاری از انها در مناطق مردابی و جنگلی، جایی که لاروهایشان به منابع غذایی دسترسی داشته باشند زندگی می‌کنند. در بین بیشتر گونه‌ها هر دو جنس نر و ماده توانایی پرواز دارند. اما در بین بعضی گونه‌ها، جنس ماده قادر به پرواز نمی‌باشد. (منبع: ویکی پدیا)

الگوریتم کرم شتاب برای اولین بار توسط دوریگو ( Dorigo)  و همکارانش به عنوان یک راه حل چند عامله  برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد عامل هوشند ارائه شد.

الگوریتم کرم شتاب الهام گرفته شده از مطالعات و مشاهدات روی کرم شتاب هاست. این مطالعات نشان داده که کرم شتاب ها حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتارکرم شتاب ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتارکرم شتاب ها دارای نوعی هوشمندی توده ای است که اخیرا مورد توجه دانشمندان قرار گرفته است.باید تفاوت هوشمندی توده ای(کلونی) و هوشمندی اجتماعی را روشن کنیم. در هوشمندی اجتماعی عناصر میزانی از هوشمندی را دارا هستند. بعنوان مثال در فرآیند ساخت ساختمان توسط انسان، زمانی که به یک کارگر گفته میشود تا یک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند برای اینکار باید از فرغون استفاده کند نه مثلا بیل!!! نکته دیگر تفاوت سطح هوشمندی افراد این جامعه است. مثلا هوشمندی لازم برای فرد معمار با یک کارگر ساده متفاوت است. در هوشمندی توده ای عناصر رفتاری تصادفی دارند و بین آن ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیر مستقیم و با استفاده از نشانه ها با یکدیگر در تماس هستند. مثالی در این مورد رفتار موریانه ها در لانه سازی است. جهت علاقه مند شدن شما به این رفتار موریانه ها وتفاوت هوشمندی توده ای و اجتماعی توضیحاتی را ارائه می دهم : فرآیند ساخت لانه توسط موریانه ها مورد توجه دانشمندی فرانسوی به نام گرس قرار گرفت. موریانه ها برای ساخت لانه سه فعالیت مشخص از خود بروز می دهند. در ابتدا صدها موریانه به صورت تصادفی به این طرف و آن طرف حرکت می کنند. هر موریانه به محض رسیدن به فضایی که کمی بالاتر از سطح زمین قرار دارد شروع به ترشح بزاق می کنند و خاک را به بزاق خود آغشته می کنند. به این ترتیب گلوله های کوچک خاکی با بزاق خود درست می کنند. علیرغم خصلت کاملا تصادفی این رفتار، نتیجه تا حدی منظم است. در پایان این مرحله در منطقه ای محدود تپه های بسیار کوچک مینیاتوری از این گلوله های خاکی آغشته به بزاق شکل می گیرد. پس از این، همه تپه های مینیاتوری باعث می شوند تا موریانه ها رفتار دیگری از خود بروز دهند. در واقع این تپه ها به صورت نوعی نشانه برای موریانه ها عمل می کنند. هر موریانه به محض رسیدن به این تپه ها با انرژی بسیار بالایی شروع به تولید گلوله های خاکی با بزاق خود می کند. این کار باعث تبدیل شدن تپه های مینیاتوری به نوعی ستون می شود. این رفتار ادامه می یابد تا زمانی که ارتفاع هر ستون به حد معینی برسد. در این صورت موریانه ها رفتار سومی از خود نشان می دهند. اگر در نزدیکی ستون فعلی ستون دیگیری نباشد بلافاصله آن ستون را رها می کنند در غیر این صورت یعنی در حالتی که در نزدیکی این ستون تعداد قابل ملاحظه ای ستون دیگر باشد، موریانه ها شروع به وصل کردن ستونها و ساختن لانه می کنند. تفاوتهای هوشمندی اجتماعی انسان با هوشمندی توده ای موریانه را در همین رفتار ساخت لانه می توان مشاهده کرد. کارگران ساختمانی کاملا بر اساس یک طرح از پیش تعیین شده عمل می کنند، در حالی که رفتار اولیه موریانه ها کاملا تصادفی است. علاوه بر این ارتیاط مابین کارگران  سا ختمانی مستقیم و از طریق کلمات و … است ولی بین موریانه ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیر مستقیم و از طریق نشانه ها با یکدیگر در تماس اند. گرس نام این رفتار را Stigmergie گذاشت، به معنی رفتاری که هماهنگی مابین موجودات را تنها از طریق تغییرات ایجاد شده در محیط ممکن می سازد.

2- الگوریتم کرم شب تاب

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

الگوریتم بهینه سازی اجتماع کرم شب تاب در سال 2005 توسط کریشناناند و گهوز ارائه شده است.  کریشناناند و گهوز در سال های 2006 تا 2008 مبانی نظری این الگوریتم را توسعه داده اند.

هوش توده ای (Swarm Intelligence) به طوری که در اجتماعات طبیعی بروز پیدا می کند نتیجه عمل هایی از جانب افراد توده است که بر طبق اطلاعات محلی انجام می شوند. به طور معمول رفتار توده به اهدافی پیچیده تر و در سطح توده ای راه می برد. نمونه هایی از این پدیده شامل گروه های مورچگان، زنبورهای عسل ، پرندگان و … می باشد.

مکانیسم های تصمیم گیری غیرمتمرکز در این نمونه ها و سایر گونه های طبیعی دیگر الهام بخش طراحی الگوریتم های گسترده ای برای حل مسائل پیچیده مانند بهینه سازی ، تصمیم گیری چند عامله و روبوتیک شده است. در فصل های گذشته به برخی از این الگوریتم ها مانند PSO و ACO اشاره شد. در این بخش به بررسی الگوریتم طرح شده توسط کریشناناند و همکارانش بر اساس رفتار اجتماعی کرم های شب تاب پرداخته می شود.

الگوریتم GSO با قرار دادن جمعیتی n عضوی از کرم های شب تاب در نقاط مختلف فضای جستجوی مسئله بهینه سازی به صورت تصادفی آغاز می شود. در ابتدا همه ی کرم ها مقدار یکسانی از لوسی فرین به اندازه ی l در اختیار دارند. هر تکرار الگوریتم شامل یک فاز به روز کردن لوسی فرین و یک فاز به روز کردن مکان کرم ها می باشد

نکات قابل ذکر:

• پروژه شبیه سازی الگوریتم کرم شب تاب در متلب توسط کارشناسان گروه ۱.۲.۳ پروژه پیاده سازی گردیده و به تعداد محدودی قابل فروش می باشد.
• فایل های پروژه به صورت کامل بلافاصله پس از خرید فایل در اختیار شما قرار خواهد گرفت.