用遗传算法解决0-1背包问题概述

}

X[i].chromsome[j]=k;

w+=k*weight[j];//个体的总重量 v+=k*value[j]; //个体的总价值

if(w>KW) i--; //如果不是解，重新生成 else { X[i].fitness=v; X[i].weight=w;

if(v==stop){bestindividual=X[i];return;}//这种情况一般不会发生

} } }

/************************************************************************/ void CalculateFitnessValue() { int i=0,j=0; for (i=0; i

w+=X[i].chromsome[j]*weight[j];//个体的总重量 v+=X[i].chromsome[j]*value[j]; //个体的总价值 }

X[i].fitness=v; X[i].weight=w;

if(v==stop){bestindividual=X[i];return;}//符合条件情况下最优解这种情况一般不会发生 if(w>KW) X[i]=bestindividual; //如果不是解，找最好的一个解代之 } }

/************************************************************************/ void SelectionOperator(void) { int i, index; double p, sum=0.0;

double cfitness[S];//选择、累积概率 individual newX[S];

for (i=0;i

for (i=0;i

for (i=1;icfitness[index])//轮盘赌进行选择 { index++;

}

}

newX[i]=X[index];

for (i=0; i

/************************************************************************/ void CrossoverOperator(void)//交叉操作 { int i=0, j=0,k=0;individual temp; for(i=0; i

/************************************************************************/ void MutationOperator(void) { int i=0, j=0,k=0,q=0; double p=0; for (i=0; i

if(X[i].chromsome[j]==1)X[i].chromsome[j]=0; else X[i].chromsome[j]=1; } } if(i==best) if(-1==comp(bestindividual,X[i]))//如果变异后适应度变小 X[i]=bestindividual; } }

/************************************************************************/ void FindBestandWorstIndividual(void) { int i; bestindividual=X[0]; for (i=1;ibestindividual.fitness) { bestindividual=X[i]; best=i; } } }

/*主函数*****************************************************************/ void main(void) {

srand((unsigned)time(0)); t=0;

GenerateInitialPopulation(); //初始群体包括产生个体和计算个体的初始值 while (t<=T) { FindBestandWorstIndividual(); //保存当前最优解 SelectionOperator(); //选择 CrossoverOperator(); //交叉 MutationOperator(); //变异 Checkalike(); //检查相似度 CalculateFitnessValue(); //计算新种群适应度 t++; }

FindBestandWorstIndividual(); //找到最优解 cout<

for(int k=0;k

/*结束***********************************************************************/