3-3-2راهکارهای جمعیت محور :
روشهای جمعیت محور معمولا به زمان اجرایی بیشتری برای تولید جواب بهینه یا نزدیک به بهینه احتیاج دارند. الگوریتمهای ژنتیک، ممتیک، مورچهها و حرکت ذرات جمعیت محور میباشند.
الگوریتم ژنتیک:
Zomaya و Teh [31] در سال 2001 از الگوریتم ژنتیک برای حل مسئله زمانبندی استفاده کردهاند. در این روش برای نمایش زمانبندی های اولیه جمعیت، از آرایه دوبعدی پردازنده و کار استفاده شده است و به دلیل اینکه عملیات مربوط به آمیزش و جهش روی آرایه یک بعدی اعمال میشوند، آرایه مذکور را سطر به سطر به یکدیگر متصل و یک آرایه یک بعدی را برای نمایش هر کروموزوم در جمعیت استفاده میکند. برای عملیات آمیزش از آمیزش چرخشی استفاده میکند که تضمین میکند واگذاری هر کار روی یک ماشین و نه بیشتر صورت گیرد. برای عملیات جهش از دو والد موجود دو ماشین و روی هر ماشین یک کار به صورت تصادفی انتخاب و با یکدیگر جابجا میکند. از روش چرخ رولت نیز برای قسمت مربوط به انتخاب نسل بعد جمعیت استفاده میکند.
الگوریتم ممتیک :
الگوریتم ممتیک نسبت به دیگر روشهای بهینهسازی جمعیت محور مرسوم، روش جدیدتری میباشد و سعی در ترکیب مفاهیم روشهای جستجوی محلی و جمعیت محور دارد به صورتیکه بتواند از جنبه های مثبت هر دو روش استفاده کند.
Xhafa و همکارانش [32] در سال 2008 از الگوریتم ممتیک برای زمانبندی استفاده کرده اند. در روش استفاده شده در قسمتهای مربوط به تولید نسل اولیه، پس از عملیات آمیزش و جهش روی راه حل های بدست آمده جستجوی محلی را صورت میدهد و در صورتیکه جواب بدست آمده از اعمال جستجوی محلی نسبت به جواب قبل بهتر بود، جایگزین آن میشود.
برای نمایش جمعیت اولیه از یک آرایه یک بعدی به اندازه کارها استفاده میکند. مقادیر ذخیره شده در هر عنصر آرایه نمایانگر ماشینی میباشد که این کار روی آن قرار داده شده است. برای تولید جمعیت اولیه از تولید تصادفی راهحل ها و روش بزرگترین کار روی سریعترین منبع و کوچکترین کار روی سریعترین منبع استفاده میکند.
برای پیاده سازی آمیزش از دو روش زیر استفاده میکند :
قرار دادن یک نقطه انفصال واحد برای هر دو والد و انتخاب قسمت قبل از نقطه انفصال از والد اول و بعد از آن از والد دوم برای یک فرزند و بلعکس برای تولید فرزند دیگر.
انتخاب عناصر آرایه فرزند از عناصر مربوط به هر والد با یک احتمال خاص.
برای پیادهسازی جهش از روشهای زیر استفاده میکند :
انتخاب تصادفی یک کروموزوم و جابجایی عناصر آن با یکدیگر.
انتخاب تصادفی دو کروموزوم و جابجایی عناصر آنها با یکدیگر.
استفاده از ترکیب دو روش بالا.
انتخاب تصادفی یک کروموزوم و جابجایی عناصر داخل آن با استفاده از بررسی فاکتوری خاص که باعث توازن شود.
و در نهایت برای پیادهسازی جستجوی محلی از روشهای زیر استفاده میکند:
به صورت تصادفی از درون آرایه نمایش دهنده هر کروموزم یک کار را انتخاب و به ماشینی که به صورت تصادفی انتخاب شده تخصیص میدهد.
کار انتخاب شده به ماشینی منتقل میشود که بهترین بهبود را در کاهش زمان اتمام داشته باشد.
دو کاری که به دو ماشین مختلف تخصیص داده شدهاند با یکدیگر جابجا می شوند به صورتیکه بهترین کاهش را در زمان اتمام کل داشته باشند.
جستجوی محلیای را بر پایه استفاده از جستجوی ممنوعه استفاده میکند.
Nesmachnow و همکارانش [33] در سال 2011 الگوریتم موازی ژنتیکی به نام pCHC ارائه دادند که سعی در پیدا کردن راهحل بهینه داشتند. برای رسیدن به این هدف جمعیت اولیه را به چند زیر جمعیت تقسیم کرده و برای هر زیر جمعیت یک الگوریتم ژنتیک را اجرا میکردند؛ در حین اجرا زیر جمعیتها در شرایط خاصی راهحلهایی را بین یکدیگر جابجا میکردند. با استفاده از مزایای اجرای موازی و جابجایی راهحلها بین هر زیر جمعیت توانستند به بهترین نتیجه در کاهش زمان اتمام آخرین کار، تا آن زمان دست یابند.
راهحل ارائه شده در سال 2011 pCHC، نتایج خوبی به همراه داشت ولی به دلیل اینکه جمعیت اولیه به چند زیر جمعیت تقسیم شده بود به سرعت تنوع خود را در جمعیتهای موجود در حین اجرای الگوریتم از دست میداد. برای حل این مشکل Nesmachnow و همکارانش [34] در سال 2012 الگوریتم دیگری را بر پایه الگوریتم pCHC ارائه دادند و نام آن را pµ-CHC گذاشتند و سعی کردن مشکل عدم تنوع را در الگوریتم pCHC رفع کنند.
برای رسیدن به این هدف دو حافظه را برای اجرای الگوریتم استفاده میکردند. یک حافظه برای نگهداری بهترین راهحلهای پیدا شده و یک حافظه هم برای نگهداری راهحلهای تولید شده در حین اجرای الگوریتم. زمانیکه جمعیت موجود برای هر زیر جمعیت به سمت همگرا شدن میل میکرد راهحلهایی را بین زیر جمعیتهای موجود جابجا میکردند. برای بالا بردن تنوع در الگوریتم از یک تابع نیز استفاده میکردند که میتوانست راهحلهایی جدید را به جمعیت موجود وارد نماید. با استفاده از این روش توانستند تا حدی مشکلات روش pCHC را حل نمایند.
3-4 جمعبندی