他力本願 ~情報術~

「人を動かす」ことを目標に情報発信術について 漫画やアニメ等の視点から書いていこうと思います。宜しくお願いいたします。

遺伝的アルゴリズム

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

遺伝的アルゴリズム

卒研の発表も終りひと段落着いたので
ナンバーズの予測プログラムを作成しようと思い
遺伝的アルゴリズムがどんなものなのか
マイクロソフトのページを見ながら作ってみたのだが上手くいかない・・・。
現状は追記に

遺伝的アルゴリズムとは
生物の進化の過程を模した最適化手法らしい・・・


遺伝的アルゴリズムの流れ

遺伝子を生成しそれらに適応度を算出する
適応度を基に適応度の高いものほど選択されやすいようにする
遺伝子を二つ選択し、その二つを交叉する
これらを繰り返すことにより適応度の高いものが生き残る
その生き残ったものを解とする

遺伝子の生成
  ↓
遺伝子の評価・淘汰←←←←
  ↓               ↑
遺伝子の選択         ↑条件を満たすまで
  ↓               ↑繰り返す
遺伝子の交叉         ↑
  ↓               ↑
遺伝子の突然変異→→→→→
  ↓
最適解の算出

今回の問題
巡回セールスマン問題
まずどんなものか知るためにマイクロソフトのページに載っていた問題を
行ってみた

巡回セールスマン問題とは
複数の都市を巡回するのにどのルートが最短の経路であるかを求める問題です

今回の設定
都市の数 4
遺伝子の数 100
何世代まで計算するか 50

今回作ったもの
遺伝子の生成
・乱数を利用し生成
 巡回する都市が重複箇所が出てそれが結果に影響し失敗
・0、1、2、3の数字の順番を乱数を利用し変更
 重複はなくなった

選択
・適応度に応じて選択される割合を多くし乱数を利用し選択
 適応度に基づく割合を与えたが適応度の低い個体の数の方が多いため
 最終的に適応度の高いものが消えてしまう
 
 例
 個体1 距離 5 割合 0.1  個数 30
 個体2 距離 6 割合 0.06 個数 30
 個体3 距離 6 割合 0.06 個数 30

    ↓
 個体1 割合 3
 個体2 割合 1.8
 個体3 割合 1.8

距離5の個体が選択する割合よりも
 距離6の個体が選択する割合の方が増えてしまう

交叉
・乱数で位置を決めその位置より前を交換

 例
 (親) 0011
 (親) 1001
 
 位置が2と3番目の間の場合
 (子) 1011
 (子) 0001

問題は特になし

今回の課題
選択方式に欠陥があるようなので改良が必要


感想
遺伝的アルゴリズムの方は何となく分ったが
ナンバーズに適用するためには
学習の仕方や評価方法などの検討が必要みたい・・・
スポンサーサイト

テーマ:プログラミング - ジャンル:コンピュータ

  1. 2006/02/27(月) 00:34:31|
  2. 未分類
  3. | トラックバック:0
  4. | コメント:0
<<もっとキャラを苛め抜いて欲しい | ホーム | 除霊ペンギンと女の子・・・変な夢見た・・・>>

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://kannnaduki.blog5.fc2.com/tb.php/83-46947a43
この記事にトラックバックする(FC2ブログユーザー)

FC2ブログランキングに参加中。
ご協力お願いします。



アクセスアップにブログジャンキー始めてみました。



このサイトの値段だそうです。


プロフィール

かんなづき

<>br

カテゴリー

<>br

最近の記事

<>br

最近のコメント

<>br

最近のトラックバック

<>br

月別アーカイブ

<>br

ブロとも申請フォーム

この人とブロともになる

<>br

ブログ内検索

RSSフィード

リンク

このブログをリンクに追加する





楽天で探す
楽天市場



ブログ(blog)ならFC2
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。