Description

به نام خدا

هوش مصنوعی
پروژه دوم – الگوریتم ژنتیک

مهلت تحویل: پنجشنبه، ۸ آبان 1۳۹۹ طراحان: حمید تراشیون، کسری کرجی، سارا توکلی

پاییز 1۳۹۹

1
هدف پروژه:
در این پروژه، با روشهایی که برگرفته از طبیعت و انتخاب طبیعی هستند، آشنا میشویم. در این روشها که مجموعاً الگوریتمهای ژنتیک نامیده میشوند؛ ایدههایی برای مدلسازی جفتگیری، جهش و انتخاب طبیعی به کار میگیریم.
همچنین یاد میگیریم که بعضی اوقات با انتخاب معیار های ساده انتخاب طبیعی، این الگوریتمها ضعیف عمل میکنند و باید معیار انتخابی در نظر بگیریم که علاوه بر عملکرد فردی، به گوناگونی جمعیت اهمیت دهد.
الگوریتمهای ژنتیک عموماً در مسئلههایی با فضای حالت بزرگ کاربرد دارند؛ این الگوریتمها این کار را با نمونه گرفتن از جمعیت و ترکیب و تغییر افراد و ارزیابی آنها انجام میدهند و سعی میکنند که نسل به نسل جوابها را بهبود دهند تا به جواب مورد نظر برسند .

توضیح پروژه:
گیتهای منطقی از عناصر اصلی ساخت مدارهای منطقی میباشند. در این پروژه میخواهیم به کمک الگوریتمهای ژنتیک، گیتهای مورد نیاز برای تولید مدار مورد نظر به طوری که مطابق جدول درستی داده شده کار کند، بیابیم.
بدین منظور جدول درستی شامل تمام حالتهای ورودی در فایل “truth_table.csv” کنار صورت پروژه داده شده است .
در فایل مذکور 1۰ ستون اول به ترتیب ورودیهای مدار و ستون آخر خروجی مدار خواهد بود.
پس شما در آخر باید لیستی شامل ۹ گیت به عنوان خروجی نشان دهید.
حال قصد داریم با انجام مراحل زیر، گیتهای موردنیاز را پیشبینی کنیم.
نحوه اتصال گیتها به این صورت است که گیت اول دو ورودی اول را میگیرد و بعد از آن هر گیت ،خروجی گیت قبلی و ورودی اصلی بعدی مدار را میگیرد.
به عنوان مثال برای ۴ گیت و ۵ ورودی، مداری به شکل زیر میتوانیم داشته باشیم:
2

لازم به ذکر است مجموعه گیتهایی که در این پروژه با آنها سروکار داریم، به شرح زیر میباشد:

فاز اول: مشخص کردن مفاهیم ژن، کروموزوم در مسئله
ابتدا باید مفهوم کروموزوم و ژن را در پروژه خود تعریف کنید. هر کروموزوم مجموعهای از ژنها است و این مجموعه، یک راه پیشنهادی برای حل مسئلهی مورد نظر میباشد.
۳
با توجه به نقش حیاتی کروموزومها در ادامه روند مسئله، تعریف کروموزوم اهمیت ویژهای دارد و باید به گونهای باشد که امکان اعمال تابع تناسب و توابع دیگر بر روی آن فراهم باشد.

فاز دوم: تولید جمعیت اولیه
در فاز بعدی باید جمعیت اولیهای از کروموزومها تعریف کنید. تولید این جمعیت اولیه باید بدون هیچ جهت گیری خاصی باشد.

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

فاز چهارم: پیادهسازی mutation و crossover و تولید جمعیت بعدی
حال برای اینکه به مدار هدف مسئله نزدیک شویم، در این قسمت نیاز به ایجاد جمعیت جدید از جمعیتهای نسل قبل خود داریم. این کار را باید با روشهای معروفی که در الگوریتم ژنتیک وجود دارد و در درس نیز با آنها آشنا شدهاید؛ یعنی mutation و crossover انجام دهید.

فاز پنجم: سوالات
1( دلیل انتخاب معیار تناسب خود را ذکر کنید.
2( روش انتخاب افراد منتخب برای تولید جمعیت بعدی و دلیل انتخاب روش به کار برده شده را شرح دهید.
۳( تاثیر mutation و crossover و احتمال هر یک از آنها را ذکر کنید.
۴( با وجود استفاده از این روشها، باز هم ممکن است که کروموزومها پس از چند مرحله دیگر تغییر نکنند. دلیل این اتفاق و مشکلاتی که به وجود میآورد را شرح دهید. برای حل آن چه پیشنهادی میدهید؟ راه حلهای خود را امتحان کنید و بهترین آنها را روی پروژه خود پیادهسازی کنید.
۴

نکات پایانی:
• تمام مراحل کار خود )تعریف کروموزوم، تولید جمعیت اولیه، تابع تناسب، عملیات های mutation و crossover، جلوگیری از سوگیری کروموزومها و دلیل تمام تصمیماتی که میگیرید( را در گزارش کار خود بیاورید.
• تعیین hyper parameter ها در این مساله اهمیت زیادی دارند و همچنین باید به دلیل تعیین و تاثیرات آنها نیز توجه داشته باشید.
• برنامهی شما باید قابلیت این را داشته باشد که فایل csv دیگری به همین نام و همین فرمت را به عنوان ورودی بگیرد و گیتهای مورد نظر را در زمان معقول نشان دهد. توجه داشته باشید این مورد هنگام تحویل بررسی خواهد شد. )تعداد سطر ها و ستون ها در فایل ورودی، بسته به اندازه ورودی ،میتواند متفاوت باشد(.
• دفت کنید که شیوهی پیادهسازی موارد خواسته شده در این پروژه اهمیت بسزایی دارد. بدست آوردن نتیجهی درست بدون روشهای خواسته شده در اینجا مدنظر نمیباشد.
• نتایج و گزارش خود را در یک فایل فشرده با عنوان AI_CA2_<#SID>.zip تحویل دهید. این پوشه باید حتما شامل موارد زیر باشد:
• یک فایل code.py که شامل تمامی کدهای شماست. )این مورد حتما باید باشد(.
• میتوانید از jupyter-notebook برای نوشتن گزارش استفاده میکنید )که به شدت توصیه میشود(. در این صورت فایل Notebook به همراه خروجی html آن را ارائه دهید. در غیر این صورت، گزارش را در فایلی با فرمت PDF ارائه دهید.
• در صورتی که سوالی در مورد پروژه داشتید بهتر است در فروم درس مطرح کنید تا بقیه از آن استفاده کنند؛ در غیر این صورت توسط ایمیل با طراحان در ارتباط باشید.
htarashion@gmail.com saratvk1377@gmail.com karajikasra@gmail.com

• هدف از تمرین، یادگیری شما است. لطفا تمرین را خودتان انجام دهید. در صورت کشف تقلب بین افراد، برای تمام افراد نمره 100- در نظر گرفته میشود.
۵