منبع پایان نامه ارشد با موضوع محدودیت زمانی و تصمیمگیری


Widget not in any sidebars

در واقع ایدهی اصلی، از آنجا نشأت میگیرد که انتخاب یک جواب بد، ممکن است منجر به جوابی بهتر از یک انتخاب تصادفی خوب گردد. در سیستمی که از حافظه استفاده میکند یک انتخاب بد ممکن است راهنمای مفیدتری برای چگونگی تغییر جواب به صورت مفید باشد. برای جلوگیری از قرارگرفتن در جوابهای بهینهی محلی و پیدا کردن جواب بهینهی سراسری، در این روش حرکت در فضای جواب فقط به پاسخهای بهتـر محـدود نمیشود، بلکـه در بین همسایگیهای بهدست آمده، بهترین جواب از نظر حداقل کردن تابع هدف انتخاب می شود. سپس این جواب که در بین همسایگیهای نقطه شروع شرایط بهتری نسبت به سایر جوابها دارد، بهعنوان نقطهی شروع برای مرحلهی بعدی در نظر گرفته میشود و این عملیات مجدداً تکرار میشود. به این نکته باید توجه کرد که ممکن است نقطهی انتخابی از نقطهی شروع در هر مرحله بهتر نباشد. علاوه بر این، جهت جلوگیری از جوابهای تکراری و قرار نگرفتن الگوریتم در یک حلقهی بسته، حرکت انتخابی در لیست حرکتهای ممنوع قرار میگیرد. این فرآیند، به یک جواب بهینهی نسبی منتهی میگردد. همچنین، بایستی توجه داشت بهمنظور اینکه الگوریتم در یک نقطهی بهینه نسبی متوقف نگردد، هر حرکت ممنوع بعد از چند مرحله تکرار دوباره مجاز میگردد یا اینکه با در نظر گرفتن ماهیت مسأله، فضای جستجو تغییر داده میشود. با تکرار این دو فرآیند در نهایت الگوریتم به جواب بهینه مطلق، همگرا میگردد [45].
3-3-5- الگوریتم آبکاری فولاد
در سال 1983 کریک پاتریک با شبیهسازی بین حداقل نمودن تابع هدف یک مسأله و سرد کردن جسم تا زمان رسیدن آن به حالت انرژی پایه، الگوریتم شبیهسازی سرد شدن را بهوجود آورد.
واژهی آنیلینگ به معنای گرم کردن جسم میباشد ولی در اصطلاح یک فرآیند فیزیکی برای بالا بردن دمای جسم تا رسیدن به نقطهی ذوب میباشد و سپس به تدریج سرد کردن تا انرژی جسم به حداقل برسد. سیمولیتد نیز در لغت به معنی شبیهسازی کردن و در اصطلاح بازسازی رفتار یک فرآیند با توجه به یک سری فرضیات با اطلاعات معلوم یا فرضی است.
در ابتدا یک نقطهی دلخواه از فضای جستجو به طور تصادفی انتخاب و تابع هدف در آن محاسبه میشود. لازم به ذکر است که جواب اولیـه جزء پارامتـرهای مهم این الگوریتـم میباشد که نقش بهسزایی را ایفا مینماید و بسته به نوع مسأله تغیر میکند. همچنین، مکانیزم ایجاد همسایگی، پارامتر مهمی میباشد که در رسیدن به جواب بهینه بسیار مؤثر خواهد بود. بعد از انتخاب این دو پارامتر، به سیستم یک دمای اولیه، متناظر با انرژی جنبشی نسبت داده میشود. انتخاب مقدار دمای اولیه دلخواه است اما بسته به اینکه تابع در نقطهی شروع چه رفتاری دارد انتخاب میگردد؛ مثلاً اگر تابع دارای تغییرات کمی است دمای کمتر انتخاب میگردد تا قابلیت تحرک کمتر باشد و اگر تابع دارای تغییرات زیاد (شیب تند) باشد دمای بیشتری در نظر گرفته میشود تا امکان حرکت و خارج شدن از مینیممهای محلی بیشتر شود. سپس یک نقطه از فضای اطراف بهعنوان گزینه برای قدم بعدی انتخاب میگردد. این نحوهی انتخاب بستگی به مسأله دارد. برای حرکت به سمت نقطهی جدید اینگونه تصمیمگیری خواهد شد، اگر جواب بهتر شد حرکت ادامه یابد و اگر نه با احتمالبه سمت نقطهی جدید برود. احتمالبا توجه به دمای سیستم و تغییر در اندازهی تابع هدف و اختلاف بین نقطهی مبدأ و مقصد انتخاب میشود. برای احتمال ذکر شده، اغلب از دو تابع مختلف استفاده میگردد، این توابع عبارتند از:
الف) تابع متروپلیس
(3-5)
ب) تابع بولتزمن
(3-6)
در این رابطه عددی ثابت است که در اغلب مسایل 1 در نظر گرفته میشود. به ، دمای محیط میگویند و همان طور که دیده میشود کاملاً مانند دمای محیط در عمل آنیلینگ جسم جامد کار میکند. کمیت، در ابتدای مسئله برابر مقدار خاصی در نظر گرفته میشود و سپس بهتدریج در ادامهی مسئله کاهش مییابد. بدین صورتکه با کاهش احتمال پذیرش جوابهایی که تابع هدف را زیاد میکنند؛ کم میشود. الگوریتم چند بار در دمای تکرار شده، سپس از دمای محیط کاسته میشود. معمولاً مسایل کاهش دما با رابطه 7- 3 نمایش داده میشود. که بیانگر سرعت سرد کردن است و شمارندهی تکرار می باشد.
(3-7)
در نهایت، الگوریتم تا آنجا ادامه مییابد که به شرایط نهایی(عدم پیشرفت، محدودیت زمانی، محدودیت تکرار الگوریتم) برسد[46]،[47].
3-3-6- الگوریتم خفاش
خفاش تنها پستانداری است که توانایی پرواز دارد و از قابلیت پژواک echolocation برخوردار است. آنها حدود بیست درصد از گونههای پستانداران را تشکیل میدهند و شامل 996 گونه متفاوت هستند. اغلب آنها این قابلیت را با درجهی مشخصی استفاده میکنند. در این میان میکرو خفاشها مشهورترین گونهای هستند که بهطور وسیعی از این قابلیت به منظور شناسایی شکار، اجتناب از برخورد با موانع و یافتن شکاف محل خواب در تاریکی استفاده میکنند.
این خفاشها پالسهای صوتی با فرکانس پایین ساطع کرده و منتظر انعکاس آن از اشیاء اطراف میمانند. پالسها از نظر ویژگی با یکدیگر متفاوت میباشند و این مسأله به گونهی آنها بستگی دارد. بسیاری از خفاشها از سیگنالهای کوتاه و با فرکانسهای متفاوت استفاده میکنند تا در اطرف یک اکتاو حرکت کنند. در حالی که بقیه از سیگنالهایی با فرکانس ثابت برای echolocation استفاده میکنند. پهنای باند سیگنال با توجه به گونهی آنها تغییر میکند و اغلب با استفاده از هارمونیکهای بیشتر افزایش مییابد.
شکل 3- 5 استفاده از پژواک برای پیدا کردن شکار توسط یک خفاش
برای ساده تر شدن کار از فرضیات زیر استفاده میشود:
تمامی خفاشها از Echolocation برای تشخیص فاصله استفاده میکنند و همچنین آنها تفاوت بین غذا و شکار و موانع را میتوانند تشخیص دهند.
خفاشها بهطور تصادفی از سرعت vi در موقعیتxi با فرکانس fmin ، طول موج متغیرλ و بلندی صداA0 برای جستجوی شکار استفاده میکنند. آنها بهطور اتوماتیک می توانند طول موج یا فرکانس پالسهای ساطع شده و نرخ ساطع شدن پالس r را بر حسب میزان نزدیکی به شکار تنظیم کنند.
فرض میشود بلندی صدا از مقدار مثبت بزرگ A0 تا مقدار ثابت حداقل Amin تغییر میکند.
فرکانس در بازه [0,fmax] در نظر گرفته میشود. فرکانسهای بالاتر طول موج کمتری دارند و مسیر کوتاهتری را طی میکنند. برای خفاشها، بازهی نوعی حدود چند متر است. نرخ ارسال پالس یا r نیز در بازهی[0,1] قرار دارد که در آن یک، ماکزیمم نرخ ارسال پالس را نشان میدهد.
علاوه بر فرضیات ذکر شده، میتوان به جای استفاده از طول موج، فرکانس را تغییر داد و λ را ثابت فرض کرد زیرا حاصلضرب fλ ثابت است. شبه کد این الگوریتم در شکل زیر آورده شده است.
________________________________________________________
Objective function f(x),x=(x1,…,xd)T