دانلود پایان نامه

میکند [35] یعنی با برداشتن گامهایی با طول مشخص از نقطهای در فضای حل به نقطه دیگر حرکت میکند. این الگوریتم از فرایند سرد کردن تدریجی مذاب فلزات برای بدست آوردن بیشترین استحکام مولکولی در کریستال آنها الگوبرداری شده است.
الگوریتم تبرید شبیهسازی شده فرایند جستجوی خود را با نقطهای تصادفی در فضای حل آغاز کرده و با هر بار کاهش دما از نقطهای به نقطه دیگر حرکت میکند و در صورت یافتن جواب بهتر آن را جایگزین جواب جاری میکند. همچون سایر الگوریتمهای فراابتکاری، تبرید شبیهسازی شده نیز رویکرد ویژه خود را برای گذر از بهینه محلی دارد که عبارت است از پذیرفتن جواب بد با احتمال مشخص. به این معنی که در هر مرحله کاهش دما چنانچه جواب حاصل شده بدتر از جواب کنونی بود با احتمالی مشخص آن را میپذیرد و به این ترتیب امکان جستجوی فضاهای حل ناشناخته را فراهم میکند و در نهایت با فراهم شدن شروط توقف، بهترین جواب بدست آمده را ارائه میدهد.
4-3-1. شمای کلی الگوریتم تبرید شبیهسازی شده
الگوریتم تبرید شبیهسازی شده به طور کلی مطابق شبیه برنامه زیر عمل میکند:
تولید یک جواب تصادفی و محاسبه مقدار تابع هدف به ازای آن.
تعیین دمای اولیه.
اعمال جهش و تولید جواب همسایگی جدید.
چنانچه جواب همسایگی از جواب اولیه بهتر بود، جایگزین کردن آن با جواب اصلی و در غیر اینصورت جایگزین کردن آن با یک احتمال مشخص.
کاهش دما.
بررسی شروط توقف. چنانچه شروط توقف برقرار بود، توقف و در غیر اینصورت مرحله 3.
4-3-2. تئوری ابری
تئوری ابری یک نوآوری و توسعه در مبحث تابع عضویت در تئوری فازی است [13] که مدلی برای انتقالهای غیر قطعی بین نمایشهای کمی و مفاهیم کیفی در ارزش زبان مورد استفاده قرار میگیرد [14]. این تئوری پیادهسازیهای موفقی در بسیاری از زمینههای بهینهسازی نظیر داده کاوی116، تشخیص هدف117، نمایش دانش118 و بهبود در الگوریتمهای هوشمند119 داشته است. برای مشاهده نمونههای کاربرد این تئوری در زمینههای مختلف به [35] مراجعه کنید.
مدل ابری فرایند انتقالی غیر قطعی بین مفاهیم کیفی و دادههای کمی را تبیین میکند و به دلیل ماهیت خود مفاهیم فازی و تصادفی را به یاد میآورد.
به عنوان مثالی جهت تبیین تئوری ابری، فرض کنید T تابعی با دامنه u باشد. در نتیجه C_T (x):u→[0, 1],∀x∈u, x→C_T (x) . یعنی به ازای هر x عضو u، تابع عددی بین [0, 1] را برمیگرداند. در اینصورت C_T (x) را در دامنه u، ابر عضویت T مینامند. حال اگر C_T (x) دارای توزیع نرمال باشد، آن را مدل ابر نرمال مینامند [35]. این ابر حاوی اعدادی تصادفی با توزیعی یکسان هستند که با امید ریاضی120 (Ex)، پراکندگی121 (En) و سوپر پراکندگی122 (He) معرفی میشوند و میتوانند ویژگیهای کیفی C_T (x) را بازتاب دهند. Ex مرکز ابر را نشان میدهد، En دامنه پراکندگی ابر را تعیین میکند که با توجه به ویژگیهای توزیع نرمال، در نهایت ابر بین [Ex-3En, Ex+3En] پراکنده خواهد شد. He نیز میزان تراکم ابر را نشان میدهد به این معنی که هرچه He بزرگتر باشد ذرات ابر پراکندهتر و تراکم ابر کمتر خواهد بود. شکل(4-4) شکل نهایی ابر را نمایش میدهد.
حال اگر سه مشخصه اصلی (Ex, En, He) و دامنه تغییرات u_0 برای هر ابر دلخواه drop(x_i, u_0) داده شده باشد میتوان به کمک یک تولید کننده ابر نرمال که تولید کننده Y نامیده میشود ابر مورد نظر را تولید کرد. نحوه تولید یک ابر نرمال با مشخصات بالا از شبه برنامه زیر طبعیت میکند [13]:
Input: {Ex, En, He}, n, u_0
Output: {(x_1, u_0 ),…,(x_n, u_0 )}
For i=1 to n
〖En〗^’=randn(En, He)
x_i=Ex±〖En〗^’ √(-2ln⁡(u_0))
drop(x_i, u_0)
در این شبه برنامه randn(En, He) اعداد تصادفی با توزیع نرمال تولید میکند و n تعداد اعداد درون ابر را مشخص میکند.
4-3-3. الگوریتم تبرید شبیهسازی شده با رویکرد ابری
الگوریتم تبرید شبیهسازی شده با رویکرد ابری از همان پدیده تبرید فلزات در دنیای واقعی الگوبرداری میکند. از آنجا که فرایند تبرید واقعی بسیار آهسته و با شیب کندی صورت میگیرد، کاهش پلهای دما که در الگوریتم تبرید شبیهسازی شده کلاسیک مورد استفاده قرار میگیرد چندان واقعی به نظر نمیرسد.به علاوه اینکه با پرش از نقطهای به نقطه دیگر در فضای حل بسیار محتمل به نظر میرسد که جستجوی بخشی از فضای حل را از دست بدهد. رویکرد ابری با تولید اعداد دارای توزیع نرمال حول یک دمای معین امکان حرکت آهستهتر و جستجوی بهتر و دقیقتر فضای حل را فراهم میکند به علاوه اینکه
الگوبرداری ما را از رفتار فیزیکی تبرید دقیقتر خواهد کرد. شکل(4-5) مقایسه نحوه جستجوی الگوریتم تبرید شبیهسازی شده کلاسیک و تبرید شبیهسازی شده با رویکرد ابری را نشان میدهد. در این شکل بهبود فرایند جستجو در الگوریتم تیرید شبیهسازی شده با رویکرد ابری کاملا واضح است.
4-3-3-1. مفاهیم الگوریتم تبرید شبیهسازی شده با رویکرد ابری و نحوه بکارگیری آنها
الگوریتم تبرید شبیهسازی شده با رویکرد ابری نیز همچون سایر فرایندهای جستجو از مجموعه مراحلی تشکیل شده است که در ادامه به طور کامل مورد بحث قرار میگیرند.
نمایش جواب
تابع ارزیابی جواب
تولید جواب همسایگی
معیار پذیرش جواب
فرایند تبرید
شروط توقف
4-3-3-1-1. نمایش جواب
نحوه نمایش جواب در الگوریتم تبرید شبیهسازی شده با رویکرد ابری دقیقا مشابه نحوه نمایش جواب در الگوریتم سیستم ایمنی مصنوعی است. لذا در این بخش از توضیح مجدد آن اجتناب میگردد. برای مطالعه چگونگی نحوه نمایش جواب در این الگوریتم به زیر فصل(4-2-2-1) مراجع
ه شود.
4-3-3-1-2. تابع ارزیابی جواب
همانطور که پیشتر در بخش(4-2-2-2) نیز اشاره شد، توابع ارزیابی عملکرد یک جواب به منظور مقایسه جوابها جهت برگزیدن جواب بهتر مورد استفاده قرار میگیرند. از آنجا که به لحاظ ماهیت الگوریتم تبرید شبیهسازی شده یعنی رسیدن به کمینه انرژی بین مولکولی ممکن این الگوریتم با مسائل مینیممسازی همخوانی بیشتری دارد، لذا میتوان از تابع هدف مسئله به عنون تابع ارزیابی عملکرد جوابها نیز استفاده کرد، یعنی هرچه تابع هدف به ازای جوابی کوچکتر باشد آن جواب بهتر خواهد بود.
4-3-3-1-3. تولید جواب همسایگی
تولید جواب همسایگی در الگوریتم تبرید شبیهسازی شده عموما به کمک یک یا چند روش از رویکردهای شناخته شده جهش در جواب انجام میشود. در الگوریتم تبرید شبیهسازی شده با رویکرد ابری که در اینجا مورد بحث قرار میگیرد نیز همچون الگوریتم سیستم ایمنی مصنوعی ارائه شده در بخش قبل، جواب همسایگی توسط انتخاب تصادفی بین یکی از دو روش انتقال و جابجایی تولید میگردد که هر دو روش در زیر بخش(4-2-2-5) به طور کامل تشریح شدهاند. به این منظور ابتدا یکی از روشهای انتقال یا جابجایی به تصادف انتخاب شده و سپس تنها یک بار اعمال میگردد.
4-3-3-1-4. معیار پذیرش جواب
معیار پذیرش در الگوریتم تبرید شبیهسازی شده شاخصهای کلیدی برای جلوگیری از توقف در بهینه محلی و رسیدن به بهینه سراسری است. نحوه عملکرد این شاخصه به این صورت است که پس از تولید جواب همسایگی (s_1) و ارزیابی عملکرد آن چنانچه جواب همسایگی از جواب جاری (s_0) بهتر بود جایگزین آن میگردد و در غیر اینصورت با احتمالی مطابق رابطه(4-3) جواب جدید جایگزین جواب جاری میشود.
(4-3)
p_acceptance=|f(s_0 )-f(s_1)|/T
این احتمال در علم ترمودینامیک به تابع بولتزمن123 شناخته میشود. در این تابع p_acceptance احتمال پذیرش جواب بدتر را محاسبه میکند، f(s_0 ) مقدار تابع هدف را به ازای جواب جاری و f(s_1) مقدار این تابع را به ازای جواب همسایگی تولید شده نشان میدهد. در این عبارت T دمای تکرار جاری را نشان میدهد.
4-3-3-1-5. فرایند تبرید
در الگوریتم تبرید شبیهسازی شده کلاسیک مقدار متغیر دما در هر تکرار ثابت بوده و فرایند جستجو در آن تکرار در دمای ثابت انجام میگردد. پس از آن برای رفتن به تکرار بعد دما با تابعی که عموما نمایی است پایینتر آورده میشود. این کار تا رسیدن به شرایط توقف ادامه مییابد. تابع نمایی کاهش دما در الگوریتم تبرید شبیهسازی شده مطابق عبارت(4-4) است:
(4-4)
T=T_0 λ^k , k=1, 2, …, 0 λ1
در این عبارت T_0 دمای اولیه الگوریتم، λ نرخ کاهش دما یا همان فاکتور توزیع نمایی و k شمارنده تعداد تکرار الگوریتم است.
تفاوت اصلی الگوریتم تبرید شبیهسازی شده با رویکرد ابری در مقایسه با رویکرد کلاسیک این الگوریتم در فرایند تبرید این دو رویکرد است. در الگوریتم تبرید شبیهسازی شده با رویکرد ابری، در هر تکرار، ابری از دماهای متفاوت که از توزیع نرمال با میانگین دمای تکرار جاری تبعیت میکنند به کمک تابع تولید Y که پیشتر توضیح داده شده حول دمای جاری تولید شده و هر نقطه دمایی در واقع امکان یک جستجوی اضافه در فضای حل را به ارمغان میآورد، به این ترتیب در هر تکرار علاوه بر جستجوی نقطهای از فضای حل که متناظر با دمای جاری آن تکرار است، محیطی مشخص از فضای حل که حول دمای جاری قرار دارد نیز مورد بررسی قرار میگیرد. بدیهی است که هرچه تعداد دماهای تولید شده توسط تابع تولید Y بیشتر باشد نقاط بیشتری مورد بررسی قرار گرفته و جستجوی دقیقتری را موجب میشوند. بر همین اساس به منظور جستجوی دقیقتر فضای حل، با بزرگتر شدن اندازه جواب که به دلیل پذیرفته شدن تعداد متفاوتی از سفارشات رخ میدهد، تعداد نقاط دمایی که توسط تابع تولید Y تولید میشوند افزایش خواهد یافت. اگر تعداد نقاط تولید شده برابر n باشد، مقدار nبرابر است با:
(4-5)
n=size of solution×10
4-3-3-1-6. شروط توقف
شرط توقف در الگوریتم تبرید شبیهسازی شده معمولا رسیدن به دمایی از پیش تعیین شده است. البته میتوان به آن بیشینه تعداد تکرارهایی که در آنها بهبودی حاصل نشده را نیز اضافه کرد. در تحقیق پیش رو رسیدن به دمای نهایی T_f به عنوان دمای نهایی به عنوان شرط توقف در نظر گرفته شده است. از آنجا که هرچه مقدار این دما کوچکتر باشد تعداد تکرارهای الگوریتم افزایش مییابد، در این پژوهش با افزایش تعداد سفارشات پذیرفته شده مقدار دمای نهایی کوچکتر خواهد شد. نحوه پیادهسازی این ویژگی به اینصورت است که اگر مقدار دمای نهایی برای افرازی با تعداد سفارش یک برابر t_f باشد، به ازای ورود به افرازی با تعداد سفارش پذیرفته شده دو این دما به مقدار ( t_f×〖10〗^(-1) ) کاهش پیدا خواهد کرد. در حالت کلیتر، مقدار دمای نهایی طبق رابطه (4-4) محاسبه میگردد:
(4-6)
T_f=t_f×〖10〗^(i-1)
در این عبارت i تعداد سفارشات پذیرفته شده در هر افراز را نشان میدهد.
شکل(4-6) شبه برنامه الگوریتم تبرید شبیهسازی شده با رویکرد ابری را برای مسئله مذکور نشان میدهد.
4-4. مسائل آزمایشی124
از آنجا که مسئله مورد بررسی در این پژوهش از جنبههای متعددی اعم از تابع هدف، نحوه تعریف کارها و … دارای نوآوری است، لذا پژوهشی که از نظر مجموعه مسائل آزمایشی و نتایج بدست آمده آن قابلیت مقایسه با مسئله حاضر را داشته باشد یافت نشد. به همین دلیل برای حصول نتایج معتبرتر و جامعتر، تصمیم به استفاده از دو رویکرد فراابتکاری با روشهای متفاوت گرفته شد. الگوریتم سیستم ایمنی مصنوعی به عنوان رویکردی جمعیت محور125
و الگوریتم تبرید شبیهسازی شده با رویکرد ابری به عنوان روشی مبتنی بر جستجوی تک نقطهای126. در نهایت به دلیل در دسترس نبودن مسائل استاندارد در این حوزه، مجموعهای از مسائل که به صورت تصادفی تولید شدهاند برای مقایسه عملکرد این دو الگوریتم مورد استفاده قرار گرفتند. پارامترهای لازم برای تولید مسائل آزمایشی تصادفی عبارتند از: تعداد بستههای سفارشی ارائه شده، تعداد محصولات قابل تولید در سیستم، بیشینه تعداد محصول قابل سفارش از هر نوع در هر بسته سفارشی، تعداد ایستگاهها و تعداد ماشینهای موجود در آنها، زمانهای پردازش، زمانهای در دسترس قرار گرفتن سفارشات، موعدهای تحویل سفارشات، زمانهای راهاندازی و در نهایت وزنهای مربوط به زودکرد، دیرکرد، رد و تحویل ناقص سفارشات. در جدول(4-1) فاکتورهای مسائل تولید شده و مقادیر آنها آورده شده است.
جدول 11 جدول 4-1. پارامترهای تولید شده تصادفی.
مقادیر
پارامترها
3، 5
تعداد بستههای سفارشی
3، 5
تعداد محصولات قابل تولید
25، 35
بیشینه تعداد محصولاتی که از هر نوع در هریک از بستههای سفارشی میتواند سفارش داده شود
2، 4
تعداد ایستگاهها
127U(4 ،1)
تعداد ماشینهای هر ایستگاه
U(100 ،10)
زمانهای پردازش
U(100 ،10)
زمانهای در دسترس قرار گرفتن سفارشات
(∑_(i=1)^(No.job)▒〖〖No. job〗_i×∑_(s=1)^(No.stage)▒〖p_ij+round(U(1,∑_(s=1)^(No.stage)▒p_ij )/(∑_(s=1)^(No.stage)▒〖No.machine〗_s ))〗〗)/(∑_(i=1)^(No.job)▒〖No. job〗_i )
موعد تحویل سفارشات
U(4 ،1)
زمانهای راهاندازی
U(5 ،1)
وزن زودکرد سفارش
U(5 ،1)
وزن دیرکرد سفارش
U(100 ،30)
وزن رد کردن سفارش
U(5 ،1)
وزن ناقص بودن سفارش
در نتیجه پارامترهای تعریف شده در جدول(4-1)، مسائل آزمایشی جهت مقایسه الگوریتمها مطابق جدول(4-2) خواهد بود.
جدول 12 جدول 4-2. مسائل آزمایشی تولید شده.
مسئله
تعداد بستههای سفارشی
تعداد محصولات قابل تولید
بیشینه محصولات قابل سفارش از هر نوع
تعداد ایستگاههای کاری
1
3
3
25
2
2
3
3
25
4
3
3
3
35
2
4
3
3
35
4
5
3
5
25
2
6
3
5
25
4
7
3
5
35
2
8
3
5
35
4
9
5
3
25
2
10
5
3
25
4
11
5
3
35
2
12
5
3
35
4
13
5
5
25
2
14
5
5
25
4
15
5
5
35
2
16
5
5
35
4
به دلیل ماهیت تصادفی الگوریتمها و نیز به دلیل در دسترس نبودن آزمایشات قبلی بر روی مسائل آزمایشی تولید شده، برای حصول نتایج دقیقتر و کاستن از وجه تصادفی بودن نتایج، هریک از مسائل فوق پنج بار توسط هرکدام از الگوریتمهای ارائه شده حل شده است.
4-5. تنظیم پارامترهای الگوریتمها(کالیبراسیون)
تنظیم پارامترهای الگوریتمهای فراابتکاری یکی از اصلیترین گامها در حصول نتایج مناسب توسط آنها است. این الگوریتمها عموما نسبت به پارامترهای تعیین کننده خود حساس هستند. این حساسیت بسته به نوع الگوریتم و ویژگیهای ساختاری آن میتواند زیاد یا کم باشد. درک این حساسیت و انتخاب بهترین ترکیب برای پارامترهای آنها میتواند در رسیدن به شاخصهای کارایی مناسب نظیر کیفیت جواب مطلوب و زمان منطقی موثر باشد.
الگوریتمهای مورد بحث در این پژوهش نیز از

مطلب مرتبط :   هوش عاطفی، خودآگاهی، مسئولیت پذیری، انعطاف پذیری

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