迷路を解くのに最も愚かな方法として、スタートから拡散する数千個の粒子をシミュレーションするという方法が紹介されています。 https://t.co/OOAcaQZmzL
数学を愛する会 on Twitter: "迷路を解くのに最も愚かな方法として、スタートから拡散する数千個の粒子をシミュレーションするという方法が紹介されています。 https://t.co/OOAcaQZmzL"
迷路を解くのに最も愚かな方法として、スタートから拡散する数千個の粒子をシミュレーションするという方法が紹介されています。 https://t.co/OOAcaQZmzL
焼きなまし法でThomson問題の解を探索する - lan496の日記
Thomson問題 Thomson問題とは、三次元単位球の表面にN個の電荷の等しい粒子を配置するとき、クーロンポテンシャル\( U = \sum_{i < j} \frac{1}{|\rm{r}_{i} - \rm{r}_{j}|}\)が最小となる配置となるを求める問題です。詳しくはwikiをThomson problem - Wikipedia, the free encyclopedia。N=5のときにて三方両錐形が解になったり、N=8で立方体が解にならないなどいろいろと面白い問題です。 去年の12月頃、そもそもこの問題設定に名前が付いていることをある方から教えていただき、N=5の場合で実際に初期条件を与えて時間発展させることで本当に三方両錐形になるのか実験してみました。 球面上の点電荷が最も安定する配置(thomson problem)のRK4を利用したシミュレーションの進捗 pic
大域的非線形数値最適化 - Wolfram Mathematica 7 Documentation
制約条件付きの非線形最適化に対する数値アルゴリズムは，大まかに分けると勾配法と直接探索法とに分けられる．勾配法では，第1導関数（勾配）か第2導関数（ヘッシアン）が使われる．この例には逐次二次計画(SQP)法，拡大ラグランジュ法，非線形内点法がある．直接探索法では，導関数情報は使われない．この例としては，Nelder-Mead法，遺伝的アルゴリズム，微分進化法，焼きなまし法がある．直接探索法の方が収束が遅い傾向があるが，関数と制約条件のノイズの存在への耐性は強い． 通常，アルゴリズムは問題の局所的なモデルを構築するだけである．また，そのようなアルゴリズムの多くは目的関数の減少，目的関数と制約条件の組み合わせであるメリット関数の減少を要求し，反復プロセスの収束を確実にする．収束した場合，このアルゴリズムは局所的最適値だけを見付けるため，「局所的最適化アルゴリズム」と呼ばれる．Mathemati
Simulated Annealing/SA -概論-
Simulated Annealing/SA -概論- 1.はじめに 一般に最適化問題とは，ある制約条件下において， 与えられた状態空間で定義された関数の最大値または最小値を与える状態空間の要素を求める． シミュレーテッドアニーリング（Simulated Annealing）は，最適化問題を解く汎用近似解法の一つである． この方法は，Fig.1のように高温で加熱した金属を徐々に少しずつ温度を下げて冷やすことによって， 元の金属より欠陥の少ない優れた結晶構造を作る物理プロセス（アニーリング）に着想を得て， これを計算機上で模擬することにより最適化問題を解こうとする手法である． Fig.1 高温時から低温時への徐冷に伴う原子の配列 2.SAの特徴 ＜長所＞ ・ 頑強性・・・多くの最適化解法が局所最適化に補足される欠点を持つのに対し，SAは用意には局所最適解につか まらず，理論上は真の最適解
Simulated Annealing for beginners
Finding an optimal solution for certain optimisation problems can be an incredibly difficult task, often practically impossible. This is because when a problem gets sufficiently large we need to search through an enormous number of possible solutions to find the optimal one. Even with modern computing power there are still often too many possible solutions to consider. In this case because we can’
「Rによるモンテカルロ法入門」読書ノート：アーカイブ - Wolfeyes Bioinformatics beta
本書は，モンテカルロ法の実践的な解説書であり，統計解析ソフトのRを用いた豊富な実例と練習問題が組まれている．モンテカルロ法とは乱数を用いて数値計算を行う手法の総称であり，本書で扱う内容は乱数の発生からモンテカルロ積分，そしてマルコフ連鎖モンテカルロ法（MCMC）の各種アルゴリズムに至るまで非常に幅広い．たいていの解説には理論に実践演習が付随した形となっており，数学的な理論を軸にして実際にRを用いたコード例が示される． 練習問題を解きつつ読書ノートをまとめてみる そんなこんなで，久保本と並行する形で「Rによるモンテカルロ法入門」を読んでいる．一応MCMCの部分だけひと通り目を通したのだが，最終的にMCMCの実装までひと通りやるにしても一連の流れを簡単にでも追っておかなければと思って，最初の乱数の部分からじっくり読み進めている．これがなかなか難しくて，手も足も出ないところをなんとかRのコードを
焼き鈍し法(SA法)メモ - Negative/Positive Thinking
はじめに 探索空間から大域的最適解を求めることができる汎用的なアルゴリズムの「焼き鈍し法」についてちょっと調べてみたのでメモ。 latticelmでも用いられているみたい。 SAアルゴリズム 温度Tによって、動作が変わる メインは「メトロポリスの手続き」で、ある温度Tにおけるアニーリング過程をシミュレートする 低下していく各温度についてMetropolisを実行する 温度が高いほど動きがあり(ランダム)、低いほど動きがなくなる(どん欲法) beta > 1 : ある温度でアニーリングに費やされる時間は温度が低下するにつれ次第に増加 RANDOMは一様乱数(0-1) 新しい解を採択する基準は「メトロポリス基準」と呼ばれる 手続きMetropolisはM個の解を生成してチェックする SAの疑似コード SA部分 Algorithm Simulated_annealing(S0,T0,alpha,
焼きなまし法で遊ぶ - 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のまじめなブログ
集合知プログラミングの第５章最適化の一部を自分なりにまとめます。 ヒルクライム法（傾斜上り法） ヒルクライム法は、ある地点から少し値を変更し、 変更後の値が変更前の値より低ければ採用する。 これを繰り返して行けば、最小値へ近づくことが出来る。 ヒルクライム法には致命的な弱点がある。 例えば、下図のようなグラフを考える。 このように、局所的最小解があるようなグラフでは、 大局的最小解を発見することはできない。 ヒルクライム法は非常に単純な方法で一般的に使われることは無いが、 この後の手法の比較のために説明する。 アルゴリズム＜初期化処理＞ ランダムな値で変数を初期化。カウントを初期化。 ＜反復処理＞ 変更する変数を一つ選ぶ。 変数の値を増加させるか、減少させるかを決定する。 変数の値を変更後、新たな変数でコストを算出する。 変更前と変更後のコストの大小を比較する。 変更後のコストが小さければ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
2014 TCO Marathon Round 3 (yowa)
Modern Heuristic Techniques for Combinatorial Problem
関西大学システム理工学部 感性情報システム研究室
モンテカルロサンプリング
Simulated Annealing
SimulatedAnnealing - KLab Public Wiki
Modern Heuristic Techniques for Combinatorial Problem
Sweep and prune - Wikipedia