پاسخ های شدنی

افراد

کیفیت پاسخ ها (تابع برازندگی)

میزان انطباق افراد با محیط پیرامون

عملگرهای ژنتیکی تصادفی

پدیده های ژنتیکی طبیعی

مجموعه پاسخ های کاندیدای بهینگی

جمعیت ارگانیسم های زنده

هدایت پاسخ ها به سمت بهینگی

تکامل جمعیت ارگانیسم ها جهت بقاء

۳-۲-۲- نمایش کروموزومی
الگوریتم ژنتیک برروی شکل رمزنگاری شده متغیرها کار می‌کند. به این منظور لازم است متغیرهای تصمیم به شکل نمایش کروموزومی رمزنگاری شده تعریف شوند. اطلاعات مربوط به متغیرهای هر پاسخ در این نمایش کروموزومی می‌گردد. یکی از روش های نمایش کروموزومی نمایش دودویی^[۶۰] است. در این نمایش هر کروموزوم به شکل رشته‌ای از بیت های ۰ و ۱ نمایش داده می‌شود. به عنوان مثال شکل ۳-۵ یک کروموزوم ۲۵ بیتی را نشان می‌دهد که از دو متغیر تشکیل شده است و طول متغیر ، ۱۰ بیت وطول متغیر ، ۱۵ بیت می‌باشد. با افزایش تعداد بیت ها دقت الگوریتم بالا می‌رود اما زمان اجرای آن نیز افزایش می‌یابد.
شکل ۳-۵: کروموزوم ۲۵ بیتی دو متغیره[۵]
روش نمایش دو دویی علی رغم استفاده گسترده در الگوریتم‌های ژنتیکی اشکالاتی نیز دارد که برخی از آنها عبارتند از:
برای کروموزوم های با طول رشته‌برابر L حداکثر می‌توان کروموزوم تولید نمود.

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

با افزایش طول رشته زمان و حافظه مورد نیاز اجرای الگوریتم افزایش می‌یابد.
به دلیل گسستگی اعداد در مبنای دودویی دقت الگوریتم محدودیت دارد.
روش دیگر نمایش کروموزومی که فاقد ایرادات فوق است نمایش کروموزوم ها با بهره گرفتن از اعداد حقیقی است. در این روش کروموزوم ها با مجموعه‌ای از ژن ها که هر یک به صورت عددی حقیقی در بازه [۰,۱] است نمایش داده می‌شود. به دلیل عدم نیاز به تبدیل رشته دودویی به عدد حقیقی در مبنای ده دهی در این روش زمان و حافظه مورد نیاز اجرای الگوریتم کاهش می‌یابد. هم چنین در این روش همگرایی بیشتری نیز دیده شده است. نمایش حقیقی کروموزوم شکل۳-۶ به صورت زیر است.
شکل ۳-۶: کروموزوم دو متغیره با نمایش حقیقی[۵]
به منظور استفاده از مقدار واقعی متغیرها در محاسبات لازم است کروموزوم ها رمزگشایی شده و از فضای ژنوتایپ به فضای فنوتایپ منتقل گردند. یکی از روش های معمول روش درون یابی خطی به صورت زیر است:
(۳-۱)
در رابطه فوق Upper bound , Lower bound به ترتیب حدود پایینی و بالایی بازه متغیر تصمیم در حوزه مسأله است. MaxGenotype وGenotype به ترتیب ارزش کروموزومی متغیر پیش از رمزگشایی و بیش ترین مقدار ارزش کروموزومی متغیر هستند. نتیجه رابطه بالا یعنی Phenotype مقدار واقعی متغیر تصمیم در حوزه مسأله است. به عنوان مثال در نمایش دودویی کروموزوم ها برای کروموزوم شکل ۳-۵ فرض می‌کنیم متغیر در بازه[۵-۵] تعریف شده باشد. خواهیم داشت:
(۳-۲)

بیش ترین مقداری است که با یک عدد ۱۰ بیتی در مبنای دو دویی می‌توان نشان داد.
یا در نمایش حقیقی کروموزوم ها برای کروموزوم شکل ۳-۶ با همان بازه تعریف خواهیم داشت:

۳-۲-۳- جمعیت آغازین
جمعیت آغازین غالباً به صورت کاملاً تصادفی تولید می گردد. به دلیل تصادفی بودن تولید جمعیت آغازین تکامل در نسل های ابتدایی سریع تر و تغییرات در مقادیر بهینه بیش تر است. اما با پیشرفت نسل ها الگوریتم به یک یا چند پاسخ بهینه شاخص همگرا می‌گردد. ممکن است برای تولید جمعیت اولیه از روش های فراابتکاری دیگر مانند بازپخت شبیه سازی شده^[۶۱] و یا جستجوی ممنوع^[۶۲] استفاده شود. این عمل کیفیت جمعیت اولیه را افزایش می‌دهد اما ممکن است به دلیل کاهش تنوع جمعیت الگوریتم را گرفتار همگرایی زودرس^[۶۳] و نقاط بهینه موضعی نماید.
شکل جمعیت آغازین بسته به روش نمایش کروموزومی متفاوت است. در نمایش دودویی جمعیت آغازین یک ماتریس تصادفی از بیت های ۰ و ۱ با ابعاد است یعنی تعداد سطرهای آن برابر تعداد کروموزوم ها در جمعیت و تعداد ستون های آن برابر طول رشته کروموزومی است. در صورتی که نمایش کروموزوم ها حقیقی باشد جمعیت آغازین یک ماتریس تصادفی از اعداد حقیقی مابین یا برابر ۰ و۱ با ابعاد است. یعنی تعداد سطرهای آن برابر تعداد کروموزوم ها در جمعیت ،تعداد ستون های آن برابر تعداد متغیرهای مسأله است.
شکل ۳-۷: جمعیت آغازین [۵]
۳-۲-۴- تابع برازندگی و تخصیص شایستگی
در هر نسل لازم است میزان شایستگی هر یک از کروموزوم ها براساس سازگاری با محیط مشخص گردد و درجه شایستگی به آن کروموزوم اختصاص یابد. شایستگی هر کروموزوم در ارتباط مستقیم با بهینگی پاسخ متناظر آن است یعنی هرچه کروموزوم پس از رمزگشایی و محاسبه توابع هدف و قیود بهینگی بیش تری در فضای شدنی ^[۶۴] ایجاد نماید درجه شایستگی اختصاص یافته به آن بالاتر است. مثلاً اگر کمینه سازی^[۶۵] یک تابع هدف مدنظر باشد شایسته‌ترین کروموزوم کروموزومی است که کم ترین مقدار تابع هدف را نتیجه دهد و قیود مسأله را نیز ارضا نماید. تابع برازندگی تابعی است که براساس بهینگی تابع هدف مقیاس شایستگی هر کروموزوم را مشخص می کند. تابع برازندگی بطور کلی به صورت زیر تعریف می‌شود:
(۳-۳)
در این رابطه F(X) تابع برازندگی، g تابع تبدیل به عددی غیر منفی به عنوان معیار شایستگی و f(X) تابع هدف است. یکی از توابع برازندگی که عمدتاً مورد استفاده قرار می‌گیرد تابع برازندگی نسبی است که نسبت مقدار تابع هدف را برای هر عضو نسبت به مجموع مقادیر تابع هدف همه اعضای جمعیت محاسبه می‌کند.
(۳-۴)
اگر بیشینه سازی^[۶۶] تابع هدف موردنظر باشد کروموزومی که تابع برازندگی نسبی آن مقدار بیش تری داشته باشد شایسته‌تر است. چنان چه کمینه سازی تابع هدف موردنظر باشد می‌توان آن را با عکس کردن تابع هدف یا تبدیل خطی با ضریب منفی به بیشینه سازی تبدیل نمود. هم چنین تابع هدف با مقادیر منفی را می‌توان با تبدیل خطی به تابع هدف با تمامی مقادیر بزرگتر از صفر تبدیل نمود. جدول ۳-۲ مقادیر تابع برازندگی نسبی را که برای یک جمعیت نمونه ۱۱ عضوی با مقادیر مثبت محاسبه شده‌اند نشان می‌دهد.
جدول ۳-۲: مقایسه مقادیر توابع هدف و برازندگی نسبی[۵]

شماره کروموزوم

۱

۲

۳

۴