الگوریتم ژنتیک
Genetic Algorithmالگوریتم ژنتیک یک الگوریتم از دسته الگوریتم‌های تکاملی است. Genetic Algorithm فضای بزرگ جواب‌ها را با population، fitness، selection، crossover و mutation جست‌وجو می‌کند.
اول این مفهوم را در ذهن نگه دار
الگوریتم ژنتیک یک الگوریتم از دسته الگوریتم‌های تکاملی است. Genetic Algorithm فضای بزرگ جواب‌ها را با population، fitness، selection، crossover و mutation جست‌وجو می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم الگوریتم ژنتیک ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع Varies by implementation / input constraints است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
جواب‌ها را encode کن.
fitness را محاسبه کن.
selection/crossover/mutation را تا شرط توقف تکرار کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای الگوریتم ژنتیک هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- برای optimization سخت که exact search عملی نیست و جواب تقریبی قابل قبول است مناسب است.
کجا معمولاً اشتباه می‌کنیم؟
- تضمین global optimum ندارد.
- encoding و fitness بد کل نتیجه را خراب می‌کنند.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای الگوریتم ژنتیک در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی Varies by implementation / input constraints و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
الگوریتم ژنتیک چه مسئله‌ای را حل می‌کند؟
الگوریتم ژنتیک یک الگوریتم از دسته الگوریتم‌های تکاملی است. Genetic Algorithm فضای بزرگ جواب‌ها را با population، fitness، selection، crossover و mutation جست‌وجو می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
تضمین global optimum ندارد.