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