۴-۲-۲ برنامه سرد سازی

 

برنامه سرد سازی شامل پارامترهایی است که نحوه سرد کردن الگوریتم را مشخص می‌کنند. مهمترین پارامترهای برنامه سرد سازی درجه حرارت آغازین^[۶۵] و نرخ کاهش درجه حرارت در هر مرحله ^[۶۶]می‌باشند. این پارامترها نقش مؤثری در همگرایی الگوریتم به جواب بهینه، ایفا می‌کنند. بدین منظور نحوه تعیین پارامترهای فوق به طور مختصر توضیح داده می‌شوند.

 

۴-۲-۳ درجه حرارت آغازین ()

 

درجه حرارت آغازین باید به اندازه کافی گرم باشد تا حرکت به همه ی حالت های مجاور را اجازه دهد. اگر درجه حرارت آغازین خیلی زیاد باشد، جستجو می‌تواند به هر همسایگی حرکت کند و جستجو به جستجوی تصادفی تبدیل می شود. این جستجوی تصادفی ادامه می‌یابد تا زمانی که دما به اندازه ی کافی کاهش یابد. مقادیر بسیار بزرگ موجب طولانی شدن مدت زمان اجرای الگوریتم و گسترش نقاط جستجو می‌باشد و مقادیر بسیار کوچک آن ممکن است موجب همگرایی زود هنگام شده و الگوریتم در بهینه ی محلی متوقف شود.

 

۴-۲-۴ دمای پایانی

 

به طور معمول اجازه داده می شود تا دما کاهش یابد و به صفر برسد. با ابن حال، این موضوع می‌تواند اجرای الگوریتم را خیلی طولانی کند. در عمل خیلی مهم نیست که اجازه داده شود تا دما به صفر برسد، زیرا با نزدیک شدن به صفر، احتمال پذیرش حرکت اشتباه، غالبا با زمانی که دما مساوی صفر شود، یکی خواهد بود. ‌بنابرین‏ شرط توقف می‌تواند یک دمای پایین مناسب باشد.

 

۴-۲-۵ کاهش دما

 

نرخ کاهش پارامتر دما برای موفقیت هر فرایند SA ، حیاتی است. از نظر تئوری پیشنهاد می شود که باید اجازه دهیم تا سیستم در دمای فعلی خود و قبل از کاهش دما، به توزیع ایستای خود خیلی نزدیک گردد و باید دما کم کم به صفر نزدیک شود. برای رسیدن ‌به این منظور تعداد تکرار در هر دما نسبت به اندازه ی مسئله، نمایی خواهد بود که به معنی زمان محاسباتی غیرقابل قبول است. لذا کاهش تعداد تکرارها اجتناب ناپذیر است. ‌بنابرین‏ می توان از تعداد تکرارهای زیاد در تعداد کمی دما، یا تعداد کمی تکرار در تعداد زیادی دما استفاده کرد و یا یک توازن بین هر دوی آن ها ایجاد کرد. به طور کلی شش روش عمده برای زمان بندی سرد شدن مورد استفاده قرار می‌گیرد که پر کاربردترین آن ها شامل یک تابع کاهش هندسی به صورت است .

 

تجربه نشان داده است که مقادیر نسبتا بزرگ αبهترین نتیجه را دارد و اکثر موفقیت های گزارش شده از مقادیر بین و استفاده کرده‌اند .

 

۴-۲-۶ تعداد تکرار در هر دما

 

تعداد تکرار در هر دما معمولا مرتبط با اندازه همسایگی یا گاهی فضای جواب است و ممکن است برای دماهای مختلف متفاوت باشد. یک روش این است که تعداد تکرار ثابتی در هر دما داشته باشیم.

 

روش دیگر این است که به صورت پویا تعداد تکرارها، با پیشروی الگوریتم تغییر یابد. به عنوان مثال مهم است که در دماهای پایین تر، زمان بیشتری صرف کنیم .[۵۶]

 

۴-۳ شرح کلی رو ش حل ابتکاری

 

همان طور که گفته شد، الگوریتم حل ابتکاری از دو مرحله تشکیل شده است. در مرحله ی اول که در بخش ۴-۴ به تشریح آن خواهیم پرداخت، هدف یافتن بهترین نحوه توزیع آمبولانس ها در مراکز و تخصیص بیماران به بیمارستان ها و مراکز در هریک از دوره های زمانی است.

 

پس از پایان مرحله ی اول و یافتن بهترین نحوه توزیع آمبولانس ها در هریک از دور ه های زمانی، در ادامه و در مرحله ی دوم با بهره گرفتن از الگوریتمی که در بخش ۴-۵ معرفی خواهد شد سعی در یافتن نحوه بازآرایی مناسب برای آمبولان سها در دوره های زمانی متوالی خواهیم داشت. در شکل ۴-۱ مراحل کلی الگوریتم ارائه شده مشاهده می شود.

 

شــروع

 

تعیین پارامترهای مسئله و الگوریتم

 

دور اول را در نظر می گیریمt=1) (

 

با بهره گرفتن از الگوریتمSA1 وSA2 بهترین نحوه تخصیص توزیع آمبولانسها و تخصیص بیماران را برای دوره Tمی یابیم

 

آیا تمامی دوره ها بررسی شده ؟

 

با بهره گرفتن از الگوریتم حریصانه نحوه بازارایی تعیین می‌گردد.

 

پایان

 

t=t+1

 

 

 

شکل ۴-۱ فلوچارت الگوریتم ابتکاری ارائه شده

 

۴-۴ مرحله ی اول: توزیع آمبولانس ها و تخصیص بیماران در هر دوره

 

‌به این منظور اقدام به تعریف دو الگوریتم شبیه سازی تبرید ( SA2و ۱ SA) نمودیم که الگوریتم SA2 به عنوان یک زیرالگوریتم در SA1 اجرا می شود. پارامترهای الگوریتم اول را با α۱ و L1 ،T1 و پارامترهای الگوریتم دوم را با α۲ و L2 ،T2 نشان می‌دهیم.

 

در ادامه ابتدا به شرح الگوریتم SA1 و پس از آن الگوریتم SA2 را توضیح می‌دهیم.

 

۱-۴-۴ الگوریتم SA1

 

هدف از اجرای الگوریتم SA1 یافتن بهترین نحوه توزیع آمبولانس در بین مراکز EMS در دوره زمانی فعلی است. مراحل اجرای این الگوریتم در شکل ۴-۲ آمده است.

 

جواب اولیه

 

در ابتدا می بایست یک جواب اولیه برای این الگوریتم ارائه دهیم. ‌به این منظور گام های زیر را انجام می‌دهیم. گام اول: برای هر مرکز خدمات فوریت های پزشکی، شاخص ، DH1(j) که این شاخص بیان گر اولویت مراکز EMS برای دریافت آمبولانس می‌باشد، تعریف می شود. این شاخص حداقل مقدار میان دو مقدار زیر است:

 

*مجموع تقاضاهای موجود در دوره که در فاصله ی زمانی از این EMS قرار دارند و می بایست به بیمارستان منتقل شوند.

 

* مجموع ظرفیت بیمارستان هایی که با این مرکز در ارتباط هستند.

 

تعیین پارامترهای برنامه برای الگوریتم (تعداد تکرار در هر دما فاکتور خنک سازی و دمای پایانی )

 

جواب اولیه آمبولانس ها بین مراکز را به دست آورید و با بهره گرفتن از الگوریتم SA2 تابع هدف آن را محاسبه کنید

 

جواب جدید را با توجه به ساختار همسایگی ایجاد کنید و با بهره گرفتن از SA2 تابع هدف آن را محاسبه کنید

 

تفاوت تابع هدف جواب جدید قبلی ∆Fرا محاسبه کنید

 

∆F>0

 

به هنگام سازی مقادیر بهترین جواب و بهترین تابع هدف

 

جواب پذیرفته می شود

 

آیا به اندازه کافی L2 در دمای فعلی جستجو شده است ؟

 

دمای پایانی؟

 

محاسبه احتمال

 

کاهش نما یا برنامه نیرید

 

پایان الگوریتم

 

خیر

 

پذیرفته می شود ؟

 

بله

 

خیر

 

بله

 

شکل ۴-۲ فلوچارت الگاریتم SA1

 

خیر

 

بله

 

پس از تعیین این شاخص، گام های دوم و سوم را تا زمانی که تمامی آمبولانس ها به مراکز EMS تخصیص یابند، ادامه می‌دهیم.

 

گام دوم: با بهره گرفتن از تکنیک چرخ رولت^[۶۷] که مقادیر آن بر اساس شاخص DH1(j) محاسبه شده اند، یکی از مراکز EMS را انتخاب می‌کنیم.