2023年8月1日发(作者：)

C++实现多⽬标遗传算法（01背包问题）（背包问题）：背包只能容得下⼀定重量b的物品，物品有m种，每种物品有⾃⼰的重量w(i)和价值v(i)，从这些物品中选择装⼊背包，是背包不超过重量b，但价值⼜要最⼤。

上⾯为单⽬标的0/1规划问题，也就是说只考虑物体的重量不考虑物体的体积，形状等问题，⼀般⽽⾔，利⽤动态规划可以很好地解决背包问题，但是如果物体过多，使⽤动态规划将浪费很⼤的资源．

遗传算法作经典的⼈⼯智能算法，可以很好的解决当物体较多的0/1规划问题。

（遗传算法概述）：

遗传算法使⽤的就是⽣物学中适者⽣存的法则。但是和⽣物中⼀些专业⼈术语有些区别：

种群(Population)：⽣物的进化以群体的形式进⾏，这样的⼀个群体称为种群。

　　个体：组成种群的单个⽣物。　　基因 ( Gene ) ：⼀个遗传因⼦。　　染⾊体 ( Chromosome ) ：包含⼀组的基因。　　⽣存竞争，适者⽣存：对环境适应度⾼的、⽜B的个体参与繁殖的机会⽐较多，后代就会越来越多。适应度低的个体参与繁殖的机会⽐较少，后代就会越来越少。　　遗传与变异：新个体会遗传⽗母双⽅各⼀部分的基因，同时有⼀定的概率发⽣基因变异。

具体流程如下：

（注：图⽚来之百度）

（具体背包问题概述）：

32件物体，属性重量，体积，价值（普通的0/1规划只考虑重量或者体积）。背包最⼤体积：75，最⼤重量：80，把物体装⼊背包，保证价值的最⼤化。//主函数⼊⼝#include"gene.h"#include #include using namespace std;int main(int argc, char*argv[]){ Gene *gene = new Gene; //实例化类，返回指针 int gen = 0; int oldMaxPop, k; double oldMax; srand((unsigned)time(NULL)); gene->initPop(); memcpy(&gene->newPop, &gene->oldPop, POP_SIZE * sizeof(struct Gene::population)); gene->statistics(gene->newPop); //计算种群的最⼤适应度和最⼩适应度以及适应度的下表号。 gene->report(gene->newPop, gen); while (gen < CENERAION_NUM) { gen += 1; if (gen % 100 == 0) { srand((unsigned)time(NULL)); } oldMax = gene->maxFitness; //oldmax为种群中最⼤适应度 oldMaxPop = gene->maxPop; //oldMaxPop指种群中最⼤适应度的个体 gene->generation(); gene->statistics(gene->newPop); if (gene->maxFitness < oldMax) { for (k = 0; k < CHROM_SIZE; k++) { gene->newPop[gene->minPop].chrom[k] = gene->oldPop[oldMaxPop].chrom[k]; } gene->newPop[gene->minPop].fitness = gene->oldPop[oldMaxPop].fitness; gene->newPop[gene->minPop].weight = gene->oldPop[oldMaxPop].weight; gene->newPop[gene->minPop].volume = gene->oldPop[oldMaxPop].volume; gene->newPop[gene->minPop].parent1 = gene->oldPop[oldMaxPop].parent1; gene->newPop[gene->minPop].parent2 = gene->oldPop[oldMaxPop].parent2; gene->newPop[gene->minPop].cross = gene->oldPop[oldMaxPop].cross; gene->statistics(gene->newPop); } else if(gene->maxFitness > oldMax){ gene->report(gene->newPop, gen); } memcpy(&gene->oldPop, &gene->newPop, POP_SIZE * sizeof(struct Gene::population)); } delete[] gene; //销毁对象占⽤空间 system("pause"); return 0;}/********头⽂件的定义********/#pragma once#ifndef GENE_H#define GENE_H#include #include #include #include #include #define POP_SIZE 200 //定义种群规模#define RRO_CROSS 0.618 //交叉概率#define PRO_MUTATE 0.03 //变异概率#define CHROM_SIZE 32 //给定染⾊体长度#define CENERAION_NUM 1000 //定义繁殖代数typedef unsigned int UINT;class Gene{public: Gene(); ~Gene();public: struct population { //定义私有的个体类 UINT chrom[CHROM_SIZE]; //定义个体的基因组 double weight; //背包的重量 double volume; //背包的体积 double fitness; //个体的适应度 UINT parent1, parent2, cross; //双亲以及交叉的节点 }; population oldPop[POP_SIZE], newPop[POP_SIZE]; int weight[CHROM_SIZE] = { 22, 15, 4, 5, 10, 19, 21, 20, 8, 13, 2, 3, 3, 17, 12, 5, 12, 4, 1, 21, 14, 23, 17, 15, 20, 22, 25, 0, 22, 15, 25, 13 }; int volume[CHROM_SIZE] = { 11, 22, 12, 21, 21, 13, 1, 10, 13, 8, 6, 25, 13, 27, 12, 23, 12, 24, 23, 11, 6, 24, 28, 10, 20, 13, 25, 23, 5, 26, 30, 15 int profit[CHROM_SIZE] = { 8, 9, 15, 6, 16, 9, 1, 4, 14, 9, 3, 7, 12, 4, 15, 5, 18, 5, 15, 4, 6, 2, 12, 14, 11, 9, 13, 13, 14, 13, 19, 4 }; int containW = 80, containV = 75; double sumFitness; //种群总适应度 double minFitness; //最⼩适应度 double maxFitness; //最⼤适应度 double avgFitness; //平均适应度 double alpha; //计算适应度时的惩罚系数 int minPop; //种群内最⼤和最⼩的适应个体 int maxPop; void initPop(); //总群初始化函数 //int calWeight(UINT *chr); //计算个体体积，重量，以及收益的函数 //int Gene::calVolume(UINT *chr); int calSum(UINT *ch, int *pt); double calFit(UINT *ch); void statistics(struct population *pop); //计算种群最⼤适应度和最⼩适应度的函数 void report(struct population *pop, int gen); //为输出的函数 int selection(int pop); //通过选择总群中符合要求的⽗母进⾏繁殖 函数返回⽗母的位置 int crossOver(UINT *parent1, UINT *parent2, int i); //传⼊要更改的个体位置，随机产⽣交叉位置 int excise(double probability);// 传⼊概率参数，进⾏交叉或者变异 int mutation(UINT i); //传⼊参数为基因组基因的位置，逐个基因判断变异概率 void generation(); //种群群体更新的函数};#endif // !GENE_H//类中代码的实现#include "gene.h"#include#includeusing namespace std;Gene::Gene(){ cout << "begin" << endl;}Gene::~Gene(){}int Gene::calSum(UINT *ch, int *pt) //ch为装⼊背包中的⼀个可能的解 pt为重量或者体积的指针{ int popSum = 0; for (int i = 0; i < CHROM_SIZE; i++) { popSum += (*ch) * pt[i]; ch++; } return popSum;}void Gene::initPop(){ int tmpWeight = 0; int tmpVolume = 0; int m = 0; bool isPop = false; //最初代的种群的初始化 for (int i = 0; i < POP_SIZE; i++) { //这⾥的POP_SIZE是种群规模 while (!isPop){ for (int j = 0; j < CHROM_SIZE; j++) { m = rand() % 1001; //rand为初始化函数，这⾥设置⽣成0的概率要⼤⼀些 if (m <= 499) oldPop[i].chrom[j] = 0; else oldPop[i].chrom[j] = 1; oldPop[i].parent1 = 0; oldPop[i].parent2 = 0; oldPop[i].cross = 0; } //剔除重量和体积⼤于背包容量的体积的个体 tmpWeight = calSum(oldPop[i].chrom, weight); tmpVolume = calSum(oldPop[i].chrom, volume); if ((tmpWeight <= containW) && (tmpVolume <= containV)) { oldPop[i].fitness = calSum(oldPop[i].chrom, profit); oldPop[i].weight = tmpWeight; oldPop[i].volume = tmpVolume; oldPop[i].parent1 = 0; oldPop[i].parent2 = 0; oldPop[i].cross = 0; isPop = true; } } isPop = false; }}void Gene::statistics(struct population *pop)

{ double tmpFitness; minPop = 0; maxPop = 0; sumFitness = pop[0].fitness; minFitness = pop[0].fitness; maxFitness = pop[0].fitness; for (int i = 1; i < POP_SIZE; i++) {

sumFitness += pop[i].fitness; tmpFitness = pop[i].fitness; //挑选出最⼤的适应度个体 if ((tmpFitness > maxFitness) && ((int)(tmpFitness * 10) % 10 == 0)){ maxFitness = pop[i].fitness; maxPop = i; } //挑选出最⼩的适应度个体 if (tmpFitness < minFitness) { minFitness = pop[i].fitness; minPop = i; } //计算出平均的适应度 avgFitness = sumFitness / (float)POP_SIZE; }}void Gene::report(struct population *pop, int gen){ int popWeight = 0; cout << "The generation is " << gen << endl; //显⽰种群的代数 cout << "The population chrom is: " << endl; for (int j = 0; j < CHROM_SIZE; j++) { if (j % 4 == 0) cout << " "; cout << pop[maxPop].chrom[j]; } cout << endl; cout << "The population's max fitness is: " << (int)pop[maxPop].fitness << endl; cout << "The population's max weight is: " << (int)pop[minPop].weight << endl; cout << "The population's max volume is: " << (int)pop[minPop].weight << endl;}int Gene::selection(int pop) //使⽤轮赌法进⾏选择{ double wheelPos, randNumber, partsum = 0; int i = 0; randNumber = (rand() % 2001) / 2000.0; wheelPos = randNumber*sumFitness; do { partsum += oldPop[i].fitness; i++; } while ((partsum < wheelPos) && (i < POP_SIZE)); return i - 1;}int Gene::crossOver(UINT *parent1, UINT *parent2, int i)

{ int j; //基因组的基因位置 int crossPos; //交叉点的位置 if (excise(RRO_CROSS)) { crossPos = rand() % (CHROM_SIZE - 1); } else { crossPos = CHROM_SIZE - 1; } for (j = 0; j <= crossPos; j++) { newPop[i].chrom[j] = parent1[j]; } for (j = crossPos + 1; j < CHROM_SIZE; j++) { newPop[i].chrom[j] = parent2[j]; } newPop[i].cross = crossPos; return 1;}int Gene::excise(double probability) //传⼊概率参数，概率选择实验int Gene::excise(double probability) //传⼊概率参数，概率选择实验{ double pp; pp = (double)(rand() % 20001 / 20000.0); if (pp <= probability) { return 1; } else { return 0; }}int Gene::mutation(UINT alleles){ if (excise(PRO_MUTATE)) { alleles == 0 ? alleles = 1 : alleles = 0; } return alleles;}void Gene::generation(){ UINT mate1, mate2; UINT i, j; int tmpWeight = 0; int tmpVolume = 0; bool notGen; for (i = 0; i < POP_SIZE; i++) { notGen = false; while (!notGen){ mate1 = selection(i); //选择有⼏率产⽣优良后代的双亲的位置 mate2 = selection(i + 1); crossOver(oldPop[mate1].chrom, oldPop[mate2].chrom, i); for (j = 0; j < CHROM_SIZE; j++) { newPop[i].chrom[j] = mutation(newPop[i].chrom[j]); //给基因变异的概率 } tmpWeight = calSum(newPop[i].chrom, weight); tmpVolume = calSum(newPop[i].chrom, volume); if ((tmpWeight <= containW) && (tmpVolume <= containV)) { newPop[i].fitness = calSum(newPop[i].chrom, profit); newPop[i].weight = tmpWeight; newPop[i].volume = tmpVolume; newPop[i].parent1 = mate1; newPop[i].parent2 = mate2; notGen = true; } } }}

2023年8月1日发(作者：)

C++实现多⽬标遗传算法（01背包问题）（背包问题）：背包只能容得下⼀定重量b的物品，物品有m种，每种物品有⾃⼰的重量w(i)和价值v(i)，从这些物品中选择装⼊背包，是背包不超过重量b，但价值⼜要最⼤。

上⾯为单⽬标的0/1规划问题，也就是说只考虑物体的重量不考虑物体的体积，形状等问题，⼀般⽽⾔，利⽤动态规划可以很好地解决背包问题，但是如果物体过多，使⽤动态规划将浪费很⼤的资源．

遗传算法作经典的⼈⼯智能算法，可以很好的解决当物体较多的0/1规划问题。

（遗传算法概述）：

遗传算法使⽤的就是⽣物学中适者⽣存的法则。但是和⽣物中⼀些专业⼈术语有些区别：

种群(Population)：⽣物的进化以群体的形式进⾏，这样的⼀个群体称为种群。

　　个体：组成种群的单个⽣物。　　基因 ( Gene ) ：⼀个遗传因⼦。　　染⾊体 ( Chromosome ) ：包含⼀组的基因。　　⽣存竞争，适者⽣存：对环境适应度⾼的、⽜B的个体参与繁殖的机会⽐较多，后代就会越来越多。适应度低的个体参与繁殖的机会⽐较少，后代就会越来越少。　　遗传与变异：新个体会遗传⽗母双⽅各⼀部分的基因，同时有⼀定的概率发⽣基因变异。

具体流程如下：

（注：图⽚来之百度）

（具体背包问题概述）：

32件物体，属性重量，体积，价值（普通的0/1规划只考虑重量或者体积）。背包最⼤体积：75，最⼤重量：80，把物体装⼊背包，保证价值的最⼤化。//主函数⼊⼝#include"gene.h"#include #include using namespace std;int main(int argc, char*argv[]){ Gene *gene = new Gene; //实例化类，返回指针 int gen = 0; int oldMaxPop, k; double oldMax; srand((unsigned)time(NULL)); gene->initPop(); memcpy(&gene->newPop, &gene->oldPop, POP_SIZE * sizeof(struct Gene::population)); gene->statistics(gene->newPop); //计算种群的最⼤适应度和最⼩适应度以及适应度的下表号。 gene->report(gene->newPop, gen); while (gen < CENERAION_NUM) { gen += 1; if (gen % 100 == 0) { srand((unsigned)time(NULL)); } oldMax = gene->maxFitness; //oldmax为种群中最⼤适应度 oldMaxPop = gene->maxPop; //oldMaxPop指种群中最⼤适应度的个体 gene->generation(); gene->statistics(gene->newPop); if (gene->maxFitness < oldMax) { for (k = 0; k < CHROM_SIZE; k++) { gene->newPop[gene->minPop].chrom[k] = gene->oldPop[oldMaxPop].chrom[k]; } gene->newPop[gene->minPop].fitness = gene->oldPop[oldMaxPop].fitness; gene->newPop[gene->minPop].weight = gene->oldPop[oldMaxPop].weight; gene->newPop[gene->minPop].volume = gene->oldPop[oldMaxPop].volume; gene->newPop[gene->minPop].parent1 = gene->oldPop[oldMaxPop].parent1; gene->newPop[gene->minPop].parent2 = gene->oldPop[oldMaxPop].parent2; gene->newPop[gene->minPop].cross = gene->oldPop[oldMaxPop].cross; gene->statistics(gene->newPop); } else if(gene->maxFitness > oldMax){ gene->report(gene->newPop, gen); } memcpy(&gene->oldPop, &gene->newPop, POP_SIZE * sizeof(struct Gene::population)); } delete[] gene; //销毁对象占⽤空间 system("pause"); return 0;}/********头⽂件的定义********/#pragma once#ifndef GENE_H#define GENE_H#include #include #include #include #include #define POP_SIZE 200 //定义种群规模#define RRO_CROSS 0.618 //交叉概率#define PRO_MUTATE 0.03 //变异概率#define CHROM_SIZE 32 //给定染⾊体长度#define CENERAION_NUM 1000 //定义繁殖代数typedef unsigned int UINT;class Gene{public: Gene(); ~Gene();public: struct population { //定义私有的个体类 UINT chrom[CHROM_SIZE]; //定义个体的基因组 double weight; //背包的重量 double volume; //背包的体积 double fitness; //个体的适应度 UINT parent1, parent2, cross; //双亲以及交叉的节点 }; population oldPop[POP_SIZE], newPop[POP_SIZE]; int weight[CHROM_SIZE] = { 22, 15, 4, 5, 10, 19, 21, 20, 8, 13, 2, 3, 3, 17, 12, 5, 12, 4, 1, 21, 14, 23, 17, 15, 20, 22, 25, 0, 22, 15, 25, 13 }; int volume[CHROM_SIZE] = { 11, 22, 12, 21, 21, 13, 1, 10, 13, 8, 6, 25, 13, 27, 12, 23, 12, 24, 23, 11, 6, 24, 28, 10, 20, 13, 25, 23, 5, 26, 30, 15 int profit[CHROM_SIZE] = { 8, 9, 15, 6, 16, 9, 1, 4, 14, 9, 3, 7, 12, 4, 15, 5, 18, 5, 15, 4, 6, 2, 12, 14, 11, 9, 13, 13, 14, 13, 19, 4 }; int containW = 80, containV = 75; double sumFitness; //种群总适应度 double minFitness; //最⼩适应度 double maxFitness; //最⼤适应度 double avgFitness; //平均适应度 double alpha; //计算适应度时的惩罚系数 int minPop; //种群内最⼤和最⼩的适应个体 int maxPop; void initPop(); //总群初始化函数 //int calWeight(UINT *chr); //计算个体体积，重量，以及收益的函数 //int Gene::calVolume(UINT *chr); int calSum(UINT *ch, int *pt); double calFit(UINT *ch); void statistics(struct population *pop); //计算种群最⼤适应度和最⼩适应度的函数 void report(struct population *pop, int gen); //为输出的函数 int selection(int pop); //通过选择总群中符合要求的⽗母进⾏繁殖 函数返回⽗母的位置 int crossOver(UINT *parent1, UINT *parent2, int i); //传⼊要更改的个体位置，随机产⽣交叉位置 int excise(double probability);// 传⼊概率参数，进⾏交叉或者变异 int mutation(UINT i); //传⼊参数为基因组基因的位置，逐个基因判断变异概率 void generation(); //种群群体更新的函数};#endif // !GENE_H//类中代码的实现#include "gene.h"#include#includeusing namespace std;Gene::Gene(){ cout << "begin" << endl;}Gene::~Gene(){}int Gene::calSum(UINT *ch, int *pt) //ch为装⼊背包中的⼀个可能的解 pt为重量或者体积的指针{ int popSum = 0; for (int i = 0; i < CHROM_SIZE; i++) { popSum += (*ch) * pt[i]; ch++; } return popSum;}void Gene::initPop(){ int tmpWeight = 0; int tmpVolume = 0; int m = 0; bool isPop = false; //最初代的种群的初始化 for (int i = 0; i < POP_SIZE; i++) { //这⾥的POP_SIZE是种群规模 while (!isPop){ for (int j = 0; j < CHROM_SIZE; j++) { m = rand() % 1001; //rand为初始化函数，这⾥设置⽣成0的概率要⼤⼀些 if (m <= 499) oldPop[i].chrom[j] = 0; else oldPop[i].chrom[j] = 1; oldPop[i].parent1 = 0; oldPop[i].parent2 = 0; oldPop[i].cross = 0; } //剔除重量和体积⼤于背包容量的体积的个体 tmpWeight = calSum(oldPop[i].chrom, weight); tmpVolume = calSum(oldPop[i].chrom, volume); if ((tmpWeight <= containW) && (tmpVolume <= containV)) { oldPop[i].fitness = calSum(oldPop[i].chrom, profit); oldPop[i].weight = tmpWeight; oldPop[i].volume = tmpVolume; oldPop[i].parent1 = 0; oldPop[i].parent2 = 0; oldPop[i].cross = 0; isPop = true; } } isPop = false; }}void Gene::statistics(struct population *pop)

{ double tmpFitness; minPop = 0; maxPop = 0; sumFitness = pop[0].fitness; minFitness = pop[0].fitness; maxFitness = pop[0].fitness; for (int i = 1; i < POP_SIZE; i++) {

sumFitness += pop[i].fitness; tmpFitness = pop[i].fitness; //挑选出最⼤的适应度个体 if ((tmpFitness > maxFitness) && ((int)(tmpFitness * 10) % 10 == 0)){ maxFitness = pop[i].fitness; maxPop = i; } //挑选出最⼩的适应度个体 if (tmpFitness < minFitness) { minFitness = pop[i].fitness; minPop = i; } //计算出平均的适应度 avgFitness = sumFitness / (float)POP_SIZE; }}void Gene::report(struct population *pop, int gen){ int popWeight = 0; cout << "The generation is " << gen << endl; //显⽰种群的代数 cout << "The population chrom is: " << endl; for (int j = 0; j < CHROM_SIZE; j++) { if (j % 4 == 0) cout << " "; cout << pop[maxPop].chrom[j]; } cout << endl; cout << "The population's max fitness is: " << (int)pop[maxPop].fitness << endl; cout << "The population's max weight is: " << (int)pop[minPop].weight << endl; cout << "The population's max volume is: " << (int)pop[minPop].weight << endl;}int Gene::selection(int pop) //使⽤轮赌法进⾏选择{ double wheelPos, randNumber, partsum = 0; int i = 0; randNumber = (rand() % 2001) / 2000.0; wheelPos = randNumber*sumFitness; do { partsum += oldPop[i].fitness; i++; } while ((partsum < wheelPos) && (i < POP_SIZE)); return i - 1;}int Gene::crossOver(UINT *parent1, UINT *parent2, int i)

{ int j; //基因组的基因位置 int crossPos; //交叉点的位置 if (excise(RRO_CROSS)) { crossPos = rand() % (CHROM_SIZE - 1); } else { crossPos = CHROM_SIZE - 1; } for (j = 0; j <= crossPos; j++) { newPop[i].chrom[j] = parent1[j]; } for (j = crossPos + 1; j < CHROM_SIZE; j++) { newPop[i].chrom[j] = parent2[j]; } newPop[i].cross = crossPos; return 1;}int Gene::excise(double probability) //传⼊概率参数，概率选择实验int Gene::excise(double probability) //传⼊概率参数，概率选择实验{ double pp; pp = (double)(rand() % 20001 / 20000.0); if (pp <= probability) { return 1; } else { return 0; }}int Gene::mutation(UINT alleles){ if (excise(PRO_MUTATE)) { alleles == 0 ? alleles = 1 : alleles = 0; } return alleles;}void Gene::generation(){ UINT mate1, mate2; UINT i, j; int tmpWeight = 0; int tmpVolume = 0; bool notGen; for (i = 0; i < POP_SIZE; i++) { notGen = false; while (!notGen){ mate1 = selection(i); //选择有⼏率产⽣优良后代的双亲的位置 mate2 = selection(i + 1); crossOver(oldPop[mate1].chrom, oldPop[mate2].chrom, i); for (j = 0; j < CHROM_SIZE; j++) { newPop[i].chrom[j] = mutation(newPop[i].chrom[j]); //给基因变异的概率 } tmpWeight = calSum(newPop[i].chrom, weight); tmpVolume = calSum(newPop[i].chrom, volume); if ((tmpWeight <= containW) && (tmpVolume <= containV)) { newPop[i].fitness = calSum(newPop[i].chrom, profit); newPop[i].weight = tmpWeight; newPop[i].volume = tmpVolume; newPop[i].parent1 = mate1; newPop[i].parent2 = mate2; notGen = true; } } }}