۳-۲-۱ روش­های بهینه سازی محلی
الگوریتم­های بهینه سازی محلی دارای برخی مزایا از قبیل سرعت همگرایی خوب و بازسازی نسبتا مناسب می­باشند. به همین دلیل در اغلب مسائل معکوس از این روش­ها استفاده می­ شود. این الگوریتم­ها امکان گیر افتادن در مینیمم محلی را دارند که در این صورت به جواب نادرست همگرا می­شوند. برای اینکه این مشکل تا حدی برطرف شود، به اطلاعات اولیه در مورد نقطه شروع نیاز است. روش­های برنامه ریزی ریاضی از جمله گرادیان مزدوج و روش­های شبه نیوتونی و روش­های بدون گرادیان مثل روش سیمپلکس در زمره روش­های بهینه سازی محلی قرار دارند.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

۳-۲-۲ روش­های بهینه سازی همگانی
روش­های بهینه سازی محلی اغلب برای حل مسائل معکوس به کار می­روند. این روش­ها زمانی به جواب همگانی همگرا می­شوند که اطلاعات پیشین در مورد حدس اولیه به تعریف تابع هدف افزوده شود. به هر حال هیچ اطمینانی وجود ندارد که بدون اطلاعات قبلی، روش بهینه سازی محلی به مینیمم بهینه دست پیدا کند. بنابراین به منظور غلبه بر این محدودیت، روش بهینه سازی همگانی به کار برده می­ شود. در روش بهینه سازی همگانی، نیاز به تعیین حدس اولیه ^[۳۹] برای حرکت به سمت مینیمم نیست، ولی محدوده پارامترها بایستی مشخص گردند. هرگونه اطلاعات قبلی در مورد پارامترها، محدوده آنها را کوچکتر کرده و این منجر به همگرایی سریعتر الگوریتم می­ شود.
مسئله بهینه سازی همگانی، پیدا کردن یک جواب از میان مجموعه جواب­های قابل قبول است که تابع هدف به ازای آن کمترین مقدار را داشته باشد. یک مسئله بهینه سازی همگانی برای تابع  به صورت زیر قابل تعریف است.
تعریف: بافرض  و  (  مجموعه اعداد حقیقی است). با پیدا کردن  به طوری که به ازای هر  وجود داشته باشد  ، آنگاه  مینیمم کننده همگانی تابع هدف است و  مینیمم همگانی است. ناحیه قابل قبول  معمولا به صورت  تعیین می­ شود که  و  به ترتیب حدود پایین و بالای متغیر  هستند.
اولین روش بهینه سازی همگانی، همان روش­های بهینه سازی محلی بودند که از چندین نقطه تابع هدف، فرایند بهینه سازی شروع می­شد. نقاط شروع به صورت تصادفی در ناحیه  تولید می­شوند. یک عیب عمده چنین روشی این است که همگرایی به یک مینیمم ممکن است چندین بار تکرار شود. در ادامه روش­های مختلف با بازدهی بیش­تر پیشنهاد شده ­اند که این روش­ها به دو دسته یقینی ^[۴۰]و تصادفی^[۴۱] قابل تقسیم هستند.
در بیش­تر روش­های یقینی، تضمینی برای پیدا کردن مینیمم بهینه وجود ندارد. اما این تضمین تحت فرضیات اضافی در مورد تابع هدف انجام پذیر است. علاوه بر آن، محاسبات زیادی به منظور یافتن مینیمم همگانی نیاز است. در روش تصادفی یک سری خصوصیات تصادفی به روش جست وجو اضافه می­ شود و به طور کلی نمونه برداری از تابع هدف روی ناحیه قابل قبول در نقاط با توزیع تصادفی انجام می­گیرد. این روش دارای یک تضمین احتمالی برای یافتن مینیمم همگانی است. از جمله الگوریتم­های همگانی تصادفی، الگوریتم ژنتیک GA ^[۴۲] و باز پخت شبیه سازی شده ^[۴۳]SA را می­توان نام برد.
۳-۳ طراحی الگوریتم حل مسائل معکوس با بهره گرفتن از روش­های بهینه سازی
در فصل قبل مشاهده شد که چگونه یک مسئله مستقیم الاستواستاتیک به روش المان­های مرزی حل می­ شود. در مسئله مستقیم جای حفره­ها مشخص بوده و با اعمال بار روی مرز خارجی مقدار جا به ­جایی­ها و ترکشن­ها روی همه مرزها، چه مرز حفره­ها و چه مرز خارجی مشخص می­شوند. در واقع هنگامی که مسئله به صورت مستقیم حل می­ شود، شکل حفره­ها مشخص می­باشد و مجهولات تنها میزان جا به ­جایی­ها و ترکشن­ها روی مرزها هستند. همان طور که مشاهده شد روش المان­های مرزی روشی است که بین گره­های موجود روی مرزها ارتباط برقرار می­ کند. هنگامی که یک مسئله به روش المان­های مرزی شبیه سازی می­ شود در قدم اول ارتباط بین گره­های موجود روی مرزها با یکدیگر روشن می­ شود. که این ارتباط در قالب ماتریس­های Hو G بیان گردید.
هنگامی که مسئله به صورت معکوس حل می­ شود، مجهولات تغییر می­ کنند. به این صورت که میزان جا به ­جایی­ها و ترکشن­ها روی مرز آزاد خارجی معلوم در نظر گرفته می­ شود و سپس به بررسی این موضوع پرداخته می­گردد که برای اینکه جا به ­جایی­ها روی مرز خارجی به شکل اندازه گیری شده اتفاق بیفتد، موقعیت و شکل حفره­ها به چه صورتی باید باشد. در واقع در روش معکوس، ورودی­ ها میزان جا به ­جایی­های قابل اندازه گیری روی مرز خارجی و خروجی­های موقعیت و شکل حفره­ها می­باشد.
روش­های بهینه سازی همواره از شیوه ­های متداول حل مسائل معکوس می­باشند. بهینه سازی به فرایند یافتن بهترین مقادیر ممکن برای یک مجموعه متغیرهای متعلق به یک سیستم اطلاق می­ شود، تا جایی که قیود مختلف اعمال شده بر مجموعه متغیر­ها برآورده گردند. عبارت بهترین نشان می­دهد که در یک مسئله بهینه سازی، یک یا چند شی طراحی می­ شود به گونه ­ای که تصمیم گیرنده امیدوار است با کم یا زیاد نمودن مقادیر، به پاسخ بهینه دست پیدا کند. یک مسئله بهینه سازی از نظر ریاضی به صورت جست و جو برای یک بردار از مجموعه متغیرها مانند متغیرهای  می­باشد، به گونه ­ای که مقدار تابع F(x) را که وابسته به بردار  است، کمینه یا بیشینه سازد. در این حالت F(x) تابع هدف^[۴۴] نامیده می­ شود. مؤلفه­ های بردار  متغیرهای مسئله بوده و متغیر­های طراحی ^[۴۵] خوانده می­شوند که پاسخ روش­های بهینه سازی هستند. در واقع این مؤلفه­ ها به صورتی با بهره گرفتن از روش­های بهینه سازی محاسبه می­شوند که تابع هدف را مینیمم کند.
برای مسئله معکوس الاستیسیته تابع هدف به صورتی در نظر گرفته می­ شود که با محاسبه موقعیت مرزهای معایب، قدر مطلق اختلاف جا به ­جایی­های اندازه ­گیری شده روی مرز خارجی و جا به ­جایی­های به دست آمده با در نظر گرفتن مرزهای محاسبه شده مینیمم گردد. رابطه زیر این تابع هدف را نشان می­دهد.
۳-۱
روند کلی حل معکوس معادله الاستیسیته که در این پژوهش از آن استفاده شده است، بدین صورت است که ابتدا جسم تحت بارگذاری قرار می­گیرد و جا به ­جایی­های روی مرز خارجی اندازه ­گیری می­شوند، این جا به ­جایی­ها در رابطه (۳-۱) با  نشان داده شده است.M تعداد گره­های مرز آزاد خارجی می­باشد که جا به ­جایی­های آنها اندازه ­گیری می­ شود و m بیانگر شماره گره می­باشد. سپس فرایند حل معکوس آغاز می­ شود، یعنی با بهره گرفتن از فرایندهای بهینه سازی مثل الگوریتم ژنتیک ابتدا یک حدس اولیه محاسبه می­ شود، سپس با فرض صحت آن فرض در دامنه، جا به ­جایی­های ایجاد شده بر اثر همان بار گذاری قبلی روی مرز خارجی اندازه گیری می­گردد. این جا به ­جایی­ها در رابطه (۳-۱) با  نشان داده شده ­اند. در نهایت با بهره گرفتن از رابطه (۳-۱) اختلاف موجود اندازه ­گیری می­ شود و سعی می­ شود در هر مرحله حدس حفره­ها، این اختلاف به حداقل مقدار ممکن برسد تا معایب موجود در دامنه مشخص گردند.
الگوریتم حل که در این پژوهش مورد استفاده قرار گرفته است، بر مبنای تلفیقی از روش­های بهینه سازی همگانی و محلی می­باشد. روش­های بهینه سازی محلی که اغلب برای حل مسائل معکوس به کار می­روند، زمانی به جواب مینیمم مطلق همگرا می­شوند که اطلاعات کافی در مورد حدس اولیه به تعریف تابع هدف افزوده شود؛ اما هیچ اطمینانی وجود ندارد که بدون اطلاعات مناسب، روش بهینه سازی محلی به مینیمم بهینه دست پیدا کند. بنابراین به منظور غلبه بر این محدودیت، روش­های بهینه سازی همگانی به کار برده می­شوند. در روش بهینه سازی همگانی، نیاز به تعیین حدس اولیه برای حرکت به سمت مینیمم نیست، ولی محدوده پارامترها بایستی مشخص گردند. در واقع هر گونه اطلاعات قبلی در مورد پارامترها، محدوده آنها را کوچکتر کرده و منجر به همگرایی سریعتر الکوریتم می­ شود. روش بهینه سازی که در این پژوهش مورد استفاده قرار گرفته است مبتنی بر الگوریتم ژنتیک (به عنوان روش بهینه سازی همگانی) می­باشد که به صورت ترکیبی با روش­های بهینه سازی محلی از جمله روش گرادیان مزدوج و روش سیمپلکس^[۴۶] مورد استفاده قرار گرفته است. در ادامه به توضیحات بیشتری در مورد این الگوریتم­ها پرداخته می­ شود.
۳-۳-۱ الگوریتم ژنتیک
الگوریتم ژنتیک]۳۱[ را می­توان به صورت ساده، یک روش جست و جوگر نامید که بر پایه مشاهدات خصوصیات فرزندان نسل­های متوالی و انتخاب فرزندان بر اساس اصل بقای بهترین، پایه­ریزی شده است. الگوریتم ژنتیک روی فرزندان یک نسل از قوانین موجود در علم ژنتیک تقلید کرده و با به کار بردن آنها به تولید فرزندان با خصوصیت بهتر می ­پردازد و در هر نسل به کمک فرایند انتخابی متناسب با ارزش جواب­ها و تولید مثل فرزندان انتخاب شده تقریب­های بهتری از جواب نهایی به دست می ­آید. این فرایند باعث می­ شود که نسل­های جدید با شرایط مسئله سازگار­تر باشند. این رقابت میان ژن­ها و پیروز شده ژن غالب(انتخاب شدن توسط الگوریتم برای تولید مثل بعدی) و کنار رفتن ژن مغلوب (جواب­های دور از هدف مسئله) روشی است که الگوریتم ژنتیک برای حل مسئله استفاده می­ کند.
۳-۳-۱-۱ ساختار الگوریتم ژنتیک
۳-۳-۱-۱-۱ افراد یا کروموزوم­ها
هر کدام از افراد جمعیت که تقریب­هایی از جواب نهایی هستند، به صورت رشته­هایی از حروف یا ارقام کد گذاری می­شوند. این رشته­ها را کروموزوم می­نامند. متداول ترین حالت، نمایش با ارقام صفر و یک می­باشد. حالات دیگر مثل استفاده از اعداد حقیقی و اعداد صحیح هم مورد استفاده قرار می­گیرند.
مقادیر موجود بر روی کوروموزوم­ها به تنهایی معنی خاصی ندارند، بلکه باید ترجمه شوند، یعنی از حالت کد خارج شوند تا به عنوان متغیرهای تصمیم گیری دارای معنی و نتیجه باشند. باید توجه داشت که فرایند جست و جو، روی اطلاعات کد شده صورت می­گیرید، مگر در صورتی که از ژن­هایی با مقادیر حقیقی استفاده شود. بعد از این که کروموزوم­ها از حالت کد گذاری شده خارج شدند، می­توان به کمک اطلاعات اولیه­ای که توسط مقادیر هدف مسئله به دست می ­آید، آن­ها را مورد بررسی قرار داد.
۳-۳-۱-۱-۲ کدگذاری
کدگذاری یکی از عناصر مهم و تعیین کننده در هر الگوریتم ژنتیک است. به تبدیل پاسخ مسئله به صورت یک ساختار (کروموزم) که از مجموعه ­ای از ژن­ها تشکیل یافته، کدگذاری می­گویند. همان طور که توضیح داده شد کروموزم یک آرایه منظم با طول ثابت از مقادیر الل^[۴۷] (ژنـهای نام همسان مجاور) می­باشد. در واقع الگوریتم ژنتیک به جای این که به طور مستقیم بر روی پارامترها یا متغیرهای مساله کار کند، با شکل کد شده آنها سر­وکار دارد. تاکنون محدودیت خاصی برای ساختار ژنها مطرح نشده است، به همین دلیل روش­های متنوعی برای کدگذاری مسائل مورد استفاده قرار می­گیرد. باید توجه داشت که نوع عملیات مورد نیاز در بسیاری از مراحل الگوریتم زنتیک به شدت وابسته به نوع ساختار انتخابی (کدگذاری) می­باشد. در ادامه این فصل به صورت مختصر به بیان این تفاوت­ها خواهیم پرداخت.
۳-۳-۱-۱-۲-۱ کدگذاری دودویی
این نوع از کدگذاری متداول­ترین نوع کدگذاری در الگوریتم ژنتیک می­باشد. هر ژن در این ساختار به صورت باینری بوده (صفر یا یک) و ساختار کروموزم عموماً به صورت یک آرایه ساده می­باشد. در کدگذاری دودویی هدف تبدیل جواب مساله به آرایه­ای از اعداد باینری (در مبنای ۲) می­باشد. این روش ساده ترین نوع کدگذاری می­باشد و تقریبا امکان تبدیل انواع دیگر کدگذاری به این روش امکان پذیر است (در بعضی مسائل بسیار مشکل است). در حقیقت این روش برگرفته از ساختار ژنتیکی موجودات زنده می­باشد، با این تفاوت که در موجودات زنده ترکیبی از چند ژن یک صفت خاص را بروز می­ دهند یا به بیان ساده­تر برخی از ژنها با یکدیگر دارای رابطه معنایی هستند و هر ژن بیانگر یک خصوصیت می­باشد. این روش علی رغم کاربرد زیاد، دارای معایبی نیز می­باشد که منجر به گسترگی فضای پاسخ مسئله می­گردد ( برای کروموزمی با تعداد n ژن، تعداد حالات مختلف کروموزم ۲ⁿ می­باشد، این مشکل بدین صورت عنوان شده است: ” اصولاً روش کدگذاری دودویی، امکان تولید کروموزم­های بسیاری را با حداقل بیت فراهم می­ کند. لذا این روش کدگذاری در مسائل واقعی باید همراه با اصلاحاتی بعد از اعمال عملگرهای ژنتیکی صورت گیرد". مزایای این روش سادگی عملگرهای ژنتیک و امکان تبدیل تمامی مسائل ژنتیکی به این ساختار می­باشد. این روش کدگذاری برای مسائلی که در آنها تمامی حالات کروموزم، نوعی پاسخ مسئله به شمار می­آیند، بسیار مناسب می­باشد.
۳-۳-۱-۱-۲-۲ کدگذاری جایگشتی
در این روش، کروموزم­ها به صورت آرایه­ای (عموما یک بعدی) از اعداد نمایش داده می­شوند، به نحوی که اعداد موجود در هر کروموزم منحصربه فرد باشند. معمولا برای آرایه n عنصری، اعداد از ۱ تا n را به عنوان مقادیر ژنهای کروموزم در نظر می­گیرند. باید توجه داشت که به دلیل عدم پذیرش اعداد تکراری، عملگرهای ژنتیک در این حالت کمی پیچیده­تر از حالت دودویی هستند. در این روش تعداد حالات مختلف کروموزم n! می­باشد. شاید در نگاه اول از نظر فرمول، پیچیدگی فضای پاسخ این حالت بیشتر از حالت دودویی باشد اما باید دقت داشت که برای تبدیل این حالت به فرم دودویی لازم است به ازای هرخانه در حالت جایگشتی [logn-1]+1 خانه در حالت دودویی داشته باشیم که به دلیل عدم وابستگی خانه­ها به یکدیگر امکان حذف حالاتی که اعداد تکراری نداشته باشیم مشکل خواهد بود. بنابراین پیچیدگی فضای پاسخ در حالت جایگشتی کمتر از حالت دودویی خواهد بود. از مزایای دیگر این روش این است که روش جایگشتی در برخی مسائل به صورت بسیار مناسب، توصیفی از پاسخ مسئله را در خود خواهد داشت.
مثال بسیار مناسب برای روش جایگشتی، مسئله فروشنده دوره­گرد است. در این مسئله هدف یافتن مسیری است که از هر شهر فقط و تنها فقط یک بار عبور نمایید، به نحوی که کمترین مسافت ممکن طی شود. برای این مسئله هر عدد بیانگر یک شهر و آرایه(کروموزم) بیان کننده ترتیب رفتن به شهر­های مختلف می­باشد. واضح است که استفاده از کدگذاری دودویی برای حل این مسئله، علاوه بر بزرگ نمودن فضای پاسخ و پیچیده نمودن عملگرها، تشخیص پاسخ مسئله از روی کروموزم را مشکل­تر می­نماید، زیرا نیازمند تبدیل کدهای باینری به کد شهرها می­باشد. کار صورت گرفته در این تحقیق، مسئله جداول زمانی را بر اساس روش جایگشتی به همراه مقداری تغییر و اصلاحات در این ساختار کدگذاری می­نماید.
۳-۳-۱-۱-۲-۳ کدگذاری مقداری
در این روش هر کروموزم به صورت آرایه­ای ساده از مقادیری است که این مقادیر می ­تواند هر چیز مرتبط با مساله باشد. مثلا اعداد اعشاری، کاراکتر و یا اشیاء کد شده نمونه­هایی از مقادیر مورد استفاده می­باشند. این روش در حل مسائل خاصی کاربرد دارد. مثلا برای پیدا کردن وزن­های شبکه ­های عصبی، یعنی وزن­های لایه ورودی، لایه مخفی و لایه خروجی می­توان از این روش استفاده نمودکه مقادیر ژن­های کروموزم همان وزن­های شبکه خواهند بود.
۳-۳-۱-۱-۴ کدگذاری درختی
در این روش به جای استفاده از ساختار آرایه­ای(پیوسته و محدود)، برای سازماندهی ژن­ها از ساختار درختی استفاده می­نماییم. از این روش برای برنامه نویسی ژنتیک و زبان­های برنامه نویسی (هوش مصنوعی) استفاده می­ شود. در روش کدگذاری درختی، هر کروموزم به صورت یک درختی از اشیاء مثل توابع یا دستورات می­باشد. به عنوان مثال در زبان LISP از این روش استفاده می­ شود.
۳-۳-۱-۱-۳ تابع برازش
تابع برازش بر اساس مجموعه ­ای از صفات ورودی(کروموزم­ها) یک مقدار خروجی تولید می­ کند. این تابع می ­تواند بر اساس فرمول ریاضی یا آزمایش محاسبه گردد. در واقع تابع برازش براساس پارامترهای مورد توجه برای حل یک مسئله، کیفیت یک پاسخ(کروموزم) را به صورت عددی مشخص می­نماید. در صورتی که این عدد، میزان مطلوبیت کروموزم را نشان دهد، مسئله مورد نظر از جمله مسائل ماکزیمم سازی است(هدف الگوریتم ژنتیک ایجاد کروموزمی خواهد بود که مقدار تابع برازش آن کروموزم ماکزیمم باشد) و اگر بیانگر میزان نامناسب بودن کروموزم باشد، مسئله مینیمم سازی می­باشد(الگوریتم ژنتیک به دنبال ایجاد کروموزمی با مقدار تابع برازش مینیمم می­باشد). اغلب، تابع برازش را برابر با همان تابع هدف مساله بهینه‌سازی در نظر می‌گیرند.
۳-۳-۱-۱-۴ جمعیت
الگوریتم ژنتیک بوسیله مجموعه ­ای از کروموزم­ها شروع به کار می­نماید. به این مجموعه، جمعیت می­گویند. برای اجرای الگوریتم ژنتیک لازم است جمعیت اولیه­ای (تصادفی) معرفی نماییم. تعیین تعداد کروموزم­های جمعیت بسیار مهم و تاثیر گذار است. افزایش تعداد کروموزم­ها در جمعیت از یک سو کیفیت جواب­ها و تنوع آنها را افزایش می­دهد و از سوی دیگر به دلیل نیاز به انجام عملیات­های بیشتر، سرعت ایجاد جمعیت­های جدید را کاهش می­دهد. به همین دلیل انتخاب عدد مناسب برای تعداد کروموزم­های جمعیت، تاثیر زیادی در کیفیت جواب­ها و سرعت رسیدن به آنها دارد. گرچه نمی­ توان عدد خاصی را برای تمامی الگوریتم­های ژنتیک عنوان نمود اما به دلیل اینکه افزایش تعداد کرموزم­های جمعیت، از یک محدوده به بعد تاثیر چندانی در بهبود کیفیت پاسخ­ها ندارد، می­توان با انجام آزمایش در این محدوده، عددی را یافته و آن را به عنوان تعداد کروموزم­های جمعیت در نظر گرفت.
۳-۳-۱-۱-۵ انتخاب
در این مرحله از الگوریتم ژنتیک، دو والد جهت جفت­گیری و تولید کروموزم جدید انتخاب می­شوند. روش انتخاب باید به نحوی باشد که احتمال انتخاب کروموزم­های برتر(از نظر تابع برازش) بیشتر باشد. در زیر تعدادی از روش­های انتخاب بررسی می­گردد. این انتخاب بر پایه برازش می­باشد. یعنی کروموزوم­هایی که دارای برازندگی بالاتری در مرحله برازش باشند، برای جفت­گیری آماده می­شوند. نمونه­هایی از نحوه انتخابی در ادامه توضیح داده می­ شود.
۳-۳-۱-۱-۵-۱ انتخاب تصادفی
در این روش یک کروموزم به صورت کاملا تصادفی انتخاب می­گردد. البته توابع مختلفی را می­توان برای ایجاد عدد تصادفی پیشنهاد داد. از این روش ‌جهت انتخاب کروموزم­های والد استفاده شده است.
۳-۳-۱-۱-۵-۲ انتخاب نخبه‌گرا
بر اساس این مفهوم، تعداد معینی از بهترین کروموزم­ها در جمعیت جدید کپی می­شوند. این روند باعث افزایش کارایی الگوریتم ژنتیک می­گردد، زیرا مانع از گم شدن جواب­های خوب بدست آمده می­ شود. این روش به عنوان روشی کمکی در کنار سایر روش­ها قابل اعمال است.
۳-۳-۱-۱-۵-۳ انتخاب مسابقه­ای
این روش که شبیه رقابت در طبیعت عمل می­نماید، توسط گلدبرگ ارائه شده است. یک زیر مجموعه­ کوچکی از کروموزم­ها (معمولا دو یا سه) به صورت تصادفی انتخاب شده و بهترین کروموزم از نظر مقدار برازندگی در این مجموعه انتخاب می­ شود. به تعداد کروموزم­های ‌مجموعه فوق، اندازه مسابقه ^[۴۸] می­گویند. این روش در جمعیت­های بسیار بزرگ به عنوان بهترین روش شناخته می­ شود.
شکل شماره ۳-۲: انتخاب مسابقه­ای
۳-۳-۱-۱-۶ جفت­گیری
به ایجاد کروموزم جدید بوسیله توزیع صفات والدین در آن، جفت­گیری می­گویند. اسم­های مختلفی مانند: برش، ادغام، همبری، تقاطع، پیوند و جفت­گیری برای این عملیات مطرح شده است. بدلیل تناسب معنایی عبارت “جفت­گیری” با عملیات مشابه صورت گرفته در طبیعت و کاربرد کلمه “ادغام” در بسیاری از کتب، از این دو کلمه برای توصیف این مرحله استفاده می­ شود. جفت­گیری یکی از عواملی است که باعث ایجاد تحول در موجودات و تولید افراد متفاوت در یک گونه می­ شود. لازم به ذکر است که بجز عملیات جفت­گیری، عملیات­های دیگری برای تولید کروموزم جدید وجود دارد. در طبیعت، نتیجه حاصل از جفت­گیری دو موجود زنده، فرزندی خواهد بود که ترکیبی از صفات والدین خود را به همراه خواهد داشت. از آنجایی که معمولا صفات برتر به عنوان ژن غالب عمل می­نمایند، ویژگی­های مثبت والدین در فرزندان بروز پیدا خواهند نمود. لذا احتمال ایجاد فرزندی برتر از دو والد با ویژگی­های مثبت مختلف به دلیل دریافت ویژگی­های مثبت والدین بسیار زیاد می­باشد.
امروزه با بهره گیری از این ایده در خصوص حیوانات و تعیین والدین مناسب جهت جفت­گیری، تولید مثل گونه­ های مختلف حیوانات را به صورت دلخواه(جهت بروز صفات مورد نظر در آنها) می­توان مدیریت نمود. در واقع مهم­ترین مرحله جهت ایجاد تحول و بهبود کیفیت کروموزم­ها، مرحله جفت­گیری و نحوی توزیع صفات والدین در فرزندان می­باشد. اثرگذاری این مرحله در همگرایی کروموزم­ها به سمت پاسخ مورد نظر به حدی است که معمولا الگوریتم ژنتیک را بوسیله روش انجام مرحله جفت گیری، معرفی می­نمایند. اکثر روش­های جفت گیری معمول بدین صورت عمل می­نمایند که طبق یک روش دلخواه، تعدادی از ژن­های والد اول و تعدادی از ژن­های والد دوم را انتخاب نموده، به نحوی که هر ژن فقط و تنها فقط در یکی از والد­ها انتخاب شده باشد. سپس کروموزم جدید بر اساس ترکیب ژن­های انتخاب شده والد اول و دوم ایجاد می­گردد. اگر عملیات جفت­گیری برای تولید دو فرزند طراحی شده باشد، کروموزم دوم از ادغام ژنـهای انتخاب نشده والد اول و دوم بوجود می ­آید.
۳-۳-۱-۱-۷ جهش^[۴۹]
یکی دیگر از عوامل تحول­زا در موجودات زنده، ‌جهش می­باشد. به پیدایش هر نوع تغییر در
ژن‌های یک کروموزوم جهش می­گویند. در واقع جهش ژنتیکی در نگاه عامه مردم به تغییرات منفی در ساختار کروموزمی اشاره می­نماید. البته از آنجایی که این تغییرات به صورت تصادفی می­باشد، امکان ایجاد کروموزم­های نامناسب در آن زیاد می­باشد. در برخی حالات بدون جهش امکان رسیدن به جواب مناسب وجود ندارد. به عنوان مثال اگر مقدار یک بیت در تمام کروموزم­ها صفر (یا یک) باشد با هیچ یک از روش­های مطرح شده در جفت­گیری نمی­ توان مقدار این بیت را یک (یا صفر) نمود؛ چون فرایند جفت­گیری بر اساس انتقال خصوصیات از والدین به فرزندان عمل می­نماید و از آنجایی که این ژن در هیچ والدی یک(یا صفر) نیست در نتیجه فرزندی نمی­ توان تولید نمود که مقدار این ژن در آن یک(یا صفر)باشد. در حقیقت عملیات جهش برای گریز از قرار گرفتن در اکسترمم­های محلی(بستگی به این دارد که تابع برازش به دنبال ماکسیمم کردن است یا مینیمم) مورد استفاده قرار می­گیرد.
در کروموزم­های دارای ساختار باینری، عمل جهش عبارت است از تغییر مقدار یک بیت از یک به صفر یا بالعکس بر اساس یک احتمال کوچک مثل P_m . مکانیزم اجرایی جهش بدین صورت است که یک عدد تصادفی بین ۰ تا ۱ تولید می­نماید؛ اگر این عدد کمتر از P_m بود آنگاه تغییر مقدار بیت انجام می­پذیرد و گرنه مقدار بیت تغییری نمی­کند.
۳-۳-۱-۱-۸ توابع جریمه­ای
با وجود ترفندهای اجرا شده در تولید کروموزوم­های مناسب، گاهی در مراحل تقاطع و جهش کروموزوم­هایی از قیدها رها شده، به عنوان یک جواب نامربوط ظاهر می­شوند. برای این گونه موارد راهکار توابع جریمه­ای مؤثر واقع می­ شود. توابع جریمه­ای به صورتی است که کلیه شرایط هندسی و فیزیکی کروموزوم را بررسی می­ کند و در صورت پذیرش، معیار برازندگی کروموزوم با تابع هدف تعیین و در غیر این صورت با عدد بزرگی جریمه می­ شود.
۳-۳-۱-۲ روند کلی حل یک مسئله با الگوریتم ژنتیک