بخشی از مقاله
مسئله فروشنده دورهگرد، یکی از مسائل پیچیده در بهینهسازی ترکیبی است. از اهداف این تحقیق، حل این مسئله با الگوریتم وراثتی، تنظیم پارامترهای الگوریتم و ارزیابی توانایی حل آن با استفاده از الگوریتم وراثتی است. در این مطالعه، برای بهبود روند جستجوی جواب بهینه، پارامترهای نرخ جهش، نرخ همبری و نرخ انتخاب با استفاده از یک استنتاج فازی که یکی از روشهای کنترل وفقی است، تنظیم میشود.
سیستم کنترل کننده فازی با توجه به تعداد شهر و شمارنده حلقه تکرار، نرخ انتخاب را مشخص میکند و مقادیر نرخ جهش و نرخ همبری با توجه به واریانس مقدار شایستگی جمعیت تعیین میشود. چهارچوب پیشنهادی برای مجموعهای از دادههای شهرهای ایران پیادهسازی و ارزیابی شده است. نتایج نشان میدهد، در الگوریتم وراثتی تعیین نوع و مقادیر عملگرهای وراثتی مانند جهش، همبری و نرخ انتخاب در روند یافتن جواب و سرعت الگوریتم تاثیر بسزایی دارد. همچنین الگوریتم وراثتی با چهارچوب پیشنهاد شده، به طور میانگین با دقت 92 درصد توانایی یافتن بهترین جواب را دارد که قابلیت بالایی برای حل این مسئله است.
-1 مقدمه
بهینهسازی5، یکی از موضوعهای مهم در زمینه محاسبات نرم و علوم مهندسی است .[1] بهینهسازی فرآیندی است که منجر به بهبود انجام کارها میشود و انتخاب بهترین جواب را میسر میسازد .[2 ,1] در مسایل سخت، انتخاب بهترین جواب از طریق ارزیابی تمام جوابها بسیار دشوار و در بعضی موارد، ناممکن است. پارامتر مهم دیگر، زمان لازم برای دستیابی به جواب بهینه میباشد. در فرآیند بهینهسازی، با تنظیم پارامترهای مسئله، انتخاب بهترین جواب مسئله از بین جوابهای ممکن در یک زمان قابل قبول میسر میشود .[3-1]
الگوریتمهای ابتکاری6، جوابهای نزدیک به جواب بهینه را در یک زمان قابل قبول یافت میکنند، با این حال، تضمینی برای پیدا شدن بهترین جواب وجود ندارد .[3 ,1] از جمله روشهای مبتنی بر جستجوی ابتکاری میتوان الگوریتم وراثتی، الگوریتم جمعیت مورچگان7 و الگوریتم ازدحام ذرات8 را نام برد. در این مقاله، از ایده الگوریتم وراثتی، برگرفته از طبیعت و نظریه تکامل داروین استفاده شده است. مسایلی که دارای طبیعت ترکیباتی9 هستند بسیار فریبندهاند، زیرا بیان آنها بسیار ساده ولی حل آنها اغلب بسیار سخت است. این نوع مسایل دارای متغیرهای گسسته هستند و هدف اصلی آنها، یافتن بهترین ترتیب یا دستهبندی است. مسئله فروشنده دورهگرد از جمله مسایلی است که دارای طبیعت ترکیباتی و از نوع بهینهسازی است.
تاکنون الگوریتمی برای حل این مسئله که توانایی بدست آوردن جواب بهینه در یک زمان چندجملهای را داشته باشد ارائه نشده است .[4] به طور کلی، مسایل BNPکامل10 مسائلی هستند که برای آنها، الگوریتمی که توانایی حل آنها را در یک زمان چندجمله-ای11 داشته باشد پیشنهاد نشده است، و از نظر محاسباتی به این مسایل، مسایل سخت12 گفته میشود .[1] اهداف این تحقیق، حل مسئله فروشنده دورهگرد با استفاده از الگوریتم وراثتی، انتخاب مناسب اجزای این الگوریتم و ارزیابی توانایی حل این مسئله با استفاده از این الگوریتم است.
پارامترهای الگوریتم وراثتی و نحوه کنترل آنها بر پیدا کردن بهترین جواب تاثیرگذار است. از آنجایی که الگوریتم وراثتی دارای ماهیت تصادفی است، قابلیت تحلیل ریاضی آن دشوار است و در چندین اجرای الگوریتم، ممکن است جوابهای متفاوتی به دست آید. در این مطالعه، با استفاده از سیستم استنتاج فازی سعی میشود، پارامترهای الگوریتم به صورت پویا و در حین اجرای الگوریتم با توجه به واریانس مقدار شایستگی، شمارنده حلقه تکرار و تعداد شهرها به نحوی تعیین شود که احتمال یافتن بهترین جواب در اولین اجرای الگوریتم بالا باشد. با استفاده از کنترل پارامترها و هدفمند کردن مراحل اجرای الگوریتم، احتمال یافتن جواب بهینه در اولین اجرای الگوریتم افزایش یافته است.
بخش دوم این مطالعه، بیان مسئله فروشنده دورهگرد میپردازد. در بخش سوم، مروری بر کارهای انجام شده در این زمینه ارائه شده است. بخش چهارم، به تشریح مراحل انجام الگوریتم وراثتی، پارامترها و نحوه تعیین پارامترها با سیستم استنتاج فازی میپردازد. در بخش پنجم، چهارچوب پیشنهادی برای مجموعهای از دادههای شهرهای ایران مورد بحث و ارزیابی قرار گرفته است. در نهایت، بخش ششم، شامل نتایج حاصل از تحقیق و پیشنهاداتی برای تحقیقات آتی در این زمینه میباشد.
-2 بیان مسئله
مسئله فروشنده دورهگرد در سال 1759 توسط اویلر به صورت حرکت اسب در صفحه شطرنج بیان شد به نحوی که از تمام نقاط صفحه شطرنج تنها یکبار عبور کند. جواب صحیح برای اسب مسیری بود که از 64 خانهی صفحه شطرنج بدون تکرار عبور کند. هرچند نام این مسئله، فروشنده دورهگرد نبود .[4] اصطلاح فروشنده دورهگرد در یک کتاب آلمانی در سال 1932 تحت عنوان فروشنده دورهگرد قدیمی به کاربرده شد .[4]
مسئله بدین شرح است: تعدادی شهر به همراه راههای ارتباطی و مسافت میان آنها معلوم است. هدف، تعیین گذری با کمترین مسافت برای فروشندهای است که میخواهد از شهری که در آن مستقر است، شروع به سفر کرده و از تمامی شهرها دقیقاٌ یکبار عبور نماید و به شهری که سفرش را از آنجا آغاز کرده است، بازگردد. این مسئله بوسیله یک گراف جهتدار و وزندار کامل به صورت G - V,E,W - بیان میشود که در آن V شامل مجموعهای از شهرها، E بیانگر مجموعه از یالهای ارتباطی بین شهرهاست و به هر یال یک وزن که یک عدد مثبت است، نسبت داده می- شود که بیانگر فاصله مکانی یال متصل کننده شهر iام - Ci - و شهر jام - Cj - است.
