دسترسی به منابع مقالات : زمان بندی ماشین های موازی نامرتبط به همراه دوباره کاری با در نظر …

  • Mutate children
  • (For each new-born apply mutation with probability pm)

    1. Replace the Current Population by the resulting Mating Pool
    2. Fitness Evaluation

    Until Stopping Criteria is met
    ۳-۶-۴٫ کدگذاری
    همانطور که در بخش قبل عنوان شد اولین گام در بکارگیری و پیادهسازی یک الگوریتم نمایش جوابهای مسئله بصورت یک کروموزوم است. در حقیقت این عمل یک مفهوم کلیدی در الگوریتم ژنتیک میباشد. یکی از ویژگیهای اصلی الگوریتم ژنتیک آن است که به طور متناوب بر روی فضای کدینگ و فضای جواب کار میکند. عملیات ژنتیک بر روی فضای کدینگ یا کروموزوم اعمال میشود در حالیکه انتخاب و ارزیابی بر روی فضای جواب عمل مینماید]۶۹[.
    هنگام استفاده از کدینگ با سه مفهوم اساسی زیر روبرو هستیم :
    قانونمند بودن کروموزوم[۱۳۷]
    موجه بودن کروموزوم[۱۳۸]
    منحصر به فرد بودن ترسیم[۱۳۹]
    قانونمندی کروموزوم مربوط به زمان بکارگیری عملیات ژنتیک میباشد. یعنی گاهی اوقات ممکن است کروموزومهایی تولید شوند که با هیچ عضوی از فضای جواب متناظر نباشند. موجه بودن یک کروموزوم مربوط به حالتی است که بعد از رمز گشایی، همه محدودیتهای مسئله را ارضا میکند، در غیر اینصورت کروموزوم غیر موجه خواهد بود.
    شکل ۳-۹٫ فضای موجه، ناموجه و غیرقانونی
    انواع ارتباط بین فضای کدینگ و فضای جواب به صورتهای زیر میباشد:
    ترسیم ۱ به ۱
    ترسیم n به ۱
    ترسیم ۱ به n
    اولین و سومین ترسیم بهترتیب بهترین و ناخوشایندترین حالت میباشند]۶۹[. مهم ترین اجزای GA در عمل به ۵ مرحله تقسیم می شود، که عبارتند از:
    جمعیت اولیه
    نحوه نمایش
    تطبیق تابع برازش و بدست آوردن برازندگی هر جواب
    انتخاب استراتژی
    اپراتورهای ژنتیک
    ۳-۶-۵٫ ایجاد جمعیت اولیه
    اولین مرحله بعد از تعیین تکنیکی که برای تبدیل هر جواب به یک کروموزوم بکار میرود ایجاد یک جمعیت اولیه از کروموزومهاست. در این مرحله جواب اولیه معمولا به صورت تصادفی تولید میشود. البته در بعضی موارد با توجه به نوع مسئله و برای بالا بردن سرعت همگرایی الگوریتم از روشهای ابتکاری نیز استفاده گردیده است.
    به طور کلی بعضی از محققین همچون ریوز[۱۴۰]، اسمیت[۱۴۱] و کاپاسالیس[۱۴۲] مفهوم بذر افشانی[۱۴۳] را ارائه کردهاند. آنها پیشنهاد کردهاند که بهجای استفاده از یک رویکرد تصادفی در ایجاد جمعیت اولیه، از جوابهای حاصله از دیگر الگوریتمهای ابتکاری استفاده شود. به هر حال عمومیترین و فراگیرترین روش، استفاده از یک رویکرد تصادفی است.
    ۳-۶-۶٫ اعمال ژنتیک
    عملیات ژنتیک فرآیند انتقال موروثی ژنها را برای ایجاد اولاد جدید در هر نسل تقلید میکنند. یک بخش مهم در الگوریتم ژنتیک ایجاد کروموزومهای جدید موسوم به فرزندان[۱۴۴] از طریق بعضی کروموزومهای قدیم موسوم به والدین[۱۴۵] است. این فرآیند مهم توسط عملیات ژنتیک صورت میگیرد. به طور کلی این عملیات توسط دو عملگر عمده انجام میشود؛ عملگر جهشی و عملگر تقاطعی.
    اما عملا انتخاب عملگرها بر حسب نوع مسئله تعریف شده و کاملا به توانایی تحلیل گر وابسته بوده و تجربی میباشند. کارایی این عملگرها در رسیدن به جواب بهینه در مسائل مختلف متفاوت است. بعضی از عملگرها فقط یک کروموزوم را در نظر گرفته و بر اساس اطلاعات آن، کروموزوم جدید ایجاد میکنند اما بعضی دیگر روی چند کروموزوم یا حتی روی کلیه کروموزومهای جمعیت قبل، عملیات انجام میدهند. به هر حال عملگرها بر اساس نحوه کار به صورت زیر دسته بندی میشوند:
    ۳-۶-۶-۱٫ عملگرهای تقاطعی[۱۴۶]
    عملگرهایی که یک یا چند نقطه از دو یا چند جواب را انتخاب و مقادیر آن را تعویض میکنند. این عملگرها یک جواب را در نظر گرفته و محلهایی از جواب را با جوابهای دیگر معاوضه کرده و جوابهای جدید را بوجود میآورند. به این نوع عملگرها، عملگرهای تقاطعی گفته میشود.
    در زیر چگونگی انجام و انواع عملگرهای تقاطعی به صورت مرحله به مرحله آورده شده است.
    اپراتور تقاطع با احتمال اجرا می شود.
    تقاطع تک نقطهای[۱۴۷]
    تقاطع دو نقطهای[۱۴۸]
    تقاطع چند نقطهای[۱۴۹]
    تقاطع یکنواخت[۱۵۰]
    چند نکته:
    هر فرزند باید خصوصیاتی را از هر والدش به ارث ببرد(اگر اپراتوری چنین واقعیتی را تضمین نکند، اپراتور جهش است).

    برای دانلود متن کامل پایان نامه به سایت zusa.ir مراجعه نمایید.