「夏」

夏が来た

ところで、夏って何月からを言うんだ？(分かってない)
知らないけど暑かったら夏だろ、うん

ということで海水浴中のポテト君です！ちょうどいい塩味が付いてます！
「6月すしnote企画」のお題No.34 夏をやってみようかなって

なんでそれにしたのかって?
他は書けなそうだったから…w

夏と言えば！
暑い！

暑いと言えば！
温度！

温度と言えば！
焼きなまし法と冷却スケジューリング！

ということで、「誰が最もクールか！？冷却スケジューリングバトル！」を開催します！！！！！！！！！！！！！！

ではまず焼きなまし法の説明から

このアルゴリズムの目的は、近接最適性(評価の高い状態同士が似ている)を持った問題について、局所解にはまらずに最適解を見つけることである

ということで

1. パラメータはx,yの2つ

2. 最適解の位置は(0,0)付近で値は10付近

3. 局所解を持つ

評価のモデルを用意しました！

ではご登場いただきましょ～～～！！！！！！！

No.１ $${8+2\cos(\sqrt{x^2+y^2})-2(x^2+y^2)^{0.3}}$$

波にべき関数を合わせた形を持ったこの関数は、度重なる波によって上がって来る評価を次々と波の先端に追い込んでいきます！なんと恐ろしい！

No.2 $${5.2+\cos(x)+\cos(y)-\frac{|x|}3-3((\frac{y-11}{10})^4-2(\frac{y-11}{10})^2+\frac{y}{10})}$$

こちらも波で攻めてきました！しかし今回はx軸とy軸を切り離し、いくつもの山を作りました！まさにエベレスト！！！！！！

No.3 $${5(-(\frac{x-9}{20})^4+2(\frac{x-9}{20})^3-1.5(\frac{x-9}{20}))+3.8(-(\frac{y-12.5}{10})^6+2(\frac{y-12.5}{10})^4-0.5(\frac{y-12.5}{10})^3)}$$

単純な形に見えますが、それはつまり大きな谷を越えなければいけないということ！まさにエベレスト！！！！！

次にアルゴリズムの内容に入ります

1. ランダムな位置をpとしてスタートする

2. pの近傍の1点qをランダムに選ぶ

3. 遷移確率=f(p,q,カウント値,カウントの最大値)

4. [0,1)のランダム値が遷移確率より低ければ遷移(p=q)

5. 2を一定回数繰り返す

6. 最後のpを解とする

ここで焼きなまし法を焼きなまし法たらしめるのが遷移確率f！

$${f=0(score(p)> score(q)のとき),1(score(p)\leq score(q)のとき)}$$
(ここでscoreはその点での評価)
とすれば、山登り法になる

しかし焼きなまし法では
$${f=\exp(\frac{score(q)-score(p)}{t(p,q,カウント値,カウントの最大値)})(score(p)> score(q)のとき)}$$
$${1(score(p)\leq score(q)のとき)}$$

t=1のとき、評価の差が負の部分ではこのようになる

つまり少し点が下がることは許容するという方法で局所解から抜け出そうという方法である

ここで、tが高ければ遷移しやすくなり、低ければ遷移しずらくなる
実際に問題を解くとき、最初は局所解から抜け出すことを、最後は周辺でより高い解を探すことを考える、つまりtを高い方から低い方に下げていく
ここからtを温度と呼び、tの下げ方を冷却スケジューリングと呼ぶ

ということで本題！冷却スケジューリングの登場です！！！

多くて面倒なのでグラフで全部出します

縦軸は温度(実際には係数をかけて調整する)
横軸はカウント値/カウントの最大値
一番下に曲がってるのが3次関数、その次が2次関数
逆に一番上に曲がってるのが立方根、その次が平方根
真ん中の2つは直線(1次関数)と離散値(5段階)

今回の決戦はこれらを踏まえたPythonプログラムで行います！！どうぞ！！！

import math
scores=[
    lambda x,y:8+2*math.cos(math.sqrt(x**2+y**2)-2*((x**2+y**2)**0.3)),
    lambda x,y:5.2+math.cos(x)+math.cos(y)-abs(x)/3-3*(((y-11)/10)**4-2*(((y-11)/10)**2)+y/10),
    lambda x,y:5*(-((x-9)/20)**4+2*(((x-9)/20)**3)-1.5*((x-9)/20))+3.8*(-((y-12.5)/10)**6+2*(((y-12.5)/10)**4)-0.5*(((y-12.5)/10)**3))
]
schedule=[
    lambda count,maxCount:2*((5*maxCount-5*count)//maxCount+1)/5,
    lambda count,maxCount:2*(maxCount-count+1)/maxCount,
    lambda count,maxCount:2*(((maxCount-count+1)/maxCount)**2),
    lambda count,maxCount:2*(((maxCount-count+1)/maxCount)**3),
    lambda count,maxCount:2*(((maxCount-count+1)/maxCount)**(1/3)),
    lambda count,maxCount:2*(((maxCount-count+1)/maxCount)**(1/2))
]
TRYCOUNT=1000
import random
maxCounts=[100,1000,10000,100000]
for t in schedule:
    data=[]
    for maxCount in maxCounts:
        scoreSum=0
        for i in range(TRYCOUNT):
            for score in scores:
                pos=[random.randint(-30,30),random.randint(-30,30)]
                nowScore=score(pos[0],pos[1])
                for count in range(maxCount):
                    near=[pos[0]+2*random.random()-1,pos[1]+2*random.random()-1]
                    newScore=score(near[0],near[1])
                    delta=newScore-nowScore
                    if(delta>=0):
                        nowScore=newScore
                        pos=near
                    elif(random.random()<math.exp(delta/t(count,maxCount))):
                        nowScore=newScore
                        pos=near
                scoreSum+=nowScore
        data.append(str(round(scoreSum/TRYCOUNT/len(scores),3)))
    print(",".join(data))

それぞれを1000回行った平均値を求めてる感じ

結果は…!?

2回実行してみてこんな感じ(試行回数で赤は最大、青は最小)
最後になっても温度の高い立方根や平方根は全体的に点数が低い、どうやら冷ますのが遅すぎるらしい
試行回数が多くなると、5段階では温度の高いまま終わるために点が低くなる
試行回数が多くなると1～3次関数の間に違いは見られないが、試行回数が十分多くないと冷ましすぎてしまうらしい

ということで優勝は！！！
直線です！！！！！

直線には！
賞金として…え－…

拍手を差し上げます！

👏👏👏👏👏👏👏👏👏👏👏👏👏

では、また今度