ی الگوریتم شبیه سازی تبرید
به منظور آشنایی بیشتر با الگوریتم SA مطابق آنچه در مرجع [2] آمده است، برخی نمادهای استفاده شده در این قسمت را بیان میکنیم. f(x) مقدار تابع هدف بهازای x بوده و x_c یک جواب جاری در هر مرحله می باشد. V (x_c) مجموعهای است که برای نشان دادن همسایههای x_c بهکار میرود.p یک عدد تصادفی است که در زمان برخورد با جواب بدتر بهمنظور بررسی پذیرش یا عدم پذیرش آن جواب بهکار میرود.
در قدم اول الگوریتم یک جواب اولیه ایجاد و مقدار تابع هدف آنرا محاسبه میکند. دراین قدم جواب اولیه بهعنوان جواب جاری x_cو بهترین جوابx^* نیز درنظر گرفته میشود. البته این دو جواب در طول الگوریتم تغییر خواهند یافت. همچنین مقدار تابع هدف جواب اولیه بهعنوان مقدار تابع هدف جواب جاری f(x_C) و بهترین جواب f(x^*) نیز در نظر گرفته میشود. در این قدم دمای اولیه T_0 بهعنوان دمای جاری T_cدر نظر گرفته میشود.
در قدم دوم در هر دما یک زنجیره مارکف ایجاد میگردد (زنجیره مارکف یک سیستم ریاضی است که در آن انتقال از یک حالت به حالت دیگر صورت می‌گیرد). در این مرحله جستجوی همسایگی تا زمانیکه زنجیره مارکف به انتها برسد انجام میگردد. بدین منظور برای هر جواب جاری یک جواب همسایه x_(c^’ ) در همسایگی آن پیدا شده و مقدارتابع هدف آن f(x_(c^’ ) ) محاسبه میگردد. درصورتیکه همسایه جدید، مقدار تابع هدف جاری را بهبود بدهد یا برابر آن باشد (f(x_(c^’ ) )≤f(x_C)) جواب همسایه بهعنوان جواب جاری پذیرفته میشود. (الگوریتم از یک نقطه به نقطه دیگر حرکت میکند) و جواب جدید بهعنوان جواب جاری پذیرفته میشود.(x_(c^’ )→x_c و ( f(x_(c^’ ))→f(x_c). درغیر اینصورت اگر جواب همسایه منجر به بدتر شدن تابع هدف جاری گردد ( f(x_(c^’ ) )f(x_c )) همسایه، با تابع احتمال e^((-∆f)/T_c ) ارزیابی میگردد. در این تابع مقدار اختلاف انرژی از طریق ∆f= f(x_(c^’ ) )-f(x_c ) محاسبه میگردد. برای اینمنظور مقدار تصادفیp∈U(0,1) تولید و سپس با تابع احتمال مقایسه میگردد. در صورتیکه مقدار p از تابع احتمال کمتر باشد جواب همسایه بهعنوان جواب جاری پذیرفته میشود. علاوه بر بهنگام سازی جواب جاری بهترین جواب نیز در این قدم بهنگام میگردد. بدین منظور بعداز یافتن هر جواب جدید که منجر به بهبود جواب جاری گردد آن جواب، با بهترین جواب مقایسه میگردد. اگر از بهترین جوابی که تا بهحال پیدا شده بهتر باشد(f(x_(c^’ ) )≤f(x^*)) جایگزین جواب بهتر میگردد. ( f(x_(c^’ ) )→f(x^* )و x_(c^’ )→x^* ) این قدم ادامه می یابد تا زمانیکه زنجیره مارکف به انتها برسد یا بهعبارت دیگر تعداد مشخصی از جستجوها انجام شده باشد. معمولا برای این زنجیره یک طول معین مشخص شده و زمانیکه تعداد جستجو (شامل تمامی نقاط پذیرفته و رد شده) به طول مشخص شده برسد زنجیره پایان می یابد. در طول زنجیره دما ثابت میماند.
در قدم سوم، بعد از اتمام یک زنجیره، کاهش دما اتفاق خواهد افتاد. معمولا برای کاهش دما از یک ضریب ثابت α (1 α0) استفاده میگردد. رابطه کاهش دما در این حالت بصورتT * α = T تعریف میگردد.
در قدم چهارم، شرط توقف الگوریتم بررسی میگردد. در صورتیکه شرط توقف برآورده شود، الگوریتم متوقف و در غیر اینصورت به قدم دوم برمیگردد. شرط توقفهای مختلفی میتوان تعریف کرد. یک شرط توقف رایج، رسیدن دمای الگوریتم به یک دمای انتهایی ( دمای انجماد ، T_f) میباشد که بهصورت ( ≤ T_f T) تعریف میگردد.
2-2-6  انتخاب پارامترهای برنامه انجماد
برای بهکار بردن شبیهسازی تبرید جهت یک مساله خاص تعداد زیادی تصمیم باید گرفته شود. این تصمیمها را میتوان به دو گروه تقسیمبندی کرد، گروه اول تصمیمهای کلی که مرتبط با پارامترهای خود الگوریتم آنیل هستند که شامل عواملی از قبیل دمای اولیه، قاعده کاهش دما، زنجیره مارکف و قاعده توقف میباشد. گروه دوم تصمیم های مربوط به یک مساله خاص شامل انتخاب فضای جواب موجه، ساختار همسایگی و شکل تابع هزینه میباشد. هر دو گروه تصمیمها باید با دقت گرفته شوند و ثابت شده که موثر بر سرعت الگوریتم و کیفیت جوابهای بهدست آمده هستند.
2-2-6-1: دمای اولیه
تعیین دمای اولیه T_0 تاثیر زیادی در انتخاب کردن و یا انتخاب نکردن جابجاییها دارد و تاکنون روش دقیقی برای آن بهوجود نیامده است و معمولا برای هر مساله با مقادیر مختلف برای آن، الگوریتم شبیهسازی تبرید را اجرا میکنند. اگر T_0 (دمای اولیه) خیلی بزرگ باشد آنگاه e^((-∆ E)⁄T) نزدیک ۱ میشود و در نتیجه هر جابهجایی که تابع هدف را بهبود ندهد، نیز پذیرفته میشود. در واقع بالا بودن بیش از حد دمای اولیه، باعث اتلاف وقت در ابتدای الگوریتم میشود، زیرا احتمال پذیرش جوابهای با سطح انرژی بالاتر زیاد میشود که الگوریتم بهطور دائم بهصورت تصادفی از یک جواب به جواب دیگر میجهد. این عمل در حالت حدی، جواب ما را شبیه به جستجو به صورت کاملاً تصادفی میکند. حال اگر 〖 T〗_0 مقدار کوچکی داشته باشد، آنگاه انتخاب یا پذیرش جوابهای خیلی بد کاهش مییابد. در واقع پایین بودن بیش از حد دمای اولیه، باعث توقف در جوابهای محلی میشود، زیرا در ابتدای الگوریتم، اجازهی جستجو را از خود میگیریم و بهعبارت دیگر با اینکار احتمال پذیرش جواب با سطح انرژی بالا کمتر میشود و در نتیجه سرعت الگوریتم، بسیار کاهش مییابد. بنابراین برای جلوگیری از این مشکلات، دمای اولیه 〖 T〗_0 را نسبتا بزرگ انتخاب میکنیم و بعد از هر تکرار، آن را کاهش میدهیم. همچنین پایین بودن بیش از حد دمای نهایی، باعث اتلاف وقت در انتهای الگوریتم میشود. در واقع در انتهای الگوریتم، از یک دمای خاص کمتر، دیگر جوابهای جدید پیشرفت چندانی در پایین آوردن سطح انرژی نمیکنند.
سه استراتژی مهم در هنگام تنظیم این پارامتر وجود دارد:
1-پذیرش کلیه جوابها: در این حالت مقدار دمای اولیه به اندازهای بزرگ در نظر گرفته میشود که کلیهی جوابها در طول فاز اولیهای از الگوریتم پذیرفته میشود. مشکل اصلی هزینهی بالای محاسباتی در این روش است.
2-وابسته به انحراف معیار: در این استراتژی دمای اولیه برابر با kσ ، براساس یک سری آزمایشات اولیه، محاسبه میگردد. که در آن σ نشاندهنده انحراف معیار استاندارد توابع هدف جوابهای بهدست آمده در آزمایشات اولیه بوده و . k=(-3)⁄(ln⁡(p)) که احتمال پذیرش p مرتبط با ناحیه بیشتر از σ3 می باشند.
3-بر اساس نرخ پدیرش : در این استراتژی، دمای اولیه به نحوی تعیین میگردد که نرخ پذیرش جوابها بیشتر از یک مقدار از قبل تعیین شدهی 〖 a〗_0 باشد. در اینصورت دمای اولیه بر اساس رابطه زیر محاسبه میگردد:
T_0=∆^+/(ln⁡((m_1 (a_0-1))⁄m_2 +a_0))
که در آن پارامترهای 〖 m〗_2 وm_1معرف تعداد جوابهایی که در آزمایشات اولیه به ترتیب کاهش و افزایش داشتهاند و 〖 ∆〗^+ میانگین مقادیر تابع هدفی است که در آزمایشات اولیه افزایش داشته است. برای مثال میتوان گفت که دمای اولیه باید بهنحوی تنظیم گردد که نرخ پذیرش بین 40% تا 50% گردد.
2-2-6-2: قاعده کاهش دما
بهطورکلی، بین کیفیت نتایج و سرعت انجماد رابطه قوی وجود دارد. مقدار دما همواره مقدار مثبت بوده و زمانیکه تعداد تکرارها به سمت بینهایت میل کند، مقدار دما نیز به سمت صفر میل میکند. در مجموع در برنامه انجماد بایستی موازنهای بین تکرارهای زیاد با تعداد کم دماها یا تکرارهای کم همراه تعداد زیاد دماها انجام گردد.
در اینجا دو روش کاهش درجه حرارت که بهطور وسیعی در الگوریتم های SA بهکار میروند، ذکر می شود:
قاعده خطی: طبق این روش دما خیلی آهسته و طبق فرمول T_i=T_0-i*β  کاهش مییابد که β ضریب ثابتی بین 0 و 1 و i شماره مرحله کاهش دما است.
قاعده هندسی یا نمایی: روش دوم بهصورت T_(k+1)=α*T_k  معرفی میگردد و در آن α ضریب ثابتی بین 0 و1 میباشد. تجربه نشان داده است که مقادیر نسبتا بزرگ α بهترین نتیجه را دارد .
2-2-6-2: زنجیره مارکف  و وضعیت پایدار
زنجیره مارکف که به افتخار آندری مارکف ریاضیدان اهل روسیه این گونه نامگذاری شده، یک سیستم ریاضی است که در آن انتقال از یک حالت به حالت دیگر صورت می‌گیرد که البته تعداد این حالات قابل شمارش است. زنجیره مارکف یک فرایند تصادفی بدون حافظه ‌است بدین معنی که توزیع احتمال شرطی حالت بعد تنها به حالت فعلی بستگی دارد و به وقایع قبل از آن وابسته نیست. این نوع بدون حافظه بودن خاصیت مارکف نام دارد. .
برای رسیدن به یک وضعیت پایدار در هر دما، تعداد کافی از حرکتها باید در نظر گرفته شود. بهطورکلی تعداد این تکرارها باید مطابق با اندازه مساله و متناسب با همسایگی تعیین گردد و ممکن است برای دماهای مختلف متفاوت باشد. یک روش این است که تعداد تکرار ثابتی در هر دما داشته باشیم. روش دیگر این است که بهصورت پویا، تعداد تکرارها با پیشروی الگوریتم تغییر یابد. بهعنوان مثال مهم است که در دماهای پایینتر، زمان بیشتری صرف کنیم. بنابراین سودمند است که تعداد تکرارها در هر دما را بهصورت هندسی یا حسابی در هر دمای جدید افزایش دهیم.
2-2-6-3: قاعده توقف
در الگوریتم شبیهسازی تبرید، معمولاً یکی از این دو معیار برای شرط توقف استفاده شده است. یک معیار، رسیدن به درجه حرارت نهایی است. معیار دیگر، نسبت میزان پراکندگی جوابهای پذیرفته شده در درجه حرارت فعلی، به تفاوت متوسط مقادیر تابع هدف جوابهای پذیرفته شده در درجه حرارت اولیه و درجه حرارت فعلی است. در صورتیکه این نسبت کم باشد، گفته میشود سیستم به حالت انجماد رسیده است و الگوریتم متوقف میشود.
2-2-6-3 : تشکیل یک جواب اولیه
نحوه ایجاد جواب اولیه باید از ابتدا معلوم باشد. در بسیاری از مواقع جواب اولیه بهصورت تصادفی انتخاب میشود. در صورتیکه ساختار کد جواب ساده باشد، این کار بهسادگی انجام میگردد، اما در خیلی از مسائل بهدلیل پیچیدگی فضای جواب و نحوهی کدگذاری آن، ایجاد یک جواب اولیهی امکانپذیر بهصورت تصادفی، کار سادهای نیست. بههمین دلیل، در بعضی مواقع نیز بهمنظور افزایش کیفیت الگوریتم ، الگوریتم یا مراحلی طراحی میگردد تا منجر به ایجاد یک جواب اولیه با کیفیت نسبتا خوبی گردد. اینکار موجب کمک به الگوریتم اصلی در رسیدن به جوابهای بهتر میگردد.

2-2-6-4: ساختار حرکت
الگوریتم انجماد تدریجی جزو الگوریتم های جستجوی محلی محسوب میگردد. این الگوریتم جستجوی خود را بر اساس یک روند تقریبا تصادفی انجام میدهد.

فصل سوم
نتایج محاسبات

3-1 ارائهی مثالهای عددی
در این بخش چند مثال عددی را بهمنظور بررسی عملکرد مدل پیشنهادی و روش اکتشافی طراحی میکنیم. در ابتدا یک مثال پایه مانند مثال 1 را طراحی میکنیم و مثالهای دیگر با تغییر مقادیر پارامترهای انتخاب شده از مثال 1 بهدست میآید.
درمثال 1، فرض میکنیم سه تامینکننده با نمرات ارزیابی 80، 70 و90 از نمره کل 100 برای تامینکنندگان 1، 2 و 3 وجود دارد (یعنی w_1=80 ,w_2=70,w_3=90 ). این نمرات از یک سیستم ارزیابی اولیه مانند AHP بهدست میآید (انتخاب معيارها بخش اول تجزيه و تحليل AHP است. سپس براساس معيارهاي شناسائي شده کانديداها ارزيابي مي‌شوند). ما فرض میکنیم سه محصول سفارش داده شده، توسط تامینکنندهها، عرضه میشود. وزنهای تابع هدف یکسان فرض میشود. یعنیb_1=b_2=b_3=b_4=0.25. حداکثر درصد قابل قبول واحدهای مرجوع شده و حداکثر واحدهای با تاخیر تحویل شده از محصولات بهصورت زیر فرض میشود.
Q_1=0.08 ,Q_2=0.06 ,Q_3=0.05 و T_1=0.05 ,T_2=0.06 ,T_3=0.06
هزینه نگهداری بهازای هر محصول، بهصورت h_1=5 ,h_2=3,h_3=2 فرض میشود. جریمه هر واحد تقاضای

دسته بندی : No category

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