{
Swap task_i and task_j between l and c
Update c_c and c_l
Change = true and break
}
}
If Change=true
Break
}
}While(Change)
شکل 4-1 الگوریتم توازن نسخه دوم
شکل 4-1 الگوریتم توازن نسخه دوم
4-7 الگوریتم پیشنهادی ژنتیک و توازن بار
در ابتدا لازم است تا مواردی چون نحوه نمایش راهحلها، پارامترهای موثر مورد استفاده و مقادیر آنها را توضیح داده و سپس الگوریتم پیشنهادی را بیان کنیم.
الگوریتم ارائه شده یک الگوریتم ژنتیک به همراه الگوریتم توازن است که روی تعدادی از فرزندان در هر نسل اعمال میشود. پارامترهایی که در الگوریتم ارائه شده تاثیرگذار بوده و استفاده شده اند را در ادامه توضیح داده و سپس روند کلی الگوریتم را ارائه میدهیم.
نمایش کروموزومها (راهحلها) و جمعیت
برای نمایش هر کروموزوم از یک آرایه به طول کارها استفاده میشود که خانههای آرایه شامل شماره ماشین میباشند. به این صورت نگاشت را نمایش میدهیم که مثلا اگر خانه پنجم آرایه مذکور مقدار دوازده را داشته باشد به این معنی است که کار پنج روی ماشین دوازده زمانبندی شده است. به دلیل اینکه در کارهای دستهای تعداد منابع و کارها ثابت بوده و تغییری نمیکند میتوانیم با پیمایش آرایه مذکور مشخص نمائیم که هر کاری روی چه ماشینی زمانبندی شده و هر ماشین چه تعداد کار برای اجرا دارد و زمان اتمام مربوط به هر کار و ماشین را مشخص نمائیم.
در الگوریتمهای تکاملی با جمعیتی از کروموزومها (راهحلها) شروع کرده و سعی در بهبود آنها داریم. برای نمایش جمعیت از یک آرایه به طول جمعیت مورد نظر استفاده میکنیم که هر خانه این آرایه شامل یک آرایه یک بعدی به طول کارها (راهحل) میباشد. برای نمایش فرزندان نیز به همین صورت عمل کرده و از آرایه دیگری با همین مشخصات به طول جمعیت فرزندان استفاده میکنیم. عملیات مربوط به انتخاب والدها برای آمیزش، عملیات آمیزش، الگوریتم توازن بار و انتخاب نسل بعد همگی روی کروموزومها صورت میگیرند. (آرایههایی به طول تعداد کارها).
جمعیت اولیه
برای تولید جمعیت اولیه راهحلها به صورت تصادفی تولید میشوند. به این صورت که برای هر کروموزوم به تعداد کارها (خانههای آرایه) به ترتیب عددی تصادفی در بازه ماشینها-1، تولید و به خانه مربوطه واگذار میشود. تعداد جمعیت در حین اجرای الگوریتم ثابت بوده و افزایش پیدا نمی کند. 75 کروموزوم جمعیت اولیه را تشکیل میدهند.
انتخاب والدها برای تولید فرزندان
برای تولید فرزندان از والدهایی که در بازه حداقل یک دهم طول کروموزوم تا یک بیستم طول کروموزوم با یکدیگر متفاوت هستند استفاده میشود. ابتدا یکی از والدها از جمعیت بصورت تصادف انتخاب، سپس یک والد دیگر نیز بصورت تصادفی انتخاب میکنیم. در صورتیکه دو والد در بازه تعریف شده با هم تفاوت داشته باشند برای تولید فرزند انتخاب می شوند. در صورتیکه والدی در بازه تعریف شده را نتوانست پیدا کند. والد دوم را به صورت تصادفی یکی از والدهای موجود قرار داده و تعداد یک دهم بیت های آن را با شماره ماشینهای تصادفی جایگزین میکند. این دو والد برای تولید فرزند جدید به مرحله بعد میروند.
در هر دور برای تولید فرزندان دو والد انتخاب شده و از دو والد انتخابی دو فرزند تولید مینمائیم .در روش پیشنهادی تعداد 150 فرزند در هر نسل از 75 والد تولید میشوند. با توجه به اینکه تعداد فرزندان از والدها بیشتر میباشد این احتمال وجود دارد که از تمامی والدها برای تولید نسل بعد استفاده شود و هر والد در تولید بیشتر از دو فرزند نقش داشته باشد. در صورتیکه یک والدشامل یک نگاشت خوب از کارها به ماشینها باشد دارای این شانس هستیم که این نگاشت در چندین فرزند دیگر هم تاثیرگذار باشد.
تولید فرزندان
برای تولید فرزندان از روش همگذری HUX استفاده میکنیم. برای هر فرزند یک والد را والد موثر درنظر میگیریم. مثلا والد 1 والد موثر در فرزند اول و والد 2 والد موثر در فرزند دوم باشد. به ازای هر خانه آرایه مربوط به هر فرزند عددی تصادفی را بین 0 تا 100 تولید مینمائیم، اگر عدد تولید شده بزرگتر یا مساوی 50 بود فرزند اول مقدار خانه آرایه خود را از والد موثرش ارث میبرد و در غیر این صورت این مقدار را از والد دوم میگیرد. برای فرزند دوم نیز به همین صورت است با این تفاوت که اگر والد موثر در فرزند دوم والد 2 بود و در صورتیکه عدد تولید شده کوچکتر از 50 باشد مقدار خانه مربوطه را از والد 1 ارث میگیرد. این عمل به تعداد خانههای آرایه نمایشدهنده نگاشت (به تعداد کارها) تکرار میشود. با استفاده از این روش خصوصیات دو والد را برای فرزندان حفظ کرده و تقریبا هر فرزند نیمی از ساختار خود را از یکی از والدها و نیمه دیگر را از والد دیگر به ارث میبرد. به دلیل شرایط انتخاب والدها، انتظار داریم فرزندانی تولید شوند که از لحاظ ساختار ژنتیکی با هم متفاوت بوده ولی ساختار ژنی والدهای خود را نیز به ارث ببرند.