#include<iostream.h> #include<stdlib.h> #include<string.h> #include<time.h> #define POPSIZE 10 #define NUMG 10 #define MAXVOL 10 #define MAXVAL 20 #define CAPACITY 30 #define MAXB (1024) #define SIM 0.90 #define CP 1.0 #define MP 0.2 #define DIST 13 //程序中用到的HASH表结构定义 typedef struct Node{ int Fitness; struct Node *Next; }HASHNODE;//链表结点 typedef struct Head{ int maxFitness; int Count; int Diff; HASHNODE *Next; }HEAD;//头结点 HEAD hashTable[DIST]; //The representation of the item; typedef struct{ int Weight; int Fitness; int Gene[NUMG]; }GENE; //随即生成的基因组 GENE parentGenome[NUMG]={ {0,0,{0,0,1,0,1,1,0,1,0,1}}, {0,0,{0,0,1,1,0,0,0,1,0,1}}, {0,0,{0,0,0,1,1,0,0,0,1,1}}, {0,0,{0,1,0,0,0,1,0,1,1,0}}, {0,0,{1,0,1,0,0,1,1,0,0,1}}, {0,0,{1,1,0,0,0,1,0,0,1,1}}, {0,0,{0,1,0,0,0,1,0,1,1,0}}, {0,0,{1,0,1,1,0,1,0,0,0,0}}, {0,0,{1,1,1,0,1,1,0,1,0,0}}, {0,0,{1,1,1,1,0,0,0,0,0,0}} }; GENE nextGenome[NUMG]; //需要装入背包的物品 int Weight[NUMG]={6,9,8,8,6, 1, 10,5,7, 1}; int Value[NUMG]={2,20,5,4,19,14,18,8,11,6}; int indexPF[POPSIZE]; int indexCF[POPSIZE]; /// void calculateCapacity(GENE * Genome,int iD){ Genome[iD].Weight = 0; for(int j=0; j<NUMG ;j++){ if(Genome[iD].Gene[j]==1){ Genome[iD].Weight += Weight[j]; } } } void calculateFitness(GENE * Genome,int iD){ Genome[iD].Fitness = 0; for(int j=0; j<NUMG ;j++){ if(Genome[iD].Gene[j]==1){ Genome[iD].Fitness += Value[j]; } } } void checkCapacity(GENE * Genome,int iD){ while(Genome[iD].Weight>CAPACITY){ int idModify = rand()%NUMG; if(Genome[iD].Gene[idModify]==1){ Genome[iD].Gene[idModify] = 0; Genome[iD].Weight -= Weight[idModify]; Genome[iD].Fitness -= Value[idModify]; } } } void initHashTable(HEAD * hashTable){ for(int i=0; i<DIST ;i++){ hashTable[i].maxFitness = 0; hashTable[i].Count = 0; hashTable[i].Diff= 0; hashTable[i].Next = NULL; } } //初始化HASH表 int maxFitness(HEAD *hashTable){ int maxF = hashTable[0].maxFitness; int index =0; for(int i=1; i<DIST ;i++){ if(hashTable[i].maxFitness>maxF){ maxF = hashTable[i].maxFitness; index = i; } } return index; } //判断适应度Fitness是否已经在HASH表中 HASHNODE* isAlreadyExist(HASHNODE *pHead,int Fitness){ HASHNODE *lastPos = NULL; while(NULL!=pHead){ if(pHead->Fitness==Fitness){ break; } //cout<<pHead->Fitness<<endl; lastPos = pHead; pHead = pHead->Next; } return pHead; } //遍历HASH表 void TraverseHashTable(HEAD * hashTable){ int index = 0; HASHNODE *lastPos = NULL; cout<<"I:"<<"MAX:"<<"C:"<<"D:"<<"O"<<endl; for(int i=0; i<DIST ;i++){ if(hashTable[i].Count==0){ continue; } cout<<i<<":"<<hashTable[i].maxFitness<<":"<<hashTable[i].Count<<":"<<hashTable[i].Diff<<":"; lastPos = hashTable[i].Next; cout<<"Content:"; while(NULL!=lastPos){ cout<<lastPos->Fitness<<":"; lastPos = lastPos->Next; } cout<<endl; } } / bool checkFitness(){ HASHNODE *pNode = NULL; int index = 0; bool sameFlag = true; initHashTable(hashTable); for(int i=0; i<POPSIZE ;i++){ index = parentGenome[i].Fitness%DIST; hashTable[index].Count++; pNode = isAlreadyExist(hashTable[index].Next,parentGenome[i].Fitness); if(NULL==pNode){ pNode = new HASHNODE; hashTable[index].Diff++; pNode->Next = hashTable[index].Next; pNode->Fitness = parentGenome[i].Fitness; if(parentGenome[i].Fitness>hashTable[index].maxFitness){ hashTable[index].maxFitness = parentGenome[i].Fitness; } hashTable[index].Next = pNode; } } index = maxFitness(hashTable); double CPount = hashTable[index].Count/(double)POPSIZE; double pDiff = hashTable[index].Diff/(double)POPSIZE; if(CPount>=0.9 && pDiff<=0.1){ sameFlag = false; } TraverseHashTable(hashTable); return sameFlag; } / int Begin = 0; int End = 1; //计算从Begin－End位置的染色体的适应度之和 int summaryFitness(int Begin,int End){ int summaryF = 0; if(Begin<End){ for(int i=Begin; i<End ;i++){ summaryF += parentGenome[i].Fitness; } }else{ for(int i=Begin; i<POPSIZE ;i++){ summaryF += parentGenome[i].Fitness; } for(i=0; i<End ;i++){ summaryF += parentGenome[i].Fitness; } } return summaryF; } / //赌轮选择染色体以便于交叉操作 int selectIndex(){ double randProb = 0.0; double crossProb = 0.0; int summaryBE = 0; int summaryF = 0; int index; bool flag = true; randProb = rand()00/1000.0; summaryF = summaryFitness(0,POPSIZE); while(flag){ summaryBE = summaryFitness(Begin,End); crossProb = (double)summaryBE/(double)summaryF; if(crossProb>randProb){ index = End; Begin = End; flag = false; } End++; if(End>POPSIZE){ End = 1; } } return index; } // bool visitedFlag[POPSIZE]; //获取当前HASH表中的最大Fitness的索引 int selectedMaxFitness(GENE *Genome){ int maxPos = 0; for(int i=0; i<POPSIZE ;i++){ if(!visitedFlag[i]){ maxPos = i; i = POPSIZE; } } for(i=0; i<POPSIZE ;i++){ if(!visitedFlag[i]&&Genome[maxPos].Fitness<Genome[i].Fitness){ maxPos = i; } } return maxPos; } // //索引排序 void sortFitness(int *indexFitness,GENE *Genome){ memset(visitedFlag,false,NUMG*sizeof(bool)); for(int i=0; i<POPSIZE ;i++){ indexFitness[i] = selectedMaxFitness(Genome); visitedFlag[indexFitness[i]] = true; } } //精英策略：保持优秀的父染色体 void keepBestParents(){ for(int i=POPSIZE*8/10; i<POPSIZE ;i++){ parentGenome[indexPF[i]].Fitness = parentGenome[indexPF[i-POPSIZE*8/10]].Fitness; parentGenome[indexPF[i]].Weight = parentGenome[indexPF[i-POPSIZE*8/10]].Weight; for(int j=0; j<NUMG ;j++){ parentGenome[indexPF[i]].Gene[j] = parentGenome[indexPF[i-POPSIZE*8/10]].Gene[j]; } } } void updateGeneration(){ keepBestParents(); for(int i=0; i<POPSIZE*8/10 ;i++){ parentGenome[indexPF[i]].Fitness = nextGenome[indexCF[i]].Fitness; parentGenome[indexPF[i]].Weight = nextGenome[indexCF[i]].Weight; for(int j=0; j<NUMG ;j++){ parentGenome[indexPF[i]].Gene[j] = nextGenome[indexCF[i]].Gene[j]; } } } void crossOver(){ int partPos; sortFitness(indexPF,parentGenome); for(int i=0; i<POPSIZE/2 ;i++){ partPos = rand()%NUMG; int Father = selectIndex(); int Mother = selectIndex(); for(int j=0; j<partPos ;j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]; nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j]; } for(;j<NUMG;j++){ nextGenome[i].Gene[j] = parentGenome[Father].Gene[j]; nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j]; } calculateCapacity(nextGenome,i); calculateFitness(nextGenome,i); checkCapacity(nextGenome,i); calculateCapacity(nextGenome,i+POPSIZE/2); calculateFitness(nextGenome,i+POPSIZE/2); checkCapacity(nextGenome,i+POPSIZE/2); } sortFitness(indexCF,nextGenome); } void mutation(){ for(int i=0; i<POPSIZE ;i++){ double prob = (rand()00)/1000.0; if(prob<MP){ int partPos = rand()%NUMG; if(nextGenome[i].Gene[partPos]==1){ nextGenome[i].Gene[partPos]=0; nextGenome[i].Weight -= Weight[partPos]; nextGenome[i].Fitness -= Value[partPos]; }else{ if(nextGenome[i].Weight+Weight[partPos]<CAPACITY){ nextGenome[i].Gene[partPos]=1; nextGenome[i].Weight += Weight[partPos]; nextGenome[i].Fitness += Value[partPos]; }else{ //don't mutate! } } } } } void printGenome(){ for(int i=0; i<POPSIZE ;i++){ cout<<parentGenome[i].Weight<<"-"; cout<<parentGenome[i].Fitness<<"-"; for(int j=0; j<NUMG ;j++){ cout<<parentGenome[i].Gene[j]; } cout<<endl; } } void main(){ int nGenerations = 1000; int nCount = 0; bool flag = true; int indexMaxResult = 0; for(int i=0; i<POPSIZE ;i++){ for(int j=0; j<NUMG ;j++){ if(parentGenome[i].Gene[j]==1){ parentGenome[i].Weight += Weight[j]; parentGenome[i].Fitness += Value[j]; } } checkCapacity(parentGenome,i); } //generateChromosomes(); //generatePopulation(); printGenome(); flag = checkFitness(); cout<<"-------"<<nCount<<"-------"<<endl; while(flag&&nCount<nGenerations){ nCount++; crossOver(); mutation(); updateGeneration(); printGenome(); flag = checkFitness(); cout<<"-------"<<nCount<<"-------"<<endl; } cout<<nCount<<endl; indexMaxResult = maxFitness(hashTable); if(nCount<nGenerations){ cout<<"The maxValue is "<<hashTable[indexMaxResult].maxFitness<<endl; cout<<"The information in Genome is as below:"<<endl; printGenome(); }else{ cout<<"OH,Sorry!"; cout<<"The maxValue may be "<<hashTable[indexMaxResult].maxFitness<<endl; cout<<"The information in Genome is as below:"<<endl; printGenome(); } }
