| 講演名 | 1996/3/14 報酬つきマルコフ過程を用いた遺伝的アルゴリズムの挙動解析 松井 和宏, 小杉 幸夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 報酬つきマルコフ過程を用いた遺伝的アルゴリズムの挙動解析法を提案し, 簡単なモデルについて実際に個体群の期待最大適応度・期待平均適応度を導出する. 報酬つきマルコフ過程は, 系が状態推移に応じた報酬を受けるマルコフ過程の拡張であるが, 状態推移による個体群の適応度の変化を報酬とみなすことで適応度推移の期待値を導くことができる. この値は世代数の関数として表され, シミュレーションなどを行なうことなく算出可能である. 本報告では, 小規模なcount-one問題や最小だまし問題などの基礎的な問題について期待適応度を導出し, その結果に基づいて, 突然変異率の最適値に関する考察や, ランダムサーチとの比較によるGAの有効性の検証を行なう. |
| 抄録(英) | We propose a method to analyze the behavior of Genetic Algorithms (GAs) using Markov processes with rewards, which are extensions of Markov processes by introducing a concept of rewards. We derive the expected maximum and mean fitness values concerning simple GA models. These values are explicitly expressed as functions of generations and can be calculated without simulations, even for the generations at infinity. We analyze a simple count-one problem and a minimal deceptive problem. We then discuss the optimum mutation rate and compare GA and random-search to show the effectiveness of GAs. |
| キーワード(和) | 遺伝的アルゴリズム / マルコフ過程 / 報酬 / 期待適応度 / 突然変異率 |
| キーワード(英) | Genetic Algorithms / Markov Processes / Rewards / Expected Fitness / Mutation Rate |
| 資料番号 | AI95-64,KBSE95-52 |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 1996/3/14(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 報酬つきマルコフ過程を用いた遺伝的アルゴリズムの挙動解析 |
| サブタイトル（和） | |
| タイトル（英） | An Analysis on the Behavior of Genetic Algorithms by Markov Processes with Rewards |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 遺伝的アルゴリズム / Genetic Algorithms |
| キーワード(2)（和/英） | マルコフ過程 / Markov Processes |
| キーワード(3)（和/英） | 報酬 / Rewards |
| キーワード(4)（和/英） | 期待適応度 / Expected Fitness |
| キーワード(5)（和/英） | 突然変異率 / Mutation Rate |
| 第 1 著者 氏名（和/英） | 松井 和宏 / Kazuhiro Matsui |
| 第 1 著者 所属（和/英） | 東京工業大学総合理工学研究科 Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 小杉 幸夫 / Yukio Kosugi |
| 第 2 著者 所属（和/英） | 東京工業大学総合理工学研究科 Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology |
| 発表年月日 | 1996/3/14 |
| 資料番号 | AI95-64,KBSE95-52 |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 573 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |