GAに関する課題

[kokoro]

問題
1から8までの数字をいくつか選び、その合計が20になるようにするにはどのように
選べばよいか？選ぶ数字は1種類につき1つまでとする。

という問題を解くGA（個体数8）のプログラムを作り、その結果を報告する。
適応度ｆは、合計値をｓとして、次の式で求めるものとする。
　
　　　　　ｓ　　　　(ｓ≤ 20)　
　　ｆ＝{
　　　　　2*20-ｓ　 (s > 20)

どうやってプログラムを書いたらさっぱりわかりません。
どなたかアドバイスをお願いします。

os:windows
コンパイラ名：bcc

[Mist]

遺伝的アルゴリズム(GA)については理解できていますか？
それもわからないということであれば丸投げになってしまいますけど。

http://home.interlink.or.jp/~kumagai/genealg.htm

[abc]

質問１～８の数字をいくつでも選べる？？
例、３選ぶ、４選ぶ、８選ぶ、合計は１５なので、５を足せば２０になることを教える？

逆に合計２３の場合はー３すれば２０になることを教える？

[abc]

－３は考えなくていい見たいですね、GAがいまいち分からないので調べて見ます。
前の投稿はスルーで

[abc]

アルゴリズム見たんですが、いまいち分かりませんでした笑
結局a[8] = {1,2,3,4,5,6,7,8};
いれてループで一個ずつ見ればいいのでは？
間違ってることを言ってる可能性６５％なので読み流しでOK

[kokoro]

GAについては何となくわかっているという感じです。

プログラムをどうやって書けばいいのかわかりません。
1から8までをランダムにすることぐらいしか…。

[Mist]

いきなりプログラムを書こうとせずに、処理の流れを文章で書いてみるのがいいと思います。
既にできているというのであればそれを見せてください。(で、以下は無視してください)


参考に出したHPの書き方を真似ると(途中まで)

1．初期集団の生成
１～８までの数字で構成される個体を8個生成する。
このとき、同じ数字を2回使用している個体は除く。

2．適応度の評価
各個体の数字の合計を計算し適応度を求める。
合計が20となるパターンが一つだけ判ればいいのであれば、20になる個体があれば終了。

3．選択
ランダムに2個の個体を選択する。
このとき、適応度の高い個体は選択されやすく、低い個体は選択されにくくする。

・
・
・

この問題はGAでよくみられるナップサック問題の亜種ですので、その辺でググられるといろいろ勉強になると思います。

[mats]

最初の世代はランダムに選びます．
ここでは1～8の数字を高々1回しか使わないので、各個体は8つのフラグ（遺伝子）を持てばいいことになります．
フラグが1ならその数字を使う，フラグが0なら使わないという感じです．
それを個体数だけ用意します．

後はGAの基本的な流れに沿って評価，次世代の決定を繰り返せばいいかと

Wikipedia の「遺伝的アルゴリズム」のページにある，SGAというのが参考になるかもしれません．

[nanashi]

http://www.morikita.co.jp/soft/8242/
を見れば参考になるのでは

[kokoro]

皆さんありがとうございます。

皆さんのアドレスを元にやってみます。

[たいちう]

アドバイスが少し錯綜気味なので、まとめのつもりで書きます。

プログラムの流れとしては、Mistさんの説明の通りでよいと思います。
ただし初期集団の生成において、このままでは、全ての個体の適応度が
4（1～8までの合計を評価式に代入）になってしまいます。

遺伝子の表現はmatsさんの形式のものが最もシンプルだと思います。
（その他のパターンとしては、0～8までの値を取りうる配列要素を8つ持つ遺伝子で、
0以外の数値は重複不可とか。）


> GAについては何となくわかっているという感じです。

ナップサック問題等を授業で習い、課題としてこの問題が出たのでしょうか？
基本をある程度理解する前に応用問題に取り組んでも時間の無駄だと思います。
まずは、授業で説明のあった基本的な問題について、プログラムを作れるようになって下さい。
そのような説明はなかったよーという場合は、ナップサック問題がお勧めです。
最も易しいし、この問題の原型でもあるので。


アルゴリズムを理解しているかどうかの判定の目安の1つですが、
理解できたと思ったら、本を閉じて、自分でプログラムを1から書いてみてください。
Cの文法や関数の使い方が分からない場合にリファレンスを見るのは良いですが、
それ以外のカンニングは禁止です。

よほど記憶力の良い人は別ですが、当たり前のようにこれができるならば、
そのアルゴリズムを十分理解しているとみなして良いでしょう。
慣れてくれば、本を読むだけでアルゴリズムのアイデアを理解し、
数ヶ月後や数年後に思い出してプログラムを書けますよ。
残念ながら書けない事も少なくないですが。


理解度の判定のより良い目安は、応用できるかどうか、というものです。
しかし応用問題を考えないといけなくて、簡単すぎたら無意味だし、
難しすぎたら手に負えないし、一人では難しい場合も多いでしょうね。