آنیل کردن شبیهسازی شده — بهینهسازی احتمالی
- سال
- 1983
- نوع
- Probabilistic metaheuristic / local search
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
آنیل کردن شبیهسازی شده یک فراابتکار جستجوی محلی احتمالی است که توسط کرکپاتریک، گلات و وکی در سال ۱۹۸۳ معرفی شد. این روش فرآیند آنیل کردن فیزیکی در متالورژی را مدلسازی میکند — که در آن یک ماده گرم شده و سپس به آرامی سرد میشود تا به حالت بلوری با انرژی پایین برسد — و از این قیاس برای فرار از بهینههای محلی در مسائل بهینهسازی ترکیبی و پیوسته استفاده میکند.
شهود پشت روش
تصور کنید که در حالی که چشمبند دارید، سعی میکنید پایینترین نقطه را در یک منظره تپهای پیدا کنید. یک جستجوی کاملاً حریصانه همیشه به سمت پایین حرکت میکند و در اولین درهای که پیدا میکند گیر میافتد — که ممکن است عمیقترین نباشد. آنیل کردن شبیهسازی شده تصادفی بودن کنترلشدهای را معرفی میکند: در ابتدا، زمانی که 'دما' بالا است، الگوریتم مایل است گاهی اوقات به سمت بالا حرکت کند و به طور تصادفی یک راهحل بدتر را بپذیرد. با کاهش دما طبق یک برنامه خنکسازی، الگوریتم به طور فزایندهای انتخابی میشود و به سمت یک راهحل همگرا میشود. این تمایل به پذیرش حرکات بدتر در دمای بالا همان چیزی است که به روش اجازه میدهد از بهینههای محلی کمعمق فرار کند و منظره را به طور کاملتری کاوش کند.
تاریخ
آنیل کردن شبیهسازی شده توسط کرکپاتریک، گلات و وکی در مقاله برجسته سال ۱۹۸۳ آنها در ساینس معرفی شد، که قیاس صریحی بین آنیل کردن ترمودینامیکی جامدات و بهینهسازی ترکیبی برقرار کرد. همین ایده به طور مستقل توسط چرنی (۱۹۸۵) در زمینه مسئله فروشنده دورهگرد مطرح شد. ون لاروهون و آرتس (۱۹۸۷) اولین درمان نظری دقیق را ارائه دادند و خواص همگرایی را تحت برنامههای خنکسازی مختلف اثبات کردند. از آن زمان، این روش به یکی از پرمطالعهترین و پرکاربردترین فراابتکارها تبدیل شده است و در طراحی مهندسی، تحقیق در عملیات، چیدمان VLSI، و تنظیم ابرپارامترهای یادگیری ماشین استفاده میشود.
چه زمانی استفاده شود
آنیل کردن شبیهسازی شده برای هر مسئلهای که بتوان ساختار همسایگی را بر فضای راهحل تعریف کرد، قابل اجرا است، صرف نظر از اینکه تابع هدف قابل مشتقگیری، محدب، یا حتی قابل بیان تحلیلی باشد. این روش به ویژه برای مسائل ترکیبی (زمانبندی، مسیریابی، مسائل گراف) و بهینهسازی جعبه سیاه پیوسته مناسب است. هیچ داده آموزشی یا فرض نرمالیتی لازم نیست. برنامه خنکسازی و ساختار همسایگی باید برای مسئله تنظیم شوند؛ اجرای کمتر از حدود ۱۰۰۰ تکرار، خطر همگرایی زودهنگام به یک بهینه محلی را دارد، در این صورت باید جستجوی محلی قطعی سادهتری ترجیح داده شود.
محدودیتها و ملاحظات
- کیفیت راهحل به برنامه خنکسازی حساس است؛ یک برنامه ضعیف میتواند نتایجی بهتر از جستجوی تصادفی به دست ندهد.
- ساختار همسایگی باید برای هر کلاس مسئله طراحی شود که نیازمند تخصص دامنه است.
- همگرایی به بهینه سراسری در عمل نیازمند خنکسازی بسیار آهسته است و زمان اجرا را برای تضمینهای کیفیت بالا طولانی میکند.
- از اطلاعات گرادیان یا ساختاری استفاده نمیکند، بنابراین روشهای مبتنی بر گرادیان در مسائل هموار و قابل مشتقگیری از آن بهتر عمل میکنند.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- میتواند از بهینههای محلی از طریق پذیرش احتمالی راهحلهای بدتر فرار کند، برخلاف صعود از تپه خالص.
- برای تقریباً هر نوع مسئلهای — ترکیبی، پیوسته، مختلط — تا زمانی که ساختار همسایگی تعریف شده باشد، کاربرد دارد.
- به اطلاعات گرادیان نیاز ندارد و نسبت به ساختار ریاضی تابع هدف بیتفاوت است.
- دارای تضمین نظری همگرایی به بهینه سراسری تحت خنکسازی به اندازه کافی آهسته (هاژک ۱۹۸۸) است.
- هایپرپارامترهای کمی: دمای اولیه، نرخ خنکسازی، و ساختار همسایگی.
کاربردها
- مسائل زمانبندی و جدولبندی ترکیبی که فضای راهحل برای جستجوی جامع خیلی بزرگ است.
- مسائل فروشنده دورهگرد و مسیریابی وسایل نقلیه در لجستیک و تحقیق در عملیات.
- چیدمان مدار VLSI و برنامهریزی کف تراشه در مهندسی برق.
- تاخوردگی پروتئین و مسائل ساختار مولکولی در زیستشناسی محاسباتی.
- بهینهسازی ابرپارامترها برای مدلهای یادگیری ماشین زمانی که اطلاعات گرادیان در دسترس نیست.
- مسائل تخصیص منابع و انتساب در مهندسی و علوم مدیریت.
چگونه کار میکند
چگونه کار میکند
الگوریتم با یک راهحل اولیه — هر نقطه قابل قبولی در فضای جستجو — و یک دمای اولیه بالا آغاز میشود. راهحل اولیه میتواند تصادفی یا خاص مسئله باشد؛ دمای اولیه معمولاً به اندازهای بالا تنظیم میشود که تقریباً هر راهحل همسایه در ابتدا پذیرفته شود.
یک راهحل همسایه با اعمال یک تغییر تصادفی کوچک (یک 'حرکت') به راهحل فعلی تولید میشود. ساختار همسایگی باید متناسب با مسئله باشد: برای یک مسئله زمانبندی، یک حرکت ممکن است دو وظیفه را جابجا کند؛ برای یک تابع پیوسته، ممکن است یک اغتشاش تصادفی کوچک به بردار پارامتر فعلی اضافه کند.
اختلاف در مقدار هدف بین راهحل جدید و فعلی محاسبه میشود. اگر راهحل جدید بهتر باشد، همیشه پذیرفته میشود. اگر بدتر باشد، با احتمالی پذیرفته میشود که با اندازه وخامت و دمای فعلی کاهش مییابد — معمولاً exp(−ΔE / T). این پذیرش احتمالی مکانیزم اصلی است که از همگرایی زودهنگام جلوگیری میکند.
پس از هر تکرار (یا پس از تعداد ثابتی حرکت در همان دما)، دما طبق یک برنامه خنکسازی کاهش مییابد — معمولاً یک برنامه هندسی T ← α·T که در آن α کمی کمتر از ۱ است. انتخاب برنامه خنکسازی به شدت بر کیفیت راهحل تأثیر میگذارد: خنکسازی خیلی سریع، جستجو را در یک بهینه محلی به دام میاندازد؛ خنکسازی خیلی آهسته، زمان محاسباتی را تلف میکند.
الگوریتم زمانی متوقف میشود که دما به زیر یک آستانه حداقل برسد، حداکثر تعداد تکرارها به دست آید، یا راهحل برای تعداد مشخصی مرحله بهبود نیافته باشد. بهترین راهحل مشاهده شده در طول کل اجرا — نه فقط حالت نهایی — به عنوان نتیجه بازگردانده میشود.
دامهای رایج
- اجرای تکرارهای خیلی کم (تقریباً کمتر از ۱۰۰۰) مانع عملکرد صحیح برنامه خنکسازی میشود و جستجو را در یک بهینه محلی به دام میاندازد — اگر زمان اجرا به شدت محدود است، جستجوی تابو یا جستجوی محلی قطعی را ترجیح دهید.
- تنظیم دمای اولیه خیلی پایین به این معنی است که الگوریتم بلافاصله مانند صعود از تپه حریصانه عمل میکند و توانایی خود را برای فرار از بهینههای محلی از دست میدهد.
- تنظیم نرخ خنکسازی خیلی تهاجمی (مثلاً α کمتر از ۰.۹) باعث همگرایی زودهنگام میشود؛ کیفیت راهحل نهایی را با شروع مجدد از چندین راهحل اولیه تأیید کنید.
- اعمال یک حرکت همسایگی که برای یک نوع مسئله طراحی شده است به مسئلهای متفاوت میتواند حرکات را غیرممکن یا بیمعنی کند — همیشه تأیید کنید که هر همسایه تولید شده یک راهحل معتبر است.
- گزارش فقط حالت نهایی به جای بهترین راهحل مشاهده شده در طول اجرا میتواند بهینه واقعی یافت شده در یک مرحله میانی را از دست بدهد.
پرسشهای متداول
چگونه برنامه خنکسازی را انتخاب کنم؟
برنامه هندسی T ← α·T با α بین ۰.۹۰ و ۰.۹۹ رایجترین نقطه شروع است. یک رویکرد عملی این است که دمای اولیه را به اندازهای بالا تنظیم کنید که تقریباً ۸۰٪ حرکات در ابتدا پذیرفته شوند، سپس آن را کاهش دهید تا زمانی که کمتر از ۱٪ حرکات رو به بالا پذیرفته شوند. اگر کیفیت راهحل نهایی ضعیف است، نرخ خنکسازی را کند کنید (α را افزایش دهید)؛ اگر زمان اجرا خیلی طولانی است، آن را سریعتر کنید. همیشه الگوریتم را چندین بار از راهحلهای اولیه متفاوت اجرا کنید تا استحکام آن ارزیابی شود.
آنیل کردن شبیهسازی شده چگونه با الگوریتمهای ژنتیک یا بهینهسازی ازدحام ذرات تفاوت دارد؟
آنیل کردن شبیهسازی شده یک راهحل واحد را حفظ میکند و همسایگی را از طریق اغتشاشات تصادفی کاوش میکند و راهحلهای بدتر را به صورت احتمالی میپذیرد. الگوریتمهای ژنتیک و بهینهسازی ازدحام ذرات مجموعهای از راهحلها را حفظ میکنند و از تقاطع، جهش یا حرکت ازدحام برای تکامل جمعیت استفاده میکنند. آنیل کردن شبیهسازی شده به طور کلی برای مسائلی با ساختار همسایگی طبیعی سادهتر است، در حالی که روشهای مبتنی بر جمعیت میتوانند برای مسائل پیوسته با ابعاد بالا مؤثرتر باشند.
آیا بهینه سراسری تضمین شده است؟
از نظر تئوری بله، تحت این شرط که دما به اندازه کافی آهسته کاهش یابد (خنکسازی لگاریتمی). در عمل، چنین خنکسازی از نظر محاسباتی غیرممکن است، بنابراین الگوریتم یک راهحل تقریباً بهینه پیدا میکند. کیفیت نتیجه با خنکسازی آهستهتر و تکرارهای بیشتر بهبود مییابد، اما تضمین زمان محدود وجود ندارد. اجرای چندین راهاندازی مجدد و نگهداری بهترین راهحل یافت شده، راهی عملی برای افزایش اطمینان است.
چه زمانی باید جستجوی تابو یا الگوریتم ژنتیک را ترجیح دهم؟
جستجوی تابو را زمانی انتخاب کنید که به یک جستجوی قطعی و هدایت شده با حافظه نیاز دارید که از بازدید مجدد راهحلهای اخیر اجتناب میکند و میتواند ساختار مسئله را به طور مؤثر در یک اجرای کوتاهتر بهرهبرداری کند. الگوریتم ژنتیک یا بهینهسازی ازدحام ذرات را زمانی انتخاب کنید که مسئله با ابعاد بالا و پیوسته باشد، یا زمانی که مجموعهای از راهحلهای متنوع برای ترسیم منظره بهینه مورد نیاز است. آنیل کردن شبیهسازی شده یک گزینه پیشفرض قوی برای مسائل ترکیبی با ساختار همسایگی واضح و زمانی که سادگی پیادهسازی مهم است، میباشد.
روشهای مرتبط
منابع
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
باز کردن مرجع DOIکپی شد.van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.
شابک: 9789027725431کپی شد.