توضیحات
چکیده
در دنیای امروز اهمیت استفاده از اینترنت و شبکههای کامپیوتری بر کسی پوشیده نیست. کاهش هزینه و صرفه جویی در وقت از مهمترین مزایای این تکنولوژی است. در این میان، انتقال دادهها بین مبدأ تا مقصد از یک مسیر بهینه اهمیت ویژهای دارد. برای یافتن یک مسیر بهینه روشهای متفاوتی تعریف شده است. ما در این پایاننامه برآنیم تا با استفاده از سه الگوریتم تکاملی که از طبیعت الهام گرفته شدهاند، مسیری بهینه را برای انتقال دادهها در یک شبکه کامپیوتری پیدا کنیم. در این مطالعه عملکرد الگوریتمهای ژنتیک، انبوه ذرات و کلونی مورچگان برای یافتن مسیر بهینه با هم مقایسه میشوند. در هر مرحله از اجرا، همواره الگوریتم بهینهسازی کلونی مورچگان کوتاهترین مسیر را کشف میکند ولی زمان اجرای آن چندین برابر دو الگوریتم دیگر است. الگوریتم ژنتیک در کمترین زمان به نسبت دو الگوریتم دیگر مسیری را معرفی میکند ولی از آنجاییکه در بهینهی محلی گیر میکند مسیر بهینه را نشان نمیدهد. الگوریتم بهینهسازی ازدحام ذرات هم زمانی نسبتاً مناسب دارد اما مسیر بهینه را نمایش نمیدهد. در همین راستا الگوریتم جدیدی را ارائه دادهایم که در آن دو الگوریتم کلونی مورچگان و ژنتیک با هم ترکیب شده اند. زمان اجرای این الگوریتم به نسبت الگوریتم کلونی مورچگان بسیار بهتر است و نیز مسیری که بر می گرداند از مسیر به دست آمده در الگوریتم ژنتیک مناسبتر میباشد.
کلمات کلیدی: الگوریتم بهینهسازی ازدحام ذرات، الگوریتم بهینهسازی کلونی مورچگان، الگوریتم ژنتیک، الگوریتمهای تکاملی، شبکههای کامپیوتری، مسیریابی.
فهرست مطالب
فصل اول 1
1- مقدمه 2
1-1 شبکه و مسیریابی 2
1-2 الگوریتم های تکاملی 4
1-2-1 الگوریتم ژنتیک 5
1-2-2 الگوریتم انبوه ذرات PSO 5
1-2-3 الگوریتم کلونی مورچگان ACO 6
1-3 نوآوریهای انجام شده 6
1-4 ساختار پایان نامه 7
فصل دوم 8
2- الگوریتمهای تکاملی 9
2-1 الگوریتم ژنتیک چیست؟ 12
2-1-1 فضای جستجو 15
2-1-2 مفاهیم اولیه در الگوریتم ژنتیک 16
2-1-3 اصول پایهای 16
2-1-4 نمای کلی الگوریتم ژنتیک 16
2-1-5 کدگذاری 18
2-1-5-1 کدگذاری دودویی 19
2-1-5-2 کدگذاری جهشی 19
2-1-5-3 کدگذاری ارزشی 20
2-1-5-4 کدگذاری درختی 20
2-1-5-5 مسایل مربوط به کدگذاری 21
2-1-6 کروموزوم 23
2-1-7 جمعیت ژنتیکی 24
2-1-8 تابع برازندگی 24
2-1-9 عملگر ترکیب یا جابهجایی 25
2-1-9-1 ترکیب تک نقطهای 26
2-1-9-2 ترکیب چند نقطهای 26
2-1-9-3 ترکیب یکنواخت 27
2-1-9-4 ترکیب نگاشت جزئی 28
2-1-9-5 ترکیب مرتب شده (OX) 29
2-1-9-6 ترکیب چرخشی (CX) 30
2-1-9-7 ترکیب مورب(DX) 31
2-1-10 عملگر جهش 31
2-1-10-1 روش تعویض 31
2-1-10-2 روش وارون سازی 32
2-1-10-3 روش ژن جزئی 32
2-1-10-4 روش درجی 33
2-1-10-5 روش درهمآمیخته 33
2-1-11 فرایند انتخاب 33
2-1-11-1 روش چرخ رولت 34
2-1-11-2 روش دورهای 35
2-1-12 عملگر ترمیم 36
2-1-13 نخبه کشی 36
2-1-14 مراحل اجرای الگوریتم ژنتیک 36
2-1-15 محدودیتهای الگوریتم ژنتیک 40
2-1-16 همگرایی در الگوی ژنتیک 40
2-1-17 برخی از کاربردهای الگوریتم ژنتیک 41
2-2 الگوریتم بهینهسازی ازدحام ذرات 42
2-2-1 تاریخچه الگوریتم بهینهسازی انبوه ذرات 49
2-2-2 پارامترهای PSO 49
2-2-3 برخی از نسخههای تغییریافتهی PSO 56
2-2-3-1 الگوریتم PSO دودویی 56
2-2-3-2 الگوریتم PSO فازی یا FPSO 57
2-2-4 کاربردها 60
2-3 الگوریتم بهینهسازی مورچهها 62
2-3-1 الگوی بهینهسازی کُلونی مورچهها 65
2-3-2 الگوریتم ساده شده مورچهها 66
2-3-3 الگوریتم مورچهها 69
2-3-4 الگوریتم مورچهها برای مساله فروشنده دورهگرد 76
2-3-5 برخی از نسخههای تغییر یافتهی الگوریتم مورچهها 79
2-3-5-1 الگوریتم مورچهها و نخبهگرایی 80
2-3-5-2 الگوریتم مورچهها و یادگیری تقویتی 80
2-3-6 سامانه کلونی مورچهها 82
2-3-7 الگوریتم مورچهی کمینه- بیشینه (MMAS) 83
2-3-8 کاربردها 84
فصل سوم 86
3- مسیریابی به کمک الگوریتمهای تکاملی 87
فصل چهارم 92
4- روش پیشنهادی 93
فصل پنجم 99
5- نتیجهگیری 100
5-1 الگوریتم بهینهسازی کلونی مورچگان 100
5-2 الگوریتم ژنتیک 100
5-3 الگوریتم بهینهسازی ازدحام ذرات 100
5-4 الگوریتم پیشنهادی 101
5-5 پیشنهادات آتی 101
منابع: 102
دیدگاهها
هیچ دیدگاهی برای این محصول نوشته نشده است.