GA for Knapsack

最終更新日：2009.7.30

更新履歴

2001.2.6: makeの前に，必ず実行ファイル（kp.exe）とオブジェクトファイル（*.o）を削除してください．

2005.12.8: ソースを修正（バグ修正，価値と重量を読み込むように拡張）しました．アイテム毎の価値と重量は「15 6」のように半角スペースで区切って一行に書くようにしてください．サンプルソース内のKP_List.dataでは，1つ目のアイテムが「価値15,重量6」2つ目のアイテムが「価値100,重量20」という意味になります．

2008.7.16: 最大適応度時に重量を合わせて出力するように変更．作図方法でも両方を出力出来る例を追加しました．

2009.7.30: エリート保存をしない時の注意を追加しました．

目次
課題内容
実験環境とサンプルプログラム
ファイル構成
コンパイル例
実行方法
実行結果
最大適応度推移のグラフ表示方法
エリート保存をしない時の注意
参考（GAの流れ図）

■課題内容

GAでナップサック問題を解く．その際，（1）各遺伝子操作オペレータ（選択，交叉，突然変異）を実装した場合と，（2）実装しない場合，について実験を行い，得られた結果の違いから各オペレータの役割を考察せよ．

＜サンプルプログラムを用いた計算機実験について＞

サンプルプログラムは，ナップサック問題における価値・荷重リスト（KP_List.data,「価値加重」という形式で記述），制約条件（KP.h），探索終了条件（終了世代数）を与えることでGAにより探索を行うシミュレータです．探索の結果としては，各世代毎の集団及び適応度の表示，最大適応度の表示を行います．この適応度の推移や集団内の個体がどのように推移（収束・発散・etc）するのかを観察し，各オペレータの役割について考察してください．

サンプルプログラムは以下からダウンロードしてください．

~~ga-knapsack.tar.gz (2008.7.16)~~
突然変異の実装ミス，適応度計算時の無駄削除，重量と価値を別個に設定するように拡張．詳細は 0README_ja.txt 参照．
(2006-07-21) 適応度計算の実装ミスを修正．
(2008-07-16) 最大適応度時に重量を合わせて出力するように変更．作図方法でも両方を出力出来る例を追加しました．
naltoma/ga-knapsack
(2017-05-08) 荷重ファイル読み込み時のバグ（指定個数+1個余分に読み込み）を修正。

■環境

以下の環境にて動作確認済みです．

OS, compiler
BSD/OS 4.0.1, gcc version 2.7.2.1
Vine Linux 2.5, gcc version 2.95.3 20010315 (release)
Red Hat Linux 7.3.2, gcc version 2.96 20000731
Mac OS X 10.5.4, gcc version 4.0.1 (Apple Inc. build 5465)

■ファイル構成

1-1-KP_List.data-10		# 実行例
1-1-KP_List.data-10.end		# 実行例の最終結果
1-1-KP_List.data-10.max		# 実行例の最大適応度推移

KP_List.data	# 荷重ファイル(書式:int型で「価値 重量」を半角スペース区切りで列挙)
KP.h		# ナップサック問題の定義
parameter.h	# GAパラメータの定義

Makefile
KP.c		# 荷重ファイルを読み込む
calc_fitness.c	# 適応度計算
ga.c		# メイン関数
initialize_gene_binary.c	# 初期集団作成
kp.exe				# 実行ファイル
mutation_binary.c		# 突然変異
random2.c			# 乱数生成
roulette_selection.c		# ルーレット選択
singlepoint_crossover.c		# 一点交叉

run_ga.sh	# 実行結果の切り出し

問題設定を変更する場合には，KP_List.data, KP.h, parameter.h に変更を加えてください．

■コンパイル例

下記のように，make時に OPTION を指定することにより，どのオペレータを実装するのかを指定することが可能です．実行ファイル名は kp.exe です．

makeし直す場合には「make clean」を忘れずに！

選択+交叉+突然変異を実装
  prompt> make

選択のみ実装
  prompt> make OPTION="-DSELECTION"

交叉のみ実装
  prompt> make OPTION="-DCROSSOVER"

突然変異のみ実装
  prompt> make OPTION="-DMUTATION"

選択+交叉を実装
  prompt> make OPTION="-DSELECTION -DCROSSOVER"

選択+突然変異を実装
  prompt> make OPTION="-DCROSSOVER -DMUTATION"

■実行方法

実行時に，
1）初期集団作成用シード値（下記の例では1），
2）GAオペレータ用シード値（同様に1），
3）荷重ファイル（同様にKP_List.data），
4）終了世代数（同様に10）
を引数として指定する．

□例
prompt> run_ga.sh  1  1  KP_List.data  10

■実行結果

〜, 〜.max, 〜.end という3種類のファイルが作成される．「〜」はシード値や荷重ファイル名によって異なり，前述の実行例だと，「1-1-KP_List.data-10」となる．

〜：実験結果の全出力
〜.max：実験結果から，各世代毎の最大適応度（価値）と重量を切り出した結果
〜.end：実験結果から，最大適応度となる個体の出力結果

■最大適応度推移のグラフ表示方法

例えば，適応度推移グラフを tgif で表示・編集するためのファイル形式に変換するためには gnuplot を使用します．

(ケース1: 適応度推移のみ出力)
prompt> gnuplot
gnuplot> plot "1-1-KP_List.data-10.max" with line
gnuplot> set terminal tgif
gnuplot> set output "result.obj"
gnuplot> replot

上記の操作により result.obj というファイルへグラフ情報が出力されますので，後は tgif を使用して編集してください．

(ケース2: 適応度と重量推移を出力)
prompt> gnuplot
gnuplot> set title 'Fitness transition with the weight'
gnuplot> set xlabel 'Generation'
gnuplot> set ylabel 'Value'
gnuplot> set y2label 'Weight'
gnuplot> set terminal postscript
gnuplot> set output "rerulst.eps"
gnuplot> plot "1-1-KP_List.data-10.max" using 2 axis x1y1 'Value' with line, \
  "1-1-KP_List.data-10.max" using 3 axis x1y2 title 'Weight' wigh line

エリート保存をしない時の注意

parameter.h 内の「ELITE_COPY」を 0.0 にすればエリート保存をしなくなりますが，プログラムがそれを前提としていなかったため，出力結果が正しく出力されません．動作としては正しく（エリート保存せずに）動いています．

エリート保存をせずに，各世代毎の適応度推移を確認するためには， calc_fitness.c の83行目を以下のように変更してください．

変更前: printf(">> max_fitness = %d %d\n",all_max_fitness,all_max_weight);
変更後: printf(">> max_fitness = %d %d\n",fitness[index],*(weight+index));

これで，各世代毎の最大適応度が出力されるようになるはずです．

参考（GAの流れ図）

質問は當間まで．