遗传算法求解0

1、遗传算法求解0-1背包问题。(步骤)#include iostream.h#include iomanip.h#include stdlib.h#include math.h#include time.h定义问题的最大规模#define max 100问题规模，即共有多少个包int packageNum;每个包的重量int packageWeightmax;每个包的价值int packageValuemax;约束，背包的最大容量int limitWeight;群体的规模int colonySize;/colonyStateik表示一个染色体/colonyState1.colonySize 0|

2、1 表示一代群体 int colonyStatemax2max;/ currAge表示当前代的编号/ (currAge+1)%2表示下一代的编号 int currAge = 0;个体评价信息表typedef struct tagIndividualMsgint index;int value; IndividualMsg;IndividualMsg individualMsgmax;/函数声明void printColonyState( int nextAge );/初始化群体void colonyInit()int i , j;int w;for( i = 0 ; i limitweight

3、 )w = 0;for( j = 0 ; j packageNum & w value - x-value;void individualEstimate()int i , j;for( i = 0 ; i colonySize ; i+ )individualMsgi.index = i;individualMsgi.value = 0;for( j = 0 ; j packageNum ; j + + )individualMsgi.value += packageValuej * colonyStateicurrAgej;qsort( individualMsg , colonySize

4、 , sizeof(IndividualMsg) , cmp );终止循环的条件bool stopFlag()/进行n代进行后停止static int n = 50;if( n- = 0 ; i-)wheeli = ( individualMsgi.value + wheeli+1 ) + colonySize * ( colonySize - i ); int seed = abs( wheel0 - ( rand() % ( 2 * wheel0 ) + 1 );choose = colonySize - 1;while( seed wheelchoose) choose-;/ coute

5、ndl;/ coutwheel :endl;/ for( i = 0 ; i colonySize ; i+ )/ coutvvsetw(5)vvwheeli;/ coutendl;/ coutseed = vvseedvvendl;/ coutvchoose vvchoosevvendl;return choose;/交叉void across( int male , int female , int index )int nextAge = (currAge+1)%2;int i , j , t;int acrossBit = rand() % (packageNum-1) + 1;for

6、( j = 0 ; j packageNum ; j+ )colonyStateindexnextAgej=colonyStateindividualMsgmale.indexcurrAgej;colonyStateindex+1nextAgej=colonyStateindividualMsgfemale.indexcurrAgej;for( i = 0 ; i acrossBit ; i+ )t = colonyStateindexnextAgei;colonyStateindexnextAgei = colonyStateindex+1nextAgei;colonyStateindex+

7、1nextAgej = t;/变异void aberrance( int index )int seed , nextAge;nextAge = (currAge+1)%2;/只有1/3的概率发生异变seed = rand() % ( packageNum * 3 );if( seed packageNum )colonyStateindexnextAgeseed = ( colonyStateindexnextAgeseed + 1 ) % 2;/处理死亡个体void dealDeath()int i , j;int weight , w;int nextAge = (currAge+1)%

8、2;for( i = 0 ; i colonySize ; i+ )weight = 0;for( j = 0 ; j limitweight )随机生成新的个体w = limitweight + 1;while( w limitweight )w = 0;for( j = 0 ; j packageNum & w = limitweight ; j + + )colonyStateinextAgej = rand() % 2;w += packageWeightj * colonyStateinextAgej;printColonyState( nextAge );最优个体保护void sa

9、veBest()int i , j;int min , minp , value;int nextAge = ( currAge+1)%2;min = individualMsg0.value;minp = -1;for( i = 0 ; i colonySize ; i+ )value = 0;for( j = 0 ; j packageNum ; j + + )value += packageValuej * colonyStateinextAgej;if( value = 0 )for( j = 0 ; j packageNum ; j + + )colonyStateminpnextA

10、gej=colonyStateindividualMsg0.indexcurrAgej;/void setProblem()int i;packageNum = 5;int w = 5,4,3 , 2 , 1 ;int v = 8,9 , 3 , 1 , 2 ;for( i = 0 ; i packageNum ; i+ )packageWeighti = wi;packageValuei = vi;limitweight = 13;colonySize = 5;void printProblem()int i;coutendl;coutproblem state:endl;coutpacka

11、geNum = vvpackageNumvvendl;coutlimitWeight = limitWeightendl;coutWeight:;for( i = 0 ; i packageNum ; i+ ) coutsetw(3)packageWeighti;coutendl;coutValue:;for( i = 0 ; i packageNum ; i+ )coutsetw(3)packageValuei;coutendl;void printColonyState( int k )cout”;if( k = currAge )coutvvcurrAge:vvendl;elsecout

12、vnext age:vendl;int i , j;for( i = 0 ; i colonySize ; i+ )for( j = 0 ; j packageNum ; j + + )coutvsetw(2)vcolonyStateikj;coutvvendl;void printIndividualMsg()int i;coutvvvvendl;coutvIndividual Msg:vvendl;for( i = 0 ; i colonySize ; i+ )coutvvindividualMsgi.indexvvtvvindividualMsgi.valuevvendl;/void m

13、ain()srand( (unsigned int)time(NULL);setProblem();printProblem();初始群体colonyInit();printColonyState( currAge );while( !stopFlag()评价当前群体individualEstimate();生成下一代for( int i = 0 ; i colonySize ; i += 2 )int male = gambleChoose();int female = gambleChoose();across( male , female , i );aberrance( i );abe

14、rrance( i + 1 );/处理死亡个体dealDeath();最优个体保护saveBest();现在的下一代变成下一轮的当前代currAge = ( currAge + 1 ) % 2;/printColonyState( currAge );输出问题解individualEstimate();cout近似解:endl;int j , w = 0;coutvvsetw(10)vvValue:;for( j = 0 ; j packageNum ; j+ )coutvvsetw(5)vvpackageValuej;coutendl;coutvvsetw(10)vvWeight:;for( j = 0 ; j v packageNum ; j+ )w += packageWeightj * colonyStateindividualMsg0.indexcurrAgej;coutvvsetw(5)vvpackageWeightj;c