جهش در الگوریتم ژنتیک

عمل جهش یک بیت شامل تبدیل عدد صفر به یک و بالعکس است که بر اساس یک احتمال کوچک مثل P_m به صورت بیت به بیت صورت می گیرد. عمل جهش به این ترتیب است که یک عدد تصادفی بین صفر تا یک تولید می شود، اگر عدد تولید شده کوچکتر از P_m باشد مقدار خروجی را برابر درست (True) وگرنه برابر غلط (False) در نظر می گیریم. اگر برای هر بیت مقدار خروجی درست باشدبیت تغییر می کند وگرنه بیت بدون تغییر باقی خواهد ماند.

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

این عمل برای جلوگیری از همگرایی سریع و کمک به الگوریتم جستجو برای فرار از به دام افتادن در مینیمم های موضعی مفید است. از سوی دیگر این عمل برای حفظ حالت متفاوت و متمایز بودن  کروموزوم ها در یک جمعیت به کار می رود. به عنوان مثال،جمعیت زیر را در نظر می گیریم:

0110 1011

0011 1101

0001 0110

0111 1100

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

0110 1011

0011 1101

0001 0110

1111 1100

نتیجه: به طور خلاصه عمل جهش باعث جنبش و حرکت در فضای جستجو و ذخیره اطلاعات از دست رفته جمعیت می شود.