طراحی ga مناسب برای حل مسئله کدینگ و fitness

[jvr90]

سلام
لطفا کمکم کنید این مسئله حل بشه
سوال اینه:
50 فعالیت تعمیراتی داریم A1,A2,...,A50
5 گروه تعمیرات
16 روز کاری

قید های مسئله:

1- در هر روز یگ گروه بایستی فارغ از کار و در حالت کشیک برای حوادث باشد
2- هر گروه در یک روز کاری یک فعالیت را انجام دهد.(هارد)
3- برخی از کار ها بهتر است به طور همزمان انجام شود .( قید نرم)
(32,50)(27,48)(23,39)(17,44)(4,33)(2,13)=i1
4- برخی از کار ها به طور همزمان انجام نشود.(قید نرم)
(7و29)(12و24)(15و43)=i2

مطلوب است طراحی ga مناسب برای حل مسئله کدینگ و fitness

راهنمایی :باید از یک ماتریس 50 در 16 استفاده کنیم

[jvr90]

پاسخ : این مسئله چطوری حل میشه

راهنمایی بیشتر:( اینو یادم رفت بگم) :redface:
- ما یک ماتریس داریم با 50 سطر و 16 ستون.
- یک x (ایکس) 200 بیتی داریم که اطلاعات هر چهار بیت معادل روز انجام کار است یعنی چهار بیت اول روز انجام فعالیت اول A1 می باشد و همین طور تا آخر.
- ابتدا کل ماتریس صفر است و اطلاعات این ایکس 200 بیتی را می خوانیم و ماتریس را کامل می کنیم (اگر فعالیت اول در روز سوم انجام شده در ماتریس باید در سطر اول در ستون سوم یک قرار دهیم ) تا کل ماتریس کامل شود.

از پنالتی باید استفده کنیم

از اساتید هر کی هر چی بلده بیاد بگه ( مخصوصا این پنالتی چی هست)

:confused

[mojalan]

پاسخ : این مسئله چطوری حل میشه

به نظر میرسه که بایستی از الگوریتم ژنتیک استفاده کنید خب قسمت اولیه هر حل مسئله ای با ژنتیک انتخاب روش کدینگ و ایجاد تابع fitness هست.
در ژنتیک افراد (جوابهای کد شده مسئله یا همون ماتریس شما) هر نسل با استفاده از تابع fitness یه امتیازی میگیرند. شما میتونید در ایحاد این تابع امتیاز دهی از روش اعمال جریمه (که فکر میکنم همون پنالتی شما هست) سعی کنی امتیاز افرادی رو که قید ها رو در نظر نگرفتند رو کم و زیاد کنی
(خدا منو ببخشه قصدم کمک کردنه ولی چون صورت مسئله درست تفهیم نشده بود حدسیات خودم رو از مسئله گفتم :biggrin: )

[jvr90]

پاسخ : این مسئله چطوری حل میشه

به نظر میرسه که بایستی از الگوریتم ژنتیک استفاده کنید خب قسمت اولیه هر حل مسئله ای با ژنتیک انتخاب روش کدینگ و ایجاد تابع fitness هست.
در ژنتیک افراد (جوابهای کد شده مسئله یا همون ماتریس شما) هر نسل با استفاده از تابع fitness یه امتیازی میگیرند. شما میتونید در ایحاد این تابع امتیاز دهی از روش اعمال جریمه (که فکر میکنم همون پنالتی شما هست) سعی کنی امتیاز افرادی رو که قید ها رو در نظر نگرفتند رو کم و زیاد کنی
(خدا منو ببخشه قصدم کمک کردنه ولی چون صورت مسئله درست تفهیم نشده بود حدسیات خودم رو از مسئله گفتم :biggrin: )

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

[mojalan]

پاسخ : این مسئله چطوری حل میشه

در یک مسئله ژنتیک اولین کار انتخاب روش کد کردن ژن ها کروموزوم ها یا افراد یا همون جوابهای مسئله است. بعد باید تابع فیتنس تعریف بشه تا با این تابع به افراد مسئله یه امییازی داده بشه. بعد روش انتخاب باید مشخص بشه برای انتخاب والدین. بعد نوبت به بازترکیب یا crossover و بعدشم جهش یا mutation . hgfji hkjohf kvo jv;dfهمینطور خصوصیات دیگه مثل نرخ بازترکیبی و جهش. انتخاب خبره و .... چیزای دیگه که خودش میشه یه درس 3 واحدی در دوره فوق لیسانس (کلا مبحث شیرینی هست و البته در بعضی مواقع بسیار راه گشا) نرم افزار متلب یه تولکیت برای اینکار داره که شما رو از بسیاری از کارها معاف میکنه. اون شاید بتونه برای شروع کمکتون کنه

[jvr90]

پاسخ : این مسئله چطوری حل میشه

خیلی ممنونم از شما :bye
میشه یه قسمت از این مسئله رو عملی حل کنید
میتونید رو کاغذ حل کنید عکسشو بذارین :biggrin:

[jvr90]

پاسخ : این مسئله چطوری حل میشه

دوستان کسی میتونه fitness نویسی رو یاده من بده با یه مثال ساده
اساتید برسین به داد من

[mojalan]

پاسخ : این مسئله چطوری حل میشه

فیتنس یعنی اینکه شما بتونی یه روالی تعریف کنی که بر اساس اون به هر کروموزوم یه امتیازی داده بشه. (بسته به سلیقه یا روش طراحی شما ممکنه این امتیاز برای افراد بهتر؛ امتیاز بیشتری باشه یا بالعکس افراد بهتر امتیاز پایینی داشته باشند. مهم اینه که شما با این ترفند بتونی افراد بهتر رو از بقیه تشخیص بدی) خب اولین موضوع اینه که طبق مسئله شما یه کروموزوم خوب (یا فرد برتر) چه فرق یا امتیازی نسبت به افراد دیگه دارهو این تفاوت یا برتری چطوری باید تبدیل به امتیاز عددی بشه .
یه روش کارآمد هم در این مواقع برای بدست آوردن امتیاز تعریف مسئله راحت یا relax problem هست بدین معنی که بعضی از قیود اصلی از مسئله حذف و با قیود ساده تری افراد رو طبقه بندی میکنند (رجوع به کتاب هوش مصنوعی راسل). در کل امتیاز دهی به جوابها (همون کروموزوم یا افراد بستگی زیادی به سلیقه طراح داره)

[mojalan]

پاسخ : این مسئله چطوری حل میشه

اینم یه مثال برای مسئله معروف 8 وزیر که امیدوارم بدردت بخوره
میدونیم که در جواب نهایی این مسئله نباید هیچ وزیری وزیر دیگه رو اصطلاحا گارد بده (یا کنه)
برای حل این مسئله با ژنتیک شما یک یا چند (بسته به تعداد افراد نسل) حالت کاملا تصادفی رو روی صفحه شطرنج میچینی که میشن افراد یا کروموزومها یا پاسهای نسل فعلی شما
شما باید فیتنس تعریف کنی تا حالت های بهتر رو جدا کنی
یه روش خیلی ساده اینه که تو هر پاسخ بشماری ببینی در این پاسخ (که در نسل اول تصادفی تولید شدن) چند تا وزیر همدیگر و گارد میکنن. خب واضحه که هر چی این تعداد کمتر باشه اون حالت جواب بهتری هست و به جواب نهای مسئله نزدیکتره.