焼き鈍し法(SA法)メモ

プログラミング

はじめに

探索空間から大域的最適解を求めることができる汎用的なアルゴリズムの「焼き鈍し法」についてちょっと調べてみたのでメモ。

latticelmでも用いられているみたい。

SAアルゴリズム

  • 温度Tによって、動作が変わる
  • メインは「メトロポリスの手続き」で、ある温度Tにおけるアニーリング過程をシミュレートする
  • 低下していく各温度についてMetropolisを実行する
    • 温度が高いほど動きがあり(ランダム)、低いほど動きがなくなる(どん欲法)
  • beta > 1 : ある温度でアニーリングに費やされる時間は温度が低下するにつれ次第に増加
  • RANDOMは一様乱数(0-1)
  • 新しい解を採択する基準は「メトロポリス基準」と呼ばれる
    • 手続きMetropolisはM個の解を生成してチェックする

SAの疑似コード

SA部分
Algorithm Simulated_annealing(S0,T0,alpha,beta,M,MaxTime);
//S0は初期解
//BestSは最良解
//T0は初期温度
//alphaは冷却率
//betaは定数
//MaxTimeはアニーリング過程に与えられた総処理時間
//Mは次のパラメータ更新までの時間
BEGIN
	T = T0;
	CurS = S0;
	BestS = CurS; //BestSはここまでに得られた最良解
	CurCost = Cost(CurS);
	BestCost = Cost(BestS);
	Time = 0;
	REPEAT
		Call Metropolis(CurS,CurCost,BestS,BestCost,T,M);
		Time = Time + M;
		T = alpha * T;
		M = beta * M;
	UNTIL( Time >= MaxTime );
END
手続きMetropolis部分
Algorithm Metropolis(CurS,CurCost,BestS,BestCost,T,M);
BEGIN
	REPEAT
		NewS = Neighbor(CurS);
		NewCost = Cost(NewS);
		ΔCost = (NewCost - CurCost);
		IF( ΔCost < 0 ) THEN
		    CurS = NewS;
		    IF( NewCost < BestCost ) THEN
		    	BestS = NewS;
		    ENDIF
		ELSE
		    IF( RANDOM < e^(-ΔCost/T) ) THEN
		    	CurS = NewS;
		    ENDIF
		ENDIF
		M = M - 1;
	UNTIL( M == 0 );
END

参考文献