الگوریتم ژنتیک: الگو ریتم ژنتیک که روش بهینه سازی الهام گرفته از طبیعت جاندار(موجودات زنده) است که میتوان در طبقه‌بندی‌ها، از آن به عنوان یک روش عددی، جستجوی مستقیم و تصادفی یاد کرد. این الگو ریتم، الگو ریتمی مبتنی بر تکرار است و اصول اولیۀ آن همانطور که پیشتر اشاره شد از علم ژنتیک اقتباس گردیده است و با تقلید از تعدادی از فرآیندهای مشاهده شده در تکامل طبیعی اختراع شده است و به طور موثّری از معرفت قدیمی موجود در یک جمعیت استفاده می‌کند، تا حل‌های جدید و بهبود یافته را ایجاد کند. این الگوریتم در مسائل متنوعی نظیر بهینه‌سازی، شناسایی و کنترل سیستم، پردازش تصویر و مسایل ترکیبی، تعین توپولوژی و آموزش شبکه‌های عصبی مصنوعی و سیستم‌های مبتنی بر تصمیم و قاعده به کار می‌رود.علم ژنتیک، علمی است که دربارۀ چگونگی توارث و انتقال صفحات بیولوژیکی از نسلی به نسل بعد صحبت می‌کند. عامل اصلی انتقال صفحات بیولوژیکی در موجودات زنده کروموزومها و ژن‌ها میباشد و نحوه عملکرد آنها به گونه‌ای است که در نهایت ژن‌ها و کروموزوم‌های برتر و قوی مانده و ژن‌ها[1]ی ضعیف‌تر از بین می‌روند. به عبارت دیگر نتیجۀ عملیات متقابل ژن‌ها و کروموزومها باقی ماندن موجودات اَصلح و برتر میباشد.
همچنین مجدداً یادآور می‌شویم که این الگوریتم برای بهینه سازی، جستجو و یادگیری ماشین مورد استفاده قرار می‌گیرد. اساس این الگوریتم قانونِ تکاملِ داروین (بقا بهترین) است که می‌گوید: موجودات ضعیف‌تر از بین می‌روند و موجودات قوی‌تر باقی می‌مانند. در واقع تکامل فرآیندی است که روی رشته‌ها صورت می‌گیرد، نه روی موجودات زنده‌ای که معرف موجودات رشته است. در واقع، قانون انتخاب طبیعی برای بقا می‌گوید که هر چه امکان تطبیق موجود بیشتر باشد بقای موجود امکان‌پذیرتر است و احتمال تولید مثل بیشتری، برایش وجود دارد. این قانون بر اساس پیوند بین رشته‌ها و عملکرد ساختمان‌های رمزگشایی شده آنها میباشد.
الگوریتم ژنتیک به دلیل تقلید نمودن از طبیعت دارای چند اختلاف اساسی با روشهای جستجوی مرسوم میباشد که در زیر به تعدادی از آنها اشاره می‌کنیم.الگوریتم ژنتیک با رشته‌های بیتی کار می‌کند که هر کدام از این رشته‌ها کلّ مجموعه متغیرها را نشان میدهد حال آنکه بیشتر روش‌ها به طور مستقل با متغیرهای ویژه برخورد میکنند.الگوریتم ژنتیک برای راهنمایی جهت جستجو، انتخاب تصادفی انجام میدهد که به این ترتیب به اطلاعات مشتق نیاز ندارد.در الگوریتم ژنتیک روشهای جستجو بر اساس مکانیزم انتخاب و ژنتیک طبیعی عمل می‌نمایند.این الگوریتمها مناسب‌ترین رشته‌ها را از میان اطلاعات تصادفی سازماندهی شده انتخاب میکنند. در هر نسل یک گروه جدید رشته‌ها با استفاده از بهترین قسمت‌های دنباله‌های قبلی و بخش جدید اتفاقی برای رسیدن به یک جواب مناسب به وجود می‌آیند. با وجود اینکه الگوریتمها تصادفی هستند ولی در زمره الگوریتمهای تصادفی ساده نیستند. آنها به طور کارآمدی به اکتشاف اطلاعات گذشته در فضای جستجو می‌پردازند تا در یک نقطه جستجوی جدیدی با پاسخ‌های بهتر به سمت بهترین جواب پیش روند. هنگام پیشآمدسازی الگوریتمهای ژنتیک عمل پیشآمدسازی ساده را نمی‌پیمایند بلکه آنها داده‌های پیشین را با تفکّرِ انتخابِ جستجویِ جدید برای رسیدن پیشرفتِ مورد نظر توأم میکنند.
الگوریتم ژنتیک [2]در هر تکرار چند نقطه از فضای جستجو را در نظر می‌گیرد بنابراین شانس اینکه به یک ماکزیمم محلی همگرا شود کاهش می‌یابد.در بیشتر روشهای جستجوی مرسوم (روش گرادیان) قاعده تصمیم حاکم به این صورت عمل می‌کند که از این یک نقطه به نقطۀ دیگر حرکت می‌کند. این روش‌ها می‌توانند در فضاهای جستجو دارای چند بیشینۀ خطرناک باشند. زیرا ممکن است آنها به یک ماکزیمم محلی همگرا شوند. لیکن الگوریتم ژنتیک جمعیت‌های کاملی از رشته‌ها (نقاط) را تولید می‌کند سپس هر نقطه را به صورت انفرادی امتحان می‌کند و با ترکیب محتویات آنها یک جمعیت جدید را که شامل نقاط بهبود یافته است تشکیل میدهد. صرف نظر از انجام یک جستجو ملاحظۀ هم‌زمانِ تعدادی نقطه در الگوریتم ژنتیک آنها را با ماشین‌های موازی تطبیق می‌سازد زیرا در اینجا تکامل هر نقطه یک فرآیند مستقل است. لذا الگوریتم ژنتیک فقط نیاز به اطلاعاتی در مورد کیفیت حل‌های ایجاد شده به وسیلۀ هر مجموعه از متغیرها دارد، در صورتی که بعضی از روشهای بهینه‌سازی نیاز به اطلاعات یا حتی نیاز به شناخت کامل از ساختمان مسأله و متغیرها دارند. چون الگوریتم ژنتیک نیاز به چنین اطلاعات مشخصی از مسأله ندارد بنابراین قابل انعطاف‌تر از بیشتر روشهای جستجو است. همچنین الگوریتم ژنتیک از روشهای جستجوی نوعی که برای راهنمایی جهت روشهای جستجویشان از انتخاب تصادفی استفاده میکنند متفاوت است زیرا اگر چه برای تعریف روشهای تصمیم‌گیری از تصادف و شانس استفاده می‌کند ولی در فضای جستجو به صورت تصادفی قدم نمی‌زند.الگوریتم ژنتیک از قوانین احتمالی پیروی می‌کند و نه از قوانین قطعی.
مکانیزم الگوریتم ژنتیک :الگوریتم ژنتیک به عنوان یک الگوریتم محاسباتیِ بهینه‌سازی با در نظر گرفتن مجموعه‌ای از نقاط فضای جواب در هر تکرار محاسباتی به نحو مؤثری نواحی مختلف فضای جواب را جستجو می‌کند. در مکانیزم جستجو گرچه مقدار تابع هدف تمام فضای جواب محاسبه نمی‌شود ولی مقدار محاسبه شده تابع هدف برای هر نقطه، در متوسط‌گیری آماری تابع هدف برای هر نقطه، در متوسط‌گیری آماری تابع هدف در کلیه زیر فضاهایی که آن نقطه به آنها وابسته بوده دخالت داده می‌شود و این زیر فضاها به طور موازی از نظر تابع هدف متوسط‌گیری آماری می‌شوند. این مکانیزم را توازی ضمنی می‌گویند. این روند باعث می‌شود که جستجوی فضا به نواحی از آن که متوسط آماری تابع هدف در آنها زیاد بوده و امکان وجود نقطه بهینه مطلق در آنها بیشتر است سوق پیدا کند. چون در این روش برخلاف روشهای تک‌مسیری فضای جواب به طور همه جانبه جستجو می‌شود، امکان کمتری برای همگرایی به یک نقطه بهینه محلی وجود خواهد داشت.
امتیاز دیگر این الگوریتم آن است که هیچ محدودیتی برای تابع بهینه شونده، مثل مشتق‌پذیری یا پیوستگی لازم ندارد و در روند جستجو خود تنها به تعیین مقدار تابع هدف در نقاط مختلف نیاز دارد و هیچ اطلاعاتِ کمکی دیگری، مثل مشتق تابع را استفاده نمی‌کند. لذا میتوان در مسائل مختلف اعم از خطی، پیوسته یا گسسته استفاده می‌شود و به سهولت با مسائل مختلف قابل تطبیق است.در هر تکرار هر یک از رشته‌های موجود در جمعیت رشته‌ها، رمزگشایی شده و مقدار تابع هدف برای آن به دست می‌آید. بر اساس مقادیر به دست آمده تابع هدف در جمعیت رشته‌ها، به هر رشته یک عدد برازندگی نسبت داده می‌شود. این عدد برازندگی احتمال انتخاب را برای هر رشته تعیین خواهد کرد. بر اساس این احتمال انتخاب، مجموعه‌ای از رشته‌ها انتخاب شده و با اعمال عملکردهای ژنتیکی روی آنها رشته‌های جدید جایگزین رشته‌هایی از جمعیت اولیه می‌شوند تا تعداد جمعیت رشته‌ها در تکرارهای محاسباتی مختلف ثابت باشد.
مکانیزم‌های تصادفی که روی انتخاب و حذف رشته‌ها عمل میکنند به گونه‌ای هستند که رشته‌هایی که عدد برازندگی بیشتری دارند، احتمال بیشتری برای ترکیب و تولید رشته‌های جدید داشته و در مرحله جایگزینی نسبت به دیگر رشته‌ها مقاوم‌تر هستند. بدین لحاظ جمعیت دنباله‌ها در یک رقابت بر اساس تابع هدف در طیّ نسل‌های مختلف، کامل شده و متوسط مقدار تابع هدف در جمعیت رشته‌ها افزایش می‌یابد. بطور کلی در این الگوریتم ضمن آنکه در هر تکرار محاسباتی، توسط عملگر های ژنتیکی نقاطی جدید از فضای جواب مورد جستجو قرار می‌گیرند توسط مکانیزم انتخاب، روند جستجوی نواحی از فضا را که متوسط آماری تابع هدف در آنها بیشتر است، کنکاش می‌کند. بر اساس سیکل اجرایی فوق، در هر تکرار محاسباتی، توسط عملگرهای ژنتیکی نقاط جدیدی از فضای جواب مورد جستجو قرار می‌گیرند توسط مکانیزم انتخاب، روند جستجو نواحی از فضا را که توسط آماری تابع هدف در آنها بیشتر است، کنکاش می‌کند. که بر این اساس، در هر تکرار محاسباتی، سه عملگر اصلی روی رشته‌ها عمل می‌کند؛ این سه عملگر عبارتند از: دو عملگر ژنتیکی و عملکرد انتخابی تصادفی.
«گلد برگ[3]» الگوریتم ژنتیکی «جان هولند» را با عنوان الگوریتم ژنتیک ساده [4]معرفی می‌کند؛ الگوریتم ژنتیک را از الگوریتم ژنتیک طبیعی اقتباس کردند.بدن همه موجودات زنده از سلول‌ها تشکیل شده است و در هر سلولی دسته کروموزوم‌های یکسانی وجود دارد. کروموزومها رشته‌هایی از DNA هستند که در واقع الگویی برای تمام بدن هستند. هر کروموزومی محتوی دسته‌هایی DNA است که ژن نامیده می‌شوند و هر ژنی پروتئین خاصی را رمزگذاری می‌کند. اساساً میتوان گفت که هر ژن، ویژگی خاصی (مثلا رنگ چشم) را رمزگذاری می‌کند. حالت‌های مختلف یک خصیصه (آبی، قهوه‌ای) آلل نامیده می‌شود. هر ژنی موقعیت خاص خود را بر روی کروموزوم دارد که این موقعیت لوکاس نامیده می‌شود. مجموعه کاملی از مواد ژنتیکی (همۀ کروموزومها) ژنوم نامیده می‌شود. دستۀ خاصی از ژن‌های موجود در ژنوم، ژنوتیپ نامیده می‌شود. ژنوتیپ به همراه تغییرات پس از تولّد، پایه و اساس فنوتیپ موجود زنده (ارگانیسم)، ویژگی‌های فیزیکی و ذهنی از قبیل رنگ چشم و هوش و غیره است.در تولید مثل، ابتدا ترکیب(یا تغییر) اتفاق می‌افتد. ژن‌های والدین برای ایجاد کروموزوم‌های جدید ترکیب می‌شوند. سپس جنین تشکیل شده دچار تغییر می‌شود. جهش به این معناست که عناصر DNA کمی تغییر پیدا میکنند و این تغییرات اغلب نتیجه نسخه‌برداری غلط از ژن‌های والدین است. میزان شایستگی موجود زنده(جنین) به واسطه بقای آن اندازه گیری می‌شود.
در الگوریتم ژنتیک، مجموعه ای از متغیرهای طراحی را توسط رشته‌هایی با طول ثابت یا متغیر کدکذاری میکنند که در سیستم‌های بیولوژیکی آنها را کرروموزوم یا فرد می‌نامند. هر رشته یا کروموزوم یک نقطۀ پاسخ در فضای جستجو را نشان میدهد. به ساختمان رشته‌ها یعنی مجموعه‌ای از پارامترها که توسط یک کروموزوم خاص نمایش داده می‌شود ژنوتیپ و به مقدار رمزگشایی آن فنوتیپ می‌گویند. الگوریتمهای وراثتی فرآیندهای تکراری هستند، که هر مرحلۀ تکراری را نسل و مجموعه‌هایی از پاسخ‌ها در هر نسل را جمعیت نامیده‌اند.الگوریتمهای ژنتیک، جستجوی اصلی را در فضای پاسخ به اجرا می‌گذارند. این الگوریتمها با تولید نسل آغاز می‌شوند که وظیفه ایجاد مجموعه نقاط جستجوی اولیه به نام «جمعیت اولیه» را بر عهده دارند و به طور انتخابی یا تصادفی تعیین می‌شوند. از آنجایی که الگوریتمهای ژنتیک برای هدایت عملیات جستجو به طرف نقطه بهینه از روشهای آماری استفاده میکنند، در فرآیندی که به انتخاب طبیعی وابسته است، جمعیت موجود به تناسب برازندگی افراد آن برای نسل بعد انتخاب می‌شود. سپس عملگرهای ژنتیکی شامل انتخاب ، پیوند(ترکیب)، جهش و دیگر عملگرهای احتمالی اِعمال شده و جمعیت جدید به وجود می‌آید. پس از آن جمعیت جدیدی جایگزین جمعیت پیشین می‌شود و این چرخه ادامه می‌یابد.معمولاً جمعیت جدید برازندگی بیشتری دارد این بدان معناست که از نسلی به نسل دیگر جمعیت بهبود می‌آید. هنگامی جستجو نتیجه‌بخش خواهد بود که به حداکثر نسل ممکن رسیده باشیم یا همگرایی حاصل شده باشد و یا معیارهای توقف برآورده شده باشد.
عملگرهای الگوریتم ژنتیک:به طور خلاصه الگوریتم ژنتیک از عملگرهای زیر تشکیل شده است
کدگذاری[5] :این مرحله شاید مشکلترین مرحله حل مسأله به روش الگوریتم باشد. الگوریتم ژنتیک به جای اینکه بر روی پارامترها یا متغیرهای مسأله کار کند، با شکل کد شدۀ آنها سروکار دارد. یکی از روشهای کد کردن، کد کردن دودویی می باشد که در آن هدف تبدیل جواب مسأله به رشته‌ای از اعداد باینری (در مبنای 2) است.
ارزیابی: تابع برازندگی را از اِعمال تبدیل مناسب بر روی تابع هدف یعنی تابعی که قرار است بهینه شود به دست می‌آورند. این تابع هر رشته را با یک مقدار عددی ارزیابی می‌کند که کیفیت آن را مشخص می‌نماید. هر چه کیفیت رشته جواب بالاتر باشد مقدار برازندگی جواب بیشتر است و احتمال مشارکت برای تولید نسل بعدی نیز افزایش خواهد یافت.
ترکیب: مهمترین عملگر در الگوریتم ژنتیک، عملگر ترکیب است. ترکیب فرآیندی است که در آن نسل قدیمی کروموزومها با یکدیگر مخلوط و ترکیب می‌شوند تا نسل تازه‌ای از کروموزومها بوجود بیاید.جفت‌هایی که در قسمت انتخاب به عنوان والد در نظر گرفته شدند در این قسمت ژن‌هایشان را با هم مبادله میکنند و اعضای جدید بوجود می‌آورند. ترکیب در الگوریتم ژنتیک باعث از بین رفتن پراکندگی یا تنوع ژنتیکی جمعیت می‌شود زیرا اجازه میدهد ژن‌های خوب یکدیگر را بیابند.
جهش[6]: جهش نیز عملگر دیگری هست که جواب‌های ممکن دیگری را متولد می‌کند. در الگوریتم ژنتیک بعد از اینکه یک عضو در جمعیت جدید بوجود آمد هر ژن آن با احتمال جهش، جهش می‌یابد. در جهش ممکن است ژنی از مجموعه ژن‌های جمعیت حذف شود یا ژنی که تا به حال در جمعیت وجود نداشته است به آن اضافه شود. جهش یک ژن به معنای تغییر آن ژن است و وابسته به نوع کدگذاری روشهای متفاوت جهش استفاده می‌شود.
رمزگشایی[7]: رمزگشایی، عکسِ عمل رمزگذاری است. در این مرحله بعد از اینکه الگوریتم بهترین جواب را برای مسأله ارائه کرد لازم است عکس عمل رمزگذاری روی جواب‌ها یا همان عمل رمزگشایی اعمال شود تا بتوانیم نسخه واقعی جواب را به وضوح در دست داشته باشیم.