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

 الگوریتم ژنتیک روش بهینه‌سازی الهام ­گرفته از طبیعت جاندار(موجودات زنده) است که می‌توان در طبقه‌بندی‌ها از آن به عنوان یک روش عددی، جستجوی مستقیم و تصادفی یاد کرد. این الگوریتم، الگوریتمی مبتنی بر تکرار است و اصول اولیه­ آن همان­طور که اشاره شد، از علم ژنتیک اقتباس گردیده و با تقلید از تعدادی از فرایندهای مشاهده­ شده در تکامل طبیعی اختراع شده است و به طور موثری از شناخت قدیمی موجود در یک جمعیت استفاده می‌کند تا حل‌های جدید و بهبود­یافته را ایجاد کند. این الگوریتم در مسائل متنوعی نظیر بهینه‌سازی، شناسایی و کنترل سیستم، پردازش تصویر و مسائل ترکیبی، تعین توپولوژی و آموزش شبکه‌های عصبی مصنوعی و سیستم‌های مبتنی بر تصمیم و قاعده به کار می‌رود.

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

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

الگوریتم ژنتیک به­ دلیل تقلید نمودن از طبیعت دارای چند اختلاف اساسی با روش‌های جستجوی  مرسوم است که به تعدادی از آن­ها اشاره می‌کنیم:

-الگوریتم ژنتیک با رشته‌های بیتی کار می‌کند که هر کدام از این رشته‌ها کل مجموعه­ ی متغیرها را نشان می‌دهد، حال آن­که بیش­تر روش‌ها به طور مستقل با متغیرهای ویژه برخورد می‌کنند.

-الگوریتم ژنتیک برای راهنمایی جهت جستجو، انتخاب تصادفی انجام می‌دهد که به این ترتیب به اطلاعات مشتق نیاز ندارد.

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

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

-الگوریتم ژنتیک در هر تکرار چند نقطه از فضای جستجو را در نظر می‌گیرد. بنابراین شانس این­که به یک ماکزیمم محلی همگرا شود، کاهش می‌یابد.

- الگوریتم ژنتیک از قوانین احتمالی پیروی می‌کند و نه از قوانین قطعی.

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