بوسیله الگوریتم بدست میآید. پس از انجام آزمایشهای زیادی روی توابع و مسایل مختلف، این نتیجه بدست آمدهاست که الگوریتم زمانی بهتر عمل میکند که مقدار TF بین 1 و 2 باشد[36]. برای سادهسازی الگوریتم مقدار TF یک یا دو در نظر گرفته میشود. یک یا دو بودن نیز بستگی به گرد کردن معیار داده شده در فرمول TF دارد. براساس Difference_Mean j,k,i، پاسخ موجود در فاز معلم، بصورت زیر به روز رسانی میشود:
X‘j,k,i = Xj,k,I + Difference_Meanj,k,i (3-3)
X‘j,k,i به روز شده مقدار Xj,k,i است. X‘j,k,i در صورتی پذیرش میگردد که مقدار تابع هدف بهتری را نتیجه بدهد. تمام مقادیر قابل قبول تابع در پایان فاز معلم نگهداری میشود و این مقادیر، ورودی فاز فراگیر قرار داده میشوند. فاز فراگیر وابسته به فاز معلم است.
3-3-2 فاز فراگیر
فراگیران دانش خودشان را از طریق تعامل بین خودشان افزایش میدهند. یک فراگیر بصورت تصادفی با دیگر فراگیری تعامل میکند تا دانشش را افزایش دهد. یک فراگیر مطالب جدید را در صورتی خواهد آموخت که دیگر فراگیران دانش بیشتری از او داشته باشند. فرایند یادگیری در این مرحله نیز شبیه مرحله قبل است ولی روابطش متفاوت است. با توجه با اندازه جمعیت n، فرایند یادگیری در این فاز در ادامه آمدهاست. اگر فراگیر فعلی P باشد، بصورت تصادفی فراگیر Q را انتخاب میکنیم بطوریکه
X‘totoal-P,i ≠ X‘total-Q,i (3-4)
X“j,P,i را بصورت زیر بدست میآوریم:
If X‘totoal-P,i X‘total-Q,i ⇒ X“j,P,i = X’j,P,i + ri ( X’j,P,i – X’j,Q,i ) (3-5)
If X ‘ totoal-P,i X ‘ total-Q,i ⇒ X “ j,P,i = X’ j,P,i + ri ( X’ j,Q,i – X’ j,P,i) (3-6)
در صورتیکه مقدار تابع هدف برای X“j,P,i بهتر باشد، X” پذیرش میشود و جایگزین مقدار قبلی میشود.
3-3-3 الگوریتم TLBO نخبه سالارانه54
الگوریتم TLBO اولیه که بوسیله Rao و دیگران در سالهای 2011و 2012 بیان گردید رویکرد نخبهگرایی در آن مطرح نبود و فقط دو پارامتر کنترلی عمومی اندازه جمعیت و تعداد نسل ها را شامل میشد. همچنین تاثیر این پارامترها برکارایی الگوریتم بصورت جزیی بررسی گردیدهاست. با وارد کردن مفهوم نخبه گرایی در الگوریتم TLBO تاثیر پارامترها در اکتشاف و ظرفیت اکتشاف را میتوان شناسایی کرد. فلوچارت TLBO با رویکرد نخبهگرایانه در شکل 3-2 نمایش داده شدهاست[39]. محققان مفهوم نخبهسالاری را در غالب الگوریتمهای تکاملی و هوش جمعی استفاده کردهاند. در هر نسل پاسخهای بدتر با پاسخهای نخبه جایگزین میگردند. در TLBO پس از جایگزینی پاسخهای بهتر بجای پاسخهای بدتر در پایان فاز فراگیر، اگر پاسخهای تکراری وجود داشت لازم است تا این پاسخهای تکراری تغییر کنند تا الگوریتم در دام پاسخهای بهینه محلی نیفتد. یک روش برای رفع پاسخهای تکراری به این صورت است که پاسخهای تکراری بوسیله جهش روی اندازههای (ابعاد) انتخابی تصادفی پاسخهای تکراری، تغییر داده میشوند. این کار قبل از اجرای نسل بعد انجام میگیرد. در رویکرد نخبهگرایی، پارامتر کنترلی اندازه نخبه نیز به پارامترها افزوده میشود.
شکل 3-1 فلوچارت TLBO[37]
شکل 3-2 فلوچارت Elitist TLBO[39]
فصل چهارم:
حل مسئله
4-1 مقدمه
مسئله زمان بندی پروژه با منابع محدود پيشينه ای بيش از 40 سال دارد. این مسئله تعمیمی از مسئله کار-خرید55 میباشد و یک مسئله NP-HARD است. برای حل اين مسئله دو رويکرد روشهای دقیق و ابتکاری وجود دارند[40]. حل مصاديق واقعی اين مسئله به دليل پيچيـدگی، گستردگی و دشواری با روشهای دقیق نظير برنامه ريزیرياضی، برنامه ريزی پويا و يا شاخه و کران غير عملی است[41]. البته در ادبيات موضوع کاربرد روشهای دقیق در حل مصاديق کوچکتر اين مسئله نيز گزارش شدهاست. به عنوان نمونـه, دكرو و همكاران در خصوص برنامه‌ريزی رياضی[42]، اكملي و همكاران[43]، همچنین كاروترز و همكاران[44]، در خصوص روشهای شمارشی مثل برنامه ريزی پويا، پتروويچ[45]؛ دميولميستر و همكاران[46] در خصوص روشهای شاخه و کران به این مسئله پرداختهاند. به دليل ناکارآمد بودن روشهای دقیق، اکثر مسائل واقعی زمانبندي پروژه با منابع محدود با رويکردهای ابتکاری حل می‌شوند. بسياری از رويکردهای ابتکاری حل مسئله برنامه ريزی پروژه با منابع محدود در سال 2006 ميلادي مورد بررسي قرار گرفتند[47]. آنها اين رويکردها را در چهار گروه با عناوين زیر دسته بندی کردند :
1- رويکردهای مبتنی بر قواعد اولويت بندی مانند روش نمونه گيری تصادفی[48].
2- رويکردهای مبتنی بر روشهای فراابتکاری مانند الگوريتم ژنتيک[49و50]، الگوريتم جستجوی ممنوع[51]، الگوريتم شبيه سازی تبريدی[52]، الگوريتم مورچه[53].
3- رويکردهای مبتنی بر روشهای ابتکاری غير متعارف مانند روشهای مبتنی بر جستجوی محلی[54]، روشهای تکاملی و مبتنی بر جمعيتی از جواب مثل الگوريتم جستجوی پراکنده[55].
4- رويکردهای مبتنی بر ساير روشهای ابتکاری مانند بهسازی پيشرو پسرو[56] و روشهای تجزيه شبکه[57].
در جدول 4-1 سیرتکاملی حل مسئله زمانبندی پروژه با منابع محدود آورده شدهاست. استفاده از الگوریتم TLBO در دسته دوم قرار میگیرد. استفاده از این الگوریتم برای حل این مسئله تاکنون گزارش نشدهاست و این پایاننامه از اولین کارها در این زمینه میباشد.
جدول 4-1 سیرتکاملی حل مسئله زمانبندی پروژه با منابع محدود
4-2 سوابق اخیر حل مسئله زمانبندی پروژه با منابع محدود
در سالهای اخیر الگوریتمهای فراابتکاری زیادی برای حل مسائل پیچیده RCPSP ارائه شدهاست. در ادامه به برخی از این الگوریتمها میپردازیم.
الگوریتم پرندگان با الهام از رفتار جمعي پرندگان و ماهي‌ها و بکارگيري مفاهيم الگوريتم‌هاي تکاملي, معرفي شد. در این الگوریتم، تعدادي ذره که راه حلهاي کانديداي مسئله هستند، يک ازدحام را تشکيل مي‌دهند. اين ذرات در فضاي مسئله حرکت کرده و براساس نتایج فردي خود و نتایج جمعي سعي ميکنند تا راه حل بهينه در فضاي جستجو را بيابند. اين روش بوسيله ابعاد و غيرخطي بودن مسئله، خيلي تحت تأثير قرار نگرفته و نتايج خوبي در محيط‌هاي استاتيک, نويزي و محيطهاي بطور پيوسته در حال تغيير مي‌گيرد. اين ويژگي‌ها به علاوه سادگي پياده‌سازي، عدم الزام بر پيوستگي تابع هدف و توانايي وفق دادن به محيط پويا باعث شده که اين الگوريتم در حوزه‌هاي بسيار مختلفي بکار برده شود. در سال 2008 زنگ و همکارانش الگوریتم بهبود یافته پرندگان را برای مسئله RCPSP بکار بردهاند[58]. در سال 2008 نیز جاربویی و همکارانش الگوریتم ترکیبی پرندگان برای این مسئله بکار گرفتهاند[59].
الگوریتم ژنتیک بصورت گسترده در حل این مسئله بکار رفتهاست. هر راه حل بوسیله یک کروموزم مشخص میگردد. هر کروموزم دارای چند ژن است. ژنها بصورت رشتههایی هستند که برای نمایش قوانین اولویت و نمایش حالت و زمان انجام هر فعالیت بکار میروند. ژنهای مربوط به کروموزم اولیه بصورت تصادفی انتخاب میگردند. عملگرهای الگوریتم ژنتیک (تقاطع و جهش( برای بدست آوردن و حفظ کردن کروموزمهای خوب استفاده میگردند و مشخصات هر نسل را برای نسل بعد نگهداری میکنند. سعی میگردد، فضای بیشتری از پاسخهای ممکن کاوش گردند و بهترین از نظر تابع هدف را پیدا کنند. در سال 2009 مندس و همکارانش الگوریتم ژنتیک مبتنی بر کلید تصادفی را برای حل مسئله RCPSP بکار بردهاند[60].
الگوریتم زنبور براساس رفتارکلونی زنبورها عمل میکند. در الگوریتم زنبور هر منبع غذایی نشان دهنده یک جواب شدنی مسئله میباشد. مقدار شهد هر منبع غذایی متناظر با مقدار تابع هدف جواب شدنی میباشد. سه نوع زنبور در این الگوریتم تعریف میگردد. زنبورهاي راهنما، آن دسته از زنبورهایی هستند که نسبت به دیگر زنبورها از موقعیت بهتري برخوردارهستند. زنبورهاي سرباز زنبورهایی هستند که به صورت تصادفی در همسایگی زنبورهاي راهنما به دنبال منبع غذایی میگردند. در نهایت زنبورهاي دسته سوم به صورت تصادفی منابع غذایی جدید را جستجو میکنند. هر چرخه الگوریتم شامل سه گام اساسی میباشد. گام اول انتخاب زنبورهاي راهنما میباشد. گام دوم، فرستادن زنبورهاي سرباز در همسایگی زنبورهاي راهنما براي پیدا کردن منابع غذایی جدید،گام سوم فرستادن زنبورهاي کاوشگر به صورت تصادفی به دنبال منابع غذایی جدید میباشد. در پیادهسازی الگوریتم زنبورها در مسئله RCPSP از یک لیست اولویت استفاده میشود. هر زنبور نشان دهنده یک موقعیت در فضای جستجو میباشد. اگر مسئله n فعالیت داشتهباشد آنگاه زنبورها در یک فضای n بعدی حرکت میکنند. هر موقعیت بعنوان یک لیست اولویت در نظر گرفته میشود. هر عنصر این لیست یک فعالیت را نمایندگی میکند و مقدار متناظر با آن عنصر، اولویت آن فعالیت را مشخص میکند. بردار موقعیت هر زنبور، مقادیر اولویتn فعالیت را مشخص میکنند. در الگوریتم مصنوعی زنبورها نیز سه نوع زنبور داریم. زنبورهاي کارگر، زنبورهایی میباشند که با در نظر گرفتن منابع غذایی شناخته شدهي قبلی خود به دنبال پیدا کردن یک منبع غذایی جدید میگردند. زنبورهاي ناظر با استفاده از اطلاعاتی که زنبورهاي کارگر در اختیارشان میگذارند، به دنبال منبع غذایی جدید میباشند. در نهایت زنبورهاي دسته سوم به صورت تصادفی منابع غذایی جدید را جستجو میکنند. در سال 2011 اکبری و همکارانش الگوریتم زنبورهای مصنوعی را برای حل مسئله RCPSP بکار بردهاند[61]. الگوریتم گروهی زنبورها درسال 2010 توسط اکبري ارائهگردید. این الگوریتم تلفیقی از الگوریتم پرندگان و الگوریتم مصنوعی زنبورها میباشد. در این الگوریتم سه نوع زنبور تعریف میگردد: زنبورهاي کارگر، زنبورهاي ناظر و زنبورهاي کاوشگر. زنبورهاي کارگر، زنبورهایی میباشند که با در نظر گرفتن منابع غذایی شناخته شده قبلی خود و بهترین جواب یافته شده تاکنون توسط خود زنبور و بهترین جواب یافت شده تاکنون دربین تمامی زنبورها، به دنبال پیداکردن یک منبع غذایی جدید میگردند. زنبورهاي ناظر به استفاده از اطلاعاتی که زنبورهاي کارگر در اختیارشان میگذارند و با در نظر گرفتن منابع غذایی شناخته شده قبلی خود، به دنبال منبع غذایی جدید میباشند. در نهایت زنبورهاي کاوشگر به صورت تصادفی در همسایگی خودشان منابع غذایی جدید را جستجو میکنند. در سال 2011 اکبری و زیارتی و ضیغمی الگوریتمهای زنبور، زنبور مصنوعی و گروهی زنبورها را برای حل RCPSP بکار گرفتند و کارایی آنها را با هم مقایسه نمودند[3]. این الگوریتمها پاسخهای رقابتپذیری با دیگر الگوریتمها را ارائه میدهند. در سال 2012 نیز ضیغمی و اکبری الگوریتم زنبور مصنوعی را با الگوریتم ژنتیک پیوند زدند و برای حل مسئله RCPSP استفادهکردند[62].
الگوریتم کرم شبتاب براساس روشنایی یک گروه از کرم شب تاب طراحی شده است. نور چشمک زن برای یک کرم شبتاب حیاتی است و برای یافتن غذا و جفتگیری و محافظت در مقابل شکارچیان از آن استفاده میکند.کرمهای شبتاب به سمت مکانهای با نور بیشتر جذب میشوند. کرمی که درخشندگی کمتری دارد به سمت کرمی که درخشندگی بیشتری دارد جذب میشود. اگر کرم شبتابی درخشندهتر از کرم مورد نظر نباشد، بطور تصادفی حرکت میکند. روشنایی با افزایش فاصله نیز کاهش مییابد. میزان روشنایی نور چشمکزن بعنوان تابع هدف در نظر گرفته میشود. در حل مسئله RCPSP هر کرم شب تاب یک زمانبندی برای مسئله را نشان میدهد. مسئلهای با n فعالیت دارای کرمهای شبتاب با فضای جستجوی n بعدی است. هر

دسته بندی : No category

دیدگاهتان را بنویسید