توضیحات

پروژه متلب مسئله فروشنده دوره گرد(TSP) با الگوریتم بهینه سازی مورچگان(ACO)

هدف بهینه سازی، یافتن بهترین راه حل از میان تمام گزینه‌های ممکن است. مسائل بهینه سازی ترکیبی، فضای جست‌و‌جوی گسسته‌ای از راه حل های ممکن را ایجاد می کنند و در بسیاری از موارد پیچیدگی-های محاسباتی بالایی دارند و در کلاس NP-hard طبقه بندی می‌شوند. مسئله فروشنده دوره گرد(TSP)  نمونه ای رایج از مسائل NP-Complete و از مشهورترین مسائل بهینه‌سازی ترکیبی است. مسئله TSP را ویلیام همیلتون و توماس گرکمن در قرن 18 میلادی مطرح کردند و سپس در دهه 1930 ریاضی دانان همچون کارل متگر و هاسلر ویتنی به بررسی آن پرداختند. مسئله فروشنده دوره گرد، یافتن کم هزینه ترین مسیری است که از یک شهر شروع شود و از تمامی شهرها دقیقاً یک بار عبور کند و به شهر شروع بازگردد. به عبارت دیگر، یافتن کم وزن ترین دور همیلتونی در یک گراف کامل و محدود، مسئله فروشنده دوره گرد را شکل می‌دهد. این مسئله از مسائل مهم در نظریه پیچیدگی محاسباتی الگوریتم‌ها به شمار می‌آید، که از راه حل آن به عنوان معیاری برای ارزیابی بسیاری از روش‌های آماری و ابتکاری و در حل مسائل بهینه‌سازی ترکیبی استفاده می‌شود. هدف تکنیک‌های ابتکاری در مواجهه با مسائل بهینه سازی، یافتن راه حل نزدیک به بهینه (تقریبی) در زمانی منطقی است. فناوری‌های فراابتکاری نیز راهبردهای سطح بالایی هستند که در فضاهای جست و جو با استفاده از روشهای گوناگون میان تنوع و افزایش فضای جست و جو تعادل ایجاد می‌کنند. نمونه‌ای از فناوری فراابتکاری، محاسبات تکاملی است که الگوریتم‌هایی همچون بهینه سازی کلونی مورچه‌ها را در بر می‌گیرد. استراتژی بهینه‌سازی کلونی مورچه‌ها بر مبنای غریزه حیوانی آنها در یافتن مسیر بهینه بنا شده است. در الگوریتم کلونی مورچه، مورچه برای یافتن منبع غذایی به صورت تصادفی جستجو را شروع می‌کند. وقتی منبع را پیدا می‌کند اسیدی را در مسیر بازگشت به لانه قرار می‌دهد. وقتی مورچه دیگری برای جستجوی غذا راه می افتد همان اسید را دنبال می کند که مورچه دیگر رفته است که کوتاهترین مسیر و بهترین راه حل است.

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

سیستم مورچه ها:

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

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

روش الگوریتم مورچگان(ACO) یک روش بر مبنای جمعیت می باشد و الهام گرفته از رفتار مورچه ها است. در این روش یک سری عوامل نرم افزاری که مورچه های مصنوعی خوانده می شوند برای یافتن جواب به جستجو می پردازند. این روش یک خط مشی تصادفی بوده و رابطه مستقیم با فرمون دارد. این روش اولین بار در سال ۱۹۹۲ توسط Marco Dorigo پیشنهاد شد و Maniezzo و colorni نیز از جمله پیشگامان بنا نهادن این الگوریتم می باشند.

تاثیرپذیری:

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

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

رفتار مورچه ها:

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

شکل مورچه ها بین غذا و لانه در حال حرکتند.

شکل  ناگاه مانعی در سر راه مورچه ها قرار داده می شود.

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

شکل مورچه ها با احتمال ۵۰-۵۰ به سمت چپ و راست حرکت می کنند.

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

شکل به تدریج مسیر کوتاه تر توسط اکثریت مورچه ها انتخاب می شود.

شباهت مورچه های واقعی و مورچه های مصنوعی:

١- هم مورچه های واقعی و هم مورچه های مصنوعی از جمعیتی تشکیل شده اند و مجموعه ای از اعضای غیر وابسته هستند که با یکدیگر همکاری می کنند. به واسطه این همکاری جواب مناسب مساله پیدا می شود.

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

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

۴- مقدار فرومونی که از هر دو گروه بر جای می ماند بستگی به کیفیت جواب بدست آمده دارد. (تابع کیفیت جواب های بدست آمده می باشد.)

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

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

٢- مورچه های مصنوعی دارای حافظه هستند آنها می توانند شرایطی که قبلا مشاهده کرده اند را به یاد بیاورند.

٣- روش فرمون گذاری در هر دو گروه متفاوت است. تنظیم زمان فرمون گذاری در مورچه های مصنوعی و واقعی فرق می کند. در مورچه های مصنوعی بستگی به مساله دارد.

۴- برای کارایی بیشتر، الگوریتم های کامپیوتری می توانند توانایی هایی مضاعف پیدا کنند که در مورچه های واقعی وجود ندارد. از جمله قابلیت جستجوی محلی که بعدأ اشاره خواهد شد.

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

یک مساله بسیار معروف در زمینه بهینه یابی می باشد. در این مساله فروشنده ای می خواهد از شهرهای مشخص شده و معین عبور کند به طوری که اولا از هر شهر فقط یکبار عبور کند و ثانیا کوتاهترین مسیر را انتخاب کرده باشد. در حقیقت هدف از حل این مساله بافتن کوتاهترین مسیر از گراف همیلتون می باشد. G(N,E) که N زیرمجموعه ای گره ها و E مجموعه ای از لبه ها می باشد برای نشان دادن کارایی روش های مختلف بهینه سازی این مساله تبدیل به یک مساله معروف و مهم شده است.

شکل مسئله فروشنده دوره گرد.

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

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

مسئله فروشنده دوره گرد، مسئله ای معروف است که ابتدا مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن در سده ۱۸ مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضی دانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد توجه قرار گرفت. مسئله فروشنده دوره گرد در سال ۱۷۵۹ توسط اویلر به صورت حرکت اسب در صفحه شطرنج بیان شد به نحوی که از تمام نقاط صفحه شطرنج تنها یکبار عبور کند. جواب صحیح برای اسب مسیری بود که از ۶۴ خانه صفحه شطرنج بدون تکرار عبور کند. هر چند نام (Travelling salesman problem) این مسئله، فروشنده دوره گرد نبود. اصطلاح فروشنده دوره گرد در یک کتاب آلمانی در سال ۱۹۳۲ تحت عنوان فروشنده دوره گرد قدیمی به کار برده شد.

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

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