ソフトコンピューティング

ソフトコンピューティング
知能情報学
マッキン
ソフトコンピューティング
Soft Computing
• 従来手法では解析できないあるいは扱いにく
かった複雑な問題を取り扱う計算技法の総称
• ニューラルネットワーク、進化的計算、ファジィ
システムに代表される
• 不精密さ、不完全さ、不確実さを許容し、扱い
やすさ、頑強性、低計算コストを達成すること
を目的とする
• 実世界の複雑であいまいな問題の解決に重
要な役割を果たす
ハードコンピューティングとの対比
• ソフトコンピューティング
（柔らかい・柔軟・あいまい）
– だいたいの正解を求める
– 時間で打ち切る（早い）
– 間違う場合もある
• ハードコンピューティング（硬い・厳密）
– 厳密な解答を求める
– 時間がかかりすぎる・答えが出ない場合がある
進化的計算
Evolutional Computation
• 生物の進化からヒントを得ている（ロマン）
• 進化は
– DNAの突然変異によって多様性がうまれ
– 環境により適応した個体(DNA)が長く（強く）生き、
より多くの子供を産む
– 徐々に環境に適応した個体(DNA)が増える
– DNAの突然変異
を繰り返す
進化的計算フロー
1.
2.
3.
4.
5.
6.
初期集団生成
評価値計算
評価値に応じて選択（次の世代に残す）
複製（子供を産む）
遺伝子操作（突然変異・交差）
決められた世代数まで2)から繰り返す
迷路再び
ゴール
スタート
迷路の状態遷移図
1
3
ゴール
2
0
1
9
1
2
1
6
1
7
1
8
1
0
1
4
2
1
6
1
1
3
5
1
5
7
9
8
4
1
2
スタート
迷路の状態遷移図
1
3
ゴール
2
0
1
9
1
2
1
6
1
7
1
8
1
0
1
4
2
1
6
1
1
3
5
1
5
7
9
8
4
1
2
スタート
迷路の状態遷移図
ゴール
1
4
1
6
1
5
8
1
7
1
8
9
1
3
6
5
4
2
1
2
0
1
2
1
1
1
0
1
9
2
7
3
1
スタート
迷路の状態遷移図
• 各状態から「右」か「左」
が選べるとする
1
4
1
5
左
右
8
1
6
1
7
1
8
左
右
左
1
0
左
9
左
4
右
左
ゴール
2
1
9
2
1
2
0
左
右
1
3
1
2
1
1
右
左
5
右
右
6
7
左
右
右
左
1
右
スタート
3
遺伝子コーディング
• 迷路の脱出ルートを、「右」「左」の列で表現
• 例）左、左、左、右
• これを個体（解答の候補）の「遺伝子」とする
• 進化計算により、この遺伝子をより良い遺伝
子に変化させることにより、探索を進める
初期集団生成
• 集団の個体数を２個体とする
• 今回は、遺伝子の長さは４の固定長とする
• 初期集団を乱数で生成する
– 例）｛左、右、左、右｝｛右、左、右、右｝
進化計算で迷路脱出
• 次の迷路の脱出を進
化計算で行う方法を
考える
ゴール
スタート
評価値（適合度）計算
• そろぞれの個体に対して、評価値を計算
– 評価値は、どれだけ早くゴールしたか
– 2手なら2点、4手なら1点、ゴールしない場合は0
点
ゴール
（ゴール状態）
– 例) ｛左、左、右、左｝0点
｛右、左、右、右｝1点
２
４
左
右左
右
右
１
３
左
スタート
（初期状態）
選択
• 評価値に応じて次世代へ選択（複製）
今回は、評価値の高い方を選択
– 例) ｛左、左、右、左｝0点淘汰
｛右、左、右、右｝1点選択
• 新しい集団は
｛右、左、右、右｝｛右、左、右、右｝
突然変異
• 集団の個体の遺伝子を突然変異させる
– 例) ｛右、左、右、右｝
↓
｛右、右、右、右｝
• 新しい集団は
｛右、左、右、右｝｛右、右、右、右｝
評価値再計算
• 集団の個体に対して、評価値を再計算
– 例) ｛右、左、右、右｝1点
｛右、右、右、右｝2点
ゴール
（ゴール状態）
２
４
左
右左
右
右
１
３
左
スタート
（初期状態）
終了条件
• 進化の終了条件は
– 決まった世代数繰り返した
– 決まった精度の解答が得られた
のいずれかで終了
• 今回は、
– ｛右、右、右、右｝2点
が最良個体（解答）として選択された
出席確認問題①
• とある迷路を進化計算で解くシステムがある。
• ある世代の最良個体が以下であった。
最良個体㊨→㊧→㊨→㊨
• この個体から1点のみの突然変異で生成する
ことができる個体を全てあげよ。
• 個体の長さは４の固定長とする。
解答例
1.
2.
3.
4.
㊨→㊧→㊨→㊨から突然変異できる個体
㊧→㊧→㊨→㊨
㊨→㊨→㊨→㊨
㊨→㊧→㊨→㊨
㊨→㊧→㊨→㊨
確認問題②
• 進化的計算のフローチャートを書け
進化的計算フローチャート(例)
開始
初期集団生成
評価値計算
評価値に応じて選択
複製
遺伝子操作
決められた世代数？
false
true
終了

Download Report