遗传算法——01背包问题中的应用 C++

        对于01背包问题，本身就附带有一定能出最优解的动态规划算法。但是动态规划算法在大数据集下（30个包以上）可能要花费大量的时间。如果在工业生产中需要快速得出相关问题的结果，那么动态规划等全遍历算法就不是最优方法。这时我们引入遗传算法来帮助快速解决01背包问题。        

        遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

        本程序中遗传算法基本流程图：

         算法伪代码：

BeginT=0; 
生成第一代种群; Evaluate p(t); //计算第一代种群的适应度While（迭代未结束T<end）//根据输入的迭代次数进行迭代Begin T=t+1; 选择 p(t)从p(t-1); //通过轮盘赌等方式从上代种群中选择较优秀的个体到下代子群Reproduce pairs in p(t); //重新生成种群Evaluate p(t); //计算当前的适应度End //迭代结束End//算法结束

        由于本程序主要解决的问题为背包问题，因此本程序特意对背包问题生成了一个二进制结构体用来存储背包中的数据，同时也可以当做一个种群来方便变异以及遗传操作。其中，本程序采用四组数据并存的种群制度，这样可以保证数据多样化。

        数据结构：

typedef struct Chrom 
{int bit[Num];  //Num为背包数据的数量，其含义为一个二进制数组，1代表选择此包，0代表不选择此包int fit=0;		//当前物品总价值int we = 0;	//当前物品总重量double rfit=0;  //此数据在四组数据中所占百分比
}chrom;

        该数据结构在本程序中创建了四组。

        本程序详细流程图：

变异模块采用轮盘赌的方式：

c = rand() % Num;
if (new_ptr[0].bit[c] == 0)new_ptr[0].bit[c] = 1;//轮盘赌随机一个元素变异
else new_ptr[0].bit[c] = 0;

完整代码：

#include<iostream>
#include<vector>
#include<stdlib.h>
#include <windows.h>
#include<time.h>
using namespace std;//
//const int Num = 10;
//const int Max_in = 165;
//int in[] = { 23,31,29,44,53,38,63,85,89,82 };
//int value[] = { 92,57,49,68,60,43,67,84,87,72 };//const int Num = 5;
//const int Max_in = 26;
//int in[] = { 12,7,11,8,9};
//int value[] = { 24,13,23,15,16};
//
//const int Num = 6;
//const int Max_in = 190;
//int in[] = { 56,59,80,64,75,17};
//int value[] = { 50,50,64,46,50,5};const int Num = 7;
const int Max_in = 50;
int in[] = { 31,10,20,19,4,3,6 };
int value[] = { 70,20,39,37,7,5,10 };//const int Num = 29;
//const int Max_in = 600;
//int in[] = { 31,10,20,19,4,3,6,14,85,89,82 ,15,7,11,8,10,20,19,59,80,31,29,44,53,11 ,64 ,19,38,11 };
//int value[] = { 70,20,39,37,7,5,10,40,84,87,72,24 ,13,23,15,20,39,37,50,64,57,49,68,60,23,46,37,43,23 };
//
int bit[Num];typedef struct Chrom 
{int bit[Num];//基因组int fit=0;int we = 0;double rfit=0;
}chrom;
chrom ptr[4];//四组并存的种群
chrom new_ptr[1];
void cul_fit(chrom *);
bool isok(chrom*,int);
void crossover();
void showptr();
void _2to10(int x);
int main() {srand(time(0));int n;int v = 0, sum = 0;long start_time = GetTickCount();/*for (int i = 0; i < pow(2, Num); i++) {//暴力解法求最优解_2to10(i);if (isok1()) {for (int j = 0; j < Num; j++) {if (bit[j])sum += value[j];}if (sum > v) {v = sum;}sum = 0;}}long end_time = GetTickCount();cout<<"正确答案为:";cout << v << "\t";cout << "运行时间为:";cout << (end_time-start_time)/1000.0/60<< "\n";cout << "请输入迭代次数\n";*/while (cin >> n) {for (int cc = 0; cc < 20; cc++) {//程序运行20次，可以尽量降低出错概率for (int i = 0; i < 4; i++) {for (int j = 0; j < Num; j++) {do {ptr[i].bit[j] = rand() % 2;} while (!isok(ptr, i));}}cul_fit(ptr);for (int i = 0; i < n; i++) {crossover();cul_fit(ptr);//showptr();//可显示基因组的每一次变化}int v = 0;for (int i = 0; i < 4; i++) {if (ptr[i].fit > v)v = ptr[i].fit;}cout << "max=" << v << endl;}cout << "请输入迭代次数\n";}system("pause");
}void cul_fit(chrom* x)//计算当前背包中物品价值
{int sum = 0;double v = 0;for (int i = 0; i < 4; i++) {for (int j = 0; j < Num; j++) {if (x[i].bit[j])sum += value[j];}x[i].fit = sum;sum = 0;}for (int i = 0; i < 4; i++) {v += x[i].fit;}for (int i = 0; i < 4; i++) {x[i].rfit=x[i].fit/v;}
}bool isok(chrom *x,int y)//判断背包总重是否超过限制
{int sum = 0;for (int j = 0; j < Num; j++) {if (x[y].bit[j])sum += in[j];}if (sum <= Max_in) { x[y].we = sum; return true; }else return false;
}
void crossover() {//交叉变异double v = (double)rand() / RAND_MAX;int n=0,m=0;for (int i = 0; i < 4; i++) {v -= ptr[i].rfit;if (v <= 0) {n = i;break;}}do {v = (double)rand() / RAND_MAX;for (int i = 0; i < 4; i++) {v -= ptr[i].rfit;if (v <= 0) {m = i;break;}}} while (m == n);int c = rand() % Num;for (int j = 0; j < Num; j++) {if (j < c) {new_ptr[0].bit[j] = ptr[n].bit[j];}else new_ptr[0].bit[j] = ptr[m].bit[j];}c = rand() % Num;if (new_ptr[0].bit[c] == 0)new_ptr[0].bit[c] = 1;//轮盘赌随机一个元素变异else new_ptr[0].bit[c] = 0;if (isok(new_ptr, 0)) {int w = 0;for (int i = 0; i < Num; i++) {if (new_ptr[0].bit[i])w += value[i];}c = 1000000;int u = 0;for (int i = 0; i < 4; i++) {if (ptr[i].fit < c) {c = ptr[i].fit;u = i;}}if(w>c)ptr[u] = new_ptr[0];}
}void showptr()//展示每一个基因组的值
{for (int i = 0; i < 4; i++) {for (int j = 0; j < Num; j++) {cout << ptr[i].bit[j];}cout << "\t" << ptr[i].fit << "\t" << ptr[i].we<< "\t" << ptr[i].rfit << endl;}cout << endl;
}void _2to10(int x)//二进制转十进制
{int xx = 0;for (int i = 0; i < Num; i++) {bit[i] = x % 2;x /= 2;}
}

        程序运行状态图：

注：可以通过适当增加迭代次数来生成较为精准的结果。

对于该程序与标准答案之间的差异对比，我做了一个表格供大家参考：

程序迭代次数100000

在100000次迭代的前提下，遗传算法每一次的结果可以做到瞬间完成，也就是0s。由上图可见遗传算法在大数据集下的精度虽然不如暴力算法，但是其优势在于可以在较短的时间下完成大数据集的计算，并得到较为精准的结果。

         总结：

        遗传算法毕竟只是一种程序的优化方法，在低数据量的情况下，解决背包问题用暴力解法可以兼顾高速和准确性来解决问题，而在较高数据量时，如果不需要太高的准确度且需要很快出答案的时候采用遗传算法是一个比较好的选择。