جستجوی مقالات فارسی – طراحی مدل یکپارچه تشکیل سلول با چیدمان سلول و زمانبندی عملیات ها با در نظر گرفتن …

  • کدینگ باینری
  • این نوع کدینگ، متداولترین نوع کدینگ می باشد. در این روش کدگذاری، هر کروموزوم یک رشته از بیتهای شامل ٠ و ١ می باشد. کدینگ باینری می تواند حالت های زیادی را پوشش دهد، حتی در مواردی که تعداد آلل ها کم باشد.
     
    شکل ۳‑۲٫ کدینگ باینری
    از طرف دیگر این نوع کدینگ برای خیلی از مسائل حالت طبیعی ندارد و اغلب اوقات لازم است که بعد از تقاطع و جهش اصلاحاتی صورت بگیرد.

    منبع فایل کامل این پایان نامه این سایت pipaf.ir است

    1. کدینگ جهشی

    این نوع کدینگ میتواند در مسائل ترتیبی نظیر مساله فروشنده دوره گرد یا مساله ترتیب کارها بکار رود. در کدینگ جهشی، هر کروموزوم یک رشته از اعداد میباشد. شکل زیر نمونه ای از این نوع کدینگ را نشان میدهد.
    شکل ۳‑۳٫ کدینگ جهشی
    کدینگ جهشی تنها برای مسائل ترتیبی مفید است. حتی برای همین مسائل نیز گاهی اوقات باید تقاطعها و جهشهای اصلاحی به منظور ایجاد کروموزومهای سازگار و مناسب انجام شود.

    1. کدینگ ارزشی

    این نوع کدینگ درمسائلی که در آنها مقادیر پیچیده نظیر اعداد حقیقی بکار میروند استفاده میشود. استفاده از کدینگ باینری برای چنین مسائلی بسیار سخت میباشد. در کدینگ ارزشی هر ژن یک کروموزوم ارزش خاصی دارد. این پارامتر با ارزش میتواند عدد، حرف یا کلمه باشد. دراین نوع کدینگ نیاز به توسعه عملگرهای جابجایی و جهش جدیدی برای مسائل خاص میباشد.
    شکل ۳‑۴٫ کدینگ ارزشی

    1. کدینگ درختی

    کدینگ درختی در برنامه های تکاملی به منظور برنامه ریزی تکاملی بکار میرود. در کدینگ درختی هرکروموزوم یک درخت از اشیائی نظیر توابع یا دستورها در زبان برنامه نویسی میباشد. شکل زیر دو نمونه از این کروموزومها را نشان میدهد. این نوع کدینگ برای برنامههای تکاملی بسیار عالی است.
    شکل ۳‑۶٫ کدینگ درختی
    نکته ای که در انتهای این قسمت باید به آن توجه کرد این است که در الگوریتم های ژنتیکی کدینگ یک رابطه بین فضای کدینگ و فضای جوابها می باشد بطوریکه الگوریتم ژنتیک عملیات تکاملی را بطور متناوب در این دو فضا انجام می دهد (شکل ۳-۷). انتخاب طبیعی نیز به عنوان یک رابطه بین کروموزومها و عملکرد جوابهای کدشده آنها می باشد.
    شکل ۳‑۷٫ فضای کدینگ وفضای جواب

    ۳-۲-۱-۵-۵- کروموزوم

    رشته یا دنبالهای از بیتها که به عنوان شکل کد شده یک جواب ممکن (مناسب یا نامناسب) از مساله مورد نظر میباشد را کروموزوم میگویند. در حقیقت بیتهای یک کروموزوم، نقش ژنها را در طبیعت بازی میکنند.

    ۳-۲-۱-۵-۶- جمعیت[۹۰]

    مجموعهای از کروموزومها را جمعیت گویند. یکی از ویژگیهای ژنتیک این است که به جای تمرکز بر روی یک نقطه از فضای جستجو یا یک کروموزوم، بر روی جمعیتی از کروموزومها کار میکند. بدین ترتیب در هر مرحله، الگوریتم دارای جمعیتی از کروموزومها بوده که خواص مورد نظر را بیشتر از جمعیت مرحله قبل دارا میباشد. هر جمعیت یا یک نسل از کروموزومها، دارای یک اندازه میباشد که به اندازه جمعیت[۹۱] معروف است. اندازه جمعیت معرف تعداد کروموزومهای موجود در جمعیت یا یک نسل است.

    ۳-۲-۱-۵-۷- مقدار برازندگی[۹۲]

    مناسب بودن یا نبودن جواب، با معیاری که از تابع هدف بدست میآید، سنجیده میشود. هر چه که یک جواب مناسبتر باشد، مقدار برازندگی بزرگتری دارد. برای آنکه شانس بقای چنین جوابی بیشتر شود، احتمال بقای آن، متناسب با مقدار برازندگی آن در نظر گرفته میشود. بنابراین کروموزمی که برازنده ترین است با احتمال بیشتری در تولید فرزندان شرکت میکند و دنبالههای بیشتری از آن به وجود میآید. به عنوان مثال چنانچه هدف بیشینه کردن یک تابع باشد، مقدار برازندگی، یک تابع صعودی از تابع هدف در نظر گرفته میشود و اگر هدف یافتن مقدار کمینه یک تابع باشد، عدد برازندگی، یک تابع نزولی از آن قرار داده میشود. معمولاً در مواردی که امکان دارد، تابع برازندگی را در فاصله [۱و۰] نرمالیزه میکنند.

    ۳-۲-۱-۵-۸- عملگر تقاطع

    این عملگر بر روی یک جفت از کروموزوم ها عمل می کند و میتواند به صورت تک نقطهای، چند نقطهای و یکنواخت باشد. عملگر تقاطعی تک نقطهای، دو کروموزوم را به طور تصادفی از یک نقطه شکسته و بخش های شکسته دو کروموزوم را جابجا می کند. بدین ترتیب دو کروموزوم جدید بدست می آید. به کروموزومهای اولیه، کروموزومهای”والد“و به کروموزوم های حاصل شده از عمل جابجایی و عمل جهش، کروموزوم”فرزند“میگویند.
     
    شکل ۳‑۸٫ مثالی از عمل جابجایی تک نقطه ای
    عملگر تقاطع با احتمال Pبر روی کروموزوم های والد عمل میکند. بدین معنی که با احتمال Pcعمل تقاطع انجام میگیرد. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقًا مشابه والدین خواهند بود (البته این مطلب بدین معنی نیست که نسل جدید همان نسل قبلی است). در صورتی که عمل تقاطع صورت بگیرد، فرزندان از قسمتهای مختلف کروموزومهای والد ساخته میشوند. اگر احتمال تقاطع ١ باشد، تمامی فرزندان از طریق عمل تقاطعی ایجاد میشوند. عملیات تقاطع با این هدف انجام میشود که کروموزومهای جدید در بردارنده قسمتهای مناسب و خوب کروموزومهای قبلی خواهند بود و شاید این کروموزومهای جدید عملکرد بهتری داشته باشند. اما بهتر است همیشه بهترین کروموزومهای نسل قبلی بدون هیچ تغییری به نسل جدید منتقل شوند.
    تفاوت عملگر چند نقطهای در مقایسه با عملگر تقاطع تک نقطه ای دراین است که نقطه شکست دو کروموزوم، بیش از یکی است و تقاطع در بخشهای شکسته شده دو کروموزوم به صورت یک در میان انجام میگیرد. شکل ۳-۹ مثالی از عمل تقاطع دو نقطه ای را نشان میدهند.
    شکل ۳‑۹٫ تقاطعی دو نقطه ای