SimulatedAnnealing

1
struct State{ // 状態を表す構造体
2
  double x;
3

4
  // f(x) = -x^4 + x^3 + x^2 + x
5
  // max f(x): 2.33.... (x = 1.28...)
6
  double eval(){ // 評価関数
7
    return -pow(x,4)+pow(x,3)+pow(x,2)+x;
8
  }
9
  void modify(){ // 遷移
10
    x += ((double)rand() / (RAND_MAX))-0.5;
11
  }
12
};
13

14
ESAnnealing<State> sa;
15
// sa内のStateの初期設定をする
16
sa.state.x=0;

1
// (epoch当たりの試行回数, 初期温度, 目標温度, 冷却係数)
2
sa.annealing(100,100000,0.1,0.99);

1
// 結果はクラス内のstateで参照できる
2
std::cout << "Solution: " << "f(x) = " << sa.state.eval() << ", x = " << sa.state.x << std::endl;

1
template <class T>
2
class ESAnnealing
3
{
4
public:
5
  T state;
6

7
  void annealing(double epoch, double temperature, double temperature_target, double coolingcoef, unsigned int seed = 42, bool verbose = true)
8
  {
9
    assert(0 <= coolingcoef and coolingcoef < 1);
10
    assert(temperature >= temperature_target);
11
    srand(seed);
12
    double initscore = state.eval();
13
    double beststate_score = initscore;
14
    T beststate = state;
15
    int estimeted_epoch = std::ceil((std::log(temperature_target) - std::log(temperature)) / std::log(coolingcoef));
16
    if (verbose)
17
      std::cout << std::fixed << std::setprecision(6)
18
                << "ESAnnealing started with:" << "\n"
19
                << "| epoch       " << epoch << "\n"
20
                << "| temperature " << temperature << "\n"
21
                << "| target temp " << temperature_target << "\n"
22
                << "| coolingcoef " << coolingcoef << "\n"
23
                << "| seed        " << seed << "\n"
24
                << "| est epoch   " << estimeted_epoch << "\n"
25
                << std::flush;
26
    int cnt = 0;
27
    while (temperature > temperature_target)
28
    {
29
      for (int i = 0; i < epoch; i++)
30
      {
31
        T newstate = state;
32
        newstate.modify();
33
        double statescore = state.eval();
34
        double newstatescore = newstate.eval();
35
        double delta = newstatescore - statescore;
36

37
        if (0 < delta)
38
        {
39
          state = newstate;
40
        }
41
        else if (frand() > std::exp(delta / temperature))
42
        {
43
          state = newstate;
44
        }
45

46
        if (beststate_score < newstatescore)
47
        {
48
          beststate_score = newstatescore;
49
          beststate = newstate;
50
        }
51
      }
52
      temperature *= coolingcoef;
53

54
      if (verbose)
55
        std::cout << cnt << "/" << estimeted_epoch - 1 << " temp: " << temperature << " eval: " << beststate_score << std::endl;
56

57
      cnt++;
58
    }
59
    state = beststate;
60
    if (verbose)
61
      std::cout << "annealed: " << initscore << "->" << beststate_score << std::endl;
62
  }
63

64
private:
65
  double frand()
66
  {
67
    return ((double)rand() / (RAND_MAX));
68
  }
69
};