الگوریتم انجماد تدریجی

درس 16: الگوریتم انجماد تدریجی

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

مقدمه

محاسبه راه حل بهینه یا Optimal solution برای اکثر مسایل بهینه سازی که در خیلی از زمینه‌های کاربردی و عملی مشاهده می‌گردند، کار دشوار و سختی است. در عمل، معمولا به راه حل‌های خوب که از الگوریتم‌های هیوریستیک Heuristic یا متاهیوریستیک (همان فراابتکاری) Metaheuristic بدست می‌آید، اکتفا می‌گردد. متاهیوریستیک‌ها مجموعه ای از فنون بهینه سازی تقریبی Approximate optimization techniques را که عمدتا در طول دو دهه گذشته شهرت پیدا کرده اند، در بر می‌گیرند. روش‌های فراابتکاری راه حل‌های قابل قبول در زمان معقول را برای مسایل پیچیده و سخت، در زمینه‌های مهندسی و علوم پایه ارایه می نمایند. برخلاف الگوریتم‌های بهینه سازی دقیق Exact optimization algorithms ، فراابتکاری‌ ها بهینه بودن جواب‌های بدست آمده را ضمانت نمی نمایند.الگوریتم انجماد تدریجی

کلمه متاهیوریستیک از کلمه یونانی “Heuriskein” به معنای هنر کشف قواعد جدید برای حل مسایل گرفته شده است. پیشوند “متا” نیز از یک کلمه یونانی به معنای “متدولوژی” سطح بالا گرفته شده است. واژه ” متاهیوریستیک ” اولین بار توسط گلوور در سال 1986 ارایه گردید. روش جستجوی متاهیوریستیک را می توان به صورت متدولوژی‌های عمومی سطح بالایی که می توانند به عنوان یک استراتژی راهنما در طراحی هیورستیک‌های اختصاصی برای حل مسایل بهینه سازی تخصصی به کار روند، تعریف کرد.

برخلاف روش‌های دقیق، متاهیوریستیک‌ها (فراابتکاری‌‌ها) برای مسایل با اندازه‌های بزرگ کاربرد دشوار دارد و راه حل‌هایی راضی کننده ای در زمان معقولی ارایه می نمایند. در این الگوریتم‌ها، هیچ گونه ضمانتی برای یافتن جواب بهینه سراسری یا حدودی از آن وجود ندارد. متاهیوریستیک‌ها (فراابتکاری‌‌ها) در طول بیست سال گذشته شهرت زیادی پیدا کرده اند. کاربرد و استفاده از آن‌ها در خیلی از مسایل، کارایی و اثر بخشی آن‌ها را برای حل مسایل پیچیده و بزرگ نشان می دهد. فراابتکاری‌ها در خیلی از زمینه‌ها از قبیل موارد زیر کاربرد دارند:

• طراحی مهندسی، بهینه سازی توپولوژی، بهینه سازی مسایل الکترونیک، آئرودینامیک، دینامک سیالات، مخابرات، رباتیک
• یادگیری ماشین و کاوش داده‌ها
• مدل سازی سیستم‌ها، شبیه سازی و تحقیق در شیمی، فیزیک، بیولوژی، کنترل، سیگنال، و پردازش تصویر
• مسایل مسیردهی و برنامه ریزی، برنامه ریزی ربات، مسایل تولید و زمان بندی، حمل و نقل و لجستیک، مدیریت زنجیره تامین

روش‌های مختلف الگوریتم‌های فراابتکاری یا متاهیوریستیک تا به حال پیشنهاد شده است که به صورت زیر است:

• بهینه سازی کلونی مورچگان Ant colony optimization
• بهینه سازی کلونی زنبوران Bee colony
• الگوریتم‌های ترتیبی cultural algorithms
• الگوریتم‌های با هم تکاملی Co-evolutionary algorithms
• الگوریتم ژنتیک Genetic algorithm
• جستجوی محلی تکراری Iterated local search
• بهینه سازی توده ذرات particle swarm intelligent
• انجماد تدریجی Simulated Annealing
• جستجوی ممنوع Taboo search
• جستجوی همسایگی متغیر Variable neighboar search

در طراحی یک فراابتکاری‌، دو معیار متناقض شامل کاوش (Exploration) و در فضای جستجو (گوناگونی و تنوع) و تبعیت (Exploitation) از بهترین راه حل‌های پیدا شده، باید در نظر گرفته شوند. در کاوش در ناحیه‌های جستجو نشده بررسی صورت می‌گیرد. در تبعیت، در ناحیه‌های امید بخش که تا به حال در آن ناحیه یک جواب خوب پیدا شده است بررسی بیشتر صورت می‌گیرد. در صورتیکه به کاوش اهمیت بیشتری داده شود، الگوریتم رفتار تصادفی بیشتری خواهد داشت و به سمت رفتار تصادفی میل می کند و در صورتی که به رفتار تبعیت توجه بیشتری شود، الگوریتم از رفتار تصادفی فاصله می‌گیرد و جستجو تنها در محدوده راه حل‌های خوب به جستجو می پردازد.

معیار‌های طبقه بندی زیادی ممکن است برای طبقه بندی فراابتکاری‌‌ها استفاده شود که در زیر به بعضی از آن‌ها اشاره می‌شود:

الهام گرفته از طبیعت در مقابل عدم الهام از طبیعت

خیلی از الگوریتم‌های فراابتکاری از فراینده‌های طبیعی الهام گرفته شده اند: از قبیل الگوریتم‌های اجتماع مورچگان و زنبور عسل که از هوش توده ای از گونه‌های مختلف مورچگان و زنبوران استفاده می کنند.

نحوه استفاده از حافظه

بعضی از الگوریتم‌های فراابتکاری از قبیل انجماد تدریجی بدون حافظه هستند و حرکت‌های قبلی را در جایی ذخیره نمی کنند. در مقابل الگوریتم انجماد تدریجی از یک حافظه که بعضی از اطلاعات را در طول جستجو بدست می‌آورد، ذخیره می کند.

قطعی در مقابل احتمالی

یک الگوریتم قطعی، یک مسئله بهینه سازی را از طریق تصمیم گیری قطعی حل می نماید(برای مثال الگوریتم جستجوی محلی و جستجوی ممنوع). در الگوریتم‌های فراابتکاری احتمالی، بعضی از قواعد احتمالی در فرایند جستجو مورد استفاده قرار می‌گیرد که می توان به الگوریتم انجماد تدریجی و الگوریتم ژنتیک اشاره کرد. در الگوریتم‌های قطعی، با داشتن یک راه حل اولیه و اجراهای متفاوت، تنها یک جواب نهایی بدست می‌آید و در حالی که در الگوریتم‌های تصادفی، با داشتن یک راه حل اولیه و اجرا‌های متفاوت، ممکن است که جواب‌های نهایی متفاوتی بدست آید.

تکراری در مقابل حریصانه

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

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

معرفی الگوریتم انجماد تدریجی

الگوریتم انجماد تدریجی یا الگوریتم گرم و سرد کردن شبیه سازی شده یا الگوریتم تبرید شبیه‌ سازی‌ شده یا الگوریتم شبیه سازی تبرید، یک روش تصادفی است که مکانیزم آماری جهت یافتن جواب مسایل بهینه سازی استفاده می کند. این الگوریتم که به اختصار با SA یا Simulate Annealing نمایش داده می شود بر مبنای دو قاعده از فیزیک آماری عمل می نماید.

قاعده اول بر این اساس است که وقتی تعادل ترمودینامیکی به یک دمای مشخص رسید، احتمال یک سیستم فیزیک برای داشتن سطح انرژی E با فاکتور بالتزمن Boltzmann Factor که رابطه آن به صورت زیر است:

که در آن k_B توزیع بالتزمن در دمای مربوطه باشد، متناسب است. براساس این قاعده، احتمال پذیرش جواب ها در دماهای مختلف متفاوت بوده و متناسب با تابع معرفی شده می باشد.

قاعده دوم نحوه رسیدن به تعادل ترمودینامیکی در یک دمای مشخص را بیان می کند. اگر یک تغییر شکل منجر به افزایش تابع هدف یا انرژی به اندازه ΔE بشود، این تغییر با احتمال فاکتور بالتزمن پذیرفته می شود. این پذیرش از طریق تولید یک عدد تصادفی با توزیع یکنواخت در فاصله بین 0 و یک و مقایسه آن با تابع تعریف شده انجام می گردد. در صورتی که مقدار عدد به دست آمده از تابع توزیع یکنواخت کوچکتر از تابع تعریف شده باشد، تغییر شکل پذیرفته می شود و در غیر این صورت، تغییر شکل پذیرفته نمی شود.

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

در این الگوریتم، x₁ معرف یک راه حل اولیه امکان پذیر است که محدودیت های مدل را رعایت نموده است. (F(x مقدار تابع هدف به ازای x بوده و x_c یک راه حل جاری در هر مرحله می باشد. (V(x_c مجموعه ای است که برای نشان دادن همسایه های x_c به کار می رود. P یک عدد تصادفی می باشد که در زمان برخورد با جواب بدتر به منظور بررسی پذیرش یا عدم پذیرش آن جواب به کار رود. در قدم اول الگوریتم، یک راه حل اولیه ایجاد و مقدار تابع هدف آن محاسبه می گردد. در این قدم، راه حل اولیه به عنوان راه حل جاری x_c و بهترین راه حل *x نیز در نظر گرفته می شود. البته، این دو راه حل در طول الگوریتم تغییر خواهد یافت. همچنین در ابتدای الگوریتم، مقدار تابع هدف راه حل اولیه، به عنوان مقدار تابع هدف راه حل جاری (F(x_c و بهترین راه حل (*F(x در نظر گرفته می شود. در این قدم دمای اولیه T₀ به عنوان دمای جاری یا همان T_c در نظر گرفته می شود.

در قدم دوم، برای هر راه حل جاری، یک راه حل همسایه که به صورت ‘x_c در همسایگی آن پیدا شده و مقدار تابع هدف آن به صورت (‘F(x_c محاسبه می گردد. در صورتی که همسایه جدید مقدار تابع هدف جاری را بهبود بدهد یا برابر آن باشد، راه حل همسایه به عنوان راه حل جاری پذیرفته می شود که در این صورت تغییرات ‘x_c به x_c و (‘F(x_c به (F(x_c انجام می شود. در غیر این صورت، اگر راه حل همسایه منجر به بدتر شدن تابع هدف جاری گردد، یعنی (F(x_c’)<F(x_c ، همسایه با تابع بالتزمن که در آن تغییرات انرژی برابر با اختلاف تابع هدف است پذیرفته می شود. برای این منظور متغیر تصادفی p که دارای تابع توزیع یکنواخت بین صفر و یک است تولید شده و سپس با تابع بالتزمن مقایسه می گردد. در صورتیکه مقدار p کمتر از تابع احتمال باشد، راه حل همسایه به عنوان راه حل جاری پذیرفته می شود و در غیر این صورت راه حل جاری تغییر نمی کند.

در قدم سوم، بعد از اتمام یک زنجیره(شامل تعدادی مشخص جستجو است که معمولا برابر با یک در نظر گرفته می شود)، کاهش دما اتفاق خواهد افتاد. معمولا برای کاهش دما از یک ضریب ثابت یا همان r بین صفر و یک استفاده می شود. رابطه کاهش دما در این حالت به صورت دمای جدید برابر با rT تعریف می شود.

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