Ｃでナップザック問題を遺伝的アルゴリズムで解くときに問題がありました。

###前提・実現したいこと
遺伝的アルゴリズムでナップザック問題を解こうとしてます。
しかし遺伝的アルゴリズムをプログラムするのは初めてだし、
プログラムが正しいか自信がないのでわからないところを質もします。
Visual Studio 2015でやりました。

###発生している問題・エラーメッセージ
エラーはでていませんが、実行して「初期集団決め→評価→選択→交叉→変異→評価→・・・」
の順にやっているんですが、実行結果を見ると所々で値が小さくなったりしてます。
これは問題ありということでしょうか？
例えば5世代目の値が「価:174」なのに６世代目になると「価値:150」みたいに落ちているということです。

###該当のソースコード
C言語とC++を併用してコーディングしました。交叉のところは一点交叉で行いました。
またそれ以外の欠陥、改善点があったらどうか教えてください。

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;

const int N = 100; //ナップザックの容量
const int M = 30; //品物の数
const int MAN = 10; //子孫の数

int Child[MAN][M]; //子孫の遺伝子情報
int Kati[MAN]; //子孫のそれぞれの価値
int Ryou[MAN]; //子孫のそれぞれの容積

//ナップザックに入れる物の情報。価値と大きさ
struct Mono {
int Money;
int ryou;
};
Mono mono[M];

void init(); //初期集団を決める
void hyoka(); //それぞれの個体の価値を集計
void sentaku(int *oya); /集団から次の世代を作るための親を決める。
引数のoya配列には親の添え字を保存する/
void Sex(int *oya); //sentaku関数で選んだ親から子孫を作る
void heni(); //突然変異を起こす
void show(); //それぞれの価値と大きさを表示

int main()
{
init();
hyoka();

int oya[2];
for (int i = 0; i < 1000; i++) {
	sentaku(oya);
	Sex(oya);
	heni();
	hyoka();
	show();
}

return 0;

}

void init()
{
//価値と大きさはランダムで決める
srand((unsigned int)time(NULL));

for (int i = 0; i < M; i++) {
	mono[i].Money = rand() % 20 + 1;
	mono[i].ryou = rand() % 10 + 1;
}

cout << "価値: ";
for (int i = 0; i < M; i++) {
	cout << mono[i].Money << ",";
}
cout << endl;

cout << "大きさ: ";
for (int i = 0; i < M; i++) {
	cout << mono[i].ryou << ",";
}
cout << endl;

for (int i = 0; i < MAN; i++) {
	for (int j = 0; j < M; j++) {
		Child[i][j] = rand() % 2;
	}
}

}

void hyoka()
{

for (int i = 0; i < MAN; i++) {
	Kati[i] = 0;
	Ryou[i] = 0;
}

int sum = 0;
for (int i = 0; i < MAN; i++) {
	for (int j = 0; j < M; j++) {
		if (Child[i][j] == 1) {
			sum += mono[j].ryou;
			if (sum > N) {
				Kati[i] = 0;
				break;
			}
			else {
				Kati[i] += mono[j].Money;
				Ryou[i] += mono[j].ryou;
			}
		}
	}
	sum = 0;
}

}

//ルーレット方式で親を決定する
void sentaku(int* oya)
{
int total = 0;
for (int i = 0; i < MAN; i++) {
total += Kati[i];
}

int k = 0;
int kazu = 0;
int kazu2 = 0;
for (int i = 0; i < 2; i++) {
	//同じ親を選ばないように同じなら別を選ぶようにする
	while (kazu == kazu2) {
		kazu = rand() % total;
	}
	kazu2 = kazu;
	for (int j = 0; j < MAN; j++) {
		//ルーレットなので乱数より大きくなったらその遺伝子を親にする
		if (kazu < Kati[j]) {
			//親の遺伝子がある配列の添え字を保存
			oya[k] = j;
			k++;
			break;
		}
	}
}

}

void Sex(int *oya)
{
for (int i = 2; i < MAN; i += 2) {
/一点交叉する境界をランダムに求める。
その境界をもとに子孫を２人作る/
int line = rand() % M + 2;
for (int j = 0; j < line; j++) {
Child[i][j] = Child[oya[0]][j];
}
for (int j = line; j < M; j++) {
Child[i][j] = Child[oya[1]][j];
}
for (int j = 0; j < line; j++) {
Child[i + 1][j] = Child[oya[1]][j];
}
for (int j = line; j < M; j++) {
Child[i + 1][j] = Child[oya[0]][j];
}
}
}

void show()
{
cout << "価値: ";
for (int i = 0; i < MAN; i++) {
cout << Kati[i] << ",";
}
cout << endl;

cout << "量:   ";
for (int i = 0; i < MAN; i++) {
	cout << Ryou[i] << ",";
}
cout << endl;

int max = Kati[0];
int ryou = Ryou[0];
for (int i = 1; i < MAN; i++) {
	if (max < Kati[i]) {
		max = Kati[i];
		ryou = Ryou[i];
	}
}

cout << "(" << max << "," << ryou << ")" << endl;

}

void heni()
{
for (int i = 0; i < MAN; i++) {
int kazu = rand() % 100;
if (kazu < 3) {
int kazu2 = rand() % M;
Child[i][kazu2] = (Child[i][kazu2] + 1) % 2;
}
}
}

行動規範の内容に同意します

回答2件

ベストアンサー

値が一度小さくなるのは親世代での最適値がうまくコピーされてないからだと思います。自分がよく使うGAは
１．配列にランダムデータ作成
２．評価
３．評価の良い順で一定確率Aで配列内に適宜コピー
４．一定確率Bで交差
５．一定確率Cで突然変異
６．２．に戻る
こんな感じです。A,B,Cのパラメータ変えると収束率が変わります。整数型の最適化問題では解の空間が滑らかではないので局所最大化問題とは別に、局所の山に崖があって、崖から転げ落ちる状態が発生します。現状では前世代での最適な遺伝子が（交差や突然変異で）死亡するので解の値が悪くなっています。つまり死亡率が高いので要素の数を増やし優秀な遺伝子が生き残る確率を上げたほうがいいでしょう。
すごく単純な解決としては前回最適な値を無傷で次世代に残したら解が後退することはないですね。