وبلاگ

تابع برازندگی را از اِعمال تبدیل مناسب بر روی تابع هدف یعنی تابعی که قرار است بهینه شود به دست می‌آورند. این تابع هر رشته را با یک مقدار عددی ارزیابی می‌کند که کیفیت آن را مشخص می‌نماید. هر چه کیفیت رشته جواب بالاتر باشد مقدار برازندگی جواب بیشتر است و احتمال مشارکت برای تولید نسل بعدی نیز افزایش خواهد یافت.

ترکیب^[۶۳]

مهمترین عملگر در الگوریتم ژنتیک، عملگر ترکیب است. ترکیب فرآیندی است که در آن نسل قدیمی کروموزوم‌ها با یکدیگر مخلوط و ترکیب می‌شوند تا نسل تازه‌ای از کروموزوم‌ها بوجود بیاید.
جفت‌هایی که در قسمت انتخاب به عنوان والد در نظر گرفته شدند در این قسمت ژن‌هایشان را با هم مبادله می‌کنند و اعضای جدید بوجود می‌آورند. ترکیب در الگوریتم ژنتیک باعث از بین رفتن پراکندگی یا تنوع ژنتیکی جمعیت می‌شود زیرا اجازه می‌دهد ژن‌های خوب یکدیگر را بیابند. متداولترین روشهای ترکیب عبارتند از :
جابه‌جایی دودوئی، جابه‌جایی حقیقی، ترکیب تک‌نقطه‌ای، ترکیب دو نقطه‌ای، ترکیب n نقطه‌ای، ترکیب یکنواخت، ترکیب حسابی، ترتیب، محدّب، بخش نگاشته، چرخه.

جهش^[۶۴]

جهش نیز عملگر دیگری هست که جواب‌های ممکن دیگری را متولد می‌کند. در الگوریتم ژنتیک بعد از اینکه یک عضو در جمعیت جدید بوجود آمد هر ژن آن با احتمال جهش، جهش می‌یابد. در جهش ممکن است ژنی از مجموعه ژن‌های جمعیت حذف شود یا ژنی که تا به حال در جمعیت وجود نداشته است به آن اضافه شود. جهش یک ژن به معنای تغییر آن ژن است و وابسته به نوع کدگذاری روش‌های متفاوت جهش استفاده می‌شود.
انواع روشهای عملگر جهش عبارتند از :
جهش باینری، جهش حقیقی، وارونه سازی بیت، تغییر ترتیب قرارگیری، وارون سازی، تغییر مقدار.

رمزگشایی^[۶۵]

رمزگشایی، عکسِ عمل رمزگذاری است. در این مرحله بعد از اینکه الگوریتم بهترین جواب را برای مسأله ارایه کرد لازم است عکس عمل رمزگذاری روی جواب‌ها یا همان عمل رمزگشایی اعمال شود تا بتوانیم نسخه واقعی جواب را به وضوح در دست داشته باشیم.

نقاط قوّت الگوریتم‌های ژنتیک

اولین و مهمترین نقطه قوّت این الگوریتم‌ها این است که الگوریتم‌های ژنتیک ذاتاً موازی‌اند. اکثر الگوریتم‌های دیگر موازی نیستند و فقط می‌توانند فضای مسأله مورد نظر را در یک جهت در یک لحظه جستجو کنندو اگر راه‌حل پیدا شده یک جواب بهینه محلی باشد و یا زیر مجموعه‌ای از جواب اصلی باشد باید تمام کارهایی که تا به حال انجام شده را کنار گذاشت و دوباره از اول شروع کرد. از آنجایی که GA چندین نقطه شروع دارد، در یک لحظه می‌تواند فضای مسأله را از چند جهت مختلف جستجو کند. اگر یکی به نتیجه نرسید سایر راه‌ها ادامه می‌یابند و منابع بیشتری را در اختیارشان قرار می‌گیرد.
به دلیل موازی بودن و این که چندین رشته در یک لحظه مورد ارزیابی قرار می‌گیرند الگوریتم های ژنتیک برای مسائلی که فضای راه‌حل بزرگی دارند بسیار مفید‌ند. اکثر مسائلی که این گونه‌اند به عنوان غیرخطی شناخته شده‌اند. در یک مسأله خطی،Fitness هر عنصر مستقل است، پس هر تغییری در یک قسمت بر تغییر و پیشرفت کل سیستم تأثیر مستقیم دارد. می‌دانیم که تعداد کمی از مسائل دنیای واقعی به صورت خطی‌اند. در مسائل غیرخطی تغییر در یک قسمت ممکن است تاثیری ناهماهنگ بر کل سیستم و یا تغییر در چند عنصر تاثیر فراوانی بر سیستم بگذارد. خوشبختانه موازی بودن GA باعث حل این مسأله می‌شود و در مدت کمی مشکل حل می‌شود. مثلاً برای حل یک مسأله خطی ۱۰۰۰ رقمی ۲۰۰۰ امکان حل وجود دارد ولی برای یک غیرخطی ۱۰۰۰ رقمی  امکان. یکی از نقاط قوت الگوریتم‌های ژنتیک که در ابتدا یک کمبود به نظر می‌رسد این است که: GA ها هیچ چیزی در مورد مسائلی که حل می‌کنند نمی‌دانند و اصطلاحاً به آنها «ساعت‌ساز نابینا»^[۶۶] می‌گوییم. آنها تغییرات تصادفی را در راه‌حل‌های کاندیدشان می‌دهند و سپس از تابع برازش برای سنجش این که آیا آن تغییرات پیشرفتی ایجاد کرده‌اند یا نه، استفاده می‌کنند. مزیت این تکنیک این است که به GA اجازه می‌دهد تا با ذهنی باز شروع به حل مسائل کند. از آنجایی که تصمیمات آن اساساً تصادفی است، بر اساس تئوری همه راه‌حل‌های ممکن به روی مسأله باز است، ولی مسائلی که محدود به اطلاعات هستند باید از راه قیاس تصمیم بگیرند و در این صورت بسیاری از راه‌حل‌های نو و جدید را از دست می‌دهند.
یکی دیگر از مزایای الگوریتم این است که آنها می‌توانند چندین پارامتر را همزمان تغییر دهند. بسیاری از مسائل واقعی نمی‌توانند محدود به یک ویژگی شوند تا آن ویژگی ماکسیمم شود و باید چند جانبه در نظر گرفته شوند.GA ها در حل این گونه مسائل بسیار مفیدند، و در حقیقت قابلیت موازی کار کردن آنها این خاصیت را به آنها می‌بخشد. و ممکن است برای یک مسأله ۲ یا چند راه‌حل پیدا شود، که هر کدام با در نظرگرفتن یک پارامتر خاص به جواب رسیده‌اند.
به طور خلاصه مزایای الگوریتم ژنتیک را می‌توان در موارد زیر برشمرد:
با متغیرهای پیوسته و هم گسسته می‌تواند عمل بهینه‌سازی را انجام دهد.
نیازی به محاسبه مشتق توابع ندارد.
بطور همزمان می‌تواند تمامی ناحیه جستجو شونده وسیع تابع هزینه را جستجو کند.
قادر به بهینه سازی مسائل با تعداد متغیرهای زیاد می‌باشد.
قابل اجرا از طریق کامپیوترهای موازی است.
توابع هزینه‌ای که بسیار پیچیده باشند نیز از این طریق قابل بهینه‌سازی می‌باشند و الگوریتم در اکسترمم محلی به دام نمی‌افتد.
قادر است تا چند جواب بهینه را بطور همزمان به دست آورد نه فقط یک جواب.
الگوریتم‌های ژنتیک بر روی مجموعه‌ای از راه‌حل‌ها اعمال می‌شوند و نه بر روی یک راه‌حل خاص.
قادر است تا متغیرها را کد بندی نموده و بهینه‌سازی را با متغیرهای کدبندی شده انجام دهد. کد بندی سرعت همگرایی الگوریتم را افزایش می‌دهد.
الگوریتم توانایی کار کردن با داده‌های عددی تولید شده و داده‌های تجربی را علاوه بر توابع تحلیلی دارد.
فرآیند ارایه شده توسط الگوریتم‌های ژنتیک بر روی فضایی از مجموعه نمایندگان یا همان فضای کروموزوم‌ها اعمال می‌گردد و نه بر روی خود فضای راه‌حل‌ها.
الگوریتم‌های ژنتیک از قوانین انتقالی احتمالی بجای قوانین انتقالی قطعی استفاده می‌کنند، بدین معنا که حرکت آن در هر نقطه از الگوریتم کاملا احتمالی بوده و بر اساس قطعیت صورت نمی‌پذیرد. این امر از مزایای مهم این روش بوده و از افتادن سیستم در کمینه محلی جلوگیری می‌نماید.
البته میزان احتمال به گونه‌ای است که احتمال حرکت به سمت مسأله بیشتر از احتمال حرکت آن به سمت مخالف جواب می‌باشد.
تنها ملاک ارزشیابی و سنجش میزان شایستگی هر راه‌حل توسط الگوریتم‌های ژنتیک، مقدار تابع شایستگی آن در فضای کروموزوم‌ها می‌باشد و نه معیارهای مورد نظر در سطح فضای راه‌حل‌ها.
برای حل برخی از مسائلی از رده NP-Hard نیز استفاده می‌شود.
این الگوریتم بیشتر در مسائل بهینه سازی و امثالهم بکار می‌رود.

محدودیت‌های GA ها

یک مشکل چگونگی نوشتن عملگر ارزیاب است که منجر به بهترین راه‌حل برای مسأله شود. اگر این کارکرد برازش به خوبی و قوی انتخاب نشود ممکن است باعث شود که راه‌حلی برای مسأله پیدا نکنیم یا مسأله‌ای دیگر را به اشتباه حل کنیم. به علاوه برای انتخاب تابع مناسب برای ارزیاب، پارامترهای دیگری مثل اندازه جمعیت، نرخ ترکیب، قدرت و نوع انتخاب هم باید مورد توجه قرار گیرند.
مشکل دیگر، که آن را «نارس» می‌نامیم این است که اگر یک ژنوم که فاصله‌اش با سایز ژنوم‌های نسل‌اش زیاد باشد. (خیلی بهتر از بقیه باشد) خیلی زود دیده می‌شود (ایجاد می‌شود) ممکن است محدودیت ایجاد کند و راه‌حل را به سوی جواب بهینه محلی سوق دهد. این اتفاق معمولاً در جمعیت‌های کم اتفاق می‌افتد. روش‌های Rank Scaling , Tournament Selection بر این مشکل غلبه می‌کنند.

استراتژی برخورد با محدودیت‌ها

بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد چگونگی برخورد با محدودیت‌های مسأله می‌باشد، زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزوم‌های غیرموجّه می‌شود. «میکالویچ» چند تکنیک معمول جهت مواجهه با محدودیت‌ها تقسیم‌بندی نموده است که در ادامه به چند تا از آنها اشاره می‌شود.

استراتژی اصلاح عملگرهای ژنتیک

یک روش برای جلوگیری از تولید کروموزوم غیرموجّه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزم‌ها، کروموزوم تولید شده نیز موجّه باشد. در این حالت یکسری مشکلات وجود دارد. مثلاً پیدا کردن عملگری که دارای شرط فوق باشد بسیار دشوار بوده و از مسأله دیگر متفاوت می‌باشد.

استراتژی رَدّی

در این روش پس از تولید هر کروموزوم آنرا از نظر موجّه بودن تست کرده و در صورت غیرموجّه بودن حذف می‌گردد. این روش بسیار ساده و کارا می‌باشد.