بخشی از مقاله
چکیده
امروزه با توجه به نیاز جامعه به توسعه و تسهیل حمل و نقل، ارتباطات و انجام امور صنعتی، استفاده از روشهای بهینهسازی به علت توانایی در کاهش هزینه و زمان، بیش از پیش در نظر گرفته میشوند. مسئله فروشنده دورهگرد - TSP - یکی از مسائل مشهور بهینهسازی است که تا کنون راه حل قطعی برای آن ارائه نشده است. از این رو بکارگیری روشهای هوش جمعی موثر است. در این تحقیق مسئله فروشنده دورهگرد با استفاده از الگوریتم جریان آب - WFA - ارائه شده است. روش پیشنهادی با استفاده از دادههای استاندارد DIMACS مربوط به سایت رقابت بینالمللی در خصوص مسئله TSP مورد ارزیابی قرار گرفته است. نتایج حاصله نشان میدهد ویژگیهای عملگرهای انشعاب، ادغام، تبخیرو بارش و همینطور دخیل بودن اندازه حرکت و قانون جاذبه موجب شده است تا سرعت و دقت قابل قبولی در حل مسئله مذکور نشان داده شود.
کلید واژه- الگوریتم جریان آب، مسئله فروشنده دورهگرد، هوش جمعی
-1 مقدمه
بعضی از مسائل وجود دارند که با افزایش ابعاد آنها، زمان حلشان به طور نمایی افزایش مییابد. این مسائل، مسائل بهینهسازی ترکیبی هستند، که زمان حل آنها به صورت تابعی غیر چند جملهای است. مسئله فروشنده دوره گرد یکی از آنها میباشد. با توجه به اهمیت و کاربرد بسیار زیاد TSP در حوزههای مختلف مهندسی از جمله تعیین مسیر بهینه انتقال داده در شبکههای کامپیوتری، مسیر حرکت روبات و بسیاری از مسائل جایگشتی، حل آن به روشهای متفاوت صورت گرفته است. مسئله فروشنده دورهگرد میتواند متقارن یا نامتقارن باشد که در حالت متقارن فاصله دو شهر به جهت حرکت بستگی ندارد. علاوه بر فروشنده دورهگرد معمولی، گونههای متعددی از این مسئله وجود دارد که از آن جمله میتوان به فروشنده دورهگرد با پنجره زمانی و فروشنده دورهگرد دورهای اشاره نمود.
برای حل مسئله فروشنده دورهگرد از روشهای مختلفی استفاده شده است. به عنوان مثال الگوریتمهای هوش جمعی در حل مسئله مذکور کاربرد دارند. الگوریتم جریان آب یکی از الگوریتمهای هوش جمعی است که به دلیل ماهیت جستجوی محلی دینامیکی موجب اجتناب از جستجوهای زاید و فرار از نقاط بهینه محلی میشود.در حل مسئله فروشنده دورهگرد با استفاده از الگوریتم جریان آب از داده های استاندارد DIMACS در خصوص مسئله TSP استفاده شده است، و نتایج بدست آمده نشان می دهد که الگوریتم جریان آب در برخی داده ها نتایج بهتری داشته است. سازماندهی این مقاله به این صورت میباشد: در بخش دوم به مرور تحقیقات مرتبط پرداخته و در بخش سوم و چهارم گزارشی از نحوه پیاده سازی و ارزیابی مسئله مورد نظر ارائه شده است. در بخش پایانی نتیجهگیری بیان میگردد.
-2 تحقیقات مرتبط
یکی از مسائلی که در علوم مختلف کاربرد دارد، مسئله پیدا کردن کوتاهترین مسیر میان راس های یک گراف است. این گراف نگاشتی از مسئله مورد نظر است و میتواند مفاهیم مختلفی داشته باشد که از جمله آنها میتوان به راههای موجود در نقشه جغرافیایی اشاره کرد. در این حالت هر راس گراف بیانگر یکشهر و هر یال آن بیانگر راه ارتباطی میان شهرها است. آنچه که در مورد نقشههای جغرافیایی از اهمیت خاصی برخوردار است، پیدا کردن کوتاهترین مسیر موجود میان این شهرها است، به نحوی که با شروع از یک شهر و پیمایش تمامی شهرها مجددا به شهر اول برگردیم، با فرض اینکه هر شهر فقط یک بار پیمایش گردد. این موضوع در میان محققان به عنوان مسئله فروشنده دوره گرد - - TSP شناخته شده میشود، که به دلیل گستردگی یا بیشتر شدن ابعاد، جزء مسائل NP-Hard میباشد .[2 ,1]برای حل مسئله فروشنده دورهگرد از روشهای مختلفی استفاده شده است، به عنوان مثال الگوریتمهای هوش جمعی در حل مسئله مذکور کاربرد دارند .[6-3 ,1]
الگوریتم جریان آب - WFA - یکی از الگوریتمهای هوش جمعی است .[9 ,7] این الگوریتم از رفتار طبیعی جریان آب از سطح بالاتر به سطح پائین تر تقلید میکند و همزمان دقیقا با فرایند جستجو برای حل بهینه مسئله عمل میکند.Yang &Wang - 2007 - الگوریتم جریان آب را برای جبران کمبود الگوریتم هایی نظیر شبیهسازی تبرید و ژنتیک ارائه کردند. الگوریتم فوق دارای تعداد پویا و متعدد از جریانها می باشد .[7] تلاش زیادی در تطبیق رفتار WFA برای حل بسیاری از مسائل بهینه سازی ترکیبی انجام شده است. به عنوان مثال برای حل مسئله طراحی بهینه خطوط تولید ساخت سلول از الگوریتم جریان آب استفاده شده است. پردازش سلول یکی از مهمترین گام ها در ساخت سلول است. برای بدست آوردن راه حل های بهینه در یک زمان قابل قبول، بخصوص برای مسائل با سایز بزرگ دشوار است. تحقیقات گسترده ای به مسائل ساخت سلول اختصاص داده شده است و روش های مختلفی برای شناسایی سلولهای ماشین ارائه شده است .[9]
در مسئله ساخت سلول از الگوریتم جریان آب استفاده و یک الگوریتم اکتشافی - WFACF - برای مسئله پردازش سلول گسترش داده شده است. این روش یک الگوریتم جریان آب را با استفاده از اپراتورهای متناسب با ضریب تشابه برای ایجاد راه حلهای سریع اولیه برای بهبود بعدی ترکیب میکند. در تحقیق گفته شده در حل مسئله ساخت سلول 37 مسئله مورد آزمایش قرار گرفته و در مقابل چندین الگوریتم مقایسه شد. WFACF نشان داد که اجرای بهتری نسبت به دیگر روشهای الگوبرداری در ارائه حل، از نظر کارائی و تاثیر بخصوص در مسائل با سایز بزرگ دارد .[9]همانطور که در حل مسئله ساخت سلول جهت بهبود راه حل از تطبیق رفتار الگوریتم جریان آب استفاده شده است، رویکرد این الگوریتم بر روی مفهوم استفاده ازجریان پویا و تکنیک هایی برای تعادل کشف راه حل و استخراج و بهرهبرداری از آن میتواند در مسائلی نظیر فروشنده دوره گرد به عنوان روش نوین و کارا در تکنولوژی بهینهسازی مکاشفهای به شمار آید.
-3 روش ارائه شده
الگوریتم جریان آب یک الگوریتم اکتشافی جدید است که اخیرا توسط دانشمندان تایوانی ابداع شده است. در این الگوریتم عوامل حل به عنوان جریانهای آب با پیمودن سطح زمین شبیه سازی می شوند، و با توجه به نیروی گرانش، جریان آب از ارتفاعات بالاتر به ارتفاعات پائینتر حرکت میکنند.
-1-3 حل مسئله TSP با استفاده از WFA
الگوریتم جریان آب یک الگوریتم اکتشافی نوین است که برای حل مسائل بهینه سازی ترکیباتی به کار می رود. با توجه به ماهیت الگوریتم جریان آب که در آغاز فقط با یک جریان آب در یک موقعیت تصادفی بیان می شود، بنابراین یک توالی تصادفی از تعداد تمامی شهرهای مورد نظر در مسئله TSP ایجاد میگردد. جایگشت به دست آمده به عنوان موقعیت راه حل آغازین، جواب اولیه برای مساله بهینه سازی می باشد، و مقدار هزینه محاسبه شده با توجه به موقعیت مورد نظر به عنوان وضعیت آن موقعیت در نظر گرفته می شود تا در گام های بعدی مورد ارزیابی قرار گیرد.
از طرفی در مسئله مورد نظر قصد داریم تا از موقعیت هایی که اخیرا مورد جستجو قرار گرفته اند را مورد بررسی قرار دهیم تا موقعیت های غیرمجاز و پیموده شده را از مجموعه کاندیدای همسایگی و مجاور حذف کنیم. بنابراین با ایجاد سه ساختار اول، دوم و سوم در راه حل اصلی، موقعیتها را در لیست تابو تعریف میکنیم.هر زیرجریان، یک راه حل جدید با توجه به جریانی است که از آن انشعاب مییابد، در مراحل بعدی از بین زیرجریانهای تولیدی، n تا از بهترینها را مورد ارزیابی قرار میدهیم . اگر تعداد زیرجریانها در انشعاب جریان محدود نباشد، منابع محاسباتیمورد استفاده قرار خواهند گرفت. بنابراین حد بالای ازتعداد زیرجریانهای انشعاب یافته از یک جریان اعمال شده است. برای انجام این طرح، تعداد زیرجریانهای انشعاب یافته از جریان i با استفاده از رابطه - 1 - حاصل می گردد:
