遺伝アルゴリズムによる NQueen解法 ~問題特性に着目した突然変異方法の改善~

Slides:



Advertisements
Similar presentations
N クイーン問題 N×N のチェス盤の上に、将棋の飛車と角 行の動きを同時にできる駒(クイーン) をお互いに動きを妨げないように N 個置 け。
Advertisements

多目的GAに対する パレート最適個体の分布制御 九州大学大学院工学府知能機械システム専攻徳井 宏司.
情報基盤アルゴリズムとして のメタヒューリスティクスの 研究 茨木俊秀、巳波弘佳、藤原洋志、 千葉英史、関口良行(関西学院大 学)、 藤重悟(京都大学)、 柳浦睦憲(名古屋大学)、 野々部宏司(法政大学)、 梅谷俊治(電気通信大学)
三木 光範 (同志社大学工学部) 廣安 知之 (同志社大学工学部) 花田 良子 (同志社大学工学部学部 生) 水田 伯典 (同志社大学大学院) ジョブショップスケジューリング問 題への 分散遺伝的アルゴリズムの適用 Distributed Genetic Algorithm for Job-shop.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
福岡工業大学 情報工学部 情報工学科 種田研究室 情報工学科 種田研究室 樽美 澄香 [C8] 対話型遺伝的アルゴリズム( IGA )による 色弱者向けの Web ページ配色最適化システム 2009 年 2 月 20 日.
世帯マイクロデータの適合度評価における 重みの決定手法
磁歪素子を用いた3軸球面モータの 駆動原理と特性評価
ユーザーイメージ収集 インターフェイスの開発
遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類
リフレッシュ型分散遺伝的アルゴリズムの 組み合わせ最適化問題への適用
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
グローバルコンピューティング環境における遺伝的アルゴリズムの検討
キャッシュ付PRAM上の 並列クィックソートと 並列マージソート
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
LZ圧縮回路の設計とハード・ソフト 最適分割の検討 電子情報デザイン学科 高性能計算研究室 4回生 中山 和也 2009/2/27.
遺伝的アルゴリズム  新川 大貴.
対話型遺伝的アルゴリズムを用いた室内レイアウトシステムの開発
遺伝的アルゴリズム概説 An Outline of Parallel Distributed Genetic Algorithms
PCクラスタにおける2個体分散遺伝的アルゴリズムの高速化
群論とルービックキューブ 白柳研究室  水野貴裕.
神奈川大学大学院工学研究科 電気電子情報工学専攻
Korteweg-de Vries 方程式のソリトン解 に関する考察
時空間データからのオブジェクトベース知識発見
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
情報工学科 05A2301 樽美 澄香 (Tarumi Sumika)
リンクパワーオフによる光ネットワークの省電力化
制約条件の確率的選択に基づく 資源追加削減法の改良 三木 光範(同志社大工) 廣安 知之(同志社大工) ○小林 繁(同志社大院)
情報工学科 05A2301 樽美 澄香 (Tarumi Sumika)
画像処理ボード上での 高速テンプレートマッチングの 実装と検証
ネットワーク性能に合わせた 分散遺伝的アルゴリズムにおける 最適な移住についての検討
MPIを用いた並列処理 ~GAによるTSPの解法~
MPIを用いた最適な分散処理 情報論理工学研究室 角 仁志
遺伝的アルゴリズムへの 統計力学的アプローチ 大阪大学 大学院理学研究科 鈴木譲 CISJ2005 於早稲田大学理工学部
蛋白質立体構造の進化的解析のための Ninf版並列MGGとその性能評価
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
テトリスにおけるAI の開発 情報論理工学研究室 13— 川原 翔太.
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
シミュレーション学講義 第**回 スケジューリング問題とJSSP.
遺伝的アルゴリズムを用いた 構造物の最適形状探索の プログラムの作成
通信機構合わせた最適化をおこなう並列化ンパイラ
進化的計算手法の並列計算機への実装 三木 光範
配牌時の役満和了率 を考慮した麻雀AIの開発
分子生物情報学(2) 配列のマルチプルアライメント法
Environment Risk Analysis
遺伝的交叉を用いた 並列シミュレーテッドアニーリング 同志社大学工学部/大学院 廣安知之,三木光範,○小掠真貴
シューティングゲームにおける 弾道予測アルゴリズムの作成
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to
数独の解生成と 解に対する番号付け 理学部 情報科学科 渡辺研究室 戸神星也.
サポートベクターマシンを用いた タンパク質スレッディングの ためのスコア関数の学習 情報科学科4年 81025G 蓬来祐一郎.
Genetic Algorithm-based Partial Least Squares GAPLS Genetic Algorithm-based Support Vector Regression GASVR 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
適応的近傍を持つ シミュレーテッドアニーリングの性能
3次元Nクイーン問題の 解の存在の検証 07-1-037-0106 前波 大貴 情報論理工学研究室 宜しくお願いします。
ウィルスって どの位感染しているのかな? 菊池研究室  小堀智弘.
コーディングパターンの あいまい検索の提案と実装
ベイズ最適化 Bayesian Optimization BO
Introduction to Soft Computing
Data Clustering: A Review
遺伝的交叉を用いた 並列シミュレーテッドアニーリングによる タンパク質立体構造予測
ビット空間における GAの解探索モニタリングシステム
設計情報の再利用を目的とした UML図の自動推薦ツール
指導教員 石水 隆 講師 情報論理工学研究室 木ノ下 翔大
表紙 分散遺伝的アルゴリズムのための 新しい交叉法.
BSPモデルを用いた 並列計算の有用性の検証
半正定値計画問題(SDP)の 工学的応用について
情報工学科 05A2301 樽美 澄香 (Tarumi Sumika)
分散遺伝的アルゴリズムにおけるパラメータの検討
各種荷重を受ける 中空押出形成材の構造最適化
Presentation transcript:

遺伝アルゴリズムによる NQueen解法 ~問題特性に着目した突然変異方法の改善~ 08-1-037-0092 瀬渡 昭良 情報論理工学研究室

目次 背景 問題提起 研究内容 実行結果 考察 結論 今後の課題

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

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

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

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

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

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

NQueen問題とは 古典的なパズル問題 N=8 解 92個 縦横斜めで重なる 駒の数を競合数

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

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

研究内容 選択・交叉の改良 突然変異の改良 遺伝補修飾の改良 高速化による改良

現在の突然変異の問題点 状態変異の突然変異では問題ないか? 集団内に最適解が出現した際の突然変異に問題 はないか? 全ての遺伝子の突然変異発生率が同じというこ とに問題はないか? 同一遺伝子が重複発生している場合、同じ突然 変異率で問題ないか?

状態変異の問題点 状態変異の問題点 競合数が増えてしまう

状態変異の改良 状態交換に変更 縦の競合が発生しなくなる

最適解発生時の突然変異の問題点 最適解が集団内にあらわれたら 1つの最適解に収束してしまう可能性大 競合数 0 競合数 8 競合数 5 競合数 0 競合数 8 競合数 5 競合数 8

最適解発生時の突然変異の改善 強制的に突然変異を発生させてやる

全ての遺伝子の突然変異率が同じ 問題点 競合数1と競合数10の遺伝子の突然変異率が同じ

全ての遺伝子の突然変異率が同じの改善点 許容競合数の設定 競合数によって補正値をつけてやる 競合数 2 競合数 8 小 大 突然変異発生率

同一遺伝子重複発生時の問題 同じ遺伝子が何世代も存在し続ける 同じ部分解しか存在しない パターンA パターンB パターンE パターンD パターンC

同一遺伝子重複発生時の改善 発生回数のカウント 発生回数が一定の値を超えると発生確率に補正 がはいる

実行結果

考察 わかったこと 安定して解の生成ができていた 問題点 全解探索にわずかに届かなかった

結論 アルゴリズムの改良が必要 最適解からの脱出が必要 同一部分解の生成を避けるべき

今後の課題 集団数と世代数を増やさずに全解探索を行う 進化過程に注目すべきか

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