README.md

الگوریتم‌های ژنتیکی

پیش‌آزمون

الگوریتم‌های ژنتیکی (GA) بر اساس یک رویکرد تکاملی در هوش مصنوعی هستند، که در آن روش‌های تکامل یک جمعیت برای یافتن یک راه‌حل بهینه برای یک مسئله مشخص استفاده می‌شود. این الگوریتم‌ها در سال ۱۹۷۵ توسط جان هنری هلند پیشنهاد شدند.

الگوریتم‌های ژنتیکی بر اساس ایده‌های زیر بنا شده‌اند:

• راه‌حل‌های معتبر برای مسئله می‌توانند به صورت ژن‌ها نمایش داده شوند.
• ترکیب به ما اجازه می‌دهد دو راه‌حل را با هم ترکیب کنیم تا یک راه‌حل معتبر جدید به دست آوریم.
• انتخاب برای انتخاب راه‌حل‌های بهینه‌تر با استفاده از یک تابع تناسب استفاده می‌شود.
• جهش‌ها برای بی‌ثبات کردن بهینه‌سازی و خروج از حداقل محلی معرفی می‌شوند.

برای پیاده‌سازی یک الگوریتم ژنتیکی، به موارد زیر نیاز دارید:

• یافتن روشی برای کدگذاری راه‌حل‌های مسئله با استفاده از ژن‌ها g∈Γ
• تعریف تابع تناسب fit: Γ→R روی مجموعه ژن‌ها Γ. مقادیر کوچکتر تابع نشان‌دهنده راه‌حل‌های بهتر هستند.
• تعریف مکانیزم ترکیب برای ترکیب دو ژن با هم و به دست آوردن یک راه‌حل معتبر جدید crossover: Γ^2→Γ.
• تعریف مکانیزم جهش mutate: Γ→Γ.

در بسیاری از موارد، ترکیب و جهش الگوریتم‌های ساده‌ای برای دستکاری ژن‌ها به عنوان دنباله‌های عددی یا بردارهای بیتی هستند.

پیاده‌سازی خاص یک الگوریتم ژنتیکی ممکن است از موردی به مورد دیگر متفاوت باشد، اما ساختار کلی به صورت زیر است:

1. انتخاب یک جمعیت اولیه G⊂Γ
2. به صورت تصادفی یکی از عملیات‌هایی که در این مرحله انجام خواهد شد را انتخاب کنید: ترکیب یا جهش
3. ترکیب:

• به صورت تصادفی دو ژن g₁, g₂ ∈ G را انتخاب کنید.
• ترکیب را محاسبه کنید g=crossover(g₁,g₂)
• اگر fit(g)<fit(g₁) یا fit(g)<fit(g₂) - ژن مربوطه در جمعیت را با g جایگزین کنید.

4. جهش - یک ژن تصادفی g∈G را انتخاب کنید و آن را با mutate(g) جایگزین کنید.
5. از مرحله ۲ تکرار کنید، تا زمانی که به مقدار کافی کوچک از fit برسیم یا محدودیت تعداد مراحل به پایان برسد.

وظایف معمول

وظایفی که معمولاً با الگوریتم‌های ژنتیکی حل می‌شوند شامل موارد زیر هستند:

1. بهینه‌سازی زمان‌بندی
2. بسته‌بندی بهینه
3. برش بهینه
4. تسریع جستجوی جامع

✍️ تمرین‌ها: الگوریتم‌های ژنتیکی

یادگیری خود را در نوت‌بوک‌های زیر ادامه دهید:

به این نوت‌بوک بروید تا دو مثال از استفاده الگوریتم‌های ژنتیکی را ببینید:

1. تقسیم عادلانه گنج
2. مسئله ۸ وزیر

نتیجه‌گیری

الگوریتم‌های ژنتیکی برای حل بسیاری از مسائل، از جمله مسائل لجستیکی و جستجو، استفاده می‌شوند. این حوزه از تحقیقاتی الهام گرفته شده است که موضوعات روان‌شناسی و علوم کامپیوتر را ترکیب کرده‌اند.

🚀 چالش

"الگوریتم‌های ژنتیکی ساده برای پیاده‌سازی هستند، اما رفتار آن‌ها دشوار است که درک شود." منبع تحقیق کنید تا یک پیاده‌سازی از الگوریتم ژنتیکی مانند حل یک پازل سودوکو پیدا کنید و توضیح دهید که چگونه کار می‌کند، به صورت یک طرح یا نمودار جریان.

پس‌آزمون

مرور و مطالعه خودآموز

این ویدئوی عالی را تماشا کنید که درباره چگونگی یادگیری کامپیوتر برای بازی سوپر ماریو با استفاده از شبکه‌های عصبی آموزش‌دیده توسط الگوریتم‌های ژنتیکی صحبت می‌کند. ما در بخش بعدی بیشتر درباره یادگیری کامپیوتر برای بازی کردن به این شکل یاد خواهیم گرفت.

تکلیف: معادله دیوفانتین

هدف شما حل معادله دیوفانتین است - یک معادله با ریشه‌های صحیح. به عنوان مثال، معادله a+2b+3c+4d=30 را در نظر بگیرید. شما باید ریشه‌های صحیحی که این معادله را ارضا می‌کنند پیدا کنید.

این تکلیف از این پست الهام گرفته شده است.

نکات:

1. می‌توانید ریشه‌ها را در بازه [0;30] در نظر بگیرید.
2. به عنوان ژن، از لیست مقادیر ریشه‌ها استفاده کنید.

از Diophantine.ipynb به عنوان نقطه شروع استفاده کنید.

---