《遗传算法求解0》由会员分享，可在线阅读，更多相关《遗传算法求解0（7页珍藏版）》请在金锄头文库上搜索。
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;elsecoutvnext age:vendl;int i , j;for( i =
