فهرست مطالب
عنوان |
صفحه |
|
|
|
چکیده |
و |
فصل اول: کلیات |
1 |
1-1 مقدمه |
1 |
1-2 اهداف پایاننامه |
1 |
1-3 ضرورت انجام تحقیق |
2 |
1-4 ساختار پایاننامه |
2 |
فصل دوم: مروری بر مسائل بهینهسازی ترکیبیاتی و الگوریتمهای فرا ابتکاری |
4 |
2-1 تعاریف ابتدایی |
4 |
2-2 مسائل ترکیبیاتی |
6 |
2-2-1 مسائل تصمیمگیری ترکیبیاتی |
6 |
2-2-2 مسائل بهینهسازی ترکیبیاتی |
7 |
2-3 یک مسئله بهینهسازی ترکیبیاتی: مسئله فروشنده دورهگرد |
8 |
2-4 پیچیدگی محاسباتی مسائل بهینهسازی ترکیبیاتی |
9 |
2-4-1 پیچیدگی الگوریتمها و مسائل |
10 |
2-4-2 آیا تمام مسائل بهینهسازی ترکیبیاتی جزو مسائل سخت هستند؟ |
12 |
2-5 روشهای مختلف حل مسائل بهینهسازی ترکیبیاتی |
13 |
2-6 مروری بر الگوریتمهای فرا ابتکاری |
15 |
2-6-1 دو مولفه اصلی الگوریتمهای فرا ابتکاری: کاوش و بهرهگیری |
15 |
2-6-2 معیارهای مختلف تقسیمبندی الگوریتمهای فرا ابتکاری |
16 |
2-6-3 الگوریتمهای فرا ابتکاری مبتنی بر تکراهحل |
17 |
2-6-3-1 الگوریتم جستجوی محلی |
19 |
2-6-3-2 الگوریتم ذوب شبیهسازی شده |
20 |
2-6-4 الگوریتمهای فرا ابتکاری مبتنی بر جمعیت |
22 |
2-6-4-1 الگوریتمهای تکاملی |
23 |
2-6-4-2 الگوریتمهای هوش جمعی |
25 |
2-7 جمعبندی |
27 |
فصل سوم: الگوریتم جستجوی گرانشی پیوسته و مولفههای آن |
28 |
3-1 مقدمه |
28 |
3-2 الگوریتم جستجوی گرانشی |
29 |
* 3-3 مولفههای اصلی الگوریتم جستجوی گرانشی |
33 |
3-4 جمعبندی |
35 |
* فصل چهارم: الگوریتم جستجوی گرانشی ترکیبیاتی پیشنهادی |
37 |
4-1 مقدمه |
37 |
4-2 بازتعریف عملگر حرکت مستقل |
37 |
4-3 بازتعریف عملگر حرکت وابسته |
39 |
4-3-1 فضای همسایگی و مفهوم حرکت وابسته در این فضا |
40 |
4-3-2 محاسبه طول حرکت وابسته |
44 |
4-4 الگوریتم جستجوی گرانشی ترکیبیاتی پیشنهادی |
45 |
4-5 جمعبندی |
48 |
* فصل پنجم: حل مسئله فروشنده دورهگرد توسط الگوریتم جستجوی گرانشی ترکیبیاتی پیشنهادی |
49 |
5-1 مقدمه |
49 |
5-2 نمایش راهحلها |
50 |
5-3 ایجاد جمعیت اولیه |
51 |
5-4 ارزیابی هر عامل |
52 |
5-5 عملگر حرکت وابسته: حرکت چند هدفه در فضای همسایگی |
52 |
5-6 عملگر حرکت مستقل: الگوریتم جستجوی محلی تغییریافته |
53 |
5-7 جمعبندی |
56 |
* فصل ششم: آزمایشها و نتایج |
57 |
6-1 مقدمه |
57 |
6-2 نمونههای انتخاب شده از مسئله فروشنده دورهگرد |
57 |
6-3 شرایط پیادهسازی و اجرای الگوریتم |
59 |
6-4 نتایج پیادهسازی الگوریتم و مقایسه |
59 |
6-5 تحلیل کارایی الگوریتم پیشنهادی |
68 |
* فصل هفتم: جمعبندی و پیشنهادات |
69 |
7-1 جمعبندی |
69 |
7-2 پیشنهادات |
70 |
مراجع فارسی |
72 |
مراجع انگلیسی |
73 |
* پیوست یک |
78 |
* مباحثی که برای اولین بار توسط مولف پایاننامه انجام شده است، با این علامت (*) نشانهگذاری شده است.
فهرست شکلها
عنوان |
صفحه |
|
|
|
شکل (2-1): روشهای حل مسائل بهینهسازی ترکیبیاتی |
14 |
شکل (2-2): مثالی از ساختار همسایگی برای یک نمونه از مسئله فروشنده دورهگرد با اندازه 3. |
18 |
شکل (2-3): پیدا کردن کوتاهترین مسیر رفت و برگشت بین لانه و غذا توسط مورچهها. |
26 |
شکل (5-1): روش نمایش آرایهای سفر (9, 0, 8, 5, 7, 2, 6, 1, 4, 3). |
51 |
شکل (5-2): یک جابجایی 2-opt از یالها. |
54 |
شکل (6-1): نمونه مسئله pr2392. |
63 |
شکل (6-2): یک سفر با 0.09% خطا برای نمونه مسئله pr2392. |
64 |
شکل (پ-1) : بهترین سفر پیدا شده برای نمونه Eil51 |
78 |
شکل (پ-2): بهترین سفر پیدا شده برای نمونه Berlin52 |
79 |
شکل (پ-3): بهترین سفر پیدا شده برای نمونه KroA100 |
79 |
شکل (پ-4): بهترین سفر پیدا شده برای نمونه KroA200 |
80 |
شکل (پ-5): بهترین سفر پیدا شده برای نمونه Gil262 |
80 |
شکل (پ-6): بهترین سفر پیدا شده برای نمونه Rat575 |
81 |
شکل (پ-7): بهترین سفر پیدا شده برای نمونه D657 |
81 |
شکل (پ-8): بهترین سفر پیدا شده برای نمونه Dsj1000 |
82 |
شکل (پ-9): بهترین سفر پیدا شده برای نمونه Rl1323 |
82 |
شکل (پ-10): بهترین سفر پیدا شده برای نمونه Pr2392 |
83 |
فهرست جدولها
عنوان |
صفحه |
جدول (6-1): نمونههاي مورد بررسي مسئله فروشنده دورهگرد |
58 |
جدول (6-2): نتایج پیادهسازی الگوریتم پیشنهادی |
61 |
جدول (6-3): رتبهبندی میان الگوریتمهای حل مسئله فروشنده دورهگرد |
66 |
فهرست الگوریتمها
عنوان |
صفحه |
الگوریتم (2-1): قالب کلی الگوریتم جستجوی کلید |
5 |
الگوریتم (2-2): قالب کلی الگوریتم جستجوی محلی |
19 |
الگوریتم (2-3): قالب کلی الگوریتم ذوب شبیهسازیشده |
22 |
الگوریتم (2-4): قالب کلی یک الگوریتم تکاملی |
24 |
الگوریتم (2-5): قالب کلی الگوریتم بهینهساز جمعیت مورچگان |
27 |
الگوریتم (3-1): قالب کلی الگوریتم جستجوی گرانشی |
32 |
الگوریتم (4-1): قالب کلی الگوریتم جستجوی محلی تغییریافته |
39 |
الگوریتم (4-2): قالب کلی الگوریتم اتصال مجدد مسیر |
41 |
الگوریتم (4-3): قالب کلی الگوریتم حرکت ساده در فضای همسایگی |
42 |
الگوریتم (4-4): قالب کلی الگوریتم حرکت چند هدفه در فضای همسایگی |
43 |
الگوریتم (4-5): قالب کلی الگوریتم جستجوی گرانشی ترکیبیاتی |
46 |
