بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
حل مساله فروشنده دوره گرد با استفاده از الگوریتم کرم شب تاب بهبود یافته
چکیده
امروزه تعداد زیادي از مسائل بهینه سازي دردنیاي ما وجود دارد که به روش دقیق قابل حل نیستند. چنین مسائلی را مسئله NP کامل می گویند. روشهاي بهینه یابی موجود براي حل مسائل NP کامل بطور عمده شامل تعداد زیادي متغیر و محـدودیت مـی باشند که از کارایی عملی آنها در حل مسائل با ابعاد واقعی می کاهد. یکی از مسائل NP کامل که زمینه هاي کاربردي بسیاري در دنیاي واقع دارد مسئله فروشنده دورگرد (Travelling Salesman Problem) می باشـد کـه از مسـائل بسـیار مهـم در تئوري گراف ها است. اکثر مسائلی که می توان آن ها را با مسئله فروشنده دورگرد مدل کرد داراي مقیاس خیلی بزرگ هسـتند.
بطوري که الگوریتم هاي موجود قادر به حل آن ها در یک زمان قابل قبول نیستند. در حال حاضر بهترین روش براي حـل ایـن نوع مسائل استفاده از الگوریتم هاي فرا ابتکاري بعنوان ابزار جستجو می باشد. در این مقاله مسئله فروشنده دوره گرد با اسـتفاده از الگوریتم کرم شب تاب بهبود یافته حل و نتایج ان با نتایج حاصل از چند الگوریتم بهینه سازي دیگر مقایسه شده است. نتایج حاصل از این مقاله بیانگر توانایی کارایی الگوریتم پیشنهادي در بهینه یابی مساله فروشنده دوره گرد می باشد
.کلمات کلیدي: فروشنده دوره گرد، الگوریتم کرم شب تاب، مسئلهNP-Hard ، جهشK-Opt
1 -مقدمه
:بدون شک مسئله فروشنده دوره گرد یکی از معروفترین مسائلی است که در زمینه هوش مصـنوعی مطـرح اسـت. مسئله فروشنده دوره گرد یک مسئله بهینه سازي گسسته کلاسیک است که جزء مسائل NP-Hard می باشـد و تـا کنـون راه حل دقیقی براي حل آن ارائه نشده است. مساله فروشنده دوره گرد چیست ؟در این مسئله هـدف یـافتن یـک دور همیلتـونی بـا کمترین هزینه در گراف شهر هاي مورد نظر است .[1] در این مسئله فروشنده دوره گردي قصد رفتن به تعـدادي شـهر را دارد که فاصله بین شهرها ثابت بوده و می بایست هر شهر فقط یک بار بازدید شود و فروشنده دوره گرد به شهر اولیه باز گردد، هدف در این مساله یافتن کوتاهترین مسیر ممکن است. به این مسیر تور (Tour)گفته می شود.
این مسئله ابتدا در دهه 1800 توسط ویلیام همیلتون ایرلندي و توماس کرکمن بریتانیایی مطرح شد و سال ها بعد در دهه 1930 شکل عمومی آن بوسیله کارل منگر از گروه ریاضی دانشگاه هاروارد و هاسلر ویتنی از دانشـگاه پرینسـتون مـورد مطالعـه قـرار گرفت.[1] این مسئله در عین سادگی کاربردهاي فراوانی دارد که برخی از آنها عبارتست از: زمان بنـدي وسـیله نقلیـه[2] بهینـه کردن مسیر حرکت جهت انتقال کالا به نقاط مختلف، بهینه کردن مسیر حرکت جهت محموله هاي پستی، مسیر یابی خـودرو [3]و کمینه کردن مسیر حرکت یک تور مسافرتی..
2 -مبانی نظري و پیشینه پژوهش
تا کنون روش ها و الگوریتم هاي مختلفی براي حل مسئله فروشنده دوره گرد مطرح شده است که هر کدام نقاط ضعف و قوت خود را دارند اما آنچه که حائز اهمیت است استفاده از روش و یا الگوریتمی است که در کمترین زمان ممکن بهترین تور را پیدا نماید. برخی از این الگوریتم هاي فراابتکاري بکار رفته جهت حل مسئله فروشنده دوره گرد، عباتند از :الگوریتم ژنتیک([4](GA، ازدحام ذرات([5](PSO، کلونی مورچگان([6](ACO،الگوریتم ممتیک([7] (Memeticو....که در هر یک از این الگوریتم ها می توان با تغییر پارامترها و بکار بردن تکنیک هایی به نتایج مطلوبتري دست پیدا کرد. سارانیا و وجاینتاي، در سال 2014 یک روش براي حل مشکل فروشنده دوره گرد، بر پایه جستجوي ممنوع و الگوریتم هاي زیستی شامل الگوریتم بهینه سازي مورچگان، الگوریتم فاخته و الگوریتم زنبور عسل ارائه کرده اند.[8] یانگ و همکاران، در سال 2012 یک رویکرد بهینه سازي براي کاهش هزینه هاي پردازش مرتبط با مسیریابی مورچه ها در ACO مرسوم مطرح کرده، و با استفاده از استراتژي تنوع فردي، ACO را بهبود دادند.[9] بطوري که سرعت و همگرایی ACO تا حد زیادي افزایش یافت. آنها این رویکرد را در حل مسئله فروشنده دوره گرد بکار بردند. ریزك االله و همکاران، در سال 2013 یک الگوریتم ترکیبی به نام ACO-FA، که الگوریتم مورچگان (ACO) را با الگوریتم کرم شب تاب (FA) براي حل مسائل نامحدود ادغام میکند، ارائه داده اند.[10] لاس زولوکوتا [11] الگوریتم کرم شبتاب را براي حل مساله فروشنده دوره گرد چند گانه به کار برد.دراین مقاله ما از یک روش جدید براي حل مساله فرمشنده دوره گرد با الگوریتم کرم شبتاب استفاده نمودیم.
-1-2 مدل ریاضی مسئله فروشنده دوره گرد:
مسئله فروشنده دوره گرد انواع مختلفی دارد و مهمترین آنها نوع متقارن و نامتقارن است .در مسئله فروشنده دوره گرد متقارن فاصله دو شهر A و B برابر است ،در حالی که در حالت نامتقارن (ATSP) به این صورت نمی باشد.[1]
مسأله TSP را می توان به صورت یک گراف کامل بدون جهت در نظر گرفت که در آن :
مجموعه کمانها و نشان دهنده مجموعه گره هاست. اگر از i به j مسیر باشد و اگر نباشد است. تعداد جواب هاي شدنی مسئله، برابر است با براي تعداد شهرها می باشد. در واقع این عدد برابر با تعداد دورهاي همیلتونی در یک گراف کامل با Nرأس، است . فرم ریاضی مسئله بصورت زیر می باشد:
-2-2 الگوریتم کرم شب تاب:
ابن الگوریتم نخستین بار درسال 2009 توسط Xin-She-Yang ابداع شد که یک الگوریتم بهینه سازي پیوسته براي حل مسایل پیوسته و گسسته میباشد.الگوریتم کرم شب تاب، از کرم هاي شب تابی که از نورهاي کوتاه و ریتمیک براي جذب شکار ، سیستم محافظتی و یا جذب جفت استفاده میکنند، الهام گرفته شده است.. در الگوریتم کرم شب تاب، دو موضوع مهم وجود دارد، تغییرات شدت نور و فرموله کردن جذابیت. براي سادگی، ما همیشه می توانیم فرض کنیم که جذابیت کرم شب تاب توسط نور آن تعیین می شود که نور ان نیز به نوبه خود با تابع هدف مرتبط می شود. جاذبه متناسب با درخشش بوده و کرم شب تاب کم نور تر به کرم شب تاب روشن تر جذب می شود و اگر هیچ نوري نباشد کرم شب تاب به صورت تصادفی حرکت می نماید.[12]
فاصله و تحلیل نور توسط هوا، کرم شب تاب را تنها براي فاصله محدودي قابل مشاهده میکند. یک کرم شب تاب را می توان بصورت یک منبع نور نقطه اي در نظر گرفت. می دانیم که شدت نور در فاصله خاص r از منبع نور از قانون مربع معکوس پیروي می کند. این قانون بیان می کند که، شدت نور I با افزایش فاصله r کاهش می یابد.
همانطور که گفته شد هوا نیز نور را تحلیل می برد تا با افزایش فاصله ضعیف تر و ضعیف تر شود. در ساده ترین حالت می توان شدت نور یک منبع نقطه اي با ضریب تحلیل γ ، در فاصله r را بصورت رابطه (2) در نظر گرفت. .( شدت نور درr=0 است)
و از آنجاکه جذابیت کرم شب تاب متناسب با شدت نور دیده شده توسط کرم شب تاب مجاور است، جذابیت کرم هاي شب
تاب بصورت رابطه (3) تعریف می شود.( جذابیت در r=0 است)
فاصله هر دو کرم شب تاب i و j برابر با فاصله دکارتی ان ها است.
همچنین روشنایی با تابع هدف متناسب است. بنابراین به روز رسانی مکان براي هر جفت از کرم هاي شب تاب و بصورت رابطه (5) است:
الگوریتم کرم شب تاب با سه فرض زیر فرموله شده است:
1. همه کرم هاي شب تاب تک جنسی هستند، به طوري که یک کرم شب تاب تمام کرم هاي شب تاب دیگر را جذب میکند.
2. جذابیت متناسب با روشنایی است، و براي هر دو کرم شب تاب، کرم شب تاب داراي روشنایی کمتر به کرم شب تاب روشن تر، جذب می شود.
3. اگر کرم شب تابی روشن تر از دیگر کرم شب تاب وجود نداشته باشد آنگاه کرم شب تاب به طور تصادفی حرکت خواهد کرد. شبه کد الگوریتم کرم شب تاب بصورت زیر است.
4.
3 -توسعه فرضیهها و الگوي مفهومی :
در الگوریتم هاي فرا ابتکاري امکان به دام افتادن مسئله در یک مینیمم محلی و همگرایی سریع وجود دارد . این امر باعث عدم رسیدن به پاسخ مناسب می شود. علاوه بر این در حل این مسئله می بایست الگوریتم باید کمترین میزان پیچیدگی را دارا باشد. زیرا پیچیدگی باعث افزایش هزینه می گردد لذا براي حل این مشکل می توان از تکنیک هایی نظیر جهش استفاده نمود که سعی در بهبود جواب ها دارد. عملگر جهش یک عملگر گسترشی بوده که باع تعریض نواحی کشف شده میشود.علاوه بر این در یک مسئله TSP براي بدست امدن کوتاهترین مسیرتا جایی که امکان دارد نباید یالهاي گراف با یکدیگر تلاقی داشته باشند. زیرا تلاقی باعث افزایش طول تور میگردد.همچنین استفاده از جهش سرعت رسیدن به پاسخ مناسب را افزایش می دهد.
3-1 محاسبه فاصله بین دو شهر:
براي محاسبه فاصله بین دو نقطه میتوان از روش هایی مانند همینگ ،اقلیدسی و ...استفاده نمود،در این مقاله ما شهرها را به صورت آرایه اي از مختصات X و Y در صفحه دو بعدي در نظر گرفته ایم و براي محاسبه فاصله بین شهرها از فرمول فاصله اقلیدسی بیان شده در رابطه (2) استفاده نموده ایم.
بنابراین مشخصات شهر ها بصورت یک ماتریس مربعی متقارن ایجاد می شود که قطر اصلی آن صفر خواهد بود چرا که فاصله هر شهر از خودش برابر صفر است.بنابراین داریم که:
به این ترتیب یک ماتریس مربعی متقارن از فاصله بین شهرها ایجاد می شود.
3-2 اپراتورهاي جهش :
براي کوتاه کردن مسیر یافته شده در الگوریتم کرم شب تاب می توان از جهش هاي مختلفی بهره برد.مانند جهش تصادفی ،Flipping و جابجایی و حریصانه و....این امر باعث میشود تا از به دام افتادن الگوریتم کم شبتاب در بهینه محلی جلوگیري به عمل آید. با این کار راه حل جدید با راه حل قبلی جایگزین مشود.ما این جهش ها را بر روي اعضا و global best انجام دادیم .جهش هاي مورد استفاده در این مطالعه در ادامه معرفی شده اند.
-1جهش جابجایی:((swapping mutation
این جهش را میتوان یه صورت تعداد نقاط اجرا کرد.این روش از پرکاربردیترین روش ها میباشد.عملگر این جهش را در حالت دو نقطه اي در شکل زیر آمده است.
٢-جهش معکوس کننده: (Inversion Mutation)
در این روش دو المان را به صورت تصادفی انتخاب میکنیم و سپس قطعه محصور بین آنها را معکوس کرده و در جاي خود قرار میدهیم.
٣-جهش الحاقی:((Insertion Mutation
در این روش دو المان را به صورت تصادفی انتخاب میکنیم یکی از دو المان را به بعد از دیگر المان انتخاب شده میبریم.
(K-Opt mutation) :k-Opt4- جهش
این جهش یکی از موثرترین جهش ها براي مسئله فروشنده دوره گرد میباشد. این جهش با بررسی مسیر حرکت و انتخاب چهار نقطه به فاصله K در صورتی که طریقه اتصال نها داراي پیچ خوردگی باشد پیچ خوردگی میان آنها را باز کرده وطول مسیر را
کاهش میدهد در شکل ١ مسیر بهینه شده شکل ٢ نمایش داده شده است.
-1 چهار نقطه تصادفی I,j,n,m را واقع در مسیر حرکت انتخاب مینماییم. -2 طول فواصل بین نقاط را با استفاده از رابطه زیر بررسی مینماییم.
|(i,j)|+|(n,m)|>|(i,m)|+|(n,j)|
