صفحه 1:
صفحه 2:
بررسی الگوریتم ژنتیک
صفحه 3:
مقدمه
درالگوریتم‌های ژنتیک ابتدا به طور تصادفی یا الگوریتمیک, چندین
جواب برای مسئله تولید م ىكنيم. اين مجموعه جواب را جمعیت
اولیه می‌نامیم. هر جواب را یک کروموزوم می‌نامیم. سپس با
استفاده از عملگرهای الگوریتم ژنتیک پس از انتخاب کروموزومهای
بهتر, کروموزوم‌ها را باهم ترکیب کرده و چهشی در آنها ایجاد
می‌کنيم. در نهایت نیز جمعیت فعلی را با جمعیت جدیدی که از
ترکیب و جهش در کروموزوم‌ها حاصل میشود, ترکیب می‌کنيم.
مثلاً فرض کنید گونه خاصی از افراد. هوش بیشتری از بقبه افراد
یک جامعه پا کولونی دارند. در شرایط کاملاً طبیعی, اين افراد
پیشرفت بهتری خواهند کرد و رفاه نسبتاً بالاتری خواهند داشت و
این رقاه, خود باعث طول عمربیشتر و باروری بهتر خواهد بود
(توجه كنيد شرايط. نه در یک جامعه سطح بالا با
ملاحظات امروزى؛ يعنى طول عمر بيشتر در اين جامعه نمونه با زاد
و ولد بیشتر همراه است). حال اگر این خصوصیت (هوش) ارثی 8
باشد بالطبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلبل
زاد و ولد بيشترٍ این‌گونه اقراد بیشتر خواهد بود. اگر همین روند را
ادامه دهید خواهید دید که در طی نسلهای متوالی دائماً جامعه
نمونه ما باهوش و باهوش‌تر میشود. بدین ترتیب یک مکانیزم ساده
طبیعی توانسته است در طی چند نسل عملاً افراد کم هوش را از
جامعه حذف کند علاوه بر اينکه میزان هوش متوسط جامعه نيز دائماً ©
در حال افزایش است.
صفحه 4:
الگوریتم ژنتیک چیست؟
الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین
برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو
استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی
sly تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند.
مختصرآً گفته میشود که الگوریتم ژنتیک یک تکنیک
برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک
الکوی حل مسئله استفاده میکند. مسئله‌ای که باید حل
شود ورودی است و راه حلها طبق یک الگو کدگذاری ِ
می‌شوند که تابع 80655 نام دارد و هر راه حل کاندید
را ارزیابی میکند که اکثر آنها به صورت تصادفی
انتخاب می‌شوند.
الگوریتم ژنتیک (68۵) یک تکنیک جستجو در علم رایاته 0
براى يافتن راه حل بهينه و مسائل جستجو است. 1
عموماً راه‌حل ها به صورت ۲ تایی ۰ و ۱ نشان داده ©
می‌شوند, ولی روشهای نمایش دیگری هم وجود دارد.
تکامل از یک مجموعه کاملاً تصادفی از موجودیت‌ها
شروع میشود و در نسلهای بعدی تکرار میشود. در هر
نسل, مناسبترین‌ها انتخاب می‌شوند نه بهترین‌ها.
صفحه 5:
GA FLOWCHART
GA Flowchart
صفحه 6:
روش های نمایش الگوریتم ژنتیک
قبل از این که یک الگوریتم ژنتیک برای یک
مسئله اجرا شود؛ یک روش برای کد کردن
ژنوم‌ها به زبان کامپیوتر باید به کار رود. یکی
از روشهای معمول کد كردن به صورت
رشته‌های باینری است: رشته‌های ۰و۱. یک راه
حل مشابه دیگر کدکردن راه حلها در آرایمای
یا اعشاری است, که دوباره هراعداد صحیح‌از
جایگاه یک جنبه از ویژگی‌ها را نشان میدهد.
اين راه حل در مقایسه با قبلی پیچیده‌تر و
مشکل‌تر است. مثلاً این روش توسط
» برای حدس ساختار ۳ بعدی یک‌استفان کرمر
استفاده شد.آمینو اسیدهاپروتئین موجود در
الگوریتم‌های ژنتیکی که برای آموزش
استفاده می‌شوند» از اين؛
.روش بهره می
صفحه 7:
عملگر های یک
الگوریتم ژنتیک
در هر مسئله قبل از آنکه بتوان الگورینم
ژنتیک را برای یافتن یک پاسخ به کار برد
به دو عنصر نیاز است:در ابتدا روشی
برای ارائه یک جواب به شکلی که
الگوریتم ژنتیک بتواند روی آن عمل کند
لازم است. در روش سنتی یک جواب به
یا اعداد» ها بیت_از رشته‌صورت یک
نمایش داده میشود. دومین‌نویسه‌ها
جزء اساسی الگوریتم ژنتیک روشی
است که بتواند کیفیت هر جواب پیشنها بیشنهاد @
توایع تناسب‌شده را با استفاده از 0
محاسبه نماید. مثلاً اگر مسئله هر مقدار qd
کوله پشتی‌وزن ممکن را برای یک ©
مناسب بداند بدون اینکه کوله پشتی پاره
i او و ۱
صفحه 8:
یکی از کاربردهای الگوریتم ژنتیک
>
9
27.2%
LLLLLSF
3 ل 5
R+LQ—L
Ga 2S
رع >== 2(
صفحه 9:
مساله جدول بندی زمانی
در یک نگاه
در این قسمت و با فرض سود بردن از يك الگوریتم
ژنتيك استاندارد در طراحي جداول زمانبندي به بیان
فرضیات: فساله فیبردازیخ.
- ورودیها:
- لیست دروس اصلي و آزمايشگاهي دانشکده
-لیست کلاسهاي درس و آزمايشگاههاي موجود در
دانشکده-
-لیست اساتید دانشکده
- خروجي: جدول بهینه برنامه ريزي دروس
-پارامترها
-اندازه جمعیت ژنتیکي: 1000
-طول كروموزوم (تعداد خانه هاي د 36
براي محاسبه طول کروموزوم از رابطه ریر -
میشود:
که در اینجا !! تعداد کل بازه هاي زماني يك ساعتي در
يك هفته, تعداد کلاس هاء و ۸ تعداد آزمایشگاه ها
صفحه 10:
حداکثر تعداد نسل ها
که در آن 0 اندازه جمعیت یا تعدلد کرومزم ها مي باشد
-احتمال عملگر ادغام : 60 1
-احتما ل عملگر جهش : اين احتمال بين دو مقدار 000و 700 /بسته به شرایط للگوریتم
متغیرمیباشد. این پارامترهاي مرزي بامقداري سعي و خطا به دست آمده است.
خصوصیات
برای کد گذاری کروموزوم ها از روش جایگشتی استفاده شده است. در کد گذاری
جایگشتی اعداد صحیح نمایانگر ژنها در کروموزوم است. به تعداد ژنها عدد غیر تکراری در
کروموزوم داریم و عمل ادغام باید به گونهای باشد که پس از ترکیب دو کروموزوم ژن
تکراری در فرزند ایجاد نشود.
نوع عملگر لنتخابتسورنمنتسا لندزه ۳ لسنکه بسرلعنیمه بسدتر جمعیّسه کار مى-
> تسعداد؛ «ارود. نیمه بسهتر مستقیط از نسلقبلکپیميشود. در تسورنمنتس لندازیم
كروموزوم به طور تسصادفیانتخابشده و یسکواز آنه بسر لساس‌میزانبرازشسه
[يسيروزعميرسد[ع
صفحه 11:
نمایش کروموزوم ها
در اين تحقيق هر كرومزوم معادل يك جدول زماني فرض شده است. در نمايش دو بعدي ستونهاي لين
جدول بازههاي زماني و سطرهاي آن مكانها (كلاسها) را مشخص ميكنند. شكلهاي |) و © نمايش يك
بعدي و دو بعدي اين كروموزومها (يا جدولها) را نشان ميدهد. همان طور كه بيشتر ذكر شد روش
كدكذاري جايكشتي ميباشد. در روش كدكذاري جايكشتي كروموزوم يك آرايه1] عضوي صحيح است كه
اعداد 0 تا (] به عناصر مختلف آن منسوب ميشوند. جون معمولاً يك كلاس در تمام ساعات هفته اشغال
نیست تعدادي از خانههاي جدول خالي ميماند كه با صفر بر ميشوند.
در ساخت این جدول» ابتدا كلاسهاي درس و سيس آزمايشكاهها درج ميشوند. هدف از اين كار اين است
كه نقض محدوديتهاي سخت را كم كنيم جون يك كلاس درس نمیتواند در آزمایشگاه تشکیل شود و بر
عكس. توابع ادغام و جهش ما نيز براي هربخش به طور جداكانه عمل خواهند كرد. در كد نوشته شده
دو پارمتر ورودي به توابع جهش و ادغام اضافه شد كه ابتدا و انتهاي بازهاي كه بايد ادغام يا جهش
روي آن صورت كيرد را مشخص ميكند. يعني هركاه قرار لست ادغام يا جهش روي كروموزومي
صورت كيرد اين عمل با توجه به اين بازه مجاز انجام خواهند شد. در حقيقت در روش به كار كرفته
oat هركز يك كلاس درسي در يك آزمايشكاه و يا يك آزمايشكاه در يك كلاس درسي واقع نخواهد شد.
به همين دليل است كه مقدار دهي اوليه
صفحه 12:
کروموزوم ها
۱ ۱۱ ۱۲ ۱۲ )أ
۲ ۷ ۱ ۱۱
زذا ۱ ۸۶ ۲ ۱ ۱۱
rata go 1 |
صفحه 13:
مان کر که گفته شد وظیفه اپراتور جهش جلو گیری از یکدستی جامعه و افتادن الگوریتم بدام نقاط بهینه محلی
است. در روش پیشنهادی جهت پیاده سازی اپراتور جهش در این تحفیق. سه ایده ابتکاری مورد استفاده قرار
گرفت. جهش از طریق جابه جایی تعدادی از ژنها (دروس) در زیر بازه مجاز خود (کلاس یا آزمایشگاه) محقق می
گردد تا از تولید کروموزومهای نامعتبر اجتناب شود. .
-چون جامعه با تکرار نسلها به سمت یکنواختی میرود؛ نرخ جهش براى جل وكيرى از يكنواختى تدريجاً افزايش
میابد.
.جا نمی شوند. فضاهای خالی جدول جابه
صفحه 14:
:#محدوديتهاي سخت به شرح زیر در نظر گرفته شدند
الف) تداخل ساعات يك استاد: اگر به دو درس
زمان بك استاد اختصاص داده شده باشد جريمهاي ماو نی با
براي آن در نظر میگیریم.
ب) تداخل دروس تیان يك ورودي خاص: از آنجا که
دروس ارائه شده براي دانشجویان يك ورودي خاص نباید دلرلي
تداخل باشند, براي این محدودیت نیز جريمهاي نسبتاً بالا در
نظر گرفتهايم.
ب) مکان نامناسب براي کلاسها و یا آزمایشگاه ها:
بك كلاس درس نمیتواند در يك آزمایشگاه تشکیل شود و یا بر
عکس, هر چند با تمهیدات به کار رفته احتمال آن ناچیز است:
ت) عدم اتصال ساعات دروس: چون هر سه ساعت دروس
آزمايشگاهي ید پشت سرهم ارائه شود همجنين براي
درسهاي سه واحدي, دو ساعت از سه ساعت آنها باید بيوسته
باشد, در صورت عدم اتصال این ساعات, جريمهاي خواهيم
داشت. ضمناً دروسي نیز وجود دارند که تنها دو ساعت در
هفته هستند که این دو ساعت نیز باید پیوسته باشد.
ج) در نظر گرفتن امکانات لازم براي دروس آزمایشگاهي: هر
درس آزمايشگاهي باید در آزمایشگاه خاص خودش برگزار شود
صفحه 15:
#محدودیت هاق نرم نيز به شرح زیر در نظر گرفته شدند
الف) ارائه دروس سه واحدي pt آزمايشگاهي در 3 ساعت متوالي:
بهتر است دروس مهم و تخصصي در سه ساعت متوالي ارائه نشود؛
زیرا موجب کاهش کیقبت آموزش مبگردد.
م6 ارات دوش اسب ad easly آزمایندگاهن دز نك زوزه stig اسه
دروس تخصصي و مهم علاوه بر رعایت شرط قبلي, در يك روز نیز
ارائه نشود و ترجبحاً در دو روز ارائه گردد.
ب) ارات دزوتن تشه واحدي:عیر آرمایشگاهن 99°93 399 تست
سرهم: ترجیحاً باید ساعات دروس سه واحدي در طول هفته پخش
شده باشند (شامل يك تك ساعت و يك دو ساعت)
ت)عدم فاصله بین دروس يك گروه در يك روز: بهتر است در برنامه
دانشجویان بین ساعات برگزاري کلاسهاي آنها ساعات خالي وجود
نداشته باشد.
ث) ترجيحات اساتيد: هر استاد ترجیحات خود را به ابن صورت که
صبح يا بعد از ظهر روزهاي خاصي را میتواند در دانشکده حضور
داشته باشد اعلام مي کند.
ج) ظرفیت مکانها: اندازه مکانها تباید کمتر از تعداد دانشجویان
درسي باشد که در این مکان تشکیل میشود. در نهایت جریمه كلي
شامل مجموع وزن جریمه هاي سخت و نرم میباشد که جریمه هاي
سخت, وزن بسبار بيشتري نسبت به جریمه هاي نرم دارند. نسبت
معکوس بین جریمه ها و تابع ارزيابي در رابطه )3( مشخص شده
صفحه 16:
این مقاله خصوصیات الگوربتم ژنتيك به عنوان ابزاري مناسب در بهینه
مور بررسي قرار گرفت. سپس 65۴ سازي پاسخهاي يك مسأله
له طراحي جدآول زمانبندي براي دروس دانشگاهي به عنوان يك
معرفي و يك راه حل ژنتيكي استاندارد براي آن 5۳۴) مسأله كاربردي
ارائه شد. به كمك افزایش نرخ جهش و ادغام و در مقابل انتقال نیمه
بهتر جمعیت در نسل بعد, شبه تصادفي بودن مرحله مقدار دهي اولیهء
و دیگر تغييراتي که در الگوریتم ژنتيك معمولي اعمال شد از همگرا
شدن الگوریتم چلوگيري شده و نتایج مطلوبي حاصل گشته است.
همچنین مشخص گردید که اجتناب از مقداردهي اولیه کاملاً تصادفي و
سعي در گریز از مینیمم هاي محلي با دستكاري در پارامتر جهش
میتواند در بهمود بازدهی الكوريتم ژنتیکي در ابن بهینه سازي حاص
موثر باشد. خصوصاً که در جستجوهاي غیر سراسري مانند الگوریتم
ژنتيك, همگرايي پیش از موعد موجب يكنواختي جامعه و به دام افتادن
در يك ابتيموم محلي ميشود. نتايج حاصله نشان میدهد الگوریتم ژنتيك
پيشنهادي در طراحي جداول زمانبندي خوش ساخت براي يك دانشکده
مفروض به خوبي عمل میکند و جداول توليدي ضمن عدم نقض شرایط
سخت و فقط با نادیده گرفتن نعدادي شرط نرم» میتوانند به برازش
چندین برابر جداول ساخته شده توسط الگوریتم هاي ژنتيك عادي دست
یابند. نتایج حاصل از تحقیق بر كارايي روشهاي بومي سازي شده
مبتني بر de الگوریتم تكاملي استاندارد و معمول تأکید دارند. آزمونهاي
مشابهي روي جدول زمانبندي امتحانات يك دانشکده نیز صورت گرفته
است که نتایج آنها نیز تأبید کننده نتایچ و استدلالهاي ارائه شده در اين
.مقاله میباشد
L
صفحه 17: