ga roulette.cpp

遗传算法求解01背包问题＋实验报告＋参考文献。如果你看了这个程序还是不能明白遗传算法的巧妙

#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)  //2的10次方，用来随机产生一个染色体时候很有用。


#define SIM 0.90		//算法终止条件之一：染色体之间的相似度上限
#define MP 0.2			//变异率

#define DIST 13			//程序中HASH表的距离

//程序中用到的HASH表中链表结点结构定义
typedef struct Node{
	int Fitness;		
	struct Node *Next;
}HASHNODE;//链表结点
//程序中用到的HASH表中头结点结构定义
typedef struct Head{
	int maxFitness;
	int Count;
	int Diff;
	HASHNODE *Next;
}HEAD;//头结点
//HASH表
HEAD hashTable[DIST];

//染色体的基因结构定义
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];
		}
	}
}
//初始化HASH表
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;
	}
}
//检查种群中的适应度是否SIM
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()%1000/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()%1000)/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();//产看是否满足SIM
		cout<<"-------"<<nCount<<"-------"<<endl;
	}
	cout<<nCount<<endl;
	indexMaxResult = maxFitness(hashTable);//所得的01背包问题的最大值

	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();
	}
}