بهینه سازی کلونی مورچگان (ACO) در چندین حوزه گوناگون مهندسی

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

هوشمندی دسته جمعی (SI) یک رشته رو به رشد حوزه مطالعاتی است که حاوی رویکرد نسبتاً مطلوبی نسبت به روش های سنتی برای حل مسئله  غالب حوزه های مهندسی است. SI با تقلید آموخته های حاصل از رفتار اجتماعی حشرات و جانوران برای نمونه: ACO، زنبور عسل بدلی (ABC)، مگس آتش (FF) و بات عسل توسعه یافته است که در آن ACO، زمینه ” الگوریتم مورچگان ” الگوهایی را که از مشاهدات رفتاری کلونی واقعی مورچگان آموخته شده مطالعه نموده است. الگوهای ACO برای طراحی الگوریتم های نو جهت حل مسائل  بهینه سازی و کنترل توزیع استفاده می شود. رفتار جستجوگرانه، تقسیم کار، طبقه بندی نوزادان و حمل و نقل مشارکتی جنبه های مختلف رفتار کلونی مورچگان است که از مورچگان واقعی الهام گرفته و بر اساس این الهامات انواع مختلفی از الگوریتم مورچگان در سالیان اخیر پیشنهاد شده اند که در آن ACO، از رفتار جستجوگرانه کلونی های مورچگان و اهداف مسائل بهینه سازی گسسته الهام گرفته است.

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

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

گاس، آرون، دنیوبورگ و پاستیلز (1989) مورچه های مختلف آزمایش پل دوگانه بالا را که در آن یک پل به صورت معنی داری طولانی تر از دیگری است بررسی نمودند، به پل دوگانه در شکل 1 رجوع کنید. در این مورد، مورچه ها تصادفاً پل کوتاهی را برای رسیدن به لانه اولویت دارد انتخاب می کنند. بنابراین، پل کوتاه تراکم بیشتری از فرومون را زودتر از پل طولانی دریافت می کنند و این واقعیت احتمال انتخاب پل کوتاه تر را برای مورچه های دیگر افزایش می دهد. دنیوبورگ ، آرون، گاس، و پاستلس (1990) یک الگو احتمالی مشاهده رفتار واقعی مورچگان نشان دادند. که در آن، فرض می شود که در یک لحظه معین از زمان، مورچگان  M₁  از پل اول استفاده می کنند و مورچگان M₁   از دومین، احتمالاً “p1” برای یک مورچه منتخب اولین پل هست:

که در آن پارامترهای K و H ثابت هستند و در داده های آزمایش گنجانده شده اند. با تغییر این مقادیر K و H  تاثیر مسیر کوتاه تر و تاثیر از راه تراکم کمتری را می توان به دست آورد. در این آزمایش دو پل، احتمال از پل دیگر P ₂، هست: p2=1-p1.

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

سیستم مورچگان، سیستم کلونی مورچگان و شبکه مورچگان ارائه شده توسط (دوریگو و گامباردلا 1997؛ دوریگو، مانیزو و کولورنی 1996، دوریگو و استوتزل 2004) اثر قابل توجهی بر ACO داشته است. دوریگو  و همکاران (1996)  قانون احتمالات ساده را به کار بردند و دوریگو  و گامباردلا  (1997) قانون حالت گذار را برای الگوی تصمیم گیری اعمال کردند. با توجه به دوریگو و همکاران.(1996)، نتو و فیلو (2011)، ویژگی های زیر برای الگوی مورچگان شرح داده شد:

• حضور مورچگان در محیط نشان دهنده یک گراف ریاضی است، مورچگان همیشه یک گره را در یک گراف اشغال می کند که نشان دهنده یک فضای جستجو است. این گره نامیده می شود.
• این موضوع یک حالت اولیه دارد.
• اگرچه این موضوع نمی تواند کل گراف را حس کند، بلکه آن می تواند دو نوع اطلاعات در مورد محله جمع آوری کردند، (1) وزن هر دنباله به NF متصل. می شود و (2) ویژگی هر یک از فرمون در این آزمایش توسط مورچگان دیگر از همان کلونی نهشته شده است.
• حرکت به سمت یک آزمایش Cij که گره های ‘ i ‘ و ‘J’ گراف را متصل می کند.
• همچنین، می تواند با فرومون های آزمایش C IJ تغییر بابد، در عمل به عنوان “نهشته از سطوح فرومون” نامیده می شود.
• این موضوع می تواند سطوح فرمون تمام مسیرهای امتحان Cij باشد که به یک گره i متصل می شود.
• این می تواند مجموعه ای از امتحان” مسیرهای ممنوع ” را تعیین کند.
• این رفتار شبه تصادفی امکان انتخاب میان آزمایشات مختلف را ممکن می سازد.
• این انتخاب می تواند (و معمولا) تحت تاثیر سطح فرمون باشد.
• این می تواند از گره i به گره j حرکت کند.

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

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

علاوه بر این در این مقاله، تحقیق و کاربرد ACO توضیح داده شده است، سازماندهی این مقاله در شکل 2 ارائه شده است. در این مقاله، نسخه مطالعات قبلی (چاندرا موهان و باسکاران، 2011e) با برخی از پیشرفت های اخیر در بررسی ACO و ACO پیشنهادی بر اساس مسیریابی برای پوشش گسترده و برای کمک به جامعه محققان توسعه یافته است.