سردکردن تدریجی فلزات

5 دقیقه مطالعه

سردکردن تدریجی فلزات

سردکردن تدریجی فلزات (Simulated Annealing) یه الگوریتم معروف توی بهینه‌سازیه که ایدش خیلی نسبتا سادس ولی کاربردای زیادی توی حل مساله‌های مختلف داره.

ایده‌‌ی کلی روش

در این روش مثل خیلی از روش‌های دیگه‌ی بهینه‌سازی فرض بر اینه که ما می‌خواهیم فضای جستجوی مساله‌ رو طوری بگردیم که به یه نقطه‌ی بهینه‌ی سراسری (global optimum) برسیم. طبق معمول مشکل ما اینه که الگوریتم‌ها هیچ دانشی ممکنه از فضای جستجو نداشنه باشن و فقط در هر قدم می‌تونن چند تا ارزیابی تابع انجام بدن یعنی فقط می‌تونن تا حدی حدث بزنن که عرصه‌ی شایستگی (fitness landscape) اطرافشون چه شکلیه. در واقع بفهمن که از نظر بهینگی منطقه‌ای که الان توش هستن چقدر از نواحی قبلی بهتر بوده.

در صورتی هم که تابع مورد نظر چند قله‌ای باشه (که معمولا هم هست) کلا فرار از نقاط بهینه‌ی محلی (local optimum) مشکل بزرگ روش‌های مورد استفادس که هر کدوم یک یا چند تا مکانیزم برای فرار از اون‌ها و رسیدن به نقاط بهینه‌ی سراسری رو استفاده می‌کنن.

شایستگی

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

چند تا از ويژگی‌های این روش در زیر آورده شدن:

  • استفاده در بهینه‌سازی پیوسته و گسسته: خیلی از روش‌های معروفی که وجود دارن برای بهینه‌سازی پیوسته تعریف شدن و زمانی که فضای جستجو گسسته‌ هستش قابل استفاده نیستن. مثلا برای کارایی مثل حل مساله‌ی سودوکو و یا انتخاب ویژگی در مسائل یادگیری ماشین می‌شه از SA استفاده کرد.
  • این روش یه روش احتمالاتی (stochastic) حساب می‌شه که در هر تکرار با مقدار شروع مختلف ممکنه جواب‌هایی متفاوت به ما بده. ولی در کل مزایای خیلی از روش‌های احتمالاتی دیگرم مثل عدم احتیاج به مشتق تابع هدف و زمان نسبتا کوتاه اجرا رو داراست.
  • این متد یه روش تک‌جوابی به حساب میاد و وقتی هزینه‌ی ارزیابی‌های تابع خیلی ممکنه بالا باشه ممکنه خیلی به کار بیاد. در عین حال خیلی هم سادس و فهمیدن مکانیزم اجرای نسخه‌های مختلف این الگوریتم چندان زیاد نیست.

مراحل الگوریتم

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

  • یه نامزد جواب به صورت تصادفی در فضای جستجو ایجاد می‌کنیم و اون رو ارزیابی می‌کنیم:
  • یه مقدار اولیه‌ی درجه‌‌ی حرارت به همراه یه روش برای کاهش حرارت در هر تکرار انتخاب می‌کنیم:

روش کاهش حرارت هم می‌تونه به صورت

\begin{align} &t_0 = 1 \newline &\alpha \in (0, 1), (e.g~\alpha=0.9) \newline &t_1 = t_0 \newline &t_{i + 1} = t_i . \alpha, i = 1, 2, 3, .. \end{align}

  • یه نامزد جواب دیگه هم به در همسایگی قبلی با یه روشی مثلا تپه‌نوردی تولید می‌کنیم و مقدار تابع به ازای اون رو حساب می‌کنیم:
  • اگر مقدار نامزد جواب اولی بیشتر از دومی بود اولی رو با دومی جایگزین می‌کنیم.
  • اگر نامزد جواب تولید شده‌ی دومی بیشتر از اولی بود (جواب دوم بدتر از اولی بود) به احتمالی که متناسب با

\begin{align} \exp{(-\frac{(f_{new} - f_{old})}{t_i})} \end{align}

در هر تکرار جواب بدتر رو می‌پذیریم.

  • مراحل الگوریتم رو از بخش جستجوی‌ محلی تا انتهای مقدار ارزیابی‌های مجاز دوباره تکرار می‌کنیم.

پیاده‌سازی

مثال زیر رو که مربوط به تابع Holder table function هستش رو در نظر بگیرین. این تابع یه تابع دوبعدی هستش که به عنوان یه تابع محک برای بررسی عملکرد روش‌های بهینه‌سازی مورد استفاده قرار می‌گیره. این تابع توی دامنه‌ی جستجوی خودش چندتا نقطه‌ی بهینه‌ی سراسری و تعداد زیادی نقطه‌ی بهینه‌ی محلی داره.

import numpy as np

def f(s: 'candidate solution') -> 'f(x)':
    """Holder table function, for more information please have a look at 
       `https://en.wikipedia.org/wiki/Test_functions_for_optimization`
    """
    x = s[0]
    y = s[1]
    return -np.abs(np.sin(x) * np.cos(y) * np.exp(np.abs(1 - np.sqrt(np.power(x, 2) + np.power(y, 2)) / np.pi)))

با یه پیاده‌سازی خیلی ساده از SA سعی می‌کنیم مقدار بهینه‌ی این تابع رو پید کنیم.

import numpy as np
import matplotlib
import matplotlib.pylab as plt
from time import time
%matplotlib inline
matplotlib.rcParams['figure.figsize'] = (10, 10)

def f(s: 'candidate solution (a numpy array)') -> 'f(x)':
    """Holder table function, for more information please have a look at 
       `https://en.wikipedia.org/wiki/Test_functions_for_optimization`
    """
    x = s[0]
    y = s[1]
    return -np.abs(np.sin(x) * np.cos(y) * np.exp(np.abs(1 - np.sqrt(np.power(x, 2) + np.power(y, 2)) / np.pi)))

def check_boundary(s: 'candidate solution (a numpy array)', boundaries: """
    a tuple (lb, ub) containing lb: lower bound,
    ub: upper bound of the search space""") -> 'candidate solution in the given search space':
    s[s < boundaries[0]] = boundaries[0]
    s[s > boundaries[1]] = boundaries[1]
    return s
    
start = time() # a varibale for storing the starting time of the algorithm
objective_function = f # the objective function to be `minimized` 
t_0 = 1 # the initial temperature 
alpha = 0.3 # annealing factor
t = t_0 # the temperature during the annealing process (out annealing scheme is `t_new = t_old * alpha`) 
dim = 2 # dimesion of the search space
boundaries = (-10, 10) # lower and upper boundaries of the search space
x_old = np.random.rand(dim) * (boundaries[1] - boundaries[0]) + boundaries[0] # initializig the solution
f_old = objective_function(x_old) # evalution of the initial solution
max_iteraions = 200 # number of iterations
function_evaluations = [] # a list for saving the progress of SA

for i in range(max_iteraions):
    x_new = x_old + np.random.randn(dim)
    x_new = check_boundary(x_new, boundaries)
    f_new = objective_function(x_new)
    
    if f_new < f_old:
        f_old = f_new
        x_old = x_new
    else:
        delta = f_new - f_old
        p = np.random.rand()
        if p < np.exp(- delta / t):
            f_old = f_new
            x_old = x_new
        
    function_evaluations.append(f_old)
    t = t * alpha

end =  time() # it is all done!
print("best solution found is: ", "(" + str(x_old) + "," + str(f_old) + ")")
print("It took about ", end - start,  " seconds")  

plt.plot(function_evaluations)
plt.xlabel('# function evaluations')
plt.ylabel('f(best_solution)')
best solution found is:  ([7.88728032  9.769077],-18.8318390538)
It took about  0.008672714233398438  seconds

sa

مقدار بهینه‌ی تابع در (۱۰ و ۱۰-) برابر با ۱۹/۲۰۸۵- هستش و این پیاده‌سازی توی یه نقطه‌ی بهینه‌ی محلی افتاده ولی به نظرم برای یه پیاده‌سازی خیلی ساده چندان بد نیست.

نظر ها

It’s actually very complicated in this full of activity life to listen news on Television, therefore I simply use web for that purpose, and get the most up-to-date information.

Nice weblog right here! Also your web site quite a bit up fast! What host are you the use of? Can I get your affiliate link for your host? I want my website loaded up as fast as yours lol

What’s Taking place i am new to this, I stumbled upon this I’ve discovered It positively helpful and it has helped me out loads. I hope to contribute & help different users like its aided me. Great job.

Hello are using Wordpress for your site platform? I’m new to the blog world but I’m trying to get started and set up my own. Do you require any coding expertise to make your own blog? Any help would be really appreciated!

Great article! This is the type of info that are meant to be shared across the web. Shame on the seek engines for no longer positioning this put up upper! Come on over and discuss with my website . Thanks =)

What’s up to all, how is the whole thing, I think every one is getting more from this web site, and your views are nice in support of new viewers.

Nice post. I was checking constantly this blog and I am impressed! Extremely helpful info specially the last part :) I care for such information a lot. I was looking for this particular info for a long time. Thank you and good luck.

Nice post. I was checking continuously this blog and I am impressed! Extremely useful information specifically the last part : ) I care for such info much. I was seeking this certain information for a very long time. Thank you and best of luck.

Every weekend i used to pay a quick visit this web page, because i want enjoyment, as this this web page conations truly pleasant funny material too.

Every weekend i used to pay a visit this web page, for the reason that i want enjoyment, as this this website conations truly fastidious funny information too.

Heya i am for the first time here. I came across this board and I find It truly useful & it helped me out much. I hope to give something back and aid others like you aided me.

Hey there! I know this is sort of off-topic but I had to ask. Does building a well-established website such as yours require a massive amount work? I am completely new to running a blog but I do write in my journal everyday. I’d like to start a blog so I will be able to share my own experience and thoughts online. Please let me know if you have any suggestions or tips for new aspiring bloggers. Thankyou!

Pretty great post. I simply stumbled upon your blog and wanted to say that I’ve truly enjoyed browsing your blog posts. After all I will be subscribing in your feed and I’m hoping you write once more soon!

My brother suggested I might like this blog. He was entirely right. This post truly made my day. You cann’t imagine just how much time I had spent for this info! Thanks!

Greate pieces. Keep writing such kind of info on your site. Im really impressed by it. Hello there, You have done a fantastic job. I’ll definitely digg it and in my view recommend to my friends. I’m confident they will be benefited from this web site.

you’re in point of fact a good webmaster. The site loading speed is incredible. It sort of feels that you are doing any unique trick. Moreover, The contents are masterpiece. you have done a great activity on this matter!

I think that what you typed made a lot of sense. However, what about this? suppose you composed a catchier title? I ain’t saying your content isn’t solid, however what if you added a headline that makes people want more?

I mean سردکردن تدریجی فلزات - ووفورو is kinda vanilla. You could look at Yahoo’s home page and watch how they create news headlines to get viewers interested.

You might add a video or a related pic or two to get readers excited about what you’ve written. Just my opinion, it could make your posts a little bit more interesting.

Hey there! I understand this is sort of off-topic but I had to ask. Does building a well-established website like yours take a lot of work? I’m completely new to blogging however I do write in my journal daily. I’d like to start a blog so I can easily share my personal experience and views online. Please let me know if you have any kind of ideas or tips for new aspiring bloggers. Thankyou!

Simply wish to say your article is as amazing. The clarity to your post is just excellent and that i can suppose you’re knowledgeable on this subject. Well together with your permission let me to take hold of your feed to stay updated with impending post. Thank you a million and please continue the enjoyable work.

I want to to thank you for this very good read!! I absolutely loved every bit of it. I have you book-marked to look at new things you post…

Hmm is anyone else experiencing problems with the pictures on this blog loading? I’m trying to find out if its a problem on my end or if it’s the blog. Any feed-back would be greatly appreciated.

Hey There. I found your blog using msn. This is a very well written article. I will make sure to bookmark it and come back to read more of your useful information. Thanks for the post. I will certainly comeback.

Fantastic website. A lot of helpful info here. I am sending it to some buddies ans also sharing in delicious. And certainly, thanks for your sweat!

I think this is among the most significant information for me. And i am glad reading your article. But want to remark on some general things, The web site style is ideal, the articles is really excellent : D. Good job, cheers

No matter if some one searches for his essential thing, therefore he/she wishes to be available that in detail, therefore that thing is maintained over here.

I’m not sure exactly why but this site is loading incredibly slow for me. Is anyone else having this problem or is it a issue on my end? I’ll check back later and see if the problem still exists.

I have been browsing online more than 4 hours today, yet I never found any interesting article like yours. It’s pretty worth enough for me. In my view, if all site owners and bloggers made good content as you did, the web will be a lot more useful than ever before.

Its such as you read my thoughts! You seem to understand a lot about this, such as you wrote the e-book in it or something. I feel that you could do with a few p.c.

to drive the message home a little bit, however other than that, this is wonderful blog. A fantastic read. I’ll definitely be back.

Descargar facebook http://twitter.com/descargar_hq descargar facebook Hello there! Do you know if they make any plugins to safeguard against hackers? I’m kinda paranoid about losing everything I’ve worked hard on. Any suggestions? Descargar facebook http://twitter.com/descargar_hq descargar facebook

Quest bars cheap fitnesstipsnew1 quest bars cheap 516999410492780544 quest bars cheap

Hmm is anyone else experiencing problems with the pictures on this blog loading? I’m trying to find out if its a problem on my end or if it’s the blog. Any feedback would be greatly appreciated. Quest bars cheap fitnesstipsnew1 quest bars cheap 516999410492780544 quest bars cheap

Descargar facebook http://twitter.com/descargar_hq descargar facebook Hello there! I know this is kinda off topic but I was wondering which blog platform are you using for this site?

I’m getting tired of Wordpress because I’ve had issues with hackers and I’m looking at options for another platform. I would be great if you could point me in the direction of a good platform. Descargar facebook http://twitter.com/descargar_hq descargar facebook

After I initially left a comment I appear to have clicked on the -Notify me when new comments are added- checkbox and now each time a comment is added I get four emails with the same comment. Perhaps there is an easy method you can remove me from that service? Appreciate it!

نظر خود را بنویسید

ایمیل شما منتشر نخواهد شد. فیلد های الزامی *

در حال بارگذاری...