الگوریتم مورچگان برای حل مسائل بهینه سازی ترکیبی
فایل ورد قابل ویرایش
82صفحه
فقط 8000تومان
چکیده
الگوریتم مورچگان روشی است که برای حل مسائل بهینه سازی ترکیبی مختلف مورد استفاده قرار می گیرد. این روش ابتدا برای حل مسئله فروشنده دوره گرد به کار گرفته شد. این الگوریتم بر پایه این منطق بنا نهاده شده که مورچه ها در مسیر خود برای یافتن غذا مقداری از یک ماده به نام فرمون بر جای می گذارند که بستگی به طول مسیر و کیفیت ماده غذایی یافته شده دارد. بقیه مورچه ها نیز بوی فرمون را احساس کرده و جذب مسیر مورد نظر می شوند و مقدار فرمون را در آن مسیر تقویت می کنند. مسیرهای کوتاهتر (از لانه تا منبع غذا) فرمون بیشتری گرفته و بدین ترتیب کوتاهترین مسیر توسط مورچه ها انتخاب می شود. رفتار توصیف شده لانه های مورچه واقعی می تواند برای حل مسائل ترکیبی شبیه سازی شود. سیاست PM(نگهداری پیشگیرانه) موضوع مطالعات بسیاری در سال های اخیر بوده است. این مطالعات معیارهای مختلفی از هزینه ، عمر اقتصادی، ریسک یا ترکیبی از این ها را مد نظر قرار داده اند. نگهداری پیشگیرانه شامل یکسری از فعالیت های تکنیکی، اجرایی و مدیریتی برای بهینه سازی طول عمر اجزاء به منظور بهبود در دسترس بودن و قابلیت اطمینان سیستم می باشد.
واژه های کلیدی : الگوریتم لانه مورچه، فرمون (pheromone)، مسئله فروشنده دوره گرد، الگوریتم ژنتیک، هزینه بهینه
فهرست مطالب
چکیده
6
مقدمه
15
فصل اول - معرفی الگوریتم ها و سیستم مورچه
18
1- تعریف الگوریتم
19
2- تفاوت هوشمندی توده ای (کلونی) و هوشمندی اجتماعی
21
3- مورچه ها چگونه می توانند کوتاه ترین مسیر را پیدا کنند؟
23
3-1 تعریف ریاضی الگوریتم مورچگان و بهره گیری از مسأله فروشنده دوره گرد جهت مسأله سازی
26
4- از مورچه های طبیعی تا مورچه های مصنوعی
29
4-1 به سمت مورچه های مصنوعی
31
4-2 تعداد مورچه ها
33
5- الگوریتم سیستم مجتمع مورچه
35
5-1 عوامل منتهی به کوتاه ترین مسیر
36
5-2 الگوریتم بهینه سازی مجتمع مورچه
37
5-3 ACO و جستجوی مبتنی بر الگو
39
5-4 ملزومات الگوریتم ACO
41
5-5 الگوریتم ACO
41
5-6 الگوریتم بروزرسانی فرومون
43
5-7 گام های حل مسأله توسط ACO
44
5-8 الگوریتم متاهیورستیک ACO
45
6- مزیت های ACO
48
7- کاربردهای ACO
49
فصل دوم – مسیریابی شبکه توسط الگوریتم ACO
51
1- مسیریابی شبکه های کامپیوتری با استفاده از ACO
52
2- الگوریتم ACO برای مسیریابی شبکه
53
3- شبکه مورچه
54
3-1 مشکل مسیریابی
54
3-2 مراحل مختلف الگوریتم Ant Net
55
3-3 الگوریتم Ant Net و خصوصیات اصلی آن
56
3-4 ساختارهای داده ای در شبکه مورچه
58
3-5 الگوریتم شبکه مورچه
60
3-5-1 ساختمان راه حل
62
3-5-1-1 نحوه ساختن مسیر توسط مورچه
63
3-5-2 بروزرسانی ساختار داده ای
64
3-6 مزایای الگوریتم Ant Net
65
3-7 نقاط ضعف Ant Net
65
4- تاریخچه برقراری توازن بار شبکه با استفاده از الگوریتم Ant Net
67
5- الگوریتم های مسیریابی
69
5-1 معرفی شبکه مورچه
69
6- برنامه طراحی شده برای شبیه سازی
71
6-1 مشخصات برنامه
71
6-2 اجزاء برنامه
72
7- شبیه سازی
74
فصل سوم – خلاصه گیری و نتیجه گیری
75
خلاصه
76
نتیجه گیری
78
پیوست الف
80
مراجع
82
فهرست جداول
جدول 1-1 کاربردهای الگوریتم های ACO
50
فهرست اشکال و تصاویر
شکل 1-1 رفتار مورچه ها در پیدا کردن مسیر بهینه
24
شکل 1-2 رفتار بهینه کلونی مورچه
25
شکل 1-3 حل مسئله فروشنده دوره گرد توسط الگوریتم بهینه سازی مورچگان
26
شکل 1-4 حل مسئله فروشنده دوره گرد توسط الگوریتم کلونی مورچگان
27
شکل 1-5 گراف الگوریتم ساز آزمایش دوم دوپل با بال هایی با طول متفاوت
31
شکل 1-6 گراف الگوریتم ساز آزمایش دوم دوپل با بال هایی با طول یکسان
33
شکل 1-7 نمایش توصیفی MBS
40
شکل 1-8 فلوچارت الگوریتم ACO
42
شکل 2-1 نحوه حرکت مورچه های پیشرو و مورچه های عقب گرد
57
شکل 2-2 ساختارهای داده ای گره iام در شبکه مورچه یا ni همسایه
60
شکل 2-3 روند حرکت مورچه ها
67
شکل 2-4 رابطه بین اجزاء برنامه
73
فصل های اصلی پایان نامه
فصل اول - معرفی الگوریتم ها و سیستم مورچه
18
فصل دوم – مسیریابی شبکه توسط الگوریتم ACO
51
فصل سوم – خلاصه گیری و نتیجه گیری
75
الگوریتم مورچگان برای حل مسائل بهینه سازی ترکیبی