وبلاگ

مرحله ۱: کدگذاری:: تعریف نحوه نمایش افراد جمعیت
مرحله ۲: مقداردهی اولیه :: ایجاد جمعیت اولیه
مرحله ۲: تکرار:: تا زمانی که معیارهای توقف برآورده نشده اند، مراحل ۳٫۱ تا ۳٫۴ را تکرار کن:
مرحله ۲-۱: انتخاب :: والدین را از جمعیت فعلی انتخاب کن
مرحله ۲-۲: ترکیب :: والدین انتخاب شده را با احتمال ترکیب، ترکیب کرده و فرزندان جدید تولید کن
مرحله ۲-۳: جهش :: عملگر جهش را باا احتمال جهش، به فرزندان حاصل اعمال کن
مرحله ۲-۴: جایگینی :: فرزندان حاصل را در جمعیت جایگزین کن.
مرحله ۵: پایان
پایان

شکل۳-۳ساختار کلی الگوریتم ژنتیک
کدگذاری: در این روش از دو نوع کدگذاری استفاده شده است. کدگذاری مستقیم^[۱۰۹] و کدگذاری جایگشتی. در کدگذاری مستقیم، جواب های ممکن به صورت برداری تحت عنوان جدول زمانی^[۱۱۰] نمایش داده می شوند. طول این بردار برابر است با تعداد کارها و مقدار درایه ام این بردار، نشان دهنده شماره ماشینی است که کار ام به آن تخصیص داده شده است. بنابراین، مقادیر موجود در این بردار اعدادی طبیعی در بازه می باشند. نکته مهم در خصوص این نوع کدگذاری این است که در یک جدول زمانی ممکن است شماره یک ماشین بیش از یک بار تکرار شود، زیرا کارها می توانند به بیش از یک ماشین تخصیص داده شوند. در کدگذاری جایگشتی^[۱۱۱]، بر خلاف کدگذاری مستقیم هر عضو تنها یک بار می تواند تکرار شود. تشکیل این کدگذاری شامل دو مرحله می باشد: ۱) برای هر ماشین ، دنباله از کارهایی که به آن ماشین تخصیص داده شده اند، ایجاد می شود، و ۲) دنباله های کارهای ایجاد شده در مرحله اول به یکدیگر الحاق می شوند. نتیجه این دو مرحله، جایگشتی از کارها می باشد که به ماشین ها تخصیص داده شده اند. قابل ذکر است که در این نوع کدگذاری، نیاز به نگهداری اطلاعات اضافی در باره تعداد کارهایی که به هر ماشین تخصیص داده شده، داریم. شکل ۳ نمونه ای از کدگذاری های مستقیم و جایگشتی را، برای ۴ ماشین و ۱۰ کار، نشان می دهد.

شکل۳-۴: مثالی از کدگذاری های مستقیم و جایگشتی برای زمانبندی ۱۰ کار بر روی ۵ ماشین
کار۱
کار ۲
کار ۳
کار ۴
کار ۵
کار ۶
کار ۷
کار ۸
کار ۹
کار ۱۰

۲

۱

۲

۳

۱

۲

۴

۴

۵

۴