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’
バブルソートの方がいい？
CACM の10月号に面白いデータを見つけました． D. H. Ackley, “Beyond efficiency,” CACM 56(10), pp. 38-40, 2013. 仮にあなたの計算機の信頼性が著しく劣っていたとして，比較命令を実行すると10%の割り合いで間違えるとしよう．そのとき，いろんなアルゴリズムは結果の正確さについてどの程度の耐性があるだろうか？で，数字列を正準化するいくつかの方法を比較してみたら，クイックソート < マージソート ≪ バブルソートということでバブルソートが圧勝ということです． クイックソートとマージソートは正準化の高速アルゴリズムで，バブルソートは遅い手法としての地位を確立（？）しています．速さは，如何に比較の回数を削減するかとか，一回の比較あたりでどれだけ遠く離れだ数同士を交換するかに由来しています． でも，正確に動作すると思っていた比較演算があ
焼き鈍し法(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
paizaオンラインハッカソンPOH![ポー！]中間レポート――1週間で1万5,000ものコードが提出される！｜gihyo.jp … 技術評論社
paizaオンラインハッカソンPOH![ポー！]中間レポート――1週間で1万5,000ものコードが提出される！ 2013年12月2日より開始したpaizaオンラインハッカソンVol1「新人女子の書いたコードを直すだけの簡単なお仕事です！」ですが、おかげ様で1週間で15,000ものコード提出を頂けています。今回は皆さんのチャレンジの様子について中間レポートをお届けします。 paizaオンラインハッカソンVol1 https://paiza.jp/poh/ec-campaign paizaオンラインハッカソンとは？ 「paizaオンラインハッカソン（略してPOH![ポー！]）」はオンラインで誰でも気軽に参加できるハッカソンを目指しているので、とくに会員登録などをしなくても参加できるような仕組みとなっています。このハッカソンは、1つの課題に対してどのようにコードを書くかより深く考えるきっかけ
![paizaオンラインハッカソンPOH![ポー！]中間レポート――1週間で1万5,000ものコードが提出される！｜gihyo.jp … 技術評論社](https://cdn-ak-scissors.b.st-hatena.com/image/square/eeffbd6a9e6e9b00e610b659b5185fee7ce49409/height=288;version=1;width=512/https%3A%2F%2Fgihyo.jp%2Fassets%2Fimages%2FICON%2F2013%2F1202_paiza.png)
新人女子プログラマの書いたコードを直すだけの簡単なお仕事です！ | paizaオンラインハッカソン（POH）
開発したいプログラム ECサイト内の2つの異なる商品（値段は同じでも構わない）を購入し、その合計価格が指定の価格以内で最大になる組み合せを探してください。 →問題詳細 新人女子プログラマの野田さんが途中まで書いたプログラム Item_a_b = 4500 // a+bの価格 Item_a_c = 500 // a+cの価格 Item_a_d = 2300 // a+dの価格 Item_b_a = 1240 // b+aの価格 Item_b_c = 5020 // b+cの価格 (中略) if Item_a_b == campaign_price print “AとBの組み合わせが最大！” if Item_a_b == campaign_price -10 print “AとBの組み合わせは-10円差でおしい！” if Item_a_c == campaign_price (以下略)
直列加算と並列加算でdoubleの足し算の結果が変わる話 - きしだのHatena
Javaに限った話ではないのだけど、Javaで並列加算が気軽にできるようになったので、気に留めておいたほうがいい話。 まず、次のようなコードを動かしてみます。 public static void main(String[] args){ double[] data = { 1.234E80, -1.234E80, 2, 3}; System.out.println(Arrays.stream(data).sum()); System.out.println(Arrays.stream(data).parallel().sum()); } 1.234×10^80と-1.234×10^80という、桁が大きくて符号の違う数を並べて、そのあとに2と3という1桁の数値を置いています。 これらを加算すると、1.234×10^80と-1.234×10^80は符号が違うだけなので、当然結果は0になります
マルコフ連鎖モンテカルロ法入門−1 - My Life as a Mock Quant
ネット上で見かけるマルコフ連鎖モンテカルロ法資料はどうも小難しいので、 マルコフ連鎖モンテカルロ法は全然難しくないということを伝えるべく平易に解説した資料を作ってみた。 ２状態離散モデルの解説を中心に、メトロポリス法の解説までを行った。 余裕があれば次は連続モデルや熱浴法・メトロポリスヘイスティング法の解説資料も作成したい。 マルコフ連鎖モンテカルロ法入門-１View more presentations from teramonagi .※ここで解説しているお天気推移モデルはオリジナルなものですので、数値・計算等にミスがある可能性が否めませんので、 ※もし間違いを見かけた方は優しく教えていただけると助かります。
俺的MCMCまとめ - yasuhisa's blog
12月くらいからMCMCの勉強しだして、いくつか代表的なアルゴリズムによるサンプリングをやったのでまとめておく。 Example of Rejection Sampling - yasuhisa's blog Example of importance sampling - yasuhisa's blog Example of Metropolis Hastings Algorithm - yasuhisa's blog Metropolis Hastings Algorithmの続き - yasuhisa's blog Gibbs Sampler Algorithmによって多変量正規分布からのサンプル抽出を行なう - yasuhisa's blog あとはモデルによって色々変わるけど、根幹となるアルゴリズムはできたからまあよいか。 これで一応自分で作れるという感じにはなったので、MCMC
第3回電王戦用Ponanza提出 - 毎日がEveryDay！
20:54先ほどドワンゴ様の方に第3回電王戦出場用Ponanzaを提出しました。評価関数などに乱数を加えた実装です。純粋なPonanza vs. 乱数を加えたPonanzaの試合結果は522-430乱数を加えたPonanzaがわずかに弱くなっていますが、対人戦で研究にはまらないために仕方のない経費という認識です。 実はPonanzaとBlunderを交互に指すという案もあり、実際にドワンゴ様の方からも許可を頂いていたのですが、やはり屋敷九段はとんでもなく強いという予想をしてやめました。 ちなみに、今回提出したPonanzaの強さは、クラスタが使えないことを差し引いても第二回電王戦で佐藤慎一四段と戦ったPonanzaより強いです。つまり（第三回電王戦Ponanza＋PC一台 ＞ 第二回電王戦Poannza＋PC10台）ということです。ソフトウェアによるコンピュータの強さの上昇も結構なものなん
ゲーム理論
ゲーム理論 はジョン・フォン・ノイマン が開発したとされ，経済学の分野で発展してきたものです。 このゲーム理論は，生物学においても積極的に利用され， 進化ゲーム理論として発展してきました。 経済学においては， 各個人が最大化するように努めていると仮定される量は効用と呼ばれます。 これは，各人がさまざまな結果に対して持つ好みを表わすものです。 その結果，経済行動がうまく説明できるような効用関数を構成することができても， 観測された行動とは独立に効用関数を測定することはできません。 これに対して，生物学におけるゲーム理論では， 最適化すべきは遺伝子頻度の動態という自然過程が求められているため， 生涯を通じての繁殖成功度が個体の行動の良さを測る利得関数とみなされます。 生物が従わなければならない制約には，エネルギーの保存，活動時間の制約， 生化学反応の効率など，物理的，化学的， 個体の行動上の決
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Simulated Annealing
нiяоко iп пеtщоякs on Twitter: "プログラミングと数学を合わせると面白い！PHPとモンテカルロ法で円周率を近似してみた #PHP｜CodeIQ MAGAZINE https://t.co/lvjFtXUQmy via @codeiq"
SimulatedAnnealing - KLab Public Wiki
Modern Heuristic Techniques for Combinatorial Problem
まーす on Twitter: "http://t.co/6YJQ0OAz0R アルゴリズムの解説がスライドと音声で置いてる？(英語)"
Ryoma Sin'ya on Twitter: "後輩が言ってた『来年出る「The Art of Counting 」』という本はこれのことか． http://t.co/wIVcMxI0C2 #書名を正確に覚えられない人いるいる"
http://www.singularpoint.org/blog/r/importance-sampling-1/
プログラミング体験ゲーム：アルゴロジック ｜ JEITA
Virtual Arena: Room 1680