مفاهیم اولیه الگوریتم مورچگان :

تاریخچه :

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

مقدمه :

هنگامی که یک مورچه به شکل تصادفی تنها حرکت می کند و به یه دوراهی می رسد به احتمال زیاد مسیری را انتخاب می کند که دارای بوی فرومون بیشتر است و آن مسیر را ادامه می دهد . همچنین با فرمونی که از خود ترشح می کند احتمال انتخاب آن مسیر را برای سایر مورچگان افزایش میدهد .

یکی از جالبترین رفتار های مورچه ها رفتاری است که برای پیدا کردن غذا از خود نشان می دهند . ، بویژه رفتاری که برای پیدا کردن کوتاهترین و بهترین مسیر میان آشیانه ( لانه ) و منبع غذا از خود بروز می دهند .

آنچه بنيان فكری الگوريتم مورچگان بر آن بنا شده است را می توان بسادگی و در يك جمله بيان نمود: " مورچه ها در بين موانع و محدوديت های موجود در طبيعت هميشه از بين جايگشت های متفاوت برای رسيدن به غذا، بهينه ترين راه را انتخاب می كنند".

عامل هوشند :

موجودی است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روی محيط تاثير بگذارد.

درباره ی مورچگان طبیعی :

1 - فرومون : (Pheromone)

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

2 - هوشمندی توده ای :

یک توده (Swarm) عبارت است از مجموعه ای از عامل ها که با یکدیگر به صورت مستقیم (کلمات ، سیگنال ، علايم و . . .) یا به صورت غیر مستقیم (از طریق تاثیر گذاری در محیط) در تماس هستند و همگی یک مسئله را به شکل گسترده حل می کنند .

یکی از خصلت های کلونی مورچه ها هوشمندی توده ای است ، به این معنی که کلونی مورچه ها نه بر اساس هوشمندی یک مغر مرکزی بلکه بر اساس توده ای از عامل های هوشمند و رابطه ی بین آنها عمل می کنند .

3 - اجتماعی بودن :

مورچه ها موجودات اجتماعی هستند و رفتار آنها در جهت بقای کلونی است تا در بقای جزء و همچنین دارای کار گروهی و تقسیم کار هستند .

4 - تصمیم گیری :

آنها برای انتخاب بین دو مسیر به صورت احتمالی (statistical) تصمیم میگیرند و معمولا مسیری را انتخاب می کنند که دارای فرومون بیشتری است (قبلا مورچه های بیشتری از آن عبور کرده است) .

الگوریتم کلونی مورچگان :

مورچه ها هنگام انتخاب بين دو مسير بصورت احتمالاتی مسيری را انتخاب می کنند که فرومون بيشتری داشته باشد يا بعبارت ديگر مورچه های بيشتری قبلا از آن عبور کرده باشند. حال می بینیم که همين تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد : همانطور که در شکل می بينيم مورچه ها روی مسير بین مبدا و مقصد ( محل غذا ) در حال حرکتند .

اولین مورچه که حرکت میکند هیچ فرومونی را نمی بیند و یکی از دو راه انتخاب میکند . ( در اینجا احتمال انتخاب هر دو مسیر برابر است . )

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

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

اگر تصادفا اولين مورچه مسير را انتخاب مي کرد و ردی از فرومون بر جای مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت می کردند و هيچ وقت کوتاهترين مسير يافته نمی شد. بنابراين تصادف و احتمال نقش عمده ای در ACO دارد .

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

اين دو ويژگی باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازی می شوند. مثلا در گراف شهرهای مسئله فروشنده دوره گرد، اگر يکی از يالها (يا گره ها) حذف شود الگوريتم اين توانايی را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره ای) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايی که مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها می توانند پس از مدت کوتاهي مسير بهينه (کوتاهترين) را بيابند. می توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد از ACO استفاده نمود :

1- مسير يابی داخل شهری و بين شهری

2- مسير يابی بين پست های شبکه های توزيع برق ولتاژ بالا

3- مسير يابی شبکه های کامپيوتری

برای پیاده سازی کلونی مورچه، از مورچه های مصنوعی به عنوان عناصری در بهینه سازی استفاده می شود. البته این عناصر تفاوتهای اساسی با مورچه های واقعی دارند که عبارتند از:

1 - حافظه: برای مورچه های مصنوعی می توان یک حافظه در نظر گرفت که مسیرهای حرکت را در خود نگه می دارند.

2 - موانع ساختگی: تغییر دادن جزئیات مسئله برای بررسی الگوریتم و رسیدن به جوابهای متنوع.

3 - حیات در محیط گسسته: مورچه های واقعی نمی توانند جدا از کلونی به حیات خود ادامه دهند.

4 - فرومون مصنوعی : تابعی از غلظت فرومون یافت شده .

همانطور که میدانیم مسئله ی یافتن کوتاهترین مسیر ، یک مسئله بهینه سازی است که گاه حل آن بسیار دشوار و کار زمانبری می باشد .

الگوریتم کلونی مورچگان (ACO) یک الگوریتم کامل و مناسب برای حل مسئله TSP است .

مزیت های تبخیر شدن فرومون :

1- تبخیر شدن مسیر های دورتر و غلیظتر شدن مسیر های نزدیکتر باعث جذابتر شدن مسیر کوتاهتر می شود .

2- اگر تبخیر وجود نداشت مسیر ابتدایی به حدی جذاب می شد که احتمال پیدایش مسیر بعدی به شدت کاهش می یافت .

3- وقتی ذخیره غذایی انتای مسیر پایان میافت فرمون موجود در مسیر باعث گمراهی سایر مورچگان می شد .

الگوریتم های کلونی مورچگان (ACO) :

- الگوریتم AS

- الگوریتم مورچگان نخبه Elite AS

- الگوریتم رتبه بندی مورچگان Rank AS

- الگوریتم جمعیت مورچگان ACS

- الگوریتم MMAS (مینیمم و ماکزیمم)

مفاهیم اولیه الگوریتم مورچگان :

تاریخچه :

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

مقدمه :

عامل هوشند :

موجودی است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روی محيط تاثير بگذارد.

درباره ی مورچگان طبیعی :

1 - فرومون : (Pheromone)

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

الگوریتم کلونی مورچگان :

اولین مورچه که حرکت میکند هیچ فرومونی را نمی بیند و یکی از دو راه انتخاب میکند . ( در اینجا احتمال انتخاب هر دو مسیر برابر است . )

1- مسير يابی داخل شهری و بين شهری

2- مسير يابی بين پست های شبکه های توزيع برق ولتاژ بالا

3- مسير يابی شبکه های کامپيوتری

برای پیاده سازی کلونی مورچه، از مورچه های مصنوعی به عنوان عناصری در بهینه سازی استفاده می شود. البته این عناصر تفاوتهای اساسی با مورچه های واقعی دارند که عبارتند از:

1 - حافظه: برای مورچه های مصنوعی می توان یک حافظه در نظر گرفت که مسیرهای حرکت را در خود نگه می دارند.

2 - موانع ساختگی: تغییر دادن جزئیات مسئله برای بررسی الگوریتم و رسیدن به جوابهای متنوع.

3 - حیات در محیط گسسته: مورچه های واقعی نمی توانند جدا از کلونی به حیات خود ادامه دهند.

4 - فرومون مصنوعی : تابعی از غلظت فرومون یافت شده .

مطالب مشابه :

مفاهیم اولیه الگوریتم مورچگان :

پاور پوینت آموزش الگوریتم مورچگان(ACO)

الگوريتم مورچگان چیست؟ توضیح با یک مثال ساده

انواع مختلف الگوریتم بهینه سازی مورچگان

الگوریتم AS از کلونی مورچگان :

دانلود چند کتاب مربوط به الگوریتمهای فرا ابتکاری

فیلم آموزشی جامع الگوریتم مورچگان کلاسیک یا ACO در متلب

کد متلب الگوریتم مورچگان برای مسأله فروشنده دوره گرد

کتاب تحقیق در عملیات یا پزوهش عملیاتی با عنوان Introduction to Operations Research

الگوریتم مورچگان