پایاننامه ارشد کامپیوتر مسیریابی شبکه کامپیوتری الگوریتم تکاملی

۱۰۰ هزار تومان ۷۵ هزار تومان
افزودن به سبد خرید

جهت خرید و پایاننامه ارشد کامپیوتر مسیریابی شبکه کامپیوتری الگوریتم تکاملی روی خرید محصول کلیک و یا با ایمیل زیر در ارتباط باشید

sellthesis@gmail.com


پایان نامه کارشناسی ارشد کامپیوتر مسیریابی شبکه های کامپیوتری توسط الگوریتم های تکاملی


خرید محصول پایاننامه ارشد کامپیوتر مسیریابی شبکه کامپیوتری الگوریتم تکاملی


چکیده:

در دنیای امروز اهمیت استفاده از اینترنت و شبکه‌های کامپیوتری بر کسی پوشیده نیست. کاهش هزینه و صرفه جویی در وقت از مهمترین مزایای این تکنولوژی است. در این میان، انتقال داده‌ها بین مبدأ تا مقصد از یک مسیر بهینه اهمیت ویژه‌ای دارد. برای یافتن یک مسیر بهینه روش‌های متفاوتی تعریف شده است. ما در این پایان‌نامه برآنیم تا با استفاده از سه الگوریتم‌ تکاملی که از طبیعت الهام گرفته شده‌اند، مسیری بهینه را برای انتقال داده‌‌ها در یک شبکه کامپیوتری پیدا کنیم. در این مطالعه عملکرد الگوریتم‌های ژنتیک‌،‌‌‌ انبوه ذرات و کلونی مورچگان برای یافتن مسیر بهینه با هم مقایسه می‌شوند. در هر مرحله از اجرا، همواره الگوریتم بهینه‌سازی کلونی مورچگان کوتاهترین مسیر را کشف می‌‌کند ولی زمان اجرای آن چندین برابر دو الگوریتم دیگر است. الگوریتم ژنتیک در کمترین زمان به نسبت دو الگوریتم دیگر مسیری را معرفی می‌کند ولی از آنجاییکه در بهینه‌ی محلی گیر می‌کند مسیر بهینه را نشان نمی‌دهد. الگوریتم بهینه‌سازی ازدحام ذرات هم زمانی نسبتاً مناسب دارد اما مسیر بهینه را نمایش نمی‌دهد. در همین راستا الگوریتم جدیدی را ارائه داده‌ایم که در آن دو الگوریتم کلونی مورچگان و ژنتیک با هم ترکیب شده اند. زمان اجرای این الگوریتم به نسبت الگوریتم کلونی مورچگان بسیار بهتر است و نیز مسیری که بر می گرداند از مسیر به دست آمده در الگوریتم ژنتیک مناسب‌تر می‌باشد.
کلمات کلیدی: الگوریتم بهینه‌سازی ازدحام ذرات، الگوریتم بهینه‌سازی کلونی مورچگان، الگوریتم‌ ژنتیک‌، الگوریتم‌‌ های تکاملی، شبکه‌های کامپیوتری، مسیریابی.


فهرست مطالب
فصل اول 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


1- مقدمه
در دنیای امروز اهمیت استفاده از اینترنت و شبکه‌های کامپیوتری بر کسی پوشیده نیست. کاهش هزینه و صرفه جویی در وقت از مهمترین مزایای این تکنولوژی است. در این میان، انتقال داده‌ها از مبدأ به مقصد در کمترین زمان ممکن از اهمیت ویژه‌ای برخوردار است. در این راستا در این پایان نامه برآنیم تا با استفاده از الگوریتم‌های هوش مصنوعی بهبودی در سرعت انتقال داده‌ها ایجاد کنیم. به همین منظور می‌خواهیم از الگوریتم‌های تکاملی استفاده تا مسیری بهینه را برای انتقال داده‌‌ها در یک شبکه کامپیوتری پیدا کنیم.


1-1 شبکه و مسیریابی
یک شبکه رایانه‌ای که اغلب به طور خلاصه به آن شبکه گفته می‌شود، گروهی از رایانه‌ها و دستگاه‌هایی می‌باشد که توسط کانال‌های ارتباطی به هم متصل شده‌اند. شبکه رایانه‌ای باعث تسهیل ارتباطات میان کاربران شده و اجازه می‌دهد کاربران منابع خود را به اشتراک بگذارند. یک شبکه رایانه‌ای اجازه به اشتراک گذاری منابع و اطلاعات را میان دستگاه‌های متصل شده به هم می‌دهد.
شبکه‌های رایانه‌ای را می‌توان برای اهداف مختلف استفاده کرد:
• تسهیل ارتباطات: با استفاده از شبکه، افراد می‌توانند به آسانی از طریق رایانامه ، پیام‌رسانی فوری، اتاق گفت‌وگو ، تلفن، تلفن تصویری و ویدئو کنفرانس، ارتباط برقرار کنند.
• اشتراک گذاری سخت افزارها: در یک محیط شبکه‌ای، هر کامپیوتر در شبکه می‌تواند به منابع سخت افزاری در شبکه دسترسی پیدا کرده و از آن‌ها استفاده کند؛ مانند چاپ یک سند به وسیله چاپگری که در شبکه به اشتراک گذاشته شده‌است.
• اشتراک گذاری پرونده‌ها، داده‌ها و اطلاعات: در یک محیط شبکه‌ای، هر کاربر مجاز می‌تواند به داده‌ها و اطلاعاتی که بر روی رایانه‌های دیگر موجود در شبکه، ذخیره شده‌ است دسترسی پیدا کند. قابلیت دسترسی به داده‌ها و اطلاعات در دستگاه‌های ذخیره سازی اشتراکی، از ویژگی‌های مهم بسیاری از شبکه‌ها است.
• اشتراک گذاری نرم افزارها: کاربرانی که به یک شبکه متصل‌اند، می‌توانند برنامه‌های کاربردی موجود روی کامپیوترهای راه دور را اجرا کنند.
مکانیزم برقراری ارتباط و تبادل داده در مقیاس‌های مختلف شبکه متفاوت است. تا زمانی که در شبکه‌های محلی به برقراری ارتباط می‌پردازیم، با بعضی از مسائل از قبیل پیدا کردن مسیر از مبدأ تا مقصد، یافتن مسیر بهینه و غیره سر و کار نخواهیم داشت. اما در شرایطی که شبکه‌ی ما یک WAN بوده و یا بخواهیم ارتباطات بین شبکه‌ای داشته باشیم، موضوع مسیریابی پیش رویمان خواهد بود.
در شبکه‌هایی در مقیاس WAN، بر خلاف شبکه‌های LAN، بسته‌های داده برای رسیدن به مقصد می‌بایست از گره‌های مختلف که شبکه‌ها را به یکدیگر مرتبط می‌سازند، عبور کنند. به این گره‌ها مسیریاب گفته می‌شود.
مسیریابی به معنی یافتن مسیر بهینه از مبدأ تا مقصد می‌باشد. حال باید دید مسیر بهینه به چه مسیری گفته می‌شود. بهینگی در مسیریابی یک مفهوم چند بعدی می‌باشد. بر خلاف آنچه که انتظار می‌رود، مسیر بهینه صرفاً کوتاه‌ترین مسیر نخواهد بود، چرا که ممکن است مسیری کوتاه‌ترین مسیر باشد ولی به دلیل وجود ترافیک و یا هزینه‌ی بالا مسیر بهینه محسوب نشود. پس در مسیریابی به هر یک از مسیرها تا مقصد یک پارامتر چند وجهی اختصاص داده می‌شود تا مسیر بهینه از روی این امتیاز‌ها مشخص گردد. از گفته‌های فوق بر می‌آید که مسیریابی یک موضوع اساسی در شبکه‌هایی که در مقیاس WAN کار می‌کنند، به شمار می‌رود.
بر همین اساس در این پایان نامه قصد داریم با استفاده از نرم‌‌افزار برنامه‌نویسی متلب مسیریابی در یک شبکه فرضی را با سه الگوریتم تکاملی ژنتیک، کلونی مورچگان و ازدحام ذرات شبیه‌سازی و آنها را از نظر کوتاه‌ترین مسیر پیدا شده و زمان انجام این کار با هم مقایسه کنیم.


1-2 الگوریتم های تکاملی
امروزه کار روي توسعه سيستم‌هاي هوشمند با الهام از طبيعت از زمينه‌هاي پرطرفدار هوش مصنوعي است. تکنیک‌های محاسبات تکاملی، بر خلاف الگوریتم‌های جستجوی متداول، روی یک مجموعه (جمعیت) از جواب‌ها (نقاط) در فضای جستجو عمل می‌کنند و با استفاده از همکاری و رقابتی که بین جواب‌ها ایجاد می‌کنند می‌توانند خیلی سریع جواب بهینه را برای مسائل بهینه‌سازی پیچیده پیدا کنند. این تکنیک‌ها بطور عمده از فرایند تکامل در طبیعت الهام گرفته شده‌اند که چهار مورد مشهور آن : الگوریتم ژنتیک، برنامه نویسی تکاملی، استراتژی‌های تکاملی و برنامه نویسی ژنتیک می‌باشند. سوای این تکنیک‌های محاسبات تکاملی الهام گرفته از فرایند تکامل در طبیعت، یک سری تکنیک‌های محاسباتی جدید ابداع شده‌اند که رفتار اجتماعی را شبیه سازی کرده‌اند نظیر الگوریتم کلونی مورچگان و الگوریتم انبوه ذرات عمده دلیلی که می‌توان برای رفتار اجتماعی موجودات زنده آورد، بهینگی آن می‌باشد. به این ترتیب منطقی به نظر می‌رسد که برای حل مسائل بهینه‌سازی مهندسی، این رفتارهای اجتماعی را شبیه‌سازی کنیم.
1- الگوریتم ژنتیک
2 الگوریتم انبوه ذرات
3- الگوریتم کلونی مورچگان ACO

مرور

هیچ دیدگاهی برای این محصول نوشته نشده است .