焼きなまし法で遊ぶ - Negative/Positive Thinking
はじめに 焼きなまし法について、どんな挙動で、どこを気をつけないといけないのかよくわかってないので、遊んでみる。 焼きなまし法メモ : http://d.hatena.ne.jp/jetbead/20111014/1318598381 評価関数 簡単のために、4次関数を使って、初期位置は小さい山の外側(x0=2.0)に配置してみる。 【関数の形】 (google) (wolfram alpha) http://www.wolframalpha.com/input/?i=-3x%5E4%2B3x%5E3%2B10x%5E2-10x%2B15 best_x = argmax f(x)を求めたい。 コード #include <iostream> #include <cmath> //xorshift // 注意: longではなくint(32bit)にすべき unsigned long xor1
焼きなまし法 - 大人になってからの再学習
最適化問題を解くための探索アルゴリズムの1つに焼きなまし法というものがある。 最急降下法のように、値が小さくなる方向に少しずつ探索を進めていくアルゴリズムでは、その出発点に依存して局所最適解に陥ることが多い。 その結果として、大域的最適解が求まらないという問題がある。 この問題を解決して、最終的に大域的最適解が求まりやすくなるように改良したのが焼きなまし法。 考え方は単純で、「たまには解から遠ざかる方向にも進んでみよっか」というもの。 常に値が小さくなる方向ではなくて、たまには逆向きに進んでみると、もっとよい解が見つかるのではないか、と考える。 しかしながら、この「たまには」という言葉はあいまいすぎるので、確率pで、という具合に確率の話で説明する必要がある。 焼きなまし法では、この確率pは、値の変化量にも影響を受けるけど（解から大きく遠ざかる方向には、あまり行かないように確率pを小さくする
焼きなまし法 | プログラミング!?で遊ぶ
前に、48都市の問題(att48)を焼きなまし法（シミュレーテッドアニーリング、SA）で解きましたが、最適解が見つかってしまったので、今度は532都市の問題(att532)を解いてみました。 以前と同じく、用いた近傍は2-opt近傍で、比較のために多スタート局所探索(MLS)でも解いてみました。 以下に実装の簡単な解説と結果を書きます。 多スタート局所探索(MLS) ランダムな巡回路を初期解とする局所探索を100回。 結果 得られた巡回路の長さ 29532 解の評価回数 99241620。 焼きなまし法(SA) 初期温度100。温度は今の温度に0.9をかけることで小さくしていきました。探索の終了条件は温度が0.1以下になったときとしました(100, 0.9, 0.1という数字は適当に決めたもの)。一定の温度で評価する解の個数は、6*(近傍のサイズ)としました。 結果 得られた巡回路の長さ
最適化アルゴリズム - sonoshouのまじめなブログ
集合知プログラミングの第５章最適化の一部を自分なりにまとめます。 ヒルクライム法（傾斜上り法） ヒルクライム法は、ある地点から少し値を変更し、 変更後の値が変更前の値より低ければ採用する。 これを繰り返して行けば、最小値へ近づくことが出来る。 ヒルクライム法には致命的な弱点がある。 例えば、下図のようなグラフを考える。 このように、局所的最小解があるようなグラフでは、 大局的最小解を発見することはできない。 ヒルクライム法は非常に単純な方法で一般的に使われることは無いが、 この後の手法の比較のために説明する。 アルゴリズム＜初期化処理＞ ランダムな値で変数を初期化。カウントを初期化。 ＜反復処理＞ 変更する変数を一つ選ぶ。 変数の値を増加させるか、減少させるかを決定する。 変数の値を変更後、新たな変数でコストを算出する。 変更前と変更後のコストの大小を比較する。 変更後のコストが小さければ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Sweep and prune - Wikipedia
