علاوه بر موتاسیون اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به موتاسیون رخ می‌دهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است.48 این همان چیزیست که مثلاً باعث می‌شود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری می‌کند.
حال می‌توانیم اینگونه بیان کنیم که: الگوريتم ژنتيک ابزاری می‌باشد که توسط آن ماشين می‌تواند مكانيزم انتخاب طبيعی را شبيه سازی نمايد. اين عمل با جستجو در فضای مسأله جهت يافتن جواب برتر و نه الزاماً بهينه صورت می‌پذيرد. الگوریتم ژنتیک را می‌توان یک روش جستجوی کلّی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید می کند. در واقع الگوریتم‌های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون49 هستند.
مكانيزم الگوريتم ژنتيك
الگوريتم ژنتيك به عنوان يك الگوريتم محاسباتيِ بهينه‌سازي با در نظر گرفتن مجموعه‌اي از نقاط فضاي جواب در هر تكرار محاسباتي به نحو مؤثري نواحي مختلف فضاي جواب را جستجو مي‌كند. در مكانيزم جستجو گرچه مقدار تابع هدف تمام فضاي جواب محاسبه نمي‌شود ولي مقدار محاسبه شده تابع هدف براي هر نقطه، در متوسط‌گيري آماري تابع هدف در كليه زير فضاهايي كه آن نقطه به آنها وابسته بوده دخالت داده مي‌شود و اين زير فضاها به طور موازي از نظر تابع هدف متوسط‌گيري آماري مي‌شوند. اين مكانيزم را توازي ضمني50 مي‌گويند. اين روند باعث مي‌شود كه جستجوي فضا به نواحي از آن كه متوسط آماري تابع هدف در آنها زياد بوده و امكان وجود نقطه بهينه مطلق در آنها بيشتر است سوق پيدا كند. چون در اين روش برخلاف روشهاي تك‌مسيري فضاي جواب به طور همه جانبه جستجو مي‌شود، امكان كمتري براي همگرايي به يك نقطه بهينه محلي وجود خواهد داشت.
امتياز ديگر اين الگوريتم آن است كه هیچ محدوديتي براي تابع بهينه شونده، مثل مشتق‌پذيري يا پيوستگي لازم ندارد و در روند جستجو خود تنها به تعيين مقدار تابع هدف در نقاط مختلف نياز دارد و هيچ اطلاعاتِ كمكي ديگري، مثل مشتق تابع را استفاده نمي‌كند. لذا مي‌توان در مسائل مختلف اعم از خطي، پيوسته يا گسسته استفاده مي‌شود و به سهولت با مسائل مختلف قابل تطبيق است.
در هر تكرار هر يك از رشته‌هاي موجود در جمعيت رشته‌ها، رمزگشايي شده و مقدار تابع هدف براي آن به دست می‌آید. بر اساس مقادیر به دست آمده تابع هدف در جمعیت رشته‌ها، به هر رشته يك عدد برازندگي نسبت داده مي‌شود. اين عدد برازندگي احتمال انتخاب را براي هر رشته تعيين خواهد كرد. بر اساس اين احتمال انتخاب، مجموعه‌اي از رشته‌ها انتخاب شده و با اعمال عملكردهاي ژنتيكي روي آنها رشته‌هاي جديد جايگزين رشته‌هايي از جمعيت اوليه مي‌شوند تا تعداد جمعيت رشته‌ها در تكرارهاي محاسباتي مختلف ثابت باشد. مكانيزم‌هاي تصادفي كه روي انتخاب و حذف رشته‌ها عمل مي‌كنند به گونه‌اي هستند كه رشته‌هايي كه عدد برازندگي بيشتري دارند، احتمال بيشتري براي تركيب و توليد رشته‌هاي جديد داشته و در مرحله جايگزيني نسبت به ديگر رشته‌ها مقاوم‌تر هستند. بدين لحاظ جمعيت دنباله‌ها در يك رقابت بر اساس تابع هدف در طيّ نسل‌هاي مختلف، كامل شده و متوسط مقدار تابع هدف در جمعيت رشته‌ها افزايش مي‌يابد. بطور كلي در اين الگوريتم ضمن آنكه در هر تكرار محاسباتي، توسط عملگرهاي ژنتيكي نقاطي جديد از فضاي جواب مورد جستجو قرار مي‌گيرند توسط مكانيزم انتخاب، روند جستجوي نواحي از فضا را كه متوسط آماري تابع هدف در آنها بيشتر است، كنكاش مي‌كند. بر اساس سيكل اجرايي فوق، در هر تكرار محاسباتي، توسط عملگرهاي ژنتيكي نقاط جديدي از فضاي جواب مورد جستجو قرار مي‌گيرند توسط مكانيزم انتخاب، روند جستجو نواحي از فضا را كه متوسط آماري تابع هدف در آنها بيشتر است، كنكاش مي‌كند. که بر این اساس، در هر تكرار محاسباتي، سه عملگر اصلي روي رشته‌ها عمل مي‌كند؛ اين سه عملگر عبارتند از: دو عملگر ژنتيكي و عملكرد انتخابي تصادفي. «گلد برگ»51 الگوريتم ژنتيكي «جان هولند» را با عنوان الگوريتم ژنتيك ساده52 معرفي مي‌كند؛ الگوريتم ژنتيك را از الگوريتم ژنتيك طبيعي اقتباس كردند.. در الگوريتم ژنتيك، مجموعه اي از متغيرهاي طراحي را توسط رشته‌هايي با طول ثابت53 يا متغير54 كدكذاري مي‌كنند كه در سيستم‌هاي بيولوژيكي آنها را كرروموزوم يا فرد55 مي‌نامند. هر رشته یا کروموزوم يك نقطۀ پاسخ در فضاي جستجو را نشان مي‌دهد. به ساختمان رشته‌ها يعني مجموعه‌اي از پارامترها كه توسط يك كروموزوم خاص نمايش داده مي‌شود ژنوتيپ56 و به مقدار رمزگشايي آن فنوتيپ57 مي‌گويند. الگوريتم‌هاي وراثتي فرآيندهاي تكراري هستند، كه هر مرحلۀ تكراري را نسل و مجموعه‌هايي از پاسخ‌ها در هر نسل را جمعيت ناميده‌اند.
الگوريتم‌هاي ژنتيك، جستجوي اصلي را در فضاي پاسخ به اجرا مي‌گذارند. اين الگوريتم‌ها با توليد نسل58 آغاز مي‌شوند كه وظيفه ايجاد مجموعه نقاط جستجوي اوليه به نام «جمعيت اوليه»59 را بر عهده دارند و به طور انتخابي يا تصادفي تعيين مي‌شوند. از آنجايي كه الگوريتم‌هاي ژنتيك براي هدايت عمليات جستجو به طرف نقطه بهينه از روشهاي آماري استفاده مي‌كنند، در فرآيندي كه به انتخاب طبيعي وابسته است، جمعيت موجود به تناسب برازندگي افراد آن براي نسل بعد انتخاب مي‌شود. سپس عملگرهاي ژنتيكي شامل انتخاب60 ، پيوند(ترکیب)، جهش و ديگر عملگرهاي احتمالي اِعمال شده و جمعيت جديد به وجود مي‌آيد. پس از آن جمعيت جديدي جايگزين جمعيت پيشين مي‌شود و اين چرخه ادامه مي‌يابد.
معمولاً جمعيت جديد برازندگي بيشتري دارد اين بدان معناست كه از نسلي به نسل ديگر جمعيت بهبود مي‌آيد. هنگامي جستجو نتيجه‌بخش خواهد بود كه به حداكثر نسل ممكن رسيده باشيم يا همگرايي حاصل شده باشد و يا معيارهاي توقف برآورده شده باشد.
عملگرهاي الگوريتم ژنتيك
الگوريتم ژنتيك از عملگرهاي زير تشكيل شده است:
کدگذاری61
اين مرحله شايد مشكلترين مرحله حل مسأله به روش الگوريتم باشد. الگوريتم ژنتيك به جاي اينكه بر روي پارامترها يا متغيرهاي مسأله كار كند، با شكل كد شدۀ آنها سروكار دارد. يكي از روشهاي كد كردن، كد كردن دودويي مي باشد كه در آن هدف تبديل جواب مسأله به رشته‌اي از اعداد باينري (در مبناي 2) است.
انتخاب
در مرحله انتخاب، يك جفت از كروموزوم‌ها برگزيده مي‌شوند تا با هم تركيب شوند، عملگر انتخاب رابط بين دو نسل است و بعضي از اعضاي نسل كنوني را به نسل آينده منتقل مي‌كند، بعد از انتخاب، عملگرهاي ژنتيك روي دو عضو برگزيده اعمال مي‌شوند، معيار در انتخاب اعضاء ارزش تطابق آنها مي‌باشد اما روند انتخاب حالتي تصادفي دارد.
بطور کلی روشهاي متداول انتخاب در الگوریتم ژنتیک عبارتند از:
انتخاب چرخ رولت – انتخاب مسابقه تصادفي – انتخاب بولتزمن – نخبه سالاري
انتخاب رقابتي – انتخاب قطع سر – انتخاب قطعي بريندل – انتخاب حالت پايدار
انتخاب جايگزيني نسلي اصلاح شده – انتخاب مسابقه (تورنمنت) – انتخاب ترتيبي
ارزیابی62
تابع برازندگي را از اِعمال تبديل مناسب بر روي تابع هدف يعني تابعي كه قرار است بهينه شود به دست مي‌آورند. اين تابع هر رشته را با يك مقدار عددي ارزيابي مي‌كند كه كيفيت آن را مشخص مي‌نمايد. هر چه كيفيت رشته جواب بالاتر باشد مقدار برازندگي جواب بيشتر است و احتمال مشاركت براي توليد نسل بعدي نيز افزايش خواهد يافت.
ترکیب63
مهمترين عملگر در الگوريتم ژنتيك، عملگر ترکیب است. تركيب فرآيندي است كه در آن نسل قديمي كروموزوم‌ها با يكديگر مخلوط و تركيب مي‌شوند تا نسل تازه‌اي از كروموزوم‌ها بوجود بيايد.
جفت‌هايي كه در قسمت انتخاب به عنوان والد در نظر گرفته شدند در اين قسمت ژن‌هايشان را با هم مبادله مي‌كنند و اعضاي جديد بوجود مي‌آورند. تركيب در الگوريتم ژنتيك باعث از بين رفتن پراكندگي يا تنوع ژنتيكي جمعيت مي‌شود زيرا اجازه مي‌دهد ژن‌هاي خوب يكديگر را بيابند. متداولترین روشهای ترکیب عبارتند از :
جابه‌جایی دودوئی، جابه‌جایي حقيقي، ترکیب تک‌نقطه‌ای، ترکیب دو نقطه‌ای، ترکیب n نقطه‌ای، ترکیب یکنواخت، ترکیب حسابی، ترتیب، محدّب، بخش نگاشته، چرخه.
جهش64
جهش نيز عملگر ديگري هست كه جواب‌هاي ممكن ديگري را متولد مي‌كند. در الگوريتم ژنتيك بعد از اينكه يك عضو در جمعيت جديد بوجود آمد هر ژن آن با احتمال جهش، جهش مي‌يابد. در جهش ممكن است ژني از مجموعه ژن‌هاي جمعيت حذف شود يا ژني كه تا به حال در جمعيت وجود نداشته است به آن اضافه شود. جهش يك ژن به معناي تغيير آن ژن است و وابسته به نوع كدگذاري روشهاي متفاوت جهش استفاده مي‌شود.
انواع روشهای عملگر جهش عبارتند از :
جهش باينري، جهش حقيقي، وارونه سازی بیت، تغییر ترتیب قرارگیری، وارون سازی، تغییر مقدار.
رمزگشايي65
رمزگشایی، عكسِ عمل رمزگذاری است. در اين مرحله بعد از اينكه الگوريتم بهترين جواب را براي مسأله ارایه كرد لازم است عكس عمل رمزگذاري روي جواب‌ها يا همان عمل رمزگشایی اعمال شود تا بتوانيم نسخه واقعي جواب را به وضوح در دست داشته باشيم.
نقاط قوّت الگوریتم‌های ژنتیک
اولین و مهمترین نقطه قوّت این الگوریتم‌ها این است که الگوریتم‌های ژنتیک ذاتاً موازی‌اند. اکثر الگوریتم‌های دیگر موازی نیستند و فقط می‌توانند فضای مسأله مورد نظر را در یک جهت در یک لحظه جستجو کنندو اگر راه‌حل پیدا شده یک جواب بهینه محلی باشد و یا زیر مجموعه‌ای از جواب اصلی باشد باید تمام کارهایی که تا به حال انجام شده را کنار گذاشت و دوباره از اول شروع کرد. از آنجایی که GA چندین نقطه شروع دارد، در یک لحظه می‌تواند فضای مسأله را از چند جهت مختلف جستجو کند. اگر یکی به نتیجه نرسید سایر راه‌ها ادامه می‌یابند و منابع بیشتری را در اختیارشان قرار می‌گیرد.
به دلیل موازی بودن و این که چندین رشته در یک لحظه مورد ارزیابی قرار می‌گیرند الگوریتم های ژنتیک برای مسائلی که فضای راه‌حل بزرگی دارند بسیار مفیدند. اکثر مسائلی که این گونه‌اند به عنوان غیرخطی شناخته شده‌اند. در یک مسأله خطی،Fitness هر عنصر مستقل است، پس هر تغییری در یک قسمت بر تغییر و پیشرفت کل سیستم تأثیر مستقیم دارد. می‌دانیم که تعداد کمی از مسائل دنیای واقعی به صورت خطی‌اند. در مسائل غیرخطی تغییر در یک قسمت ممکن است تاثیری ناهماهنگ بر کل سیستم و یا تغییر در چند عنصر تاثیر فراوانی بر سیستم بگذارد. خوشبختانه موازی بودن GA باعث حل این مسأله می‌شود و در مدت کمی مشکل حل می‌شود. مثلاً برای حل یک مسأله خطی 1000 رقمی 2000 امکان حل وجود دارد ولی برای یک غیرخطی 1000 رقمی امکان. یکی از نقاط قوت الگوریتم‌های ژنتیک که در ابتدا یک کمبود به نظر می‌رسد این است که: GA ها هیچ چیزی در مورد مسائلی که حل می‌کنند نمی‌دانند و اصطلاحاً به آنها «ساعت‌ساز نابینا»66 می‌گوییم. آنها تغییرات تصادفی را در راه‌حل‌های کاندیدشان می‌دهند و سپس از تابع برازش برای سنجش این که آیا آن تغییرات پیشرفتی ایجاد کرده‌اند یا نه، استفاده می‌کنند. مزیت این تکنیک این است که به GA اجازه می‌دهد تا با ذهنی باز شروع به حل مسائل کند. از آنجایی که تصمیمات آن اساساً تصادفی است، بر اساس تئوری همه راه‌حل‌های ممکن به روی مسأله باز است، ولی مسائلی که محدود به اطلاعات هستند باید از راه قیاس تصمیم بگیرند و در این صورت بسیاری از راه‌حل‌های نو و جدید را از دست می‌دهند.
یکی دیگر از مزایای الگوریتم این است که آنها می‌توانند چندین پارامتر را همزمان تغییر دهند. بسیاری از مسائل واقعی نمی‌توانند محدود به یک ویژگی شوند تا آن ویژگی ماکسیمم شود و باید چند جانبه در نظر گرفته شوند.GA ها در حل این گونه مسائل بسیار مفیدند، و در حقیقت قابلیت موازی کار کردن آنها این خاصیت را
