الگوریتم ژنتیک و تابع برازندگی

ملاک برای مقایسه
به طور خلاصه الگوریتم ژنتیک را می‌توان به صورت زیر از فرآیند تطابق طبیعی استنتاج کرد:
Widget not in any sidebars

همانطور که خصوصیات ارثی موجودات زنده بوسیله ژن‌ها بر روی کروموزوم‌ها، رمزگذاری شده‌اند هر یک از پاسخهای ممکن را نیز می‌توان بوسیله رشته‌های عددی در سیستم دودوئی رمزگذاری کرد و جمعیتی از رشته‌های عددی فوق را به عنوان نامزدهای حل مسأله در نظر گرفت.
در سیستم‌های طبیعی، عدم قابلیت بقا و سازش ژن، سبب تغییر کثرت نسبی ژن‌ها به نفع دیگر ژن‌ها و بالعکس قابلیت بقا و سازش ژن مذکور، کثرت نسبی ژن‌ها را به نفع همین ژن تغییر می‌دهد. از طریق کثرت نسبی ژن‌ها، انتخاب طبیعی سبب تجمع تنوعات مفید می‌گردد. مشابه با این وضعیت، قابلیت بقای هر رشته جمعیت، توسط میزان انطباق آن رشته با شرایط مسأله سنجیده می‌شود. در الگوریتم ژنتیک، مسأله و شرایط آن به مثابه محیط در نظریه تکاملی انواع است. اطلاعات و شرایط مسأله در تابعی به نام تابع ارزیابی گنجانیده و با تخصیص هر یک از رشته‌های جمعیت به عنوان متغیر تابع ارزیابی، عددی بدست می‌آید که نشان دهنده درصد سازش (بقا) آن رشته با شرایط مسأله (محیط) است. بالا بودن مقدار تابع ارزیابی (عدد برازندگی) به ازای هر رشته جمعیت، نشان دهنده شانس بیشتر جهت حضور آن رشته در جمعیت بعدی و پایین بودن آن، نشان احتمال بالای عدم حضور رشته مربوط در جمعیت بعدی است. در نتیجه در جمعیت بعدی، رشته‌های با عدد برازندگی بالاتر بیش از یک بار تکرار شده، رشته‌های با عدد برازندگی پایین، از جمعیت حذف می‌شوند.
یکی از عواملی که پدیدآورنده تحول در موجودات و بوجودآورنده افراد متفاوت یک‌گونه است، عمل تقاطع است. در عمل تقاطع طبیعی کروموزوم‌های همتا با یکدیگر جفت شده، ژنهایی بین آن دو مبادله می‌شود. مشابه با آن برای ایجاد تنوع در رشته‌های عددی و تبادل اطلاعات رشته‌ها با یکدیگر عمل تقاطع به صورت زیر روی رشته‌ها انجام می‌گیرد:
ابتدا رشته‌های جمعیت دو به دو با یکدیگر جفت می‌شوند و سپس از یک نقطه که بصورت تصادفی انتخاب می‌شود به دو تکه تقسیم شده، نیم تکه‌ها بین دو رشته تعویض می‌شوند.
یکی دیگر از عوامل تحول‌زا در موجودات، جهش می‌باشد. جهش پیدایش هرگونه تغییر در ترتیب استقرار بازها، حذف یا اضافه‌شدن یک نوکلئوتید در طول زنجیره DNA و یا جانشین شدن بازی به جای باز دیگر در زنجیره DNA می‌باشد. مشابه این فرآیند، عمل جهش روی رشته‌های عددی بدین صورت واقع می‌شود که ابتدا یک عدد تصادفی بین 1 تا L (طول رشته) انتخاب می‌شود. این عدد را K می‌نامیم. سپس در رشته مورد نظر K امین عنصر را مشخص نموده، در صورت صفر بودن به یک تبدیل می‌کنیم و بالعکس.
مطالب فوق به طور خلاصه در جدول (3-1) نشان داده شده است:
در مدل ریاضی روش ژنتیک، هر کدام از عملگرهای ژنتیک شبیه‌سازی می‌شوند و ترکیب آنها فرآیند طبیعی انتخاب اصلح را مشخص می‌نماید. در این روش یک نمونه از تمامی متغیرهای تصمیم‌گیری که مؤثر بر تابع هدف می‌باشند به عنوان یک عضو تلقی می‌گردد که تعدادی از این نمونه‌ها، مجموعه‌ای از اعضا را تشکیل می‌دهند و به عنوان جمعیت نمونه در فضای متغیرها نامیده می‌شود. سپس با اجرای عملگرهای ژنتیک بر روی اعضا و جمعیت اولیه، نسل جدیدی که شایستگی بالاتری دارد تولید می‌گردد.
جدول 3-1. مقایسه الگوریتم ژنتیک با فرآیند تکامل طبیعی [36]
جدول 3-1. مقایسه الگوریتم ژنتیک با فرآیند تکامل طبیعی [36]
فرآیندهای سازگار با سیستم‌های طبیعی
الگوریتم ژنتیک
کروموزوم
خصوصیات ارثی موجودات زنده بر روی کروموزوم‌های رمزگذاری شده است.
رشته‌های عددی 0 و 1
پاسخهای ممکن مسأله را بوسیله رشته‌های عددی رمز گذاری می‌کنیم.
محیط
تابع برازندگی
مسأله در قالب یک رابطه ریاضی گنجانده می‌شود.
اصل انتخاب طبیعی
REPRODUCTION