ナップザック問題を遺伝的アルゴリズムで解いてみました。
参考にさせていただいたサイトはあるのですが、何年も前のことだったので、検索しても見つけることができませんでした。

品物の数：30
最大重量:20億以下
個体数:1000
足切りライン（総価値がこの順位以下の遺伝子は次世代に残さない）:100
繰り返し回数（世代数）:30

その品物を採用するかしないかを遺伝子としました。
品物が30個あるので、遺伝子は30bitになります。
親遺伝子は上位100の中からランダムに2個選びます。
遺伝子に2か所切断ポイントを設け、たとえば最初の10bitは親1から受け継ぎ、次の10bitは親2から受け継ぎ、最後の10bitは再び親1から受け継ぐという感じです。
また5%の確率で突然変異を起こし、どこか1か所の遺伝子を反転させます。
総重量が20億を超えた場合は、価値をゼロと設定するようにしました。

以下にc++のプログラムと出力結果、このプログラムを30回実行したときの結果を示します。
最初は個体数100で実行したのですが、30回の出力結果のうち約2/3ぐらいの値がゼロになってしまったので、個体数を1000に増やしてやり直しました。

このプログラムを30回実行した時の結果

total weight = 1910747977    total value = 6464034476
total weight = 1868897366    total value = 6149837764
total weight = 1956576401    total value = 6598594667
total weight = 1946821635    total value = 6654768552
total weight = 1979202615    total value = 6062806162
total weight = 1944531771    total value = 6642663376
total weight = 1946821635    total value = 6654768552
total weight = 1956576401    total value = 6598594667
total weight = 1973553954    total value = 6252225161
total weight = 1944531771    total value = 6642663376
total weight = 1944531771    total value = 6642663376
total weight = 1946821635    total value = 6654768552
total weight = 1997568486    total value = 6070438783
total weight = 1944531771    total value = 6642663376
total weight = 1956576401    total value = 6598594667
total weight = 1946821635    total value = 6654768552
total weight = 1946821635    total value = 6654768552
total weight = 1944531771    total value = 6642663376
total weight = 1670057539    total value = 6391292585
total weight = 1881346006    total value = 5898972591
total weight = 1944531771    total value = 6642663376
total weight = 1944531771    total value = 6642663376
total weight = 1944531771    total value = 6642663376
total weight = 1988366392    total value = 6264049448
total weight = 1971130380    total value = 4977496842
total weight = 1956576401    total value = 6598594667
total weight = 1884428665    total value = 5906022845
total weight = 1944531771    total value = 6642663376
total weight = 1946745995    total value = 6648157753
total weight = 1946821635    total value = 6654768552

このプログラムを1回実行したときの出力結果

goods0  weight = 137274936  value = 128990795
goods1  weight = 989051853  value = 575374246
goods2  weight = 85168425  value = 471048785
goods3  weight = 856699603  value = 640066776
goods4  weight = 611065509  value = 819841327
goods5  weight = 22345022  value = 704171581
goods6  weight = 678298936  value = 536108301
goods7  weight = 616908153  value = 119980848
goods8  weight = 28801762  value = 117241527
goods9  weight = 478675378  value = 325850062
goods10  weight = 706900574  value = 623319578
goods11  weight = 738510039  value = 998395208
goods12  weight = 135746508  value = 475707585
goods13  weight = 599020879  value = 863910036
goods14  weight = 738084616  value = 340559411
goods15  weight = 545330137  value = 122579234
goods16  weight = 86797589  value = 696368935
goods17  weight = 592749599  value = 665665204
goods18  weight = 401229830  value = 958833732
goods19  weight = 523386474  value = 371084424
goods20  weight = 5310725  value = 463433600
goods21  weight = 907821957  value = 210508742
goods22  weight = 565237085  value = 685281136
goods23  weight = 730556272  value = 619500108
goods24  weight = 310581512  value = 88215377
goods25  weight = 136966252  value = 558193168
goods26  weight = 132739489  value = 475268130
goods27  weight = 12425915  value = 303022740
goods28  weight = 137199296  value = 122379996
goods29  weight = 23505143  value = 304092766

generation0  weight = 6177667707  value = 0  gene = 000001010111001010001111101010
generation1  weight = 6177667707  value = 0  gene = 000001010111001010001111101010
generation2  weight = 1453684641  value = 3664776929  gene = 001001000000010010010000010000
generation3  weight = 1453684641  value = 3664776929  gene = 001001000000010010010000010000
generation4  weight = 1477189784  value = 3968869695  gene = 001001000000010010010000010001
generation5  weight = 1883730339  value = 5391137027  gene = 001001000000010010111000010001
generation6  weight = 1883730339  value = 5391137027  gene = 001001000000010010111000010001
generation7  weight = 1896156254  value = 5694159767  gene = 001001000000010010111000010101
generation8  weight = 1772259433  value = 6204797021  gene = 101001000000100011101000011101
generation9  weight = 1772259433  value = 6204797021  gene = 101001000000100011101000011101
generation10  weight = 1778530713  value = 6403041853  gene = 101001000000110010101000011101
generation11  weight = 1807332475  value = 6520283380  gene = 101001001000110010101000011101
generation12  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation13  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation14  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation15  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation16  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation17  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation18  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation19  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation20  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation21  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation22  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation23  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation24  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation25  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation26  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation27  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation28  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111
generation29  weight = 1944531771  value = 6642663376  gene = 101001001000110010101000011111

number of goods = 30
max weight = 2000000000
total weight = 1944531771
total value = 6642663376

knapsack.cpp

#include <iostream>
#include <algorithm>
#include <time.h>
using namespace std;

int N_G = 30; // 品物の数 (number of goods)
long long MAX_W = 2000000000; // 最大重量 (max weight)
int N_P = 100; // 個体数 (number of population)
int CUT_LINE = 20;
int ITERATION = 30; // 繰り返し回数

long long* weight;
long long* value;

// 個体のクラス
class POPULATION
{
protected:
	int* gene; // 個体の遺伝子
	long long weight_p; // 個体の総重量
	long long value_p; // 個体の総価値
public:
	POPULATION();
	~POPULATION();
	void calc_weight_and_value(); // 個体の総重量と総価値を計算する
	long long get_value() { return value_p; }
	long long get_weight() { return weight_p; }
	void set_gene(int i, int g); // 遺伝子を設定する
	int get_gene(int i) { return gene[i]; }
	void mutation(); // 突然変異
	void initialize(); // 遺伝子の初期化
};

POPULATION** population;

POPULATION::POPULATION()
{
	gene = new int[N_G];
}

POPULATION::~POPULATION()
{
	delete []gene;
}

// 遺伝子の初期化
void POPULATION::initialize()
{
	for (int i = 0; i < N_G; i++)
		set_gene(i, rand() % 2);
	calc_weight_and_value();
}

void POPULATION::set_gene(int i, int g)
{
	gene[i] = g;
	if (weight[i] > MAX_W)
		gene[i] = 0;
}

// 個体の総重量と総価値を計算する
void POPULATION::calc_weight_and_value()
{
	weight_p = 0;
	value_p = 0;
	for (int i = 0; i < N_G; i++) {
		if (gene[i] == 1) {
			weight_p += weight[i];
			value_p += value[i];
		}
	}
	// 総重量が最大重量を超えていた場合は、総価値をゼロに設定
	if (weight_p > MAX_W)
		value_p = 0;
}

// 突然変異
void POPULATION::mutation()
{
	int mutation_point = rand() % N_G;
	if (gene[mutation_point] == 0)
		set_gene(mutation_point, 1);
	else
		set_gene(mutation_point, 0);
}

void create_object()
{
	weight = new long long[N_G]; // 品物の重量を代入するための変数
	value = new long long[N_G]; // 品物の価値を代入するための変数

	// 個体群の生成
	population = new POPULATION*[N_P];
	for (int i = 0; i < N_P; i++)
		population[i] = new POPULATION;
}

// 品物の価値と重量の初期設定
void initialize_weight_and_value()
{
	// N = 30
	value[0] = 128990795; weight[0] = 137274936;
	value[1] = 575374246; weight[1] = 989051853;
	value[2] = 471048785; weight[2] = 85168425;
	value[3] = 640066776; weight[3] = 856699603;
	value[4] = 819841327; weight[4] = 611065509;
	value[5] = 704171581; weight[5] = 22345022;
	value[6] = 536108301; weight[6] = 678298936;
	value[7] = 119980848; weight[7] = 616908153;
	value[8] = 117241527; weight[8] = 28801762;
	value[9] = 325850062; weight[9] = 478675378;
	value[10] = 623319578; weight[10] = 706900574;
	value[11] = 998395208; weight[11] = 738510039;
	value[12] = 475707585; weight[12] = 135746508;
	value[13] = 863910036; weight[13] = 599020879;
	value[14] = 340559411; weight[14] = 738084616;
	value[15] = 122579234; weight[15] = 545330137;
	value[16] = 696368935; weight[16] = 86797589;
	value[17] = 665665204; weight[17] = 592749599;
	value[18] = 958833732; weight[18] = 401229830;
	value[19] = 371084424; weight[19] = 523386474;
	value[20] = 463433600; weight[20] = 5310725;
	value[21] = 210508742; weight[21] = 907821957;
	value[22] = 685281136; weight[22] = 565237085;
	value[23] = 619500108; weight[23] = 730556272;
	value[24] = 88215377; weight[24] = 310581512;
	value[25] = 558193168; weight[25] = 136966252;
	value[26] = 475268130; weight[26] = 132739489;
	value[27] = 303022740; weight[27] = 12425915;
	value[28] = 122379996; weight[28] = 137199296;
	value[29] = 304092766; weight[29] = 23505143;

	for (int i = 0; i < N_G; i++)
		cout << "goods" << i << "  weight = " << weight[i] << "  value = " << value[i] << endl;
	cout << endl;
}

// 個体群の初期設定
void initialize_population()
{
	for (int i = 0; i < N_P; i++) 
		population[i]->initialize();
}


void delete_object()
{
	for (int i = 0; i < N_P; i++)
		delete population[i];
	delete []population;
	delete []value;
	delete []weight;
}

// 個体群を価値が高い順に並べ替える
void ranking()
{
	for (int i = 0; i < N_P - 1; i++) {
		for (int j = i + 1; j < N_P; j++) {
			if (population[i]->get_value() < population[j]->get_value()) {
				POPULATION* tmp = population[i];
				population[i] = population[j];
				population[j] = tmp;
			}
		}
	}
}

// 遺伝子の交叉と突然変異
void cross_over()
{
	for (int i = CUT_LINE; i < N_P; i++) {
		int parent1 = rand() % CUT_LINE; // 1番目の親の遺伝子をカットラインより上位の個体の中から選択
		int parent2 = rand() % CUT_LINE; // 2番目の親の遺伝子をカットラインより上位の個体の中から選択

		int cut_point1 = rand() % N_G; // 1番目の遺伝子の切断ポイントを決定
		int cut_point2 = rand() % N_G; // 2番目の遺伝子の切断ポイントを決定

		// 1番目の交叉ポイントが2番目の交叉ポイントより大きかった場合に入れ替える
		if (cut_point1 > cut_point2) {
			int tmp = cut_point1;
			cut_point1 = cut_point2;
			cut_point2 = tmp;
		}
		
		// 一番目の切断ポイント以下の遺伝子を1番目の親の遺伝子からコピー
		for (int j = 0; j < cut_point1; j++)
			population[i]->set_gene(j, population[parent1]->get_gene(j));
		
		// 1番目の切断ポイントと2番目の切断ポイントの間の遺伝子を2番目の親の遺伝子からコピー
		for (int j = cut_point1; j < cut_point2; j++)
			population[i]->set_gene(j, population[parent2]->get_gene(j));
		
		// 2番目の切断ポイント以降の遺伝子を1番目の親の遺伝子からコピー
		for (int j = cut_point2; j < N_G; j++)
			population[i]->set_gene(j, population[parent1]->get_gene(j));

		// ランダム値が5%より小さかった場合に突然変異を起こす
		if (rand() % 100 < 5)
			population[i]->mutation();

		// 個体の総重量と総価値を計算
		population[i]->calc_weight_and_value();
	}
}

int main()
{
	srand((unsigned)time(NULL));
	create_object(); // 個体群の生成
	initialize_weight_and_value(); // 各品物の重量と価格の初期化

	long long max_value = 0;
	long long final_weight = 0;
	initialize_population(); // 個体群の初期化
	ranking(); // 個体群を価値の高い順番に並び変える
	for (int i = 0; i < ITERATION; i++) {
		cross_over(); // 遺伝子の交叉と突然変異
		ranking(); // 個体群を価値の高い順番に並び変える

		// その世代において最も価値の高かった個体の総重量と総価値の表示
		cout << "generation" << i << "  weight = " << population[0]->get_weight() << "  value = " << population[0]->get_value();
		
		// 価値が最高だった個体の遺伝子の表示
		cout << "  gene = ";
		for (int j = 0; j < N_G; j++)
			cout << population[0]->get_gene(j);
		cout << endl;

		// その世代の価値が最も高かった場合は、総重量と総価値を保存する
		if (max_value < population[0]->get_value()) {
			max_value = population[0]->get_value();
			final_weight = population[0]->get_weight();
		}
	}
	cout << endl;
	cout << "number of goods = " << N_G << "    " << "max weight = " << MAX_W << endl;
	cout << "total weight = " << final_weight << "    total value = " << max_value << endl;

	delete_object();
}