بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
الگوریتم ژنتیک چیست؟
نکات کلی در مورد الگوریتم ژنتیک
الگوريتم هاي ژنتيک از اصول انتخاب طبيعي داروين براي يافتن فرمول بهينه جهت پيش بيني يا تطبيق الگو استفاده مي کنند.
الگوريتم هاي ژنتيک اغلب گزينه خوبي براي تکنيک هاي پيش بيني بر مبناي رگرسيون هستند.
در هر نسل، بهترین های آن نسل انتخاب می شوند و پس از زاد و ولد، مجموعه جدیدی از فرزندان را تولید می کنند.
اسلاید 2 :
مسائل NP
یک نمونه دسته ای از مشکلات که نمی توانند از طریق روش قدیمی و سنتی حل شوند، مسائل NP است.
مثال هایی از مسائل NP عبارتند از: مسئله فروشنده دوره گرد، مسئله N وزیر، مسئله کوله پشتی و ... الگوریتم های ژنتیکی از جمله روشهایی هستند که برای حل اینگونه مسائل بکار می روند.
مسئله زمانبندی هم جزء مسائل NP محسوب می شود
اسلاید 3 :
ساختار های کلی الگوریتم ژنتیکی
n1-شروع: یک جمعیت تصادفی از کروموزوم ها تولید کنید.
n2- تناسب: تناسب هر کروموزوم در جمعیت ارزیابی می شود.
n
n3- جمعیت جدید: یک جمعیت جدید از طریق تکرار گام هایی ایجاد می شود تا هنگامی که جمعیت جدید کامل شود.
اسلاید 4 :
nمراحل ایجاد جمعیت جدید
n
nالف- انتخاب: انتخاب دو کروموزوم والد از جمعیت موجود بر طبق تناسب آنها.
nب- ترکیب: از ترکیب والدین یک فرزند جدید تولید می شود و اگر ترکیبی صورت نگیرد فرزند دقیقا کپی یکی از والدین می باشد.
nج- جهش: ممکن است با یک احتمال در هر یک از کروموزوم های فرزند جهش ایجاد شود.
nد- پذیرش: فرزند جدید در یک جمعیت جدید پذیرفته می شود.
nه- جایگزینی: جمعیت جدید تولید شده جایگزین جمعیت قبلی می شود تا الگوریتم بار دیگر تکرار شود.
اسلاید 5 :
n
n4- تست: اگر به شرط پایان الگوریتم رسیده باشیم متوقف می شود و بهترین راه حل از جمعیت جاری برگردانده می شود.
n
n5- تکرار: به گام دو برمی گردیم(تناسب).
اسلاید 6 :
نحوه عملکرد الگوریتم ژنتیک
اسلاید 7 :
نقاط قوت الگوریتمهای ژنتیک
1- موازی بودن الگوریتم ژنتیک
2- جستجوی فضای جستجو در چند جهت مختلف
3- امکان شکستن فضاهای جستجو به فضاهای کوچکتر
اسلاید 8 :
محدودیت الگوریتمهای ژنتیک
1- نوشتن عملگر Fitness که منجر به بهترين راه حل براي مسئله شود.
2- اگر عملگر Fitness به خوبي و قوي انتخاب نشود ممکن است باعث شود که راه حلي براي مسئله پيدا نکنيم يا مسئله اي ديگر را به اشتباه حل کنيم.
3- انتخاب مناسب پارامترهای دیگر مانند اندازه جمعیت، نرخ جهش و نرخ تبادل
4- اگر اندازه جمعیت بسیار کوچک باشد آنگاه الگوریتم ژنتیک نمی تواند فضای راه حلی کافی برای انتخاب داشته باشد و اگر بسیار بزرگ شود آنگاه سودمند نبوده و دچار مشکل خواهد شد.
اسلاید 9 :
ارائه الگوریتم پیشنهادی برای زمانبندی فرآیندهای سیستمهای ناهمگن با GA
اسلاید 10 :
ارائه الگوریتم پیشنهادی برای زمانبندی فرآیندهای سیستمهای ناهمگن با GA
گام دوم: تعیین اولویت تسکها
n این روش بر اساس اولویت با توجه به سطح گره و تعداد مراجعاتی که به گره از سطوح بالا می شود کار می کند.
n با توجه به شکل صفحه قبل گره های T0،T1،T2وT11 در سطح شماره صفر و بقیه گره ها نیز شماره سطحشان با توجه به شکل مشخص می شود. این DAG دارای حداکثر عمق 3 می باشد که این پارامتر را هم در روش پیشنهادی لحاظ می کنیم.
+(شماره سطح تسک- حداکثر عمق)= ضریب اولویت یک تسک
(مجموع ضریب اولویت فرزندان)+(تعداد مراجعه ها از سطوح بالا به تسک مورد نظر)
n
