شبیه سازی تبرید (Simulated Annealing) – به زبان ساده

در ریاضیات و علوم کامپیوتر، «مساله بهینه‌سازی» (Optimization Problem)، در واقع مساله پیدا کردن «بهترین» راه حل، از میان کلیه راه حل‌های «ممکن» برای مساله است. نوع خاصی از مسائل بهینه‌سازی وجود دارند که در آن‌ها، به دلیل زیاد شدن تعداد «اشیا» (Objects) (منظور تعداد مشاهدات است)، مدیریت کردن آن‌ها با استفاده از «روش‌های ترکیبیاتی» (Combinatorial Methods) امکان‌پذیر نیست. یک مثال شناخته شده از چنین مسائلی، «مساله فروشنده دوره‌گرد» (Traveling Salesman Problem) است که از دسته مسائل «ان‌پی کامل» (NP-Complete که در آن، NP سرنامی برای عبارت Non-Deterministic Polynomial است) محسوب می‌شود.

برای حل چنین مسائلی، یک الگوریتم بسیار کاربردی به نام «شبیه سازی تبرید» (Simulated Annealing) (به آن «تبرید شبیه سازی شده»، «بازپخت شبیه سازی شده» و یا به طور خلاصه، SA نیز گفته می‌شود) وجود دارد. از الگوریتم شبیه سازی تبرید اغلب برای تخمین «بهینه سراسری» (Global Optimization) در مسائل بهینه‌سازی که فضای جستجوی آن‌ها بزرگ است، استفاده می‌شود.

همچنین، این الگوریتم معمولا هنگامی که فضای جستجو گسسته باشد، مورد استفاده قرار می‌گیرد (همه سفرهایی که از مجموعه مشخصی از شهرها طی آن‌ها عبور می‌شود). در این مطلب، به الگوریتم شبیه سازی تبرید و کاربرد آن در حل مسائل بهینه‌سازی پرداخته می‌شود، اما پیش از پرداختن به الگوریتم، مفهوم فرایند بازپخت (انیلینگ | Annealing) در «متالورژی» (Metallurgy) که الگوریتم تبرید شبیه سازی شده در واقع تقلیدی از آن است، بیان خواهد شد. سپس، الگوریتم شبیه سازی تبرید شرح داده می‌شود و در نهایت به حل مساله فروشنده دوره‌گرد با آن پرداخته می‌شود. کد مربوط به پیاده‌سازی الگوریتم شبیه سازی تبرید در زبان برنامه‌نویسی «پایتون» (Python) و «جاوا» (Java) در انتخای این مطلب، ارائه شده است.

فرایند بازپخت یا انیلینگ

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

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

مساله فروشنده دوره‌گرد

در مساله «فروشنده دوره‌گرد» (Travelling Salesman Problem | TSP)، پرسش زیر مطرح می‌شود:

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

این مساله، یکی از مسائل «ان‌پی-سخت» (NP-Hard) در بهینه‌سازی کامپیوتری محسوب می‌شود که در حوزه «تحقیق در عملیات» (Operational Research | OR) و «علوم نظری رایانه» (Theoretical Computer Science | TCS) حائز اهمیت است. در «نظریه پیچیدگی محاسباتی» (Theory of Computational Complexity)، نسخه تصمیم مساله فروشنده دوره‌گرد (که در آن یک طول L داده شده، وظیفه تصمیم‌گیری پیرامون آن است که آیا گراف دارای دوری کمتر از L است یا خیر) از جمله مسائل ان‌پی-کامل محسوب می‌شود.

بنابراین، این امکان وجود دارد که بدترین زمان اجرا برای هر الگوریتم برای TSP، با افزایش تعداد شهرها به صورت «فوق چند جمله‌ای» (Superpolynomially) افزایش پیدا کند (اما نه بیش‌تر از نمایی).

این مساله برای اولین بار در سال ۱۹۳۰ فرموله شد و یکی از مسائلی است که بیشترین مطالعات در حوزه بهینه‌سازی روی آن انجام شده است. از این مساله، به عنوان «بنچ‌مارک» (Benchmark) برای بسیاری از روش‌های بهینه‌سازی استفاده می‌شود. هرچند حل مساله فروشنده دوره‌گرد حتی به لحاظ کامپیوتری نیز دشوار است، تعداد زیادی از «روش‌های تکاملی» (Evolutionary Algorithms) و «الگوریتم‌های دقیق» (Exact Algorithm) برای حل این مساله شناخته شده هستند که می‌توانند TSP را با تعداد هزاران و حتی میلیون‌ها شهر حل کنند. مساله فروشنده دوره‌گرد را می‌توان به صورت یک مساله گراف و یا «برنامه‌نویسی خطی صحیح» (Integer Linear Programming) فرموله کرد. تعداد کل پاسخ‌های ممکن برای مساله برابر با «$$\frac{1}{2}\left(n-1\right)!$$» برای n>2 است که در آن، n تعداد کل شهرها است. در واقع، این عدد تعداد دورهای همیلتونی در یک گراف کامل با n راس را نشان می‌دهد.

الگوریتم شبیه سازی تبرید

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

فیلم آموزش شبیه سازی تبرید Simulated Annealing در متلب MATLAB در فرادرس

کلیک کنید

یعنی در واقع، جواب‌های یک مساله به خوبی گرم می‌شوند و با نوسانات زیادی تغییر می‌کنند؛ سپس، به تدریج دامنه تغییرات کم می‌شود و در واقع یک سری شیار به سمت جواب بهینه ساخته می‌شوند. الگوریتم شبیه سازی تبرید برای اولین بار در سال ۱۹۸۳، توسط «کریک‌پاتریک» (Kirkpatrick) و همکاران معرفی شد. شایان ذکر است، الگوریتم شبیه سازی تبرید از جمله الگوریتم‌های فراابتکاری (فراتکاملی | فرااکتشافی | Metaheuristic) محسوب می‌شود. در الگوریتم شبیه سازی تبرید، از روش احتمالاتی برای حل مساله بهینه‌سازی استفاده می‌شود. علاقمندان به مشاهده ویدئوی آموزشی این الگوریتم به زبان فارسی، می‌توانند از «آموزش شبیه‌سازی تبرید یا Simulated Annealing در متلب» بهره‌مند شوند.

در الگوریتم شبیه سازی تبرید (SA)، نقطه s یک حالت از سیستم فیزیکی محسوب می‌شود و تابع (E(s مشابه با انرژی داخلی سیستم در حالت s است. هدف آن است که با شروع سیستم از یک حالت اولیه دلخواه (یک s₀ دلخواه)، به حالتی رسیده شود (S_n) که تابع (E(s در آن کمینه است. در واقع، با شروع از یک حالت دلخواه از سیستم فیزیکی، به حالتی رسیده می‌شود که انرژی داخلی سیستم در آن حالت کمینه است (سیستم کمترین انرژی را در آن حالت خواهد داشت). برای انجام این کار، الگوریتم از یک نقطه دلخواه آغاز به کار و سپس، یک حالت همسایه را انتخاب می‌کند. پس از آن، به طور احتمالی تصمیم می‌گیرد که در حالت کنونی بماند و یا به حالت همسایه جا به جا شود. مجموع این جا به جایی‌های احتمالی، سیستم را به سوی حالتی با انرژی داخلی کمتر هدایت می‌کند. این کار تا جایی انجام می‌شود که سیستم به یک حالت عقلانی برسد یا اینکه میزان محاسبات، از یک آستانه مشخص بیشتر شود. برای درک بهتر وجه تمایز الگوریتم شبیه سازی تبرید با برخی از دیگر روش‌های ابتکاری مانند تپه‌نوری، مثال زیر قابل توجه است.

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

چالش اصلی در حل مساله فروشنده دوره گرد با استفاده از روشی مانند الگوریتم «تپه‌نوردی» (Hill Climbing)، از آنجا نشات می‌گیرد که این الگوریتم با جا به جایی بین همسایه‌ها معمولا به حالت کمینه می‌رسد و در همان نقطه متوقف می‌شود (در واقع در حالتی که نسبت به دیگر همسایگی‌های بررسی شده کمینه باشد متوقف می‌شود؛ در صورتی که امکان دارد یک کمینه سراسری وجود داشته باشد). در واقع، الگوریتم تپه‌نوردی «کمینه محلی» (Local Minimum) را معمولا به سرعت پیدا می‌کند، اما ممکن است در همان جا متوقف شود و بنابراین از آنجا به «کمینه سراسری» (Global Minimum) نمی‌رسد. این در حالی است که شبیه‌سازی تبرید می‌تواند راه حل خیلی خوبی را حتی در حضور «نویز» (Noise) برای چنین مساله‌ای پیدا کند.

راهکار الگوریتم شبیه سازی تبرید برای غلبه بر این مشکل و بهبود استراتژی مذکور، استفاده از دو ترفند است. ترفند اول، از «الگوریتم متروپولیس» (Metropolis Algorithm) گرفته شده که در سال ۱۹۵۳ توسط متروپولیس و همکاران اون کشف شده است. در این الگوریتم، گاهی مسیرهای کوتاه پذیرفته نمی‌شوند، زیرا این عدم پذیرش منجر به آن می‌شود که الگوریتم «فضای راه حل ممکن» بزرگ‌تری را اکتشاف کند. ترفند دوم، مجددا با تقلید از فرایند بازپخت فلز و کاهش دما به دمای پایین‌تر اتفاق می‌افتد. پس از آنکه بررسی‌ها و جا به جایی‌های زیادی انجام شد و مشاهده شد که تابع (E(s (این تابع در واقع همان تابع هزینه یا Cost Function است) به آرامی کاهش پیدا می‌کند (دما کاهش پیدا می‌کند)، اندازه انجام جا به جایی‌های «بد» کنترل می‌شود. پس از چندین بار کاهش دما به مقدار کم‌تر، فرایند «فرونشانی» (Quench) با پذیرش جا به جایی‌های خوب به منظور پیدا کردن کمینه محلی تابع هزینه اتفاق می‌افتد. «زمان‌بندی‌های بازپخت» (Annealing Schedules) متعددی برای کاهش درجه حرارت وجود دارد، اما نتایج به طور کلی خیلی به جزئیات حساس نیستند.

اکنون، الگوریتم شبیه سازی تبرید به صورت ریاضیاتی و دقیق ارائه می‌شود. احتمال انتقال از یک حالت فعلی، مثلا s به حالت کاندید جدید مانند $$s\prime$$ با یک تابع احتمال پذیرش $$P(e,e\prime,T)$$ مشخص می‌شود که در آن، (e=E(s و $$e\prime=E(s\prime)$$ است (چنانچه پیش‌تر بیان شد، تابع E در فضای حالت نشان‌گر انرژی داخلی سیستم و T نشان‌گر دما است. دمای T بر اساس زمان تغییر می‌کند). بنابراین، با توجه به آنکه پیش‌تر گفته شد هدف آن است که انرژی سیستم کمینه باشد، پس حالتی که (منظور s است) در آن (E(s کمتر باشد، بهتر از حالتی است که در آن مقدار (E(s بیشتر باشد. نکته قابل توجه در الگوریتم تبرید شبیه سازی شده آن است که تابع احتمال P همواره و حتی در  شرایطی که e کوچک‌تر از $$e\prime$$ است، باید مثبت باشد. این خصوصیت موجب می‌شود الگوریتم در بهینه محلی که نسبت به بهینه سراسری «بدتر» است، متوقف نشود. در واقع، در صورتی که $$s\prime$$ بهتر از s $$E(s)\ge E(s\prime)$$ باشد، $$s\prime$$ پذیرفته می‌شود و اگر $$s\prime$$ بدتر از s باشد و موجب $$E(s)< E(s\prime)$$ شود، $$s\prime$$ با یک احتمال پذیرفته می‌شود. تابع احتمال P به صورت زیر است:

$$p=e^{-\frac{E(s\prime)-E(s)}{T}}=e^{-\frac{\Delta f}{T}}$$

در صورت کاهش دمای T و میل کردن آن به سمت صفر، احتمال P نیز باید کاهش پیدا کند و یا به صفر و یا یک عدد مثبت میل کند. در این شرایط، P هنگامی به سمت صفر میل می‌کند که $$e$$ باشد و در صورتی به یک عدد مثبت میل می‌کند که $$e\prime$$ باشد. همانطور که مشهود است، دما در کنترل تغییرات سیستم نقش اساسی دارد. همانطور که پیش‌تر هم بیان شد، دما در شبیه‌سازی به صورت تدریجی کاهش پیدا می‌کند. بنابراین، الگوریتم از $$T=\infty$$ و به عبارتی، از یک دمای بسیار بزرگ کار خود را آغاز می‌کند و در هر مرحله با توجه به یک زمان‌بندی تبرید از پیش مشخص شده، کاهش پیدا می‌کند. زمان‌بندی تبرید با توجه به این موضوع انجام می‌شود که اگر منابع مورد استفاده (مثلا میزان محاسبات) به پایان برسند، زمان انجام فرایند نیز به پایان می‌رسد. از همین رو، الگوریتم ابتدا در فضای بزرگی از راه حل‌ها، صرف نظر از انرژی داخلی سیستم به دنبال پاسخ می‌گردد و به تدریج، به سمت مناطق دارای انرژی کمتر جا به جا می‌شود. این منطقه، به تدریج کوچک‌تر می‌شود و این کار، تا زمانی که بهینه سراسری یافته شود، ادامه پیدا می‌کند. برای یک مساله دارای فضای متناهی، افزایش زمان موجب می‌شود تا با احتمال یک، الگوریتم در نقطه بهینه سراسری متوقف شود؛ هر چند زمان لازم برای انجام این کار، بیش‌تر از زمان لازم برای جستجو در کل فضا است و بنابراین، این موضوع در عمل کاربردی ندارد.

فلوچارت الگوریتم شبیه سازی تبرید

حل مساله فروشنده دوره‌گرد با شبیه سازی تبرید

برنامه‌ای که با بهره‌گیری از آن می‌توان مساله فروشنده دوره‌گرد را با الگوریتم شبیه سازی تبرید حل کرد، از این مسیر [+] در دسترس است. در ادامه، انیمیشن مربوط به حل مساله فروشنده دوره‌گرد با استفاده از این برنامه برای ۴۸ تا از مراکز استان‌های ایالات متحده آمریکا، قابل مشاهده است.

شبه کد الگوریتم تبرید شبیه سازی شده

فیلم مجموعه آموزش الگوریتم های بهینه سازی هوشمند – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

کد الگوریتم تبرید شبیه سازی شده در جاوا

کد الگوریتم تبرید شبیه سازی شده در پایتون