進化計算におけるOneMax問題のMarkov連鎖を用いた収束時間解析
スポンサーリンク
概要
- 論文の詳細を見る
進化計算を実際の問題に適用する場合,その計算時間を予測することは非常に重要である.本論文では,OneMax問題の収束時間をMarkov連鎖モデルを用いて解析した結果について報告する.最初に,OneMax問題の進化過程をMarkov連鎖モデルの1つであるWright-Fisherモデルを用いて記述し,その遷移行列を計算する.次に,集団が連鎖平衡にある場合,OneMax問題が非対称突然変異モデルと同等であることを示す.非対称突然変異モデルは集団遺伝学でよく研究されており,遷移行列の固有値はすでに知られている.我々は,その結果からOneMax問題における遷移行列の固有値の解析的な形を導いた.Markov連鎖の定常状態への収束時間は,遷移行列の2番目に大きい固有値を用いることで理論的に予測することができる.得られた理論的予測値と平均適応度の収束時間を実験的に比較し,良い一致が得られること示す.
- 2013-08-21
著者
-
古谷 博史
宮崎大学工学部
-
坂本 眞人
宮崎大学工学部
-
張 玉安
宮崎大学大学院農学工学総合研究科
-
安永 和馬
宮崎大学工学部
-
張 玉安
中国青海大学コンピュータ技術・応用工学科
-
古賀 仁信
宮崎大学大学院工学研究科
-
馬 青蓮
宮崎大学大学院農学工学総合研究科
関連論文
- フラダンス衣装用デザインプログラム作成の試み
- 3次元コンピュータグラフィックスを用いたドライビングシミュレータのプログラムの実装
- 3次元コンピュータグラフィックスによる簡易的なドライビングシミュレータに関するプログラムの試作
- 遺伝的アルゴリズムにおける最適解がはじめて出現する世代数の実験的解析
- 遺伝的アルゴリズムにおける最適解出現分布のマルコフ連鎖による研究
- 遺伝的アルゴリズムにおける最適解出現分布のマルコフ連鎖による研究
- 遺伝的アルゴリズムにおける最適解出現確率に及ばす突然変異の効果
- パーティクルシステムによる水の表現の試み
- 経営戦略におけるドメインコンセンサスの実証研究
- 3次元CGによるフラ衣装用デザインプログラムの試作
- 単眼立体視によるコンピュータビジョンに関する基礎研究
- A-017 多変量解析を用いた血友病Bの研究(モデル・アルゴリズム・プログラミング,一般論文)
- アミノ酸変異がタンパク質機能に及ぼす影響の評価 : アミノ酸相同性行列の比較
- 5N-1 全称状態のみの交代性コオペレーティング有限オートマトンシステムに関するある性質について(アルゴリズム,学生セッション,ソフトウェア科学・工学,情報処理学会創立50周年記念)
- 遺伝的アルゴリズムにおける交叉の役割の連鎖解析
- 2K-2 遺伝的アルゴリズムにおける最適解の出現世代数の予測
- 産業技術領域における総合的教育システムの開発
- 遺伝的アルゴリズムにおける最適解出現世代数のマルコフ連鎖による予測
- 遺伝的アルゴリズムにおける最適解出現分布のマルコフ連鎖による研究
- 遺伝的アルゴリズムにおける最適解出現世代数のマルコフ連鎖による予測
- ラグランジュ補間法を用いた解像度変換に関する考察
- フラダンス衣装用デザインのためのプログラム開発
- 遺伝的アルゴリズムにおける確率的揺らぎの効果 : スキーマの固定と消滅(進化的計算, 第11回MPSシンポジウム: 複雑系の科学とその応用)
- 遺伝的アルゴリズムにおける確率的揺らぎの効果 : スキーマの固定と消滅
- 再帰的な形式文法とCGによる花序の描写について
- コンピュータアニメーションの中割りアルゴリズムに関する一考察
- シーン認識の周波数依存に関する実験的研究
- 単色イメージスケールを用いた3配色プログラムのアルゴリズムに関する研究
- 極限周期軌道理論に関する一考察
- ニューラルネットワークを用いたDNA突然変異によるスプライシング異常の解析
- 三次元経営戦略モデルの研究開発
- マツダ系列企業のセントラリティの時系列分析
- D-17-2 マツダ企業グループのセントラリティの時系列分析(D-17. ソフトウェアインタプライズモデリング,一般セッション)
- セルラオートマトンによる海上交通の複雑さに関する考察
- 画像処理による似顔絵作成に関する研究
- サポートベクターマシンを用いた血友病Bデータベースの解析-アミノ酸置換の第IX因子活性への影響-
- OneMax問題と非対称突然変異の関係について
- 項目反応理論を用いたプログラミングテストの分析
- レイのデザイン用プログラムの試作
- 速度レーン道路標示を再現した簡易的なドライビングシミュレータの試み
- OpenGL による布アニメーションの試み (第II報)
- マツダ企業グループにおける個別企業の重要度の研究
- フラクタル次元を用いた企業行動の実証研究
- 物体との衝突を考慮した布アニメーションの試み
- カラリゼーションに関する基礎的研究
- アパレル用型紙作成プログラムの検討
- 生地デザイン用プログラムの試作
- 決定性トップダウンピラミッドセルラジェネレータによるテクスチャ生成に関する基礎的研究
- 色彩設計を支援するプログラムに関する研究
- OneMax問題における収束時間予測法の検討
- 生物種間の配列類似性を利用した血友病第IX因子遺伝子の解析
- Javaによる簡易的な3次元CGの試作に関する研究
- プログラミング学習のデバッグ段階に影響を与える要因
- OpenGLによる布アニメーションの試み(第III報)
- アパレル用型紙自動生成に関する基礎研究
- 囲碁のUCTアルゴリズムに関するシミュレーションプログラムの試作
- 時空間最適化フレームワークと粒子群最適化法によるインタラクティブ物体追跡システム
- メレによるフラ衣装用デザインプログラムの試作
- レイのデザイン用プログラムの試作(第II報)
- 進化計算におけるOneMax問題のMarkov連鎖を用いた収束時間解析
- 進化計算におけるOneMax問題のMarkov連鎖を用いた収束時間解析
- (1+1)EAのマルコフ連鎖モデルによる分析
- (1+1)EAのマルコフ連鎖モデルによる分析
- 3次元有限オートマトンと3次元層を持った時間限定ボトムアップピラミッドセルラアクセプタの受理能力の関係
- ONEMAX問題における成功確率
- タンパク質の立体構造を利用した遺伝病の解析
- 生物種間の配列類似性を利用した血友病第IX因子遺伝子の解析
- 進化計算におけるOneMax問題のMarkov連鎖を用いた収束時間解析
- A-20-1 AR技術を用いた仮想フラ楽器の検討(A-20.スマートインフォメディアシステム,一般セッション)
- A-4-2 カラリゼーションソフトに関する基礎的研究(A-4.信号処理,一般セッション)