ナップザック問題を遺伝的アルゴリズムで解いてみました。
参考にさせていただいたサイトはあるのですが、何年も前のことだったので、検索しても見つけることができませんでした。
品物の数：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();
}