蟻コロニー最適化 - Wikipedia
蟻コロニー最適化の概念図 蟻コロニー最適化（ありコロニーさいてきか、Ant Colony Optimization、ACO）とは、Marco Dorigo が 1992年の博士論文で提案したアルゴリズムであり、グラフを使ってよい経路を探すことで単純化できるような計算問題の確率的解法である。これはアリがコロニー（＝群れ）から食物までの経路を見つける際の挙動からヒントを得たものである。 実世界では、アリは始めランダムにうろつき、食物を見つけるとフェロモンの跡を付けながらコロニーへ戻る。他のアリがその経路を見つけると、アリはランダムな彷徨を止めてその跡を辿り始め、食物を見つけると経路を補強しながら戻る。 しかし、時間とともにフェロモンの痕跡は蒸発しはじめ、その吸引力がなくなっていく。その経路が長いほどフェロモンは蒸発しやすい。それに対して、経路が短ければ行進にも時間がかからず、フェロモンが蒸発す
ALGORITHM NOTE ナップザック問題 Knapsack Problem
大きさ w と価値 v を持った品物が N 個あり、これらを大きさ W のナップザックに入れたいとします。このとき、大きさの合計が W を超えず、価値の合計が最大になるような品物の組み合わせを求めたい。これがナップザック問題です。各品物を「選択する」か「選択しない」かの組み合わせなので、厳密には0-1ナップザック問題ともいいます。(各品物が複数個ある場合は、0123ナップザック問題と呼ばれます) この問題を力任せで解こうとすれば、N 個の品物を「選択する」か「選択しないか」の全組み合わせを全て調べることになるので、計算効率は O(2N) となります。N が数十個でも、実用的な時間では計算できません。 品物の大きさ w、ナップザックの大きさ W がともに整数であれば、ナップザック問題は動的計画法により O (NW) の効率で厳密解を求めることができます。 C[i][w] が、大きさ w のナ
SoftComputing lab.
遺伝的アルゴリズム 用語集 遺伝的アルゴリズム（ＧＡ） Genetic Algorithm 遺伝的アルゴリズムとは、生物の進化の過程をまねることでソフトウェアの最適化を図る手法です。考え方としては、遺伝と、自然淘汰を繰り返すことによって、より優秀なアルゴリズムを導き出そうというものです。 遺伝的アルゴリズムは、はじめに異なった遺伝子を持ついくつかの初期集団を用意し、そのなかで、選択（selection）、交差（crossover）、突然変異（mutation）の３つのプロセスを行います。選択とは、集団の中から優秀なものを選び出すことです。交差とは、選び出された集団のなかでランダムに遺伝子の一部を交換を行うことです。突然変異とは、低い確率で起こり、遺伝子情報の一部をランダムに書き換えることです。具体的には、以下のような流れになります。 １．もとになるアルゴリズムをいくつか用意する。 ２．個
SRM162-DIV2-250
最小と最大の数を与えられた時にそのレンジの数の最小公倍数を求める。 順繰りにかけていって、その際に最大公約数で割ってく。最大公約数はユークリッドの互除法で。 def lcm(first,last): l =1 for i in range(first,last): l = l * i / gcd(l,i) return l def gcd(a,b): if(b==0): return a return gcd(b, a % b) print lcm(1,5) print lcm(4,5) print lcm(1,12) 実行 /usr/bin/python /Users/kzfm/python/lcmr.py 12 4 27720
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Math::ES - Evolution Strategy Optimizer
biais.org
moleculardesign.de
いま何行目？みたいなやつ - id:lopnor
