遗传算法解背包问题（C++）⾃⽤备份
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cmath>
#include<ctime>
using namespace std;
//定义问题的最⼤规模
#define max 100
//为题规模，即共有多少个包
int packageNum;
/
/每个包的重量
int packageWeight[max] = {5,3,11,15,7,9,13,6,8,14};
//每个包的价值
int packageValue[max] ={100,5,20,100,60,40,90,40,50,80};
//约束，背包的最⼤容量
int limitWeight;
//群体的规模
int colonySize;
//colonyState[i][k] 表⽰⼀个染⾊体
//lonySize][0|1] 表⽰⼀个群体
int colonyState[max][2][max];
/
/ currAge 表⽰当前代的编号
// (currAge+1)%2 表⽰下⼀代的编号
int currAge = 0;
// 个体评价信息表
typedef struct tagIndivdualMsg
{
int index;
int value;
}IndivdualMsg;
IndivdualMsg indivdualMsg[max];
//函数声明
void printColonyState(int nextAge);
//初始化群体
void colonyInit()
{
int i, j;
int w;
for(i=0; i<colonySize; i++)
{
//保证找到⼀个符合约束的染⾊体
w = limitWeight +1;
while(w > limitWeight)
{
w = 0;
for(j=0; j<packageNum&&w<=limitWeight; j++)
{
colonyState[i][currAge][j] = rand()%2;
w += packageWeight[j] * colonyState[i][currAge][j];
}
}
}
}
//对个体进⾏评价
int cmp(const void *a, const void *b)
{
IndivdualMsg *x = (IndivdualMsg *)a;
IndivdualMsg *y = (IndivdualMsg *)b;
return y->value - x->value;
}
//适应度函数
void indivdualEstimate()黄昏里
{
int i, j;
for(i=0; i<colonySize; i++)
{
indivdualMsg[i].index = i;
indivdualMsg[i].value = 0;
for(j=0; j<packageNum; j++)
indivdualMsg[i].value += packageValue[j]*colonyState[i][currAge][j];
}
qsort(indivdualMsg, colonySize, sizeof(IndivdualMsg), cmp);
偶尔怎么造句}
//终⽌循环的条件
bool stopFlag()
{
/
/进⾏n代进⾏后停⽌小仲马的作品
static int n = 50;
if(n-- <= 0)
return fal;
el
return true;
}
//赌轮选择
int gambleChoo()
{
int wheel[max] = {0};
int i = colonySize-1;
int choo;
wheel[i] = indivdualMsg[i].value;
for(i--; i>=0; i--)
wheel[i] = (indivdualMsg[i].value + wheel[i+1]) + colonySize*(colonySize-i);
int ed = abs(wheel[0]-(rand()%(2*wheel[0]+1)));
choo = colonySize-1;
文秘专业while(ed > wheel[choo])
choo--;
return choo;
}
/
/交叉
void across(int male, int female, int index)
{
int nextAge = (currAge+1) %2;
int i, j, t;
int acrossBit = rand() % (packageNum-1) + 1;
for(j=0; j<packageNum; j++)
{
colonyState[index][nextAge][j] = colonyState[indivdualMsg[male].index][currAge][j];
colonyState[index+1][nextAge][j] = colonyState[indivdualMsg[female].index][currAge][j]; }
for(i=0; i<acrossBit; i++)
{
t = colonyState[index][nextAge][i];
colonyState[index][nextAge][i] = colonyState[index+1][nextAge][i];
colonyState[index+1][nextAge][j] = t;
}
}
//变异
void aberrance(int index)
{
int ed, nextAge;
nextAge = (currAge+1) %2;
/
/只有1/3的概率发⽣异变
ed = rand() %(packageNum*3);
if(ed < packageNum)
colonyState[index][nextAge][ed] = (colonyState[index][nextAge][ed] + 1) %2; }
//处理死亡个体
void dealDeath()
{
int i, j;
int weight, w;
int nextAge = (currAge+1) %2;
for(i=0; i<colonySize; i++)
{
weight = 0;
for(j=0; j<packageNum; j++)
weight += packageWeight[j] * colonyState[i][nextAge][j];
if(weight > limitWeight)
{
w = limitWeight +1;
while(w > limitWeight)
{
w = 0;
for(j=0; j<packageNum&&w<=limitWeight; j++)
{
colonyState[i][nextAge][j] = rand() %2;
w += packageWeight[j] * colonyState[i][nextAge][j];
}
}
}
}
//printColonyState(nextAge);
}
//最优个体保护
void saveBest()
{
int i, j;
int min, minp, value;
int nextAge = (currAge+1) %2;
min = indivdualMsg[0].value;
minp = -1;
for(i=0; i<colonySize; i++)
{
value = 0;
for(j=0; j<packageNum; j++)
value += packageValue[j] *colonyState[i][nextAge][j];
if(value <= min)
{
min = value;
minp = i;
}
}
if(minp >= 0)
{
for(j=0; j<packageNum; j++)
鲕粒灰岩
{
colonyState[minp][nextAge][j] = colonyState[indivdualMsg[0].index][currAge][j]; }
}
}
void printResult()
{
cout<<"-----------------------------------------------------------"<<endl;
cout<<"结果:"<<endl;
int j, w = 0;
cout<<tw(10)<<"物品I ";
for(j=0; j<packageNum; j++)
{
cout<<tw(5)<<j+1;
}
百度dns
cout<<endl;
cout<<tw(10)<<"重量W ";
for(j=0; j<packageNum; j++)
{
w += packageWeight[j] *colonyState[indivdualMsg[0].index][currAge][j]; cout<<tw(5)<<packageWeight[j];
}
cout<<endl;
cout<<tw(10)<<"价值V ";
for(j=0; j<packageNum; j++)
cout<<tw(5)<<packageValue[j];
cout<<endl;
cout<<tw(10)<<"Choo: ";
for(j=0; j<packageNum; j++)
cout<<tw(5)<<colonyState[indivdualMsg[0].index][currAge][j];
cout<<endl;
cout<<"总重量: "<<w<<endl;
cout<<"总价值: "<<indivdualMsg[0].value<<endl;
}
///
void tProblem()
{
int i;
cout<<" 遗传算法求解下⾯的背包问题"<<endl;
cout<<"-------------------------------------------------------"<<endl;
cout<<"物品I 1 2 3 4 5 6 7 8 9 10 "<<endl;
cout<<"重量W 5 3 11 15 7 9 13 6 8 14 "<<endl;
cout<<"价值V 100 5 20 100 60 40 90 40 50 80 "<<endl;
cout<<"-------------------------------------------------------"<<endl;
packageNum=10; //物品的个数
limitWeight=25; //背包容量
colonySize = 100;//克隆次数
cout<<"物品个数= "<<packageNum<<endl;
提前批需要多少分
cout<<"背包容量= "<<limitWeight<<endl;
cout<<"克隆次数= "<<colonySize<<endl;
}
void printColonyState(int k)
{
cout<<"----------------------------------------------------"<<endl;
cout<<"colonyState-->";
if(k == currAge)
cout<<"currAge:"<<endl;
el
cout<<"next age:"<<endl;
int i, j;
for(i=0; i<colonySize; i++)
{
for(j=0; j<packageNum; j++)
cout<<tw(2)<<colonyState[i][k][j];
cout<<endl;
}
}
void printIndividualMsg()
{
int i;
cout<<"---------------------------------------------------"<<endl;
cout<<"Individual Msg:"<<endl;
for(i=0; i<colonySize; i++)
cout<<indivdualMsg[i].index<<"\t"<<indivdualMsg[i].value<<endl; }
int main()
{
srand((unsigned int)time(NULL));
tProblem();
//初始化群体
colonyInit();
printColonyState(currAge);
while(! stopFlag())
{
//评价当前群体
indivdualEstimate();
//⽣成下⼀代
for(int i=0; i<colonySize; i+=2)
{
int male = gambleChoo();
int female = gambleChoo();
across(male, female, i);
aberrance(i);
aberrance(i+1);
}
莫斯科旅游攻略//处理死亡个体
dealDeath();
//保护最优个体
saveBest();
//现在的下⼀代变成下⼀轮的当前代
currAge = (currAge+1) %2;
}
//输出问题解
indivdualEstimate();
printResult();
system("Pau");
}
