نوع فایل: word
قابل ویرایش 67 صفحه
چکیده:
هدف از انجام این پروژه آن است که در لایه ی شبکه سیستم های کامپیوتری با استفادهازالگوریتم های ژنتیک بتوان یک مسیر را از یک نقطه به نقطه ی دیگر انتخاب کرد تا زمان و ترافیک شبکه حداقل شود .روی شبکه ای که از هزاران هزار کامپیوتر تشکیل یاقته است ارسال و دریافت اطلاعات بین دو کامپیوتر می تواند از مسیرهای مختلف و متفاوتی صورت گیرد.این مسیرها دارای طول و میزان ترافیک های متفاوتی خواهند بود.اما ما با بهره گیری از الگوریتم های ژنتیک به دنبال روش هستیم که مسیر بهینه را از لحاظ طول و ترافیک به دست آوریم.به طوریکه زمان ارسال ودریافت اطلاعات کاهش یابد.در انجام این پروژه با تحقیق روی الگوریتم های ژنتیک روشی را برای مسیریابی بر مبنای آن به دست می آوریم که نتیجتاً مسیری بهینه و موفق خواهد بود هر چند که در همسایگی پاسخ بهینه نیز باشد.
برای انجام این پروژه ابتدا به مطالعه ی الگوریتم های ژنتیک می پردازیم وبه تاریخچه و ساختار کلی این گونه الگوریتم ها پی می بریم .پس از شناخت مراحل حل مسئله توسط الگوریتم ژنتیک به تحقیق روی روشهای مسیریابی در شبکه های کامپیوتری می پردازیم و خلاصه ای از آن را بیان می کنیم .در ادامه سعی می کنیم تا الگوریتم های ژنتیک را برای مسیریابی در شبکه به کار ببریم.با استفاده از این گونه الگوریتم ها روشی را برای مسیریابی ارائه داده و با شبیه سازی شبکه به وسیله ی گراف آن را پیاده سازی می نمائیم.در انتها یک نمونه شبکه را روی روش پیاده سازی شده اجرا کرده و نتایج عملی آن را گزارش می دهیم.
مقدمه:
در شبکه های کامپیوتری لایه ی شبکه بسته ها را از مبدا به مقصد می رساند برای رسیدن به مقصد باید در بین راه از چندین منبع بگذرد. کار لایه ی شبکه با لایه ی پیوند داده ها متفاوت است. لایه ی شبکه پایین ترین لایه ای است که با انتقال انتها به انتها سروکار دارد این لایه برای رسیدن به اهدافش باید توپولوژی زیر شبکه ی ارتباطات را بداند و مسیرهای مناسبی را انتخاب نماید.نباید مسیرهایی انتخاب کند که بعضی از خطوط ارتباطی و مسیریابها بار اضافی را تحمل کند و بعضی دیگر بی کار باشند. زمانی که منبع و مقصد در دو شبکه مختلف باشد لایه ی شبکه باید از عهده ی اختلافهای بین آنها برآید و مشکلات ناشی از آنها را حل کند.اکنون به چگونگی عملکرد لایه ی شبکه می پردازیم.دو مسئله ی مختلف برای سازماندهی زیر شبکه وجود دارد.یکی از آنها از اتصالها استفاده می کند و دیگری بی اتصال کار می کند.در زمینه ی عملکرد داخلی زیر شبکه اتصال را مدار مجازی می نامند.بسته های مستقل سازمان بی اتصال،داده گرام نامیده می شود.هدف مدارهای مجازی پرهیز از انتخاب مسیر جدید برای هر بسته یا سلول است.هربسته که از زیر شبکه عبور میکند به مسیریاب میرسد،مسیریاب میداند که از کدام خط رسیده و شماره ی مدار مجازی را نیز میداند و بر مبنای این اطلاعات بسته باید به خط خروجی صحیحی انتقال داده شود. وقتی اتصال شبکه برقرار شد شماره ی مدار مجازی که اکنون در آن ماشین در حال استفاده نیست،به عنوان شناسه ی اتصال انتخاب می شود و این شماره ها فقط دارای ارزش محلی هستند.اگر به طورعمومی در کل شبکه معنی داشته باشند امکان دارد دو مدار مجازی که دارای شماره ی مدار یکسانی هستند از مسیرهایی عبور کنند که منجر به ابهام میشوند.با توجه یه اینکه در این پروژه هدف ما پیدا کردن کوتاهترین مسیر بین دو مسیریاب برای انتقال بسته از مسیریاب مبدا به مسیریاب مقصد میباشد لذا اولین مورد برای شروع کار چگونگی نمایش صورت مسئله می باشد که شرح و بیان مسئله در فصل دوم توضیح داده میشود.به طوری که قابل پیاده سازی باشد.در واقع ما شبکه را به صورت گرافی متشکل از گرهها و یالها نمایش خواهیم داد.برایپیاده سازی این مسئله در فصل سوم به بررسی الگوریتمهای قطعی می پردازیم و به ایننتیجه خواهیم رسید که الگوریتمهای قطعی پیدا کردن جواب بهینه را تضمین می کند ولی هزینه ی زمانی برای n>=40 غیر قابل قبول است در واقع چنین الگوریتمهایی دارای هزینه ی زمانی نمایی خواهند بود که سودمند نخواهند بود.به همین خاطر ما به دنبال روشی خواهیم بود که این هزینه ی زمانی را کاهش دهد و لذا الگوریتمهای ژنتیک روش مناسبی پیشنهاد میشود.که در فصل چهارم به بررسی الگوریتمهای تکاملی و مفاهیم موجود در آن می پردازیم در ادامه فصل مثالی از رنگ آمیزی گراف برای آشنای با کارکرد این الگوریتم ارائه می شود و سپس در فصل پنجم به رائه ی روشی بر اساس الگوریتمهای ژنتیک برای مسئله ی مسیریابی می پردازیم. و براساس این طراحی در فصل 6 به پیاده سازی و شرح کد مربوطه خواهیم پرداخت.و در نهایت ارزیابی و ارائه ی نتایج بدست آمده را در فصل 7 ارائه می دهیم و نتیجه خواهیم گرفت که الگوریتمهایژنتیک جوابهای نزدیک به بهینه را ارائه میدهند.
فهرست مطالب:
چکیده
فصل اول
مقدمه
فصل دوم
بیان و شرح مسئله
فصل سوم
انواع الگوریتم های مسیر یابی
معرفی نمونه ای از الگوریتم قطعی
فصل چهارم
تاریخچه
مفاهیم ژنتیکی
الگوریتم GA
کاربردهای الگوریتم ژنتیک
کد رنگ آمیزی گراف با GA
فصل پنجم
طرح کلی مسئله
فصل ششم
ورودی و خروجی مسئله
پیدا کردن شایسگی هر ژن
عملگر انتخاب
عملگر ترکیب و جهش
نحوه ی اجرا و شرط خاتمه الگوریتم
کد مسیر یابی در شبکه
فصل هفتم
ارزیابی و نتایج
منابع و ماخذ
منابع و مأخذ:
[1] میبدی، محمد رضا وبیگی، حمید."حل مسئله تناظر گراف توسط آتوماتاهای یادگیر". دانشکده ی مهندسی کامپیوتر. دانشگاه صنعتی امیر کبیر. تهران. ایران. 1379.
[2] مبیدی، محمد رضا و رضا پور میر صالح، مهدی. "یک روش ترکیبی (GA+LA) برای حل مسئله تناظر گراف ". دانشکده مهندسی کامپیوتر . دانشگاه صنعتی امیر کبیر. تهران. ایران . 1382.
[3] پرژه پایانی آقای مهندس ناصر لطفی
[4] K.Bryant,’Genetic Algrithms and the travelling salesman problem’, Thesis, Harvey mudd college , Dept.of Mathematics,2000.
پروژه یافت کوتاهترین مسیر در شبکه های کامپیوتری مبتنی برپردازش تکاملی. doc