پروژه پایانی، الگوریتم ژنتیک doc

پروژه الگوریتم ژنتیک در 50 صفحه بصورت کاملا ویرایش شده مطابق با اصول نگارشی با فونت بی نازینی انجام شده و از نظر محتوا دارای قوی تریت مطالب مربوط می باشد. قالب پروژه word می باشد تا در صورت صلاحدید ویرایش گردد.

چکیده:

الگوریتم ژنتیک (Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتم‌های تکامل است که از تکنیک‌های زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند.در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای تصادف هستند. مختصراً گفته می‌شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسأله‌ای که باید حل شود ورودی است و راه‌حل‌ها طبق یک الگو کد گذاری می‌شوند که تابع fitness نام دارد هر راه حل کاندید را ارزیابی می‌کند که اکثر آنها به صورت تصادفی انتخاب می‌شوند. کلاً این الگوریتم‌ها از بخش های زیر تشکیل می‌شوند: تابع برازش، نمایش، انتخاب، تغییر.

در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. در هوش مصنوعی الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود دارای ورودی‌هایی می‌باشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راه‌حلها تبدیل می‌شود سپس راه حلها بعنوان کاندیداها توسط تابع ارزیاب (Fitness Function) مورد ارزیابی قرار می‌گیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه می‌یابد. الگوریتم ژنتیک بطور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخش‌های آن به صورت فرایندهای تصادفی انتخاب می‌شوند

فصل اول: مقدمه. 1

1-1.    مقدمه. 1

1-2.    معرفی فصلهای بعدی.. 7

فصل دوم: الگوریتم ژنتیک.. 9

2-1.    الگوریتم ژنتیک چیست؟ 9

2-2.    نظریهالگوریتم ژنتیک.. 15

2-3.    توصیف مشکل جدول زمانبندی آزمون. 17

2-3-1.    تعریف مشکل. 19

2-3-2.    موانع درگیر(موانع موجود) 19

2-4.    الگوریتم ژنتیک.. 21

2-4-1.    نمایش کروموزوم. 23

2-4-2.    مقداردهی اولیه. 24

2-4-3.    ارزیابی.. 25

2-4-4.    گزینش... 26

2-4-5.    جهش یاموتاسیون. 26

2-4-6..    هم گذری.. 27

2-4-7.    اجرای الگوریتم ژنتیک.. 29

2-4-8.    ارزیابی جدول زمانبندی.. 30

2-5.    عملگرهای یک الگوریتم ژنتیک.. 31

2-5-1.    شبه کد. 31

2-5-2.    ایده اصلی.. 32

2-5-3.    روش‌های انتخاب.. 33

2-6. نتایج محاسباتی.. 34

فصل سوم: مثال عملی.. 38

3-1.    حل مسائل معروف بااستفاده ازالگوریتم ژنتیک.. 38

3-2.    روش جستجوی تکاملی.. 43

3-3.    نظریه داروین.. 43

3-4.    انواع مختلف الگوریتمهای تکاملی.. 44

3-5.    کدگذاری ونحوه نمایش... 44

فصل چهارم: نتیجه گیری.. 47

4-1.    نتیجه گیری.. 47

5.         فصل پنجم: مراجع  50

نتیجه گیری

الگوریتم های ژنتیک معمولا پاسخ های مناسبی برای مسائل دارند اما این پاسخ ها بستگی به مسئله مطرح شده دارد پاسخ ها لزوما بهترین پاسخ نبوده و تضمینی برای بهترین بودن آن وجود ندارد الگوریتم ژنتیک سعی دارد جواب مناسبی را پیدا کند بنابراین پیدا کردن پاسخ مناسب بستگی به این دارد که چقدر مراحل را تکرار کنیم، یکسری پارامترها وجود دارند که مشخص می کنند چند جواب تولید کنیم مثلا  10،20و... و سپس جواب های تولید شده ارزیابی می شوند که این جواب ها به عنوان نسل جدیدی در نظر گرفته می شود.

بنابراین به صورت منطقی برای این مسائل راه حل دیگری وجود ندارد باید سعی کنیم از تکنیک هایی استفاده کنیم تا مسئله حل شود .