読者です 読者をやめる 読者になる 読者になる

Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

GAでナップサック問題

3ヶ月研修

マッチ箱の脳(AI)―使える人工知能のお話』を読んでいるのですが、分かりやすくて面白い本です。遺伝的アルゴリズム(GA)という言葉は聞いたことがあるのですが、本書を読んで概要は理解できたような気がします(多分)…。

本当にGAで問題が解けるのか確かめてみたくなり、

に掲載されているナップサック問題に取り組んでみました…。

プログラムはRubyでおおまか書いてしまったのですが、うまく解けないところをみると、まだまだ改善しなければならないようです…。多分、選択のところが今のままではダメっぽいです。

疑問点など

上記のサイトでは、ナップサックに入る最大重量を40kgとしていますが、この大きさだと、ほとんどのというか全ての染色体の適応度は、1になる可能性が高く、次の世代を作る「選択」の作業が難しいような気がします。染色体を初期化するとき、乱数(0と1)を使いますが、0が大目に出るように仕向けた方がいいのではという気もしますが、これだと、ちょっといんちきっぽくなってしまうのでしょうか…。

GAでは、

  1. 評価関数を使って適応度を求め
  2. 遺伝子を選択して交叉を行い
  3. 突然変異を起こして

というサイクルを繰り返します。

  • このループはどこで止めればいいのか。
  • 交叉はどれくらいやればいいのか。

など、疑問点はありますが、来週、いろいろ試してみようと思います。