بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
رویکردی نوین برای حل مساله فروشنده دوره گرد با استفاده از موازی سازی الگوریتم های کیاتیکی ژنتیک، رقابت استعماری و شبیه سازی تبرید
چکیده
مساله فروشنده دوره گرد(TSP) 4 جزء مساله های برتری است که بطـور گسـترده توسـط ریاضـیدانان و دانشـمندان علـوم مختلف مورد مطالعه قرار گرفته و یکی از مسائل مشهور بهینه سازی ترکیبی است. اساس آن به این صورت مـی باشـد کـه یک فروشنده دوره گرد می خواهد به N شهر برود و کالای خود را به فروش برساند، به طوری که از هر شهر فقط یک بـار عبور کند و از تمام شهر ها گذشته باشد و در نهایت کمترین مسیر را طی کند. تا کنون الگوریتمی ارائه نشده که بتواند ایـن مساله را در زمان چندجملهای حل کند، در نتیجه این مساله از رده مسائل NP-Hard بوده و برای حـل چنـین مسـائلی مـی
توان با استفاده از الگوریتم های متاهیوریستیک جوابهای نزدیک به بهینه را در زمان معقولی بدست آورد. در این مقالـه یـک
روش جدید با استفاده از موازی سازی الگوریتم های ژنتیک ، رقابت استعماری و شبیه سـازی تبریـد بـر اسـاس نگاشـت آشوب برای حل مساله فروشنده دوره گرد پیشنهاد شده است. هدف از این مقاله بهبود در سرعت همگرایی به همراه دقیقتر شدن جستجو برای محاسبه بهینه سراسری می باشـد. الگـوریتم پیشـنهادی بـا دیگـر الگـوریتم هـای ابتکـاری MHPSO ،
CDPSO ، DPSO ، FRAG_GA ، ICA ، Memetic SOM و CO-Adaptive Net مقایسه شده است. نتـایج آزمایشـات بـر
روی 24 نمونه TSP از کتابخانه TSPLIB نشان می دهد که روش ارائه شده از عملکرد بهتری در مقایسه با دیگر الگـوریتم های ابتکاری برخوردار است.
کلید واژه: فروشنده دوره گرد، الگوریتم رقابت استعماری، الگوریتم ژنتیک، الگوریتم شبیه ساز تبرید، آشوب.
-1 مقدمه
مساله فروشنده دورهگرد (TSP) جزء مساله های برتری است که بطور گسترده توسط ریاضیدانان و دانشمندان علوم
مختلف مورد مطالعه قرار گرفته است. در سال 1800 آقای William Rowan Hamilton در تئوری گراف از مساله فروشنده
دوره گرد استفاده کرد. و در سال 1832 در آلمان به نام مساله فروشنده دوره گرد شناخته شد. فرم کلی این مساله اولین بار
در 1930 توسط Karl Menger ارائه شد، و بعدا توسط Hassler Whitney، مساله TSP در دانشگاه Harvard و Princeton در ایالات متحده معرفی شد. در سالMerrill Flood 1940 این مساله در شرکت RAND در کالیفرنیا مشهور
شد. مساله فروشنده دورهگرد شامل یافتن یک تور بهینه در n شهر است، که در آن فروشنده از یک شهر مشخص، تور را شروع کرده همه شهرها را ملاقات میکند و در پایان تور به شهر مبدا باز میگردد. با این محدودیت که هر شهر فقط و
فقط یکبار ملاقات شود. در نتیجه می توان گفت مساله فروشنده دورهگرد نمونهای از مساله دور همیلتونی است.
مساله فروشنده دوره گرد می تواند متقارن یا غیر متقارن باشد. درحالت متقارن، فاصله بین دو شهر بـا هـم برابـر بـوده و بـه جهت حرکت فروشنده بستگی ندارد. به طور مثال اگر فاصله میان دو شهرj و i با dij نشان داده شود، در صورتی که مقـدار (dij = dji) باشد مساله فروشنده دوره گرد ازنوع متقارن است در غیر اینصـورت نـا متقـارن مـی باشـد. فاصـله شـهر i از
خودش را با dii نشان می دهیم که مقدار آن صفر است و روی قطر اصلی ماتریس می باشد. هـدف مسـاله فروشـنده دوره
گرد پیدا کردن جایگشتی از 1'2'3'…'Q می باشد که کمترین طول را دارد. مدل برنامه ریزی خطـی TSP بـه صـورت زیر است:
که n تعداد شهر ها، i و j شماره شهر ها که عدد صحیح بین یک تا n و dij فاصله شهر i ازj می باشد. TSP یکی از مسائل
بهینه سازی ترکیبی NP-Hard است(.(4 که با افزایش تعدا شهرها پیچیدگی محاسبات به صورت نمـایی بـالا مـی رود کـه
برای حل نمونه های بزرگ در زمان مناسب غیر ممکن است. برای یک مساله متقارن بـا n شـهر، تـور امکـان پـذیر
است. پیچیدگی زمانی مساله TSP، است. با فرض این که زمان مورد نیاز برای ارزیابی یک مسیر باشد، جدول1 رشد سریع مساله TSP را نشان می دهدکه دیگر با روش های برنامه ریزی خطی نمی توان جواب بهینه آن را بـه دسـت آورد.
جدول .1 تعداد مسیر ممکن و تخمین محاسبه زمان r
با وجود واضح بودن حکم مساله فروشنده دورهگرد، این مساله تا حد زیادی چالش برانگیز است، تا به امروز الگوریتمی ارائه نشده که بتواند این مساله را در زمان چند جمله ای حل کند، در نتیجه این مساله از رده مسائل سخت بوده و برای حل آن بیشتر از الگوریتمهای متا هیوریستیک که از سال 1978 به بعد استفاده شد. حل این مساله کاربرد وسیعی در حوزه های مختلف مهندسی از جمله حل انواع مسائل زمانبندی، مسیریابی، جایابی کالا در انبار، جایابی ماشین ها در کارگاه ها، طراحی مدارات چاپی و ... دارد.
الگوریتم پیشنهادی برای حل TSP را می توان 2 دسته طبقه بندی کرد: روش دقیق و روش های تقریبی(یا اکتشافی). در روش دقیق، تضمین راه حل بهینه در تعداد محدود مراحل و تعداد محدودی از شهرها است. پیچیدگی زمانی روش های ارائه شده در این ادبیات، به صورت نمایی با n (تعداد شهرها) افزایش می یابد. برای مثال راه دقیق برای مساله متقارن با
2392 شهر در طی یک دوره بیش از 27 ساعت بر روی سوپر کامپیوتر قدرتمند تعیین شد(.(5 با این حال، روش تقریبی (اکتشافی و فرا اکتشافی) برای پیدا کردن یک راه حل نزدیک به بهینه در زمان مناسب است.
از دهه 1950 روشهای زیادی بر مبنای الگوریتمهای دقیقِ از قبیل الگوریتم شاخه و حدّ و الگوریتم بهبود تصاعدْ
(6) و همچنین الگوریتمهای اکتشافی8 بسـیاری از قبیـل الگـوریتم ژنتیـک7)9 و (8 ، جسـتجوی محلـی9)10 و 10 و (11،
جستجوی حرام12) 11 و (13، شبکه های عصبی14) 12 و 15 و (16 وکلونی مورچگان17)13 و (18 برای حـل مسـاله TSP ارائه شده است. در میان روش های ارائه شده برای حل مسـاله فروشـنده دوره گـرد، الگـوریتم ژنتیـک یکـی از روش هـای
پرکاربرد و موثر است.
روش های زیادی نیز بر اساس الگوریتم های جستجوی محلی برای حل مساله فروشنده دوره گرد ارائه شده اسـت(.(9
برخی محققین مطالعاتی روی الگوریتم های تکاملی ترکیبی14 برای بهتر شدن نتایج حـل مسـاله فروشـنده دوره گـرد انجـام داده اند که در(19 و 20 و (21 قابل مشاهده است. در حالت کلی می توان نتیجه گرفت که ترکیب الگوریتمهـای جسـتجوی
محلی با الگوریتم ژنتیک برای حل TSP، کارایی بالاتری دارد.
در این مقاله یک روش جدید با استفاده از موازی سازی الگوریتم های ژنتیک ، رقابت استعماری و شبیه سازی تبریـد بر اساس نگاشت آشوب برای حل مساله فروشنده دوره گرد پیشـنهاد شـده اسـت. هـدف از ایـن مقالـه بهبـود در سـرعت همگرایی به همراه دقیقتر شدن جستجو برای محاسبه بهینه سراسری می باشد. ساختار ادامه مقاله بـه ایـن شـرح اسـت: در بخش دوم الگوریتم رقابت استعماری، در بخش سوم الگوریتم ژنتیک ، در بخش چهارم الگوریتم شبیه سـازی تبریـد و در بخش پنجم آشوب شرح داده شده است. در بخش ششم الگوریتم پیشنهادی بیان شده و در بخـش هفـتم نتـایج حاصـل از
آزمایش الگوریتمها بر روی مجموعه دادههای تست ارائه شده است. سپس در بخش هشتم نتیجهگیری ذکر شده است.
-2 الگوریتم رقابت استعماری
الگوریتم رقابت استعماری((ICA یکی از قدرتمندترین الگوریتم های تکاملی است که از آن برای حل گسترده وسیعی از مساله های بهینه سازی استفاده شده است.این الگوریتم با مدلسازی ریاضی فرایند تکامل اجتماعی- سیاسی، برای حل مسائل ریاضی بهینه سازی بکار گرفته می شود(ICA .(22 با تعدادی جمعیت اولیه تصادفی که هر کدام از آن ها یک کشور
نامیده می شوند؛ شروع می شود. تعدادی از بهترین عناصر جمعیت به عنوان امپریالیست15 انتخاب می شوند و باقیمانده
جمعیت نیز به عنوان مستعمره16، در نظر گرفته می شوند. همه مستعمرات بین امپریالیست ها بر اساس تابع هزینه تقسیم می شوند. برای مثال، فرض می کنیم که تعداد امپریالیست ها برابر با سه باشد. در این حالت،کشور های چهارم تا ششم ، به عنوان اولین مستعمره امپراطوری17ها فرض می شوند. بعد از آن، کشورهای هفتم تا نهم به عنوان دومین مستعمره امپراطوری انتخاب می شوند. این اقدام برای تمامی کشورها تکرار می شود. .این فرایند در شکل 1 آمده است.
شکل.1 تقسیم مستعمرات در میان امپریالیست ها
بعد از شکل گیری تمامی امپراطور ها، رقابت بین کشور ها آغاز می شود. اول، استعمارگران بسته به قدرتشان، این
مستعمرات را به سمت خود می کشند که موجب موقعیت جدید مستعمرات می شود. این حرکت در شکل 2 نشان داده
شده است.
شکل.2 حرکت مستعمرات به سمت امپریالیست
در این مدل، یک متغییر تصادفی با توزیع یکنواخت و عددی بزرگتر از یک و نزدیک به دو است(در بسیاری از موارد برابر با 2 است)، و همچنین، فاصله میان استعمارگر و مستعمره می باشد.
در حین حرکت، اگر موقعیت مستعمره بهتر از امپریالیست باشد مکانشان جابجا می شود. بعد از آن، الگوریتم با یک امپراطوری جدید ادامه می دهد. قدرت هر امپراطوری از تابع هزینه امپریالیست و مستعمرات تعیین می شود(.(22 رقابت در میان امپراطوری ها بر اساس قدرت شان، مهمترین بخش ICA است که ضعیف ترین امپراطوری، مستعمرات خود را به
تدریج از دست می دهد تا مستعمره ای باقی نماند و امپراطوری های قوی تر، این مستعمرات را تصاحب کرده و بر قدرت
خویش می افزاید(.(22 نتیجه این عمل که امپراطوری، مستعمره ای را نداشته باشد موجب سقوط آن امپراطوری می شود. شمای کلی این توصیف در شکل 3 آمده است.
شکل.3 سقوط امپراطوری ضعیف
پس از مدتی، همه امپراطوری ها، سقوط کرده و تنها یک امپراطوری باقی می ماند و بقیه کشورها تحت کنترل این
امپراطوری واحد، قرار می گیرند. در چنین موقعیتی رقابت استعماری به پایان رسیده و الگوریتم، متوقف می شود.
-3 الگوریتم ژنتیک
الگوریتم ژنتیک در سال 1975 توسط جان هلند18 به صورت تئوری بیان شد(23 و .(24 این الگوریتم تکنیکی است که از تکامل ژنتیکی و اصول انتخاب طبیعی داروین به عنوان الگوی حل مساله استفاده می کند و بر روی جمعیتی از راه حـل
های بالقوه به جستجوی راه حل نهایی می پردازد. در هر نسل، بهترین های آن نسل انتخاب می شوند، و پس از زاد و ولد،
مجموعه جدیدی از فرزندان را تولید می کنند. در این فرآیند افراد مناسب تر با احتمال بیشتری در نسل هـای بعـدی بـاقی خواهند ماند. در آغاز الگوریتم، تعدادی از افراد(جمعیت اولیه) به صورت تصادفی ساخته شده و تابع هدف برای تک تـک
آن ها ارزیابی می شود. اگر شرط رسیدن به جواب برقرار نباشد، نسل بعدی با انتخاب والدین بر اسـاس میـزان برازنـدگی شان تولید می شود و فرزندان با احتمال ثابتی دچار جهش می شوند. سپس میزان برازندگی فرزندان جدید محاسبه شـده و
جمعیت جدید، از جایگزینی فرزندان با والدین ایجاد می شود و این فرآیند تا برقرار شدن شرط خاتمه تکرار می شود.
-4 الگوریتم شبیه سازی تبرید
الگوریتم شبیه سازی تبرید(SA) 19، در سال 1980 توسط کیرکپاتریک 20 و همکارانش ارائه شد. SA رویکردی است بر مبنای مدل مونت کارلو که برای مطالعه رابطه بین ساختار اتمی، آنتروپی و دما در طول بازپخت یک ماده استفاده می شود. طی فرآیند شبیه ساز سرد کردن فلزات، یک ماده تا دمایی بیشتر از دمای ذوبش گرم می شود و سپس به تدریج، دمای آن پایین آورده می شود. نحوه ی کاهش دما بسیار کند و در حدی است که ماده در تعادل ترمودینامیکی است. به عبارت دیگر، دمای جسم آنقدر ثابت می ماند که بهترین ساختار بلوری یا کمترین انرژی در آن دما تشکیل شود. در
الگوریتم SA، جواب های پیشنهادی برای مساله، در دمای بالاتر قرار دارند و اغلب جواب های مناسبی نیستند. سپس
متغییری که نقش دما را بر عهده دارد به مرور زمان کاهش داده می شود تا به این ترتیب جواب های بهتری در دماهای پایین تشکیل شوند. الگوریتم، جواب های بعدی را با استفاده از جواب های فعلی بدست می آورد. در این الگوریتم، گرم کردن با اعمال تغییرات تصادفی بیشتر بر روی متغیرها مترادف است. در دماهای بالاتر، متغیرها دارای تغییرات زیادتری
هستند و هر چه دما پایین تر می آید، دامنه تغییرات تصادفی متغییر ها نیز، کمتر می شود همواره تغییراتی که منجر به بهتر
شدن نتجه شوند، پذیرفته می شوند. اما تغییراتی که منجر به بدتر شدن نتیجه شوند، با احتمال رابطه 3 پذیرفته می شوند.
این احتمال نیز با کمتر شدن دما، کمتر می شود.
که در آن اختلاف بین هزینه حل جاری از حل همسایگی ، دما، و r یک متغیر تصادفی با توزیع یکنواخت است.
-5 آشوب
تولید اعداد تصادفی یکسان(یکنواخت) برای شبیه سازی پدیده های پیچیده بسیار مهم می باشد. یک تولید کننده اعداد تصادفی21 وسیله ای فیزیکی ویا روشی محاسباتی است که برای تولید دنباله ای از اعداد که الگوی خاصی ندارند (
یعنی بطور تصادفی ظاهر شده اند ) به کار می رود.
سیستم های کامپیوتری بطور وسیعی برای تولید اعداد تصادفی مورد استفاده قرار می گیرند در حالیکه تولید کننده های
خوبی نیستند هرچند الگوهای آنها به راحتی قابل تشخیص نیست .برخی از پدیده های طبیعی الگوهای مناسبی برای تولید
این اعداد هستند به عنوان مثال برخی پدیده های فیزیکی از جمله اختلالات حرارتی در دیودهای زنر22 دارای رفتاری کاملاً تصادفی هستند و می توانند پایه ای برای تولید اعداد تصادفی فیزیکی و سخت افزاری باشند(1 و .(25 تولیدکننده های اعداد شبه تصادفی الگوریتم هایی با قابلیت تولید اعداد تصادفی هستند هرچند اعداد تولید شده توسط آنها به طور تناوبی تکرار می شود و یا آنکه حافظه زیادی را اشغال می کنند. یکی از متداولترین تولیدکننده های اعداد تصادفی
،23LCG است که رابطه ای بازگشتی دارد :
بیشترین تعداد عددی که این رابطه می تواند تولید کند m عدد شبه تصادفی است.
تولید اعداد تصادفی یکسان(یکنواخت) برای کاربردهای مختلفی بکار می روند و نقش بسیار مهمی دارند. از جمله کاربردهای اعداد تصادفی می توان به:شبیه سازی ،نمونه برداری ،آنالیز عددی ،برنامه نویسی کامپیوتری و از همه مهمتر
نقش آنها در اجرای الگوریتم های تصادفی و مخصوصا بهینه سازی های اکتشافی می باشد(1 و .(25
آشوب پدید ه ای است که در سیستمهای غیر خطی تعریف پذیر رخ می دهد که حساسیت زیاد به شرایط اولیه و رفتار
