読者です 読者をやめる 読者になる 読者になる

にほんごのれんしゅう

日本語として伝えるための訓練を兼ねたテクログ

焼きなまし法(Simulated Annealing)のJava8による再実装

課題

  • 焼きなまし法(SA)と呼ばれるかなりレガシーなアルゴリズムにはだいぶ世話になったのでJavaでも使ってみたかった。(Pythonではよく使っていた)
  • Javaでの実装を探していたが、見つからないので、PythonのコードをJava8で再実装した。(目的関数の設定にラムダを用いている)
  • 素早く解を出すのにSAは向いている(精度はともかく)

コーディングポリシー

  • Wikipediaの記事の疑似ソースコードよりはわかりやすくしたい。したがって具体的な数式を解くようなコードを例とする。焼きなまし法Wikipedia
  • Pythonのtheanoのような内部で微分可能なメタ数式を使わないで解くので目的関数自体はハードコードになることを許容する。

ソースコード

import java.util.*;
import java.util.function.*;
public class SAoriginal {
	public Double T;
	public Double vec;
	public SAoriginal(){
		System.out.println("SAcreated");
		/**
		 * default parameters
		 */
		T = 10000.;
		vec = 0.;
		cost2 = x -> (3*((x-1)*(x-1)) + (x-2)*(x-2));
	}
	private Function<Double,Double> cost2;
	public void set(Function<Double,Double> cost2){
		this.cost2 = cost2;
	}
	public Double calc(){
		double step = 1.;		
		while (T > 0.01){
			Double rnd = new Random().nextDouble();
			Double direction = (rnd - 0.5) * step;
			Double newCost = cost2.apply(vec+direction);
			Double oldCost = cost2.apply(vec);
			//温度から確率を定義する
			Double p = Math.pow(Math.E, -1.*Math.abs(newCost - oldCost)/T);
			if( newCost < oldCost || new Random().nextDouble() < p ){
				vec = vec + direction;
			}
			T = T * 0.999;
		}
		return vec;
	}
	public Double get(){
		return vec;
	}
}

そこそこの速度とそこそこの性能

  • 使いようによってはいろいろできそう。
  • ちょっと複雑な式とかを解かせるのによさそう。
  • 一個できるとほかのアルゴリズムも気になるよね