ga.cpp

一个遗传算法的VC版本

#pragma once

#include "ga.h"
using namespace std;

//参数设置函数定义
void CGA::preSet(const vector<vector<int> >& mapDist,float _pcross,float _pmutation,int _popsize,int _maxgen,int _evolveWay)
{
	//设置参数
	pcross = _pcross;
	popsize = _popsize;
	popsize = _popsize;
	maxgen = _maxgen;
    evolveWay = _evolveWay;
	lchrom = mapDist.size();	

	genes.resize(lchrom);
	max_var = 0;
	for(int i=0;i<lchrom;++i)
	{
		genes[i].ID = i;
		for(int j=0;j<lchrom;++j)
		{			
			genes[i].linkCost[&genes[j]] = mapDist[i][j];
			if( mapDist[i][j] > max_var)
				max_var = mapDist[i][j];
		}
	}	
}

//遗传算法启动函数定义
pair<vector<int>,int> CGA::start()
{
	initpop(oldpop);  //产生初始种群

	//通过不断进化，直到达到最大世代数
	int best; //最优染色体编号
	for(gen = 0;gen<maxgen;gen++)
	{			
		generation(oldpop,newpop); //从当前种群产生新种群
		oldpop.pop_chrom.swap(newpop.pop_chrom); 
		oldpop.sumfitness = newpop.sumfitness;
		newpop.pop_chrom.clear();									
	}
	best = chooseBest(oldpop); //最佳染色体

    pair<vector<int>,int> result; //最优结果
    for(int i=0;i<lchrom;++i)
		result.first.push_back(oldpop.pop_chrom[best].chrom_gene[i]->ID);
	result.second = oldpop.pop_chrom[best].varible;
	///////////////////////////////////////////////////////////////////////////////
	//////////////////////////         改动                   ////////////////////
	return result;
}


//产生一个随机整数(在[low,high)区间上)
inline int CGA::randomInt(int low,int high)
{	
	if(low==high)
		return low;	
	return low+rand()%(high-low);
}

//计算一条染色体的个体适应度
inline void CGA::chromCost(Chrom& chr)
{
	float sum=0;
	for(int i=0;i<lchrom;++i)
	{
		sum += (chr.chrom_gene[i])->linkCost[chr.chrom_gene[i+1]];
	}
	sum += (chr.chrom_gene.front())->linkCost[chr.chrom_gene.back()];
	chr.varible = sum;
	chr.fitness = max_var*(lchrom) - chr.varible;
}

//计算一个种群的个体适应度之和
inline void CGA::popCost(Pop &pop)
{
	float sum=0;
	for(int i=0;i<popsize;++i)
	{
		sum+=pop.pop_chrom[i].fitness;
	}
	pop.sumfitness = sum;
}

//随机初始化一条染色体
inline void CGA::initChrom(Chrom& chr)
{	
	vector<int> tmp(lchrom);
	for(int i=0;i<lchrom;i++)
		tmp[i]=i;
	int choose;
	while(tmp.size()>1)
	{
		choose = randomInt(0,tmp.size());
		chr.chrom_gene.push_back(&genes[tmp[choose]]);
		tmp.erase(tmp.begin()+choose);
	}
	chr.chrom_gene.push_back(&genes[tmp[0]]);
	chromCost(chr);	
}

//随机初始化种群
inline void CGA::initpop(Pop& pop)
{
	pop.pop_chrom.reserve(popsize);
	Chrom tmp;
	tmp.chrom_gene.reserve(lchrom);
	for(int i=0;i<popsize;i++)
	{
		initChrom(tmp);
		pop.pop_chrom.push_back(tmp);
		tmp.chrom_gene.clear();
	}
	popCost(pop);
}


//轮盘赌选择,返回种群中被选择的个体编号
inline int CGA::selectChrom(const Pop& pop)
{
	float sum = 0;
	float pick = float(randomInt(0,1000))/1000;
	int i = 0;
	if(pop.sumfitness!=0)
	{
		while(1)
		{
			sum += pop.pop_chrom[i].fitness/pop.sumfitness;
			++i;
			if( (sum > pick) || i==pop.pop_chrom.size())
				return i-1;  
		}		
	}
	else
		return randomInt(0,pop.pop_chrom.size());	
}

//精英策略，返回最优秀的一条染色体
inline int CGA::chooseBest(const Pop& pop)
{
	int choose = 0;
	float best = 0;
	for(int i = 0;i< pop.pop_chrom.size();++i)
	{
		if(pop.pop_chrom[i].fitness > best)
		{
			best = pop.pop_chrom[i].fitness;
			choose = i;
		}		
	}
	return choose;
}

//染色体交叉操作,由两个父代产生两个子代( 顺序交叉 OX )
inline void CGA::crossover(Chrom& parent1,Chrom& parent2,Chrom& child1,Chrom& child2)
{
	child1.chrom_gene.resize(lchrom);
	child2.chrom_gene.resize(lchrom);

	vector<Gene*>::iterator v_iter,p1_beg,p2_beg,c1_beg,c2_beg,p1_end,p2_end,c1_end,c2_end;	
	p1_beg = parent1.chrom_gene.begin();
    p2_beg = parent2.chrom_gene.begin();
	c1_beg = child1.chrom_gene.begin();
    c2_beg = child2.chrom_gene.begin();
	p1_end = parent1.chrom_gene.end();
    p2_end = parent2.chrom_gene.end();
	c1_end = child1.chrom_gene.end();
    c2_end = child2.chrom_gene.end();
	

	vector<Gene*> v1(parent2.chrom_gene),  v2(parent1.chrom_gene); //用于交叉的临时表	

	//随机选择两个交叉点
    int pick1 = randomInt(1,lchrom-1);
	int pick2 = randomInt(pick1,lchrom-1);
	int dist = lchrom-1-pick2; //第二交叉点到尾部的距离	

	//子代保持两交叉点间的基因不变
	copy(p1_beg+pick1, p1_beg+pick2+1, c1_beg+pick1);
    copy(p2_beg+pick1, p2_beg+pick2+1, c2_beg+pick1);
	
	//循环移动表中元素
	rotate(v1.begin(), v1.begin()+pick2+1,v1.end());
    rotate(v2.begin(), v2.begin()+pick2+1,v2.end());	

	//从表中除去父代已有的元素	
	for(v_iter = p1_beg+pick1; v_iter!=p1_beg+pick2+1; ++v_iter)	
		remove(v1.begin(),v1.end(),*v_iter);
	for(v_iter = p2_beg+pick1; v_iter!=p2_beg+pick2+1; ++v_iter)	
		remove(v2.begin(),v2.end(),*v_iter);	
    
	//把表中元素复制到子代中
	copy(v1.begin(), v1.begin()+dist, c1_beg+pick2+1);
	copy(v1.begin()+dist, v1.begin()+dist+pick1, c1_beg);
	copy(v2.begin(), v2.begin()+dist, c2_beg+pick2+1);
	copy(v2.begin()+dist, v2.begin()+dist+pick1, c2_beg);	
}

//染色体变异操作,随机交换两个基因
inline void CGA::mutation(Chrom& chr)
{
	vector<Gene*>::iterator beg = chr.chrom_gene.begin();
	int pick1,pick2;
	pick1 = randomInt(0,lchrom);
	do{
		pick2 =randomInt(0,lchrom);
	}while(pick1==pick2);

	iter_swap(beg+pick1, beg+pick2);
}

//世代进化(由当前种群产生新种群)
void CGA::generation(Pop& oldpop,Pop& newpop)
{	
	newpop.pop_chrom.resize(popsize);
	int mate1,mate2,j;
	float pick;
	float tmp;
	Chrom gene1,gene2,tmp1,tmp2;
	gene1.chrom_gene.resize(lchrom);
	gene2.chrom_gene.resize(lchrom);
	tmp1.chrom_gene.resize(lchrom);
	tmp2.chrom_gene.resize(lchrom);
	
	//将最佳染色体放入下一代
	mate1 = chooseBest(oldpop);
	newpop.pop_chrom[0] = oldpop.pop_chrom[mate1]; 
	j = 1;

	//产生两条新染色体
	do{
		int count = 0;
		mate1 = selectChrom(oldpop);
		mate2 = selectChrom(oldpop);
		pick = float(randomInt(0,1000))/1000;
		gene1= oldpop.pop_chrom[mate1];
		gene2= oldpop.pop_chrom[mate1];
		
		if(pick < pcross)  //交叉操作
		{			
			if(evolveWay==1)
			{
				crossover(oldpop.pop_chrom[mate1],oldpop.pop_chrom[mate2],newpop.pop_chrom[j],newpop.pop_chrom[j+1]);
				chromCost(newpop.pop_chrom[j]); //计算适应度
				chromCost(newpop.pop_chrom[j+1]);
			}
            else if(evolveWay==2) //强迫进化
			{
				int count = 0;
				bool flag1 = false;
				bool flag2 = false;
				while(1)
				{
					crossover(oldpop.pop_chrom[mate1],oldpop.pop_chrom[mate2],tmp1,tmp2);
					chromCost(tmp1); //计算适应度
					chromCost(tmp2);
					if(tmp1.fitness > gene1.fitness)
					{
						gene1 = tmp1;
						flag1 = true;
					}
					if(tmp2.fitness > gene2.fitness)
					{
						gene2 = tmp2;
						flag2 = true;
					}
					if((flag1==true && flag2==true) || count> 31) //当子代都比父代优秀或寻找次数超过n次，跳出
					{
						newpop.pop_chrom[j] = gene1;
						newpop.pop_chrom[j+1] = gene2;
						break;
					}
					count++;
				}
			}
		}
		else
		{
			newpop.pop_chrom[j].chrom_gene = oldpop.pop_chrom[mate1].chrom_gene;
			newpop.pop_chrom[j+1].chrom_gene = oldpop.pop_chrom[mate2].chrom_gene;
			chromCost(newpop.pop_chrom[j]);
			chromCost(newpop.pop_chrom[j+1]);

		}		

		pick = float(randomInt(0,1000))/1000;
		if(pick < pmutation)  //变异操作
		{			
			if(evolveWay==1)
			{
				mutation(newpop.pop_chrom[j]);
				chromCost(newpop.pop_chrom[j]); //计算适应度
			}
			else if(evolveWay==2) //强迫进化
			{
				int count = 0;
				tmp = newpop.pop_chrom[j].fitness;
				do{					
					mutation(newpop.pop_chrom[j]);
					chromCost(newpop.pop_chrom[j]); //计算适应度
					count++;
				}while(tmp > newpop.pop_chrom[j].fitness && count < 20); //当子代比父代优秀或寻找次数超过n次，跳出
			}
		}

		pick = float(randomInt(0,1000))/1000;
		if(pick < pmutation)  //变异操作
		{			
			if(evolveWay==1)
			{
				mutation(newpop.pop_chrom[j+1]);
				chromCost(newpop.pop_chrom[j+1]); //计算适应度
			}
			else if(evolveWay==2) //强迫进化
			{
				int count = 0;
				tmp = newpop.pop_chrom[j+1].fitness;
				do{					
					mutation(newpop.pop_chrom[j+1]);
					chromCost(newpop.pop_chrom[j+1]); //计算适应度
					count++;
				}while(tmp > newpop.pop_chrom[j+1].fitness && count < 20); //当子代比父代优秀或寻找次数超过n次，跳出
			}
		}
		j += 2;		
	}while(j < popsize-1);

	popCost(newpop); //计算新种群的适应度之和	
}