c言語。 組み合わせ最適化問題の中でナップサック問題について質問です。 ナップサック問題を遺伝的アル

c言語。

組み合わせ最適化問題の中でナップサック問題について質問です。
ナップサック問題を遺伝的アルゴリズムで解くプログラムの書き方を教えてください。
・乱数をつかって下のデータを基に作りたいです。
・
母集団の個体数 100
・世代数 200
・突然変異率 0.01
・選択方法 エリート選択を使う
・エリート個体は2個体で残りの98個体はルーレット選択をする。

品物 価値 重さ
1 75 7
2 84 9
3 58 13
4 21 5
5 22 16
6 95 28
7 28 15
8 76 43
9 88 60
10 53 37
11 58 44
12 81 63
13 32 34
14 89 95
15 54 61
16 23 29
17 42 57
18 52 72
19 58 83
20 53 84
21 30 48
22 26 45
23 40 74
24 40 78
25 26 52
26 39 79
27 25 64
28 23 64
29 16 55
30 12 74
MAX 重さ = 744

質問者からの補足コメント

• ・遺伝子の長さは30。
  ・遺伝子座の値が1なら品物を入れて、0なら入れない。
  ・適合度は遺伝子座が１になっている価値の合計、ただし重さの合計が744を超えた場合は0。
  
  ・答え　
  最終世代のなかで適合度の最も高い個体を知りたいです。
  
  画像のようなグラフが書けるようにしたです。

  
    補足日時：2020/08/11 23:26

No.2 ベストアンサー 回答者： cametan_42 回答日時： 2020/08/11 23:02

なかなか面白そうな問題だな、ってんでWebに転がってる論文をいくつか読んでたんですが・・・。

結論から言うと、この問題は「解けません」。提示されてる条件が足りない。

っつーかね、個人的にも以前「ナップサック問題」ってのはプログラムした事があって、「フツーに問題設定して解くと」、恐らくこの問題の解は、

1番の品物、価値が 75、重さ 7が105個
2番の品物、価値が 84、重さ 9が1個

以上、ってなっちゃうのね。これでトータルの重さは「縛り」である744ピッタシ。終わり。

でも、この解は恐らくこの問題が求めてる解じゃないんですよ。

果てさて、キチンとこの問題における「条件」を理解していますか?

No.5 回答者： k-841 回答日時： 2020/08/19 12:33

目的は問題を解くことではなくてGAのプログラムを書くことと認識しました。

戦略的に、
＞・適合度は遺伝子座が１になっている価値の合計、ただし重さの合計が744を超えた場合は0。
このような評価関数を設定するあたり、真面目に解こうという気がないことは明白だと思います。

とすると、後はいくつかの不足した戦略を自分で決めて、機能ごとに関数を書くだけですね。
不足している戦略は、交差と世代交代ですかね。
　1点交差なのか、多点交差なのか、一様交差なのか
　交差によって出来上がる個体数はどうするのか（単純に2だけ作り親だけが死ぬか、もっとたくさん作って2個体だけ残すか、・・・）

これだけ決まれば、次の処理を作れば完成です。
・初期遺伝子群の生成
・交差対象の選定処理（ルーレット選択）
・交差処理
・突然変異処理
・個体の評価
・世代交代（どの個体を除外するかを決める）
一つ一つはそれほど難しい処理ではありません。

グラフを書きたいなら、世代数と最大スコアを1行で出力するだけです。
こんな感じ。
1 250
2 300
3 300
4 305
...
200 500
Excelに貼り付けてもいいし、gnuplotに描画させることもできます。

No.3 回答者： cametan_42 回答日時： 2020/08/12 00:28

> 画像のようなグラフが書けるようにしたです。

うん、やっぱ理解してませんね。
何故

> ・遺伝子の長さは30。
>・遺伝子座の値が1なら品物を入れて、0なら入れない。
>・適合度は遺伝子座が１になっている価値の合計、ただし重さの合計が744を超えた場合は0。

と言う条件が付加されざるを得ないのか。

一回Wikipediaのナップサック問題の項を読んでみて下さい。

ナップサック問題:
https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83 …

一般的に「ナップサック問題」と言った場合に想定されるもの、そして、「遺伝的アルゴリズム」で解かれるナップサック問題は限定的な条件が付いてるんじゃないか、と言う把握。
Wikipediaのナップサック問題の項目を一回良く読んでみましょう。貴方がまず「一番最初に」提示しなきゃいけない「特殊な」ナップサック問題に当てはまる条件が何なのか、ちょっと考えて下さい。

No.1 回答者： Tacosan 回答日時： 2020/08/10 02:42

どこまでできていてどこで困っている?