ی میافتیم. بنابراین سطرهای تکراری را تغییر میدهیم. مثلا جایگشت جدیدی را جایگزین آن میکنیم و زمانبندی اولیه را روی آن اعمال میکنیم.
سپس ماتریس Population را براساس نتایج هر سطر که همان makespan ها هستند، بصورت صعودی مرتب میکنیم. حال لیستهای فعالیت نخبه را جایگزین سطرهای آخر ماتریس میکنیم. با اینکار پاسخهای بدتر را حذف مینماییم. حال ماتریس Population باز هم تغییر کرد. مجددا فازهای معلم و فراگیر را تکرار میکنیم. در پایان سطر اول ماتریس کمترین رمان تکمیل را دارد. تعداد تکرار (maxit)، اندازه جمعیت، تعداد موضوعات آموزش و اندازه نخبه، پارامترهای عمومی و ورودی الگوریتم هستند. در شکل 4-13، یک لیست شدنی،که از شکل 4-11 بدست آوردهایم، را نمایش میدهد که چگونه با اجرای الگوریتم ETLBO و تاثیر فازهای معلم و فراگیر، لیست جدیدی بدست میآید. makespan لیست اولیه 16 است که در لیست جدید به 13 بهبود مییابد.
شکل 4-13 بهبود زمان تکمیل فعالیتها با اجرای ETLBO
در شکل 4-14 فلوچارت حل مسئله زمانبندی پروژه با منابع محدود با الگوریتم بهینهسازی مبتنی بر آموزش-یادگیری آمدهاست.
فصل پنجم
نتایج عددی و نتیجه‌گیری
5-1 مقدمه
در این فصل کارایی الگوریتم مبتنی بر آموزش-یادگیری را در حل مسئله RCPSP بررسی میکنیم و با دیگر الگوریتمهای فراابتکاری که در حل این مسئله بکار گرفته شدهاند، مقایسه میکنیم. از نمونه مسائل کتابخانه PSPLIB[69] استفاده کردهایم. این کتابخانه شامل نمونه مسائل استانداردی برای مسئله RCPSP است. نمونه مسائل این کتابخانه 4 نوع منبع دارند و شامل 30، 60، 90 و 120 فعالیت هستند. فعالیتها با اعداد طبیعی مشخص شدهاند و طول زمان هر فعالیت عددی بین 1 تا 10 واحد زمانی است. در بخش بعد این کتابخانه بیشتر توضیح داده میشود. الگوریتم را با استفاده از نرمافزار MATLAB 2012 پیادهسازی کردهایم و مسائل را با ترکیبها و پیکربندیهای مختلف، براساس پارامترهای اندازه جمعیت، حداکثر زمانبندیها (تعداد تکرار) و اندازه نخبه حل کردهایم. تاثیر این پارامترها را بر الگوریتم تحلیل و بررسی نمودهایم. برای مقایسه با دیگر الگوریتمها، از معیارهای نرخ همگرایی و درصد انحراف میانگین از پاسخ بهینه یا از طول مسیر بحرانی استفاده شدهاست. از آنجا که برای مسائل J60 و J90 و J120 در کتابخانه مذکور پاسخ بهینه نداریم، از طول مسیر بحرانی در این مسائل برای محاسبه درصد انحراف میانگین استفاده شدهاست. در مورد مسائل J30 جواب بهینه را داریم. بنابراین از خود جواب بهینه استفاده مینماییم.
5-2 کتابخانه PSPLIB
گستردگی حالتهاي مختلف مسئله زمانبندی پروژه با منابع محدود، فرضیات مختلف آن و روشهاي مختلفی حل این مسئله که با توجه حالتهاي متفاوت آن طراحی شده است، باعث ایجاد مسائل استاندارد براي این حالتهاي متفاوت شدهاست. به کمک این مسائل استاندارد امکان مقایسه الگوریتمهای مختلف را تسهیل کردهاست. دیویس70 اولین بار 83 نمونه استاندارد از مسئله زمانبندی پروژه با منابع محدود ایجاد نمود. پترسون71 و هیبر72،11 مثال نمونه ایجاد کردند. سپس تالبوت73 و پترسون 10 مثال دیگر ایجاد کردند. پترسون، همه مثالهای گفته شده به همراه 6 مثال دیگر را در یک دسته جمعآوری کرد و یک مجموعه شامل 110 مثال استاندارد بوجود آورد. پترسون، پاسخ بهینه برای هر 110 مثال را با تابع هدف کمترین زمان تکمیل پروژه، بدست آورد و به مجموعه استانداردش اضافه کرد. همه این مثالها، مسئله زمانبندی پروژه با منابع محدود تک حالتی74 بودند[68]. نقطه ضعف نمونه مسائل مجموعه پترسون، نداشتن پارامترهایی بود که براي آزمایش الگوریتمها، استفاده شود. پارامترهایی را در طرح مسائل استاندارد باید تعیین نمود، تا بتوان به کمک این پارامترها، پیچیدگی مسئله را کنترل کرد. آلوارز75 و تاماریت76 مجموعه مسائل استاندارد دیگری با 144 مثال را ارائه کردند و 5 نوع پارامتر برای آنها در نظر گرفتند. در این مثالها مسائل با 25 و 49 و 101 فعالیت تعریف شدهاند[68]. بعد از آنها کولیش77 480 مسئله نمونه با 30 فعالیت برای مسئله زمانبندی پروژه با منابع محدود یک حالته و 640 مسئله نمونه با 10 فعالیت برای مسئله زمانبندی پروژه با منابع محدود چندحالته78 ایجاد کرد. کولیش و اسپرچر79 به مجموعه قبلی مثالهای جدید با 60 و 90 و 120 فعالیت افزودند و 10000 مسئله نمونه ایجاد کردند[68]. کولیش برنامه ProGen اولین، تولید کننده مسائل برنامهریزي و تخصیص منابع را ایجاد کرد که از روش نمایش فعالیت روي گره80 برای تولید مسائل استفاده میکند. ProGen محققان را قادر میسازد که مثالهای مورد نظر خود را همراه با پارامترهای مختلف ایجاد کنند. سه پارامتر مهم NC81 و RF82 و RS83 هستند که در کنترل پیچیدگی مسائل بکار میروند. NC متوسط تعداد روابط پیشنیازي در هر فعالیت است، RF متوسط درصد مقدار منابعی است که هر فعالیت لازم دارد و RS استحکام میزان منابع را نشان میدهد. اگر منبع مورد نظر به اندازهای باشد که معادل منبع نامحدود باشد RS صفر میشود. با استفاده از ProGen، کولیش و اسپرچر یک کتابخانه استاندارد برای مسئله زمانبندی پروژه با منابع محدود یک حالته ایجادکردند که طبق جدول 5-1 مقادیر پارامترهای NC و RF و RS انتخاب شدهاند. این مثالها در کتابخانه موسوم به PSPLIB در سایت اینترنتی http://www.om-db.wi.tum.de/psplib موجود میباشد.
جدول 5-1 مقادیر پارامترهای مسائل نمونه در کتابخانه PSPLIB
با توجه به جدول 3*4*4=48 ترکیب مختلف برای سه پارامتر داریم. برای هر یک از 48 حالت، بطور جداگانه برای مسائل با 30 و 60 و 90 فعالیت، 10 مسئله تولید شده است که جمعا 480 مسئله برای هرکدام از مسائل با 30و 60 و 90 فعالیت ایجاد گردیدهاست. همچنین 600 مسئله با 120 فعالیت نیز ایجاد شده است. هر کدام از مسائل در فایلی جداگانه در کتابخانه PSPLIB تعریف گردیدهاند. برای مثال فایل j3015_4.SM یعنی مسئله 30 فعالیت ( با دو فعالیت مجازی ابتدایی و انتهایی 32 فعالیت) دارد و مسئله شماره 4 برای ترکیب پارامترها با شماره 15 است. پسوند SM نیز مشخص میکند که فعالیتها تک وضعیتی هستند، یعنی یک روش اجرا دارند. شماره ترکیب پارامترها در فایل j30PAR.SM قرار دارند.
برای نمونه مسائل با 30 فعالیت، جواب بهینه با الگوریتمهای دقیق بدست آمدهاست که در فایل j30OPT.SM موجود است. نمونه مسائل با 60 و 90 و 120 فعالیت بهعلت پچیدگی زیاد، با روشهای دقیق حل نشدهاند. نمونه مسائل با 60 و 90 و 120 فعالیت موجود در کتابخانه را بدون در نظر گرفتن محدودیت منابع حل کردهاند و پاسخهای بدست آمده را بعنوان حد پایین برای نمونه مسائل مذکور با محدودیت منابع، در نظر گرفتهاند. در فایلهای j60lb.txt و j90lb.txt و j120lb.txt از کتابخانه PSPLIB، این حدهای پایین ذخیره شدهاند. برای این مسائل، بهترین پاسخهای بدست آمده با الگوریتمهای ابتکاری، در فایلهای j60HRS.SM و j90HRS.SM و j120HRS.SM در دسترس هستند. این فایلها دایما بهروز میگردند. از آنجا که این کتابخانه در اینترنت در دسترس است، براي مسائلی که جواب بهینه آنها بدست نیامدهاست، هر فردي میتواند در صورتیکه جواب بهینه یا بهتر براي آن مسائل بدست آورد به کتابخانه اضافه کند. پروژههای تعریف شده در کتابخانه پروژهها با 30 و 60 و 90 و120 فعالیت، به ترتیب با نامهای J30 و J60 و J90 وJ120 مشخص میشوند.
5-3 نتایج آزمایش اجرای الگوریتم با پیکربندیهای مختلف
در این قسمت تاثیر پارامترهای اندازه جمعیت، حداکثر زمانبندیها (تعداد تکرار) و اندازه نخبه را بر الگوریتم TLBO بررسی کردهایم. معیارهای کارایی را نرخ همگرایی (موفقیت) و درصد انحراف میانگین از پاسخ بهینه برای J30 و از طول مسیر بحرانی برای J60 و J90 و J120 در نظر گرفتهایم. بصورت پیشفرض منظور از کارایی را نرخ همگرایی در نظر گرفتهایم. نرخ همگرایی از رابطه زیر بدست میآید:
Success Rate = S/M * 100 (5-1)
در این رابطه M تعداد کل مسائل نمونه است وS تعداد مسائل نمونهاي است که با موفقیت حل شدهاند. Success Rate، درصد موفقیت در، یافتن پاسخ بهینه است.
درصد انحراف میانگین از رابطه زیر بدست میآید:
Average percent deviations = i/instances ∑_1^(instances )▒(E-CPM)/CPM * 100 (5-2)
در این رابطه E پاسخ بدست آمده از الگوریتم و CPM طول مسیر بحرانی در گراف فعالیتهاست. Instances نیز تعداد مسائل نمونه است.
5-3-1 تاثیر اندازه جمعیت با تعداد تکرار ثابت
در اولین آزمایش تاثیر اندازه جمعیت را بر کارایی الگوریتم TLBO بررسی کردهایم. اندازه نخبه را 4 فرض کردهایم. تعداد تکرار را دو حالت 100 و 1000 در نظر گرفتهایم. منظور از تعداد تکرار، حداکثر تعداد زمانبندیهای انجام گرفته برای هر نمونه مسئله میباشد. در صورتیکه پاسخ بهینه یا حد پایین، زودتر از رسیدن به حداکثر زمانبندی، بدست آید، اجرای برنامه خاتمه مییابد. در این جا نرخ همگرایی، معیار کارایی میباشد.
در حالت با تعداد تکرار 100، اندازه جمعیت را از 10 تا 100 با طول گامهای 10 تغییر دادهایم. نتایج بدست آمده در جدول 5-2 و شکل 5-1 نمایش داده شدهاست.
جدول 5-2 تاثیر اندازه جمعیت بر کارایی الگوریتم TLBO با تعداد تکرار 100
Population size
10
20
30
40
50
60
70
80
90
100
Success rate
J30
82.5
83.5
84.4
85.4
84.6
84.2
85.6
85.0
85.4
86.7
J60
71.5
71.3
72.1
71.3
71.9
71.7
72.1
71.7
71.7
72.1
J90
71.3
71.3
70.6
71.9
71.7
71.3
71.3
71.5
71.9
71.9
J120
28.3
27.8
28.2
28.2
27.7
27.8
28.5
28.3
28.3
27.8
j30 case study
J60 case study
j90 case study
J120 case study
شکل 5-1 تاثیر اندازه جمعیت بر کارایی الگوریتم TLBO با تعداد تکرار 100
در حالت با تعداد تکرار1000، اندازه جمعیت را از 25 تا 100 با طول گامهای 25 تغییر دادهایم. نتایج بدست آمده در جدول 5-3 نمایش داده شدهاست.
جدول 5-3 تاثیر اندازه جمعیت بر کارایی الگوریتم TLBO با تعداد تکرار 1000
Population size
25
50
75
100
Success rate
J30
89.6
88.1
88.3
89.4
J60
71.5
71.7
71.3
72.3
J90
72.1
73.1
72.1
73.1
J120
29.5
29.3
29.1
29.1
شکل 5-2، براساس تعداد فعالیتها و اندازه جمعیت نتایج را نمایش دادهاست. نتایج در مسائل J60 و J90 بسیار به هم نزدیک هستند.
شکل 5-2 تاثیر اندازه جمعیت بر کارایی الگوریتم TLBO با تعداد تکرار 1000
شاید انتظار این است که رابطه خطی بین کارایی الگوریتم و اندازه جمعیت وجود داشته باشد ولی بطور کامل اینگونه نیست. در بیشتر نتایج تعداد جمعیت 100 بیشترین کارایی را دارد ولی همواره اینگونه نیست، مثلا در تعداد تکرار1000 برای مسائل J120 تقریبا شیب نمودار ثابت است و تاثیر جمعیت بر کارایی بصورت جزیی منفی است. در تعداد تکرار 100، در مسائل J30 و J60 و J90 تاثیر جمعیت، بیشتر مثبت است و با افزایش تعداد فعالیت از این تاثیر کاسته میشود. در حالت تعداد تکرار 1000 نیز تقریبا همین گونه است. بطور کلی میتوان گفت که با افزایش جمعیت، احتمال افزایش کارایی بالا میرود.
5-3-2 تاثیر اندازه جمعیت با تعداد تکرار متغیر
در آزمایش بعد تاثیر تعداد جمعیت و تعداد تکرار را بر کارایی الگوریتم TLBO بررسی کردهایم. اندازه نخبه را از 10 تا 100 با طول گامهای 10 و تعداد تکرار را از 250 تا 25 تغییر دادهایم. بطوریکه حاصلضرب تکرار د

دسته بندی : No category

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