遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~

Slides:



Advertisements
Similar presentations
多目的GAに対する パレート最適個体の分布制御 九州大学大学院工学府知能機械システム専攻徳井 宏司.
Advertisements

©2008 Ikuo Tahara探索 状態空間と探索木 基本的な探索アルゴリズム 横形探索と縦形探索 評価関数を利用した探索アルゴリズム 分岐限定法 山登り法 最良優先探索 A ( A* )アルゴリズム.
三木 光範 (同志社大学工学部) 廣安 知之 (同志社大学工学部) 花田 良子 (同志社大学工学部学部 生) 水田 伯典 (同志社大学大学院) ジョブショップスケジューリング問 題への 分散遺伝的アルゴリズムの適用 Distributed Genetic Algorithm for Job-shop.
世帯マイクロデータの適合度評価における 重みの決定手法
遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類
リフレッシュ型分散遺伝的アルゴリズムの 組み合わせ最適化問題への適用
到着時刻と燃料消費量を同時に最適化する船速・航路計画
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
グローバルコンピューティング環境における遺伝的アルゴリズムの検討
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
LZ圧縮回路の設計とハード・ソフト 最適分割の検討 電子情報デザイン学科 高性能計算研究室 4回生 中山 和也 2009/2/27.
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
遺伝的アルゴリズム  新川 大貴.
対話型遺伝的アルゴリズムを用いた室内レイアウトシステムの開発
遺伝的アルゴリズム概説 An Outline of Parallel Distributed Genetic Algorithms
PCクラスタにおける2個体分散遺伝的アルゴリズムの高速化
群論とルービックキューブ 白柳研究室  水野貴裕.
神奈川大学大学院工学研究科 電気電子情報工学専攻
モード付き並列機械における オンラインスケジューリング
Korteweg-de Vries 方程式のソリトン解 に関する考察
時空間データからのオブジェクトベース知識発見
情報工学科 05A2301 樽美 澄香 (Tarumi Sumika)
香川大学工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学工学部 富永浩之
リンクパワーオフによる光ネットワークの省電力化
マイクロシミュレーションにおける 可変属性セル問題と解法
情報工学科 05A2301 樽美 澄香 (Tarumi Sumika)
画像処理ボード上での 高速テンプレートマッチングの 実装と検証
ネットワーク性能に合わせた 分散遺伝的アルゴリズムにおける 最適な移住についての検討
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
Occam言語による マルチプリエンプティブシステムの 実装と検証
外部共有サーバーによる認証設定と そのセキュリティ問題に関する基礎的考察 施設設計工学研究室 馬場 健.
MPIを用いた並列処理 ~GAによるTSPの解法~
遺伝的アルゴリズムへの 統計力学的アプローチ 大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部
蛋白質立体構造の進化的解析のための Ninf版並列MGGとその性能評価
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
巡回冗長検査CRC32の ハード/ソフト最適分割の検討
シミュレーション学講義 第**回 スケジューリング問題とJSSP.
遺伝的アルゴリズムを用いた 構造物の最適形状探索の プログラムの作成
通信機構合わせた最適化をおこなう並列化ンパイラ
早わかりアントコロニー最適化 (Ant Colony Optimization)
Environment Risk Analysis
遺伝的交叉を用いた 並列シミュレーテッドアニーリング 同志社大学工学部/大学院 廣安知之,三木光範,○小掠真貴
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
数独の解生成と 解に対する番号付け 理学部 情報科学科 渡辺研究室 戸神星也.
Genetic Algorithm-based Partial Least Squares GAPLS Genetic Algorithm-based Support Vector Regression GASVR 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
顔特徴点移動量・点間距離変化量の組み合わせに基づく顔表情認識
適応的近傍を持つ シミュレーテッドアニーリングの性能
3次元Nクイーン問題の 解の存在の検証 07-1-037-0106 前波 大貴 情報論理工学研究室 宜しくお願いします。
Data Clustering: A Review
配送計画最適化システム WebMETROのご紹介
遺伝的交叉を用いた 並列シミュレーテッドアニーリングによる タンパク質立体構造予測
遺伝アルゴリズムによる NQueen解法 ~問題特性に着目した突然変異方法の改善~
遺伝的アルゴリズム (GA) を活用した スペクトルの波長選択および時系列 データにおけるプロセス変数かつその時間 遅れ (ダイナミクス) の選択 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
ビット空間における GAの解探索モニタリングシステム
全体ミーティング (5/23) 村田雅之.
設計情報の再利用を目的とした UML図の自動推薦ツール
表紙 分散遺伝的アルゴリズムのための 新しい交叉法.
シミュレーテッドアニーリングにおける 重要温度領域に関する考察
情報工学科 05A2301 樽美 澄香 (Tarumi Sumika)
分枝カット法に基づいた線形符号の復号法に関する一考察
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
分散遺伝的アルゴリズムにおけるパラメータの検討
参考:大きい要素の処理.
各種荷重を受ける 中空押出形成材の構造最適化
遺伝的交叉を用いた 並列シミュレーテッドアニーリングの検討 小掠 真貴 廣安 知之 三木 光範 角 美智子 岡本 祐幸 同志社大学大学院
Presentation transcript:

遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~ 08-1-037-0050 馬場 亮輔 情報理論工学研究室

目次 背景 問題提起 検証 研究内容 劣性遺伝子、完全遺伝子 結果 考察 結論 今後の課題

背景 遺伝的アルゴリズム 活用分野 集積回路の設計 スケジュール管理

遺伝的アルゴリズムとは 評価 画期的な方法 定式不要 式で定義する必要なし 遺伝子 突然変異 選択 交叉

遺伝的アルゴリズムの例 評価 世界で一番高いところは? 座標 突然変異 選択 交叉

遺伝アルゴリズムの例 もし同じ高さのものが複数あったら

問題提起 複数の最適解が存在する場合 遺伝的アルゴリズムは使用できるか?

検証 複数の最適解が存在する問題 NQueen問題

NQueen問題とは 古典的なパズル問題 クィーンが互いに   取り合う組の数=競合数 右の例は競合数0

実行 評価 N=8 集団数100 試行回数1000 駒の配置 突然変異 選択 交叉

結果 発見できた解 1~0個 見つけられてない

研究内容 選択・交叉の改良 突然変異の改良 高速化による改良 新たな遺伝オペレーティングの追加

オペレーティング追加の問題点 改善方法の1つ 評価、タイミングが難しい 時間増 構造難化 加えないシンプルな方が良い

新しい手法 追加しない 今あるものだけ 遺伝補修飾の考案

遺伝補修飾とは 遺伝情報に性質を与える。 例:巡回セールスマン問題 巡回しなくてもよいことなど、巡回する地点自体に性質を与える。 遺伝アルゴリズムの例でよくあつかわれる巡回セールスマン問題を用いると

劣性遺伝子 初期に設定する集団の駒数を N未満にするという性質を加えた遺伝子

NQueen問題で使用した場合 駒がない状態を保持 競合数低下 近似解探索ができるのでは? 競合数3 →競合数2

劣性遺伝子の結果 近似解の生成

劣性遺伝子の考察 近似解を生成する効果がある。

完全遺伝子 盤上のある行の全てに駒が   配置される性質を持つ遺伝子

NQueen問題で使用した場合 すべての位置をとれる 探索範囲を狭めることが   できるのでは?

完全遺伝子の結果 発見する解に変化がなかった

完全遺伝子の考察 原因 着目 解は生成できているが、重複解を生成している そのため、解としてカウントされていない 解の個数は変わらない  そのため、解としてカウントされていない 着目 解の個数は変わらない ならば解が生成される早さは?

解が生成される早さ 解があまり生成されていないため、結果がわかりにくい 完全遺伝子消滅までに発見された解の中にある完全遺伝子の割合を調査。 共同研究者の開発した最も解が生成されるプログラムに完全遺伝を適用。 完全遺伝子消滅までに発見された解の中にある完全遺伝子の割合を調査。 N 初期集団数 終了世代数 選択方法 交叉方法 突然変異率 遺伝補修飾含有率 試行回数 8 100 1000 ルーレット選択 一点交叉 0.1 20%

完全遺伝子の考察 解が早い段階で生成    完全遺伝消滅までに発見された解に対する完全遺伝の割合

結論 新たに遺伝オペレーティングを用いず、遺伝補修飾という手法を用いてN-Queen問題の解探索を行った。 当初目的としていた解探索能力の向上とはいかなかった 劣性遺伝子では近似解の探索が行えた。 完全遺伝子においては解の生成速度向上が図れた。

今後の課題 遺伝補修飾の消滅が特に性能向上のカギ 集団内において、いかに一定量の遺伝補修飾を保つかが問題

おわりに ご静聴いただきありがとうございました