کلونی مورچه ها

مقدمه :

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

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

به‌کارگیری سیستم مورچگان اولین بار (الگوریتم مورچگان) توسط Dorgio و همکاران . به
  عنوان یک نگرش با چندین عامل برای حل مسائل بهینه‌سازی ترکیبی یا راه‌حل
  چندعامله (multi Agent) مشکل، مانند مسئله فروشنده دوره گرد یا (TSP) (Traveling Sales Person)
  و مسئله تخصیص منابع یا QAP
  پیشنهاد و ارائه شد.

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

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

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

1. اجتماعی بودن:

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

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

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

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

وقتی غذای انتهای یک مسیر جذاب تمام می‌شد رد باقی می ماند.لذا وقتی یک مورچه مسیر کوتاهی (خوبی) را از خانه تا غذا بیابد بقیهٔ مورچه‌ها به احتمال زیادی همان مسیر را دنبال می‌کنند و با تقویت مداوم آن مسیر و تبخیر ردهای دیگر،
به مرور همهٔ مورچه‌ها هم مسیر می‌شوند. هدف الگوریتم مورچه‌ها تقلید این رفتار توسط مورچه‌هایی مصنوعی ست که روی نمودار در حال حرکت اند. مساله یافتن کوتاه‌ترین مسیر است و حلالش این مورچه‌های مصنوعی اند
Emergent Intelligence

2.      هوشمندی توده‌ای: هوش جمعی (swarmIntelligence)

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

مورچه‌ها چگونه کوتاهترین مسیر را انتخاب می‌کنند؟

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

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

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

• ترشح اسید فرمیک در مسیر حرکت
• دنبال کردن مسیرهای با اسید فرمیک بیشتر
• تبخیر

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

این نوع هوشمندی هیچ نیازی به کنترل مرکزی و دید کلی نسبت به سیستم ندارد

•   Stigmergy  :  ایده اصلی در تعاملات ارتباط با واسطه محیط    لانه سازی موریانه ها  ترشح اسید فرمیک توسط مورچه هامزایایی که هوش جمعی
       از آن بهره می برند
• مقیاس پذیری(scalability): تعاملات توزیع شده موجودات
• خطا پذیری(Fault tolerance)
• عدم وجود کنترل متمرکز
• قابلیت تطبیق پذیری عاملها
• سرعت انتقال تغییر
• تفکیک پذیری (modularity)
• خودکار بودن   سیستم : نیاز به نظارت انسان نیست
• کارکرد موازی

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

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

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

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

1.   چندمنظوره می باشد

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

2.قوی می باشد

یعنی با کمترین تغییرات برای دیگر مسائل بهینه‌سازی ترکیبی به کار برده می‌شود

3.یک روش مبتنی بر جمعیت می‌باشد.       مزیتهای     ACO :       ایجاد انعطاف در حل هرگونه مسئله بهینه‌سازی      پسخورد مثبت (پسخورد مثبت، منجر به کشف سریع جوابهاب خوب می‌شود)       محاسبات توزیع شده (محاسبات توزیع شده از همگرایی زودرس و
بی‌موقع جلوگیری می‌کند)       هیوریستیک آزمند سازنده (به کشف جوابهای قابل قبول در مراحل اولیه جستجو کمک می‌کند).

·       کاربردهای الگوریتم مورچگان :
از کاربردهای الگوریتم (ACO) می‌توان
به بهینه کردن هر مسئله‌ای که نیاز به یافتن کوتاهترین مسیر دارد استفاده می شود:
·مسیریابی داخل شهری و بین شهری
·مسیریابی بین پست‌های شبکه‌های توزیع برق ولتاژ بالا
·مسیریابی شبکه‌های کامپیوتری 

· مسیر یابی تامین مواد اولیه جهت تولید به هنگام

·برنامه ریزی دروس دانشگاهی

·توازن بار ترافیک شبکه ومسیریابی مبتنی برمهندسی ترافیک

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

·مسئله زمان بندی حرکت قطار ها

·الگوریتم ی مورچه و کاربرد آن در برنامه ریزی پرواز

·بهینه سازی سکوهای دریا

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

·مسأله راهیابی در شبکه های مخابرات راه دور 

v     الگوریتم مورچگان و بهره‌گیری از مسأله فروشنده
دوره‌گرد جهت مسأله‌سازی:
در مسئله فروشنده دوره‌گرد، یک فروشنده سفر خود
را از یک شهر آغاز کرده و پس از یک سفر کامل دوباره به شهر خودش بازمی‌گردد و از
هر شهر فقط یکبار عبور می‌کند ودرضمن باید از همه شهرها عبور نموده و کمترین مسافت
را طی نماید.
قانون 1 :تصمیم گیری

قانون 2 :بروز رسانی

قانون 3 : تبخیر

از کابردهای این الگوریتم، رسیدن به راه حل تقریباً بهینه در مسئله فروشنده دوره‌گرد است. به طوری که انواع الگوریتم مورچه‌ها برای حل این مساله تهیه شده. زیرا این روش عددی نسبت به روشهای تحلیلی و genetic در مواردی که نمودار مدام با زمان تغییر کند یک مزیت دارد؛ و آن این که الگوریتمی ست با قابلیت تکرار. و لذا با گذر زمان می‌تواند جواب را به طورزنده تغییر دهد. که این خاصیت در روتینگ شبکه‌های کامپیوتری و سامانه حمل و نقل شهری مهم است.

مساله فروشنده دوره گرد

الگوریتم

پروسه پیدا کردن کوتاه‌ترین مسیر توسط مورچه ها، ویژگی‌های بسیار جالبی دارد، اول از همه قابلیت
تعمیم زیاد و خود- سازمانده بودن آن است. در ضمن هیچ مکانیزم کنترل مرکزی ای وجود
ندارد. ویژگی دوم قدرت زیاد آن است. سیستم شامل تعداد زیادی از عواملی است که به
تنهایی بی اهمیت هستند بنابراین حتی تلفات یک عامل مهم، تاثیر زیادی روی کارآیی
سیستم ندارد. سومین ویژگی این است که، پروسه یک فرآیند تطبیقی است. از آنجا که
رفتار هیچ کدام از مورچه‌ها معین نیست و تعدادی از مورچه‌ها همچنان مسیر طولانی تر
را انتخاب میکنند، سیستم می تواند خود را با تغییرات محیط منطبق کند و ویژگی آخر
اینکه این پروسه قابل توسعه است و می تواند به اندازهٔ دلخواه بزرگ شود.
همین ویژگی‌ها الهام بخش طراحی الگوریتم هایی شده اند که در مسائلی که نیازمند این
ویژگی‌ها هستند کاربرد دارند.اولین الگوریتمی که بر این اساس معرفی شد،الگوریتم ABC بود. چند نمونه دیگر از این الگوریتم‌ها عبارتند از: Ant Net،ARA،PERA، Ant Hot Net

·                   نرم‌افزارهای کاربردی در این الگوریتم:

        در برنامه‌های کامپیوتری الگوریتم از زبان برنامه‌نویسی  (Borland C ++5.02,C)نیز استفاده می‌شود
         مدلهای ریاضی که دراین الگوریتم استفاده می‌شود جوابهای آن بااستفاده از نرم‌افزار LINGO
بدست می‌آید.      

جمع‌بندی و نتیجه‌گیری:

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

منابع:     1. ح. توحیدی و ح. نظام‌آبادی‌پور وس. سریزدی «انتخاب ویژگی با استفاده
از الگوریتم جمعیت مورچگان باینری» هشتمین کنفرانس سیستمهای هوشمند، 1386.
    2. م. صفاری و 1. جمال‌نیا «الگوریتم‌های لانه مورچه و کاربرد آن در نگهداری پیشگیرانه» اولین همایش ملی مدیریت صنعتی.     3. م.م. سپهری و ع. جعفری «حل مسأله تأمین بهنگام قطعات موردنیاز سیستم‌های تولیدی با استفاده از مدل ریاضی و الگوریتم مورچگان» نشریه دانشکده فنی، اردیبهشت ماه 1383.
     4.مقاله ارشد سید صابر ناصر ا سدی دانشکده علم وصنعت ایران
5. مقاله ارشد سید صادق ناصر علوی دانشکده شهید باهنر کرمان  6. کیوان قصیری استاد یار دانشکده راه آهن دانشکده علم وصنعت ایران    7.فهیمه مرشد سلوک کارشناس دانشکده راه آهن دانشکده علم وصنعت ایران     8. سمانه حسینی سمنائی و کامران زمانی فر دانشجوی دکتری دانشکده فنی مهندسی اصفهان(عضو هیئت علمی کامپیوتر)     9. کار تحقیقی محمد نوری ولیلی صدیق عضو ا نجمن علمی    10. علی برادران هاشمی-  محمد رضا میبدی -   سعید شیری قیدار  دانشگاه کامپیوتر  امیر کبیر     11. پریسا رحما نی -  مهدی داد بخش  - ابولفضل طرقی حقیقت  

انجمن سیستمهای فازی ایران