gatspdlg.cpp

自己编写的遗传算法源代码（GA)

// GATSPDlg.cpp : implementation file
//

#include "stdafx.h"
#include "GATSP.h"
#include "GATSPDlg.h"
#include "DRAWMAP.h"
#include "CANSHU.h"
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
using namespace std;
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif


//设置相关参数
const int lchrom = 15;   // 染色体长度，城市的个数

double pcross = 0.85; //交叉率
double pmutation = 0.1; //变异率
int popsize = 100; //种群大小
int gen; //当前世代
int maxgen = 100; //最大世代数
double max_var = 5000 ; //路径最大连接开销!!
double total_distance = 75000;   // 15个城市的最大距离，用来计算适应度
int loc[15];        // 存储编号

struct Gene
{
	string name;
	map<Gene*,double> linkCost;//该城市到其它城市的路程开销
	int num;                  // 该城市的编号
};

//染色体定义(到各城市顺序的一种组合)
struct Chrom
{
	vector<Gene*> chrom_gene; //染色体（到各城市去的顺序）
	double varible; //路程总开销
	double fitness; //个体适应度 
};

//种群定义
struct Pop
{
	vector<Chrom> pop_chrom; //种群里的染色体组
	double sumfitness; //种群中个体适应度累计 
};

// 城市名称
string citys[lchrom] = {"哈尔滨","北京","太原","兰州","西安","成都","拉萨","昆明",
"海口","广州","厦门","杭州","南京","武汉","上海"};

//int position[6] = {250,5,200,40,180,50};


// 城市之间的距离
const double dis[lchrom][lchrom] = {{0,1217,1683,2536,2275,2970,4085,3624,3725,3223,2873,2091,1925,2308,1934},
{1217,0,468,1375,1057,1753,2939,2412,2642,2186,1995,1303,1043,1221,1236},
{1683,468,0,933,596,1288,2490,1964,2305,1896,1826,1271,996,954,1272},
{2536,1375,933,0,588,689,1564,1415,2187,1967,2174,1915,1679,1329,1991},
{2275,1057,596,588,0,698,2009,1369,1837,1512,1625,1328,1099,750,1411},
{2970,1753,1288,689,698,0,1438,738,1548,1429,1783,1783,1621,1127,1916},
{4085,2939,2490,1564,2009,1438,0,1466,2573,2686,3155,3222,3049,2565,3349},
{3624,2412,1964,1415,1369,738,1466,0,1109,1257,1793,2093,2018,1490,2262},
{3725,2642,2305,2187,1837,1548,2573,1109,0,417,1001,1620,1688,1281,1808},
{3223,2186,1896,1967,1512,1429,2686,1257,417,0,595,1214,1306,965,1401},
{2873,1995,1826,2174,1625,1783,3155,1793,1001,595,0,782,976,898,949},
{2091,1303,1271,1915,1328,1783,3222,2093,1620,1214,782,0,276,656,188},
{1925,1043,996,1679,1099,1621,3049,2018,1688,1306,976,276,0,529,312},
{2308,1221,954,1329,750,1127,2565,1490,1281,965,898,656,529,0,1916},
{1934,1236,1272,1991,1411,1916,3349,2262,1808,1401,949,188,312,1916,0}};

vector<Gene> genes(lchrom); //保存全部基因
Pop oldpop; //当前代种群
Pop newpop; //新一代种群

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

//计算一条染色体的个体适应度
inline void chromCost(Chrom& chr)
{
	double sum=0;
	for(int i=0;i<chr.chrom_gene.size()-1;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=total_distance - chr.varible;
}

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

//随机初始化一条染色体
void 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 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); //种群的适应度
}

//轮盘赌选择,返回种群中被选择的个体编号
int selectChrom(const Pop& pop)
{
	double sum = 0;
	double 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 chooseBest(const Pop& pop)
{
	int choose = 0;
	double 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;
}
void 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-2);
	int pick2 = randomInt(pick1+1,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 mutation(Chrom& chr)
{
	vector<Gene*>::iterator beg = chr.chrom_gene.begin();
	int pick1,pick2;
	pick1 = randomInt(0,lchrom-1);
	do{
		pick2 =randomInt(0,lchrom-1);
	}while(pick1==pick2);
	
	iter_swap(beg+pick1, beg+pick2);
}
bool comp(const Chrom&a, const Chrom& b)
{
	return a.fitness > b.fitness;
}

//世代进化(由当前种群产生新种群)
void generation(Pop& oldpop,Pop& newpop1)
{ 
	Pop newpop;
	newpop.pop_chrom.resize(popsize*3);
	int mate1,mate2,j;
	double pick;
	double 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);
	newpop1.pop_chrom.resize(popsize);
	//将最佳染色体放入下一代
	mate1 = chooseBest(oldpop);
	newpop1.pop_chrom[0] = oldpop.pop_chrom[mate1];  // 杰出者选择
	j = 0;
	int count = 0;  // 执行次数
	int times;
	while(true)
	{
		do{
		mate1 = selectChrom(oldpop);  //随机选择一个个体
		mate2 = selectChrom(oldpop);  //随机选择一个个体
		}while(mate1 == mate2);

		pick = float(randomInt(0,1000))/1000; //产生随机数
		gene1= oldpop.pop_chrom[mate1];
		gene2= oldpop.pop_chrom[mate2];
		if(pick < pcross) //交叉操作
		{
			crossover(gene1,gene2,tmp1,tmp2);//杂交
			chromCost(tmp1); //计算新个体适应度
			chromCost(tmp2); //计算新个体适应度
			newpop.pop_chrom[j] = tmp1;
			newpop.pop_chrom[j+1] = tmp2;
			count += 2;
		}	
		else
		{
			newpop.pop_chrom[j].chrom_gene = gene1.chrom_gene;
			newpop.pop_chrom[j+1].chrom_gene = gene2.chrom_gene;
			chromCost(newpop.pop_chrom[j]);
			chromCost(newpop.pop_chrom[j+1]);
			count += 2;
		} 
		pick = float(randomInt(0,1000))/1000;
		if(pick < pmutation) //变异操作
		{
				mutation(newpop.pop_chrom[j]);
				chromCost(newpop.pop_chrom[j]); //计算适应度 
				
		}
		pick = float(randomInt(0,1000))/1000;