焼きなまし法（Simulated Annealing）を実施します。焼きなまし法の設計において、以下の点に注意します。

焼き鈍しの序盤に大きな変化を許容すると、特定の文字列候補の出現率が完全に0になり、一度消えた候補を再構築することが難しくなります。そのため序盤では、すべての候補が最低限の確率を維持するような値を設定し、各辺の確率Aijがその閾値を下回らないようにします。

グラフをすべての辺で（なるべく）等しい値に初期化し、これを用いて焼きなまし法を行います。

文字列は最後まで “aabbccddeeff” で固定します。

図：各辺Aijが均一な値で初期化されたグラフの初期状態。

上図の初期状態では、文字列3（251 cfddcba）のような短い文字列は高い得点を得られますが、文字列8（15639 dcfaabebefcd）のように長い文字列は5.86点しか得られません。

生スコアをそのまま評価関数として焼きなましを行うと、文字列8の出現率が仮に2倍になったとしてもわずか6点ほどの増加しか得られず、逆に短い文字列の出現率の変化が大きくスコアに寄与する状態になります。

Score = 25940

図：生スコアで焼きなましを行った際の挙動

このため、文字列8や文字列4のような「構築は難しいが得点への貢献が大きい文字列」が評価関数から無視されやすくなります。初期状態での確率が低すぎるため、これらの文字列の出現率が高くなったとしても、スコア改善にほとんど寄与しないのです。

図：確率が0となり、単純な近傍探索で再採用が不可能な文字列8。

一度出現率が0になると、単純な近傍探索だけでは候補として採用するのが不可能になります。

そこで、文字列8や文字列4のような、高得点の文字列の出現率改善をしっかり評価できる評価関数を設計する必要があります。

図：文字列8の初期出現率（0.000375）。これを適切に評価し改善したい。

次のグラフは、出現率に対して冪乗（pow関数による累乗）をとった場合の値を示しています。

初期確率が x = 0.0001 の場合、そのままの確率を評価に用いる（ピンク色）と、確率が改善されても評価関数への影響がほぼゼロになります。一方、確率を0.1乗したものを係数として用いると、小さな確率の改善でも評価に反映されることがわかります。実験的に検証すると、0.4乗程度が適切であることが分かりました。

このように出現率に対して冪乗（pow関数による累乗）をとることで、小さい確率の改善を評価に反映します。

Score = 45416

図：各文字列の出現率に対し一律でpow(確率, 0.4) を適用した評価関数を用いた結果

これにより、得点の高い文字列の出現率改善を評価関数に組み込むことが可能になり、スコアが大幅に向上しました。

しかし、文字列17のように初期の出現率が極端に低い一部の文字列は最初から無視されてしまいます。できるだけ多くの良い文字列候補を残しておき、バランス調整は後半に行いたいところです。

では、バランス良く候補を残すにはどうすればよいでしょうか？指数が0に近ければ全ての文字列の評価値が1に近づきすぎて変化が評価されません。逆に指数が1に近ければ、小さい確率が0に近づきすぎて評価されません。そこで、焼きなまし法の経過時間を基準に、指数を0.001から非線形で徐々に1へ変化させる方法を採用します。

例 : 重み付け後確率 = pow(確率, (0.001 + 0.999 * pow(経過時間/制限時間, 1.5)))

この方法を取ると、焼きなまし中盤で高得点文字列の出現率をバランスよく向上させることができます。

Score = 48248

図：経過時間に応じて重みを変え、最終的に生スコアに近い評価にした結果（スコア = 48248）。

実行時間の中盤では、高得点の文字列の出現率がある程度の水準を維持していることが確認できます。

図：piが大きい文字列の出現率が一定水準を保っている状態。