حل مسئله فروشنده دوره گرد با ترکیب دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک
فایل ورد قابل ویرایش
4000تومان
چکیده
مساله فروشنده دوره گرد جزء مسائل مشهور و کلاسیک تحقیق در عملیات می‌باشد. بسیاری از فعالیت‌های علمی را می‌توان به صورت مسئله فروشنده دوره گرد در آورد و سپس حل نمود. روش‌های بهینه یابی موجود برای حل مسائل سخت همچون مسئله فروشنده دوره گرد بطور عمده شامل تعداد بسیار زیادی متغیر و محدودیت می‌باشند که از کارایی عملی آنها در حل مسائل با ابعاد واقعی می‌کاهد بدین علت در دهه‌های اخیر استفاده از الگوریتم‌های ابتکاری و فوق ابتکاری مورد توجه قرار گرفته است. در این بین الگوریتم‌های فوق ابتکاری به دلیل ساختار ساده و توانایی‌هایی که از خود نشان داده‌اند مورد استفاده محققین تحقیق در عملیات قرار گرفته است.
در این تحقیق با ترکیب دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک سعی شده است الگوریتم ترکیبی ساخته شود که تور بهتری را برای مسئله فروشنده دوره گرد بدست آورد. پس از طراحی الگوریتم، تنظیم پارامترهای آن با حل مسائل متعدد صورت گرفته است و برای مقایسه روش پیشنهادی با روش‌های الگوریتم ژنتیک و مورچگان برخی از مسائل حل شده است. نتایج بدست آمده نشان می‌دهد که روش ترکیبی پیشنهادی TSP فروشنده دوره گرد موجود در سایت در اغلب مسائل قادر است جواب بهتری بدست آورد.
واژه‌های کلیدی: فروشنده دوره گرد، الگوریتم ترکیبی، الگوریتم کلونی مورچگان، الگوریتم ژنتیک
فهرست مطالب
فصل اول آشنایی با الگوریتم ژنتیک....................................................................................................... 1
مقدمه .............................................................................................................................................................. 2
1-1 زمینه‌های بیولوژیکی............................................................................................................................... 2
1-2 فضای جستجو......................................................................................................................................... 3
1-3 مسائل NP.............................................................................................................................................. 4
1-4 مفاهیم اولیه در الگوریتم ژنتیک............................................................................................................. 5
1-4-1 اصول پایه............................................................................................................................................ 5
1-5 شمای کلی الگوریتم ژنتیک................................................................................................................... 5
1-6 کد کردن .................................................................................................................................................. 6
1-7 انواع کدینگ............................................................................................................................................. 7
1-7-1 کدینگ مستقیم.................................................................................................................................. 7
1-7-2 کدینگ غیرمستقیم............................................................................................................................ 7
1-8 روش‌های کدینگ.................................................................................................................................... 7
1-8-1 کدینگ باینری.................................................................................................................................... 7
1-8-2 کدینگ جهشی................................................................................................................................... 8
1-8-3 کدینگ ارزشی.................................................................................................................................... 8
1-8-4 کدینگ درختی................................................................................................................................... 9
1-9 مسائل مربوط به کدینگ......................................................................................................................... 9
1-10 فضای کدینگ و فضای جواب............................................................................................................ 10
1-11 کروموزوم............................................................................................................................................. 11
1-12 جمعیت.............................................................................................................................................. 12
1-13 مقدار برازندگی................................................................................................................................... 13
1-13-1 عملگر تقاطعی............................................................................................................................. 13
1-13-2 عملگر جهشی.............................................................................................................................. 15
1-14 مراحل اجرای الگوریتم ژنتیک........................................................................................................... 17
1-15 الگوریتم ترکیبی مورچگان................................................................................................................ 24
1-16 الگوریتم پیشنهادی............................................................................................................................ 27
1-17 الگوریتم ژنتیک با توجه به نوع عملگر............................................................................................. 28
1-18 تحلیل حساسیت پارامترها................................................................................................................ 29
1-19 تجزیه و تحلیل نتایج......................................................................................................................... 31
منابع............................................................................................................................................................... 33
فهرست اشکال
شکل 1-1 نمونه‌ای از فضای جواب................................................................................................................ 3
شکل 1-2 کدینگ درختی.............................................................................................................................. 9
شکل 1-3 تقاطعی دو نقطه‌ای..................................................................................................................... 14
شکل 1-4 عمل تقاطعی یکنواخت.............................................................................................................. 15
شکل 1-5 نمونه‌ای از عمل جهش.............................................................................................................. 15
شکل 1-6 مراحل اجرای الگوریتم ژنتیک.................................................................................................... 18
شکل 1-7 چرخ رولت................................................................................................................................... 19
شکل 1-8 نحوه حرکت مورچه‌ها برای یافتن منبع غذائی وفرومون ریزی................................................ 26
فهرست جداول
جدول 1-1 کدینگ باینری............................................................................................................................. 7
جدول 1-2 کدینگ جهشی............................................................................................................................ 8
جدول 1-3 کدینگ ارزشی............................................................................................................................. 8
جدول 1-4 محل اتصال متغیر‌های فرزند ١ والد ١ فرزند ٢ والد ٢............................................................ 14
جدول 1-5 نمونه‌ای از عمل جهش............................................................................................................. 16
جدول 1-6 انتخاب کروموزوم‌ها با استفاده از مدل چرخ رولت................................................................... 19
جدول 1-7 نمایش جمعیت اولیه................................................................................................................ 22
جدول 1-8 نتایج عمل تقاطع..................................................................................................................... 22
جدول 1-9 نتایج عمل جهش..................................................................................................................... 22
جدول 1-10 کروموزوم با بیشترین مقدار برازندگی.................................................................................... 23
جدول 1-11 نشان می‌دهد که مقادیر کوچک و بزرگ پارامتر آلفا باعث افزایش طول تور می‌شود........ 29
جدول 1-12 تاثیر پارامتر بتا بر عملکرد الگوریتم ترکیبی......................................................................... 30
جدول 1-13 با افزایش مقدار پارامتر مقدار EC به جواب نزدیکتر به بهینه افزایش می‌یابد................... 30
جدول 1-14 با افزایش عملکرد الگوریتم بهبود می‌یابد............................................................................. 31
جدول 1-15 مقایسه نتایج بدست آمده از الگوریتم پیشنهادی................................................................ 31
حل مسئله فروشنده دوره گرد با ترکیب دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک
