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

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

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

با وجود آن که فقط ۲ درصد از گونه های حشرات دارای زندگی اجتماعی هستند، اما بیش از ۵۰ درصد توده زیستی حشرات را تشکیل می دهند. این میزان در برخی جاها، مانند جنگل های بارانی آمازون به بیش از ۷۵ درصد می رسد. منظور از زندگی اجتماعی، تجمع تعداد زیادی از یک گونه خاص در قالب یک مجموعه یا کُلونی (Colony) و تعامل آن ها با همدیگر است. همه مورچه ها و موریانه ها و همچنین برخی از گونه های زنبورها در قالب کلونی زندگی می کنند. اجتماع حشرات می توانند مسائلی را با همکاری یکدیگر حل و فصل نمایند که هیچ یک از اعضای آن اجتماع به تنهایی قادر به حل آن ها نمی باشد. اکثر این مسائل به صورت مسائل بهینه سازی قابل بیان هستند. به عنوان مثال تلاش حشرات برای یافتن کوتاه ترین مسیر در هنگام جستجو برای غذا، تخصیص مناسب نیروهای کاری برای انجام کارهای مختلف، و همچنین طبقه بندی محل های حاوی تخم ها و نوزادان، از جمله مسائل بهینه سازی هستند که حشرات اجتماعی با همکاری یکدیگر آن ها را حل می کنند. این مسائل همگی دارای معادلی در بین مسائل بهینه سازی روزمره , تخصصی ما انسان ها هستند.

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

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

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

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

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

الگوریتم بهینه‌سازی کلونی مورچگان (ACO) یک روش احتمالی برای حل مسائل محاسباتی است که می‌توانند به شکل یافتن مسیرهای مناسب و خوب در طول گراف، تعریف شوند. این الگوریتم عضوی از خانواده الگوریتم‌های کلونی مورچگان و دسته هوش ازدحامی (Swarm Intelligence) است و یک الگوریتم بهینه‌سازی متاهیورستیک به شمار می آید. اولین الگوریتم این خانواده در پایان نامه دکتری مارکو دوریگو در سال ۱۹۹۲ معرفی شد که هدف آن جستجوی مسیر بهینه در یک گراف، بر اساس رفتار مورچه‌ها در جستجوی مسیری بین کلونی و منبع غذا بود. این ایده از آن زمان برای حل کلاس وسیع‌تری از مسائل عددی به کار رفته و در نتیجه مسائل زیادی پدیدار شده‌اند که جنبه‌های مختلف رفتار مورچه‌ها را مطرح کرده‌اند.

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

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

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

شبه کد (Pseudo-Code) مربوط به یک الگوریتم مورچگان در حالت کلی، به صورت زیر است که المان های آن، نیازمند تعیین جزئیات برای پیاده سازی نهایی هستند. در نسخه های مختلف الگوریتم مورچگان، این مولفه ها، دارای ساختارهای کم و بیش متفاوتی هستند.

procedure  ACO_MetaHeuristic                 // تابع اصلی

           while   (not_termination)               // بررسی شرط خاتمه و حلقه تکرار

                     generateSolutions()              // ایجاد راه حل

                     daemonActions()                  // عملیات کمکی

                     pheromoneUpdate()            // به روز رسانی فرومون

           end while                                    // پایان حلقه تکرار

end procedure                                      // پایان تعریف تابع اصلی

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

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

نخستین نسخه الگوریتم ACO که به نام سیستم مورچگان (Ant System) خوانده می‌شود، برای اولین بار، برای حل مسئله فروشنده دوره‌گرد به کار رفته است. این الگوریتم نسبتا ساده است و بر مبنای عملکرد جمعی گروهی از مورچه هاست که هر کدام، یک مسیر از مسیرهای ممکن متشکل از شهرها را طی می کنند.

در هر مرحله، هر مورچه بر طبق قوانین زیر از یک شهر به شهر دیگر حرکت می‌کند:

  1. هر شهر تنها باید فقط یک بار ملاقات شود.
  2. شهری که در یک نقطه دور واقع شده، شانس کمی برای انتخاب شدن دارد(قابلیت دید).
  3. هر چه رد فرومون در مسیر اتصال بین دو شهر (لبه) شدیدتر باشد، احتمال اینکه آن لبه انتخاب شود بالاتر است.
  4. بعد از اتمام سفر، مورچه فرومون بیشتری روی تمام لبه‌هایی که از آن گذشته قرار می‌دهد، البته اگر سفر کوتاه باشد.
  5. بعد از هر تکرار، فرومون تبخیر می‌شود.

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

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

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

مراجع مطالعاتی و منابع آموزشی مهم

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

کتاب های خارجی

Ant Colony Optimization عنوان:  Ant Colony Optimization
ترجمه عنوان: بهینه سازی کلونی مورچگان
مولف: Marco Dorigo, Thomas Stützle
سال چاپ: ۲۰۰۴
انتشارات: A Bradford Book
لینک دسترسی: لینک
Evolutionary Optimization Algorithms عنوان: Evolutionary Optimization Algorithms
ترجمه عنوان: الگوریتم های بهینه سازی تکاملی
مولف: Dan Simon
سال چاپ: ۲۰۱۳
انتشارات: Wiley
لینک دسترسی: لینک
Computational Intelligence: An Introduction عنوان:  Computational Intelligence: An Introduction
ترجمه عنوان: مقدمه ای بر هوش محاسباتی
مولف: A. P. Engelbrecht
سال چاپ: ۲۰۰۷
انتشارات: Wiley
لینک دسترسی: لینک
Ant Colony Optimization عنوان: Ant Colony Optimization
ترجمه عنوان: بهینه سازی کلونی مورچگان
مولف: Julia Pizzo
سال چاپ: ۲۰۱۵
انتشارات: CLANRYE INTERNATIONAL
لینک دسترسی: لینک
Swarm Intelligence: From Natural to Artificial Systems عنوان: Swarm Intelligence: From Natural to Artificial Systems
ترجمه عنوان: هوش ازدحامی: از سیستم های طبیعی تا مصنوعی
مولف: Bonabeau, Guy Theraulaz, Marco Dorigo
سال چاپ: ۱۹۹۹
انتشارات: Oxford University Press
لینک دسترسی: لینک
Metaheuristics: From Design to Implementation عنوان: Metaheuristics: From Design to Implementation
ترجمه عنوان: الگوریتم های فرا ابتکاری: از طراحی تا پیاده سازی
مولف: El-Ghazali Talbi
سال چاپ: ۲۰۰۹
انتشارات: Wiley
لینک دسترسی: لینک

کتاب های فارسی

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

 

منابع آموزشی آنلاین

 مجموعه فرادرس های الگوریتم مورچگان در متلب عنوان: مجموعه فرادرس های الگوریتم مورچگان در متلب
مدرس:  دکتر سیدمصطفی کلامی هریس
مدت زمان: ۶ ساعت و ۴۹ دقیقه
نحوه استفاده: دریافت به صورت لینک دانلود و بر روی DVD
زبان: فارسی
نحوه آموزش: تئوری و عملی
ارائه دهنده: سازمان علمی-آموزشی فرادرس
لینک دسترسی: لینک
 وبسایت الگوریتم مورچگان عنوان: وبسایت الگوریتم مورچگان
نحوه استفاده: آموزش های متنی و بعضا ویدئویی
زبان: انگلیسی و چند زبان دیگر
نحوه آموزش: تئوری
ارائه دهنده: افراد مختلف
لینک دسترسی: لینک
0 پاسخ

ارسال یک پاسخ

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

پاسخ دهید

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