الگوریتم کلونی مورچه ها قسمت 2

الگوریتم کلونی مورچگان در رتبه دوم پر اهمیت‌ترین الگوریتم‌ها، در دسته الگوریتم‌های تکاملی قرار می‌گیرد. رفتار بیولوژیکی مورچه برای پیدا کردن غذا نقطه شروع شبیه سازی مصنوعی ما است.

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

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

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

رفتار جستجو گرانه مورچه‌ها

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

حال با توضیحات بالا یک سوال مهم پیش می‌آید: فرض کنید یک مورچه که به عنوان اولین مورچه است، در مسیری حرکت کرده و بقیه مورچه‌ها نیز به دنبال او راه افتاده‌اند. اگر در مسیر حرکت آن غذا پیدا نشود، آن زمان تصمیم چیست؟ طبق این فرضیه هیچ وقت مسیرهای جدید اکتشاف نمی‌شوند و حرکت به یک حلقه بدون پایان تبدیل می‌شود.!

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

 

الگوريتم های بهینه سازی کلونی مورچگان

تفاوت مورچه‌های واقعی و مورچه‌های مصنوعی

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

مدل تصادفی:

احتمال اینکه مورچه بعدی مسیر A را انتخاب کند:

 

 

 

nA(t) و nB(t) تعداد مورچه هایی که در زمان t در مسیر A و B قرار دارند.

c: درجه جذب برای یک مسیر ناشناخته هر چه c بزرگتر باشد به معنی مقدار فرومون بیشتر برای عدم انتخاب مسیر تصادفی است.

a: بایاس به سمت فرومون به جا مانده در روند تصمیم گیری.

ساختار کلی الگوریتم کلونی مورچگان را باهم بررسی کردیم. در طی چند سال گذشته بهینه‌سازی‌های زیادی بر روی این الگوریتم انجام شد، که از انواع آن‌ها می‌توان به الگوریتم‌های زیر اشاره کرد:

SACO: Simple Ant Colony Optimization

ACOA: Ant Colony Optimization Algorithms

AS: Ant System

Elitist AS: Elitist Ant System

ACS: Ant Colony System

Max-Min AS

و …

منبع


الگوریتم کلونی مورچه ها در هوش مصنوعی

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

بهینه سازی کلونی مورچه ها یا Ant Colony Optimization و به اختصار (ACO)، که در سال ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) و در رساله دکتری وی مطرح شد، یکی از بارزترین نمونه ها برای روش های هوش جمعی است. این الگوریتم از روی رفتار جمعی مورچه ها الهام گرفته شده است. مورچه ها با همکاری یکدیگر، کوتاه ترین مسیر را میان لانه و منابع غذایی پیدا می کنند تا بتوانند در کمترین زمان مواد غذایی را به لانه منتقل کنند. هیچ کدام از مورچه ها، به تنهایی قادر به انجام چنین کاری نیستند، اما با همکاری و پیروی از چند اصل ساده، بهترین راه را پیدا می کنند. الگوریتم مورچه ها، یک مثال بارز از هوش جمعی هستند که در آن عامل هایی که قابلیت چندان بالایی ندارند، در کنار هم و با همکاری یکدیگر می توانند نتایج بسیار خوبی به دست بیاورند.

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

برای هر مورچه کارهای زیر باید انجام شود:

۱- قانون حرکت احتمالی: براساس این قانون مورچه را در فضای جستجو حرکت داده به این ترتیب راه حل مسئله ایجاد می شود
۲- ارزیابی بهترین: باید بهترین راه حلی که توسط این مورچه ایجاد شده را ارزیابی کرد
۳- به روز کردن فرمن: فرمن هر ضلع را با استفاده از تقویت یک راه حل خوب به روز می کنیم
۴-  دوباره به مرحله دوم برگشته و این کار را ادامه می دهیم تا به میزان فرمن دلخواه برسیم
يک رفتار پايه اي ساده در مورچه ها وجود دارد : آنها هنگام انتخاب بين دو مسير بصورت احتمالاتي (Statistical) مسيري را انتخاب مي کنند که فرمن بيشتري داشته باشد يا بعبارت ديگر مورچه هاي بيشتري  قبلا از آن عبور کرده باشند. حال می بینیم که همين تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد :
همانطور که در شکل مي بينيم مورچه ها روي مسير در حرکت اند (در دو جهت مخالف)
اگر در مسير مورچه ها مانعي قرار دهیم مورچه ها دو راه براي انتخاب کردن دارند.
اولين مورچه از A مي آيد و به C مي رسد، در مسير هيچ فرمني نمي بيند بنابراين براي مسير چپ و راست احتمال يکسان مي دهد و بطورتصادفي و احتمالاتي مسير CED  را انتخاب مي کند.
مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرمن را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا)  انتخاب مي کنند. در نهايت مسير CED  بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED  کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرمن بيشتري در آن وجود دارد.
نکته ديگر مسئله تبخير شدن فرمن بر جاي گذاشته شده است. برفرض اگر مانع در مسيرAB  برداشته شود و فرمن تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرمن و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند. تبخیر فرمون از ۳ جهت مفید است:

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

۲) اگر فرمن اصلاً تبخیر نمی شد، مسیرهایی که چند بار طی می‌شدند، چنان بیش از حد جذاب می‌شدند که جستجوی تصادفی برای غذا را بسیار محدود می‌کردند،

۳) وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می‌ماند.

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

همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گردTSP)) ، در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. برای حل مسئله فروشنده سیار که باید از n شهر دیدن کند و از هر کدام فقط یکبار عبورکند نیز می توان از الگوریتم ACO استفاده کرد. مثلا اگر زوج مرتب (N,E) را در نظر بگیریم که N تعداد شهرها و E اضلاع گراف باشند و di,j فاصله اقلیدسی بین شهرهای i و j باشد و  b تعداد مورچه ها در شهر i و در زمان t، هریک از مورچه ها باید مراحل زیر را انجام دهد:

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

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

از کاربردهايACO  مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود مانند :
۱٫ مسير يابي داخل شهري و بين شهري
۲٫  مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا
۳٫ مسير يابي شبکه هاي کامپيوتري

برخی از کاربردهای الگوریتم کلونی مورچه ها

مسيريابي شبکه‌هاي کامپيوتري با استفاده از ACO:

اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند. روش ACR : Ant Colony Routering پيشنهاد شده که بر اساس ايده کلونی مورچه به بهينه سازي جداول مي‌پردازد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي (Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.

استفاده پژوهشگران از الگوي کلونی مورچه ها جهت اداره ترافيک

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

حل مسائل زمانبندي پروژه ها با منابع محدود با استفاده از الگوريتم مورچگان

مساله زمانبندي پروژه ها با منابع محدود (RCPSP) درگير يافتن توالي مناسبي براي انجام فعاليتهاي يك پروژه است به نحوي كه محدوديت هاي تقدم و و تاخر شبكه پروژه و انواع مختلف محدوديتهاي منبعي موجود در پروژه به طور همزمان ارضاء شوند و معيار سنجش معيني از جمله زمان انجام پروژه، هزينه انجام، تعداد فعاليتهاي تاخيردار و غيره بهينه گردند. RCPSP  مساله اي NP-hard به شمار مي آيد و اهميت اين مساله در ابعاد تئوري و عملي باعث شده است كه تاكنون رويكردهاي ابتكاري و يا فراابتكاري جهت حل اين مساله ارائه شود. رويكردي بر اساس بهينه سازي توسط كلوني مورچگان براي حل مساله زمانبندي پروژه ها با منابع محدود ارائه شده است . از جمله تفاوتهاي اصلي رويكرد ارائه شده  با این شیوه قانون انتخاب احتمالات به صورت نوين، تغيير پارامترهاي الگوريتم به صورت پويا، جلوگيري از بروز رفتارهاي نامناسب الگوريتم در تكرارهاي بالا و تعيين رفتار كلي الگوريتم در تكرارهاي بالا می باشد.

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

بكارگيري الگوريتم مورچه همانند ساير روشهاي بهينه سازي تكاملي، نيازمند تعدادي پارامتر كنترل كننده ميباشد. اين پارامترها كه اغلب به كمك آناليز حساسيت تعيين مي شوند، نقش تعيين كننده اي در عملكرد روش دارند. علاوه بر اين پارامترها بايد از ضريب جريمه نيز براي مسايل بهينه سازي مقيد استفاده كرد. در اين کاربرد از الگوريتم مورچه اي با كمترين تعداد پارامترهاي كنترل كننده، براي بهينه سازي شبكه هاي توزيع آب استفاده شده است.

الگوريتم مورچه اي براي طراحي مسير حركت باربران خودكار در سيستم تك حلقه

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

استفاده از الگوريتمaco  درطراحي شبكه هاي توزيع شعاعي

در اینجا از الگوريتم کلونی مورچه ها در طراحي بهينه شبكه هاي توزيع شعاعي كه در آنها مسير تغذيه مشخص است، استفاده مي شود. اين الگوريتم ضمن ارائه ميزان نفوذ هر يك از سطوح ولتاژ در شبكه مورد مطالعه، ظرفيت بهينه ترانسفورماتور ها و سطح مقطع بهينه فيدرها را در هر يك از سطوح ولتاژي ارائه مي نمايد. الگوريتم فوق بر روي يك شبكه نمونه اجرا شده و نتايج آن نشانه برتري روش ارائه شده نسبت به روش الگوريتم pso و الگوريتم سطح تغذيه است. نقطه قوت اين الگوريتم سرعت بالا، يعني بيشتر از ۲۴۰ برابر الگوريتم تعيين سطح تغذيه و بيش از ۱۸ برابر الگوريتم pso و همچنين كاهش۱۰ درصدي (بطور متوسط) قيمت نهايي در مقايسه با ديگر الگوريتم هاي موجود به سبب اضافه كردن ظرفيت ترانسفورماتور ها به عنوان متغير فضاي جستجو مي باشد.

ارايه يک مدل ابتکاري مبتني بر سيستم اجتماع مورچه ها براي حل مسئله زمان بندي حركت قطار

در اينجا با توسعه الگوريتم فوق ابتکاري سيستم اجتماع مورچه ها (acs) الگوريتمي براي زمان بندي حركت قطار معرفي شده است. ابتدا نوعي از مسئله زمان بندي حركت قطار در قالب يک برنامه ريزي رياضي مدلسازي و سپس الگوريتمي مبتني بر acs براي حل آن پيشنهاد شده است. با اين فرض که هر قطار در مسئله زمان بندي حرکت قطار معادل يك شهر در مسئله فروشنده دوره گرد (tsp) باشد، acs  بر روي گراف مسئله tsp، توالي حركت قطارها را مشخص مي کند. بر اساس اين توالي و رفع تلاقي در برخورد قطارها، زمان بندي حرکت مشخص خواهد شد.

بررسی پارامترهای الگوریتم AntNet

تنوع زیادی در پروتکلها و الگوریتم های مسیریابی برای ارتباطات شبکه ای وجود دارد. در مسیریابی سنتی جداول مسیریابی به واسطه تبادل اطلاعات مسیریابی بین مسیریابها به روز می شوند. الگوریتم هایی که با الهام از کلونی مورچه ها ارائه شده از عاملهای موبایل در مسیریابی شبکه ها استفاده می کنند. در این الگوریتم ها مسیریابی بصورت hop by hop و بر اساس خاصیت stigmergic در کلونی مورچه ها انجام می شود. stigmergicشکلی از ارتباط غیر مستقیم است که به وسیله تاثیر روی محیط انجام می شود. به این صورت که عامل ها (مورچه ها) در شبکه حرکت می کنند و جداول مسیر یابی را به روز می کنند.
منبع

الگوریتم کلونی مورچه ها قسمت 1
الگوریتم کلونی مورچه ها قسمت 2
الگوریتم کلونی مورچه ها قسمت 3

0 پاسخ

دیدگاه خود را ثبت کنید

تمایل دارید در گفتگوها شرکت کنید؟
در گفتگو ها شرکت کنید.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *