حل مسئله زمانبندي کارها با استفاده از الگوريتم ژنتيک
ده سال پیش منتشر شده
تعداد بازدید: 4981
کد پروژه: 16715
شرح پروژه
هدف ازين تمرين، حل مسئله زمانبندي کارها با استفاده از الگوريتم ژنتيک است. اين مسئله به صورت زير تعريف مي شود:
J کار و M ماشين داريم. هر ماشين مي تواند تعدادي کار انجام دهد. فرض مي کنيم هر کار تنها توسط يک ماشين قابل انجام است. هر دو کار i و j سه وضعيت متفاوت نسبت به هم مي توانند داشته باشند:
- i پيش نياز j است. به عبارت ديگر، j وقتي قابل اجرا است که i اجرا شده باشد.
- j پيش نياز i است.
- دو کار با هم ارتباطي ندارند.
همچنين اجراي کار i، به زمان ti احتياج دارد.
منظور از مسئله زمان بندي کارها، اختصاص دادن يک زمان شروع به هر کار است. هر ماشين در هر لحظه تنها مي تواند يک کار را انجام دهد. پس يک زمان بندي، نشان مي دهد که اجراي هر کار در چه زماني آغاز مي شود.
زمان بندي مطلوب، سه ويژگي زير را بايد داشته باشد:
- همه کارها بايد اجرا شوند
- تمامي شرط هاي پيش نيازي کليه کارها بايد رعايت شود.
- کل زماني که صرف اجراي اعمال مي شود بايد کمينه باشد.
برنامه اي بنويسيد که اين مسئله را حل کند. ورودي برنامه فايل با نام input.txt با ساختار زير است:
- خط اول به ترتيب دو عدد m و n
- پس از آن، n خط که هر کدام دو عدد دارد. اين عدد، به ترتيب شماره دو کار هستند که نشان مي دهند کار اول پيش نياز کار دوم است. شايان ذکر است که دنباله پيش نيازها نبايد تناقض داشته باشند. هر گونه چرخه اي در پيش نيازها يک تناقض است. مثلا (i,j),(j,k),(k,i) تناقض بوده و معتبر نمي باشد.
- سپس m خط که هر کدام در هر خط سه عدد وجود دارد. عدد اول شماره يک کار، عدد دوم شماره ماشين انجام دهنده آن کار و عدد سوم زمان اجراي اين کار است. هر کار حتما بايد توسط دقيقا يک ماشين قابل انجام باشد.
برنامه با خواندن فايل ورودي، کارها را زمان بندي نموده و به ازاي هر ماشين در خروجي چاپ مي کند. خروجي نيز ين فايل output.txt است. ساخت test case بر عهده شماست.
کليه مراحل مدلسازي بايد بطور کامل و با ذکر دليل کافي براي در نظر گرفتن اين مدلسازي نوشته شود. همچنين تمامي نتايج به دست آمده نيز بايد با تحليل مناسب باشد. لطفا نمودارهاي لازم براي نتايج مانند نمودار ميانگين، بهترين fitness جمعيت، پراکندگي جمعيتو هر نمودار لازم را رسم کنيد.
اين تمرين با نرم افزار متلب پياده سازي مي شود و کد شما بايد شامل يک تابع کلي به نام RunGA.m باشد که با اجراي آن تمام مراحل الگوريتم اجرا شود (مسئله را بطور مناسب ماژول بندي کرده، تا کد خوانايي داشته باشيد. به عنوان مثال، هر يک از اعمال مربوط به الگوريتم ژنتيک مانند محاسبه fitness و ... در قالب توابع مجزا تعريف کنيد)
توجه: بايد موارد زير بصورت کاملا واضح و با زبان رياضي به صورت مجزا بيان شود:
1- نحوه نگاشت و نمايش مولفه هاي مسئله در قالب کروموزوم (در مدل شما کروکوزوم چه معنايي دارد؟)
2- نحوه توليد جمعيت اوليه (به همراه توجيه معنايي روش توليد جمعيت اوليه)
3- فرمولاسيون تابع برازش و مفهوم اجزاي آن (چرا اين برازش خوب است؟)
4- سياست انتخاب کروکوزوم
5- نحوه باز توليد نسل جديد کروکوزوم ها
6- شرط پايان تکرار الگوريتم
توجه بسيار مهم: در صورتي که گزارش شما ترجمه عيني از مقالات باشد، يا از گزارش افراد ديگري، حتي به اندازه يک خط، استفاده کرده باشيد کار شما تقلب علمي محسوب شده و نمره کل درس شما صفر خواهد شد. همچنين عکسهاي استفاده شده همگي بايد داراي ارجاع به منبع باشند و گرنه تقلب علمي محسوب خواهند شد.
به علاوه کپي کردن از کد و گزارشِ همکلاسي هاي خود، و همچنين از گزارش افرادي که ترم هاي پيش اين درس را داشته اند مجاز نيست. استفاده از ابزارها (toolboxها) و کدهاي آماده در اينترنت نيز مجاز نمي باشد، مگر اينکه به وضوح، استفاده از آنها آزاد و مجاز اعلام شود. در صورت مشاهده ، نمره کل درس شما صفر خواهد بود.
****همه ي کدهاي موجود در اينترنت در دست اينجانب مي باشد. سعي در کپي کردن آنها نکنيد.
زیرساخت:
matlab
قابل تحویل:
مهارت ها و تخصص های مورد نیاز
بودجه
5,000 تومان تا 100,000 تومان
مهلت برای انجام
2روز
وضعیت مناقصه
انجام شده
درباره کارفرما
عضویت ده سال پیش
