tsp2dlg.cpp

用遗传算法解决旅行商问题

// TSP2Dlg.cpp : 实现文件
//

#include "stdafx.h"
#include "showpic.h"
#include "TSP2.h"
#include "TSP2Dlg.h"
#include "Dlg2.h"
#include <cmath>
#include <ctime>
#include <vector>
#include <hash_map>
#include <string>
#include <iostream>
#include <algorithm>
#include <windows.h>   
#include <stdio.h> 
using namespace std;
using namespace stdext;

#ifdef _DEBUG
#define new DEBUG_NEW
#endif



float pcross=0.8; //交叉率
float pmutation=0.1; //变异率
int popsize=100; //种群大小
const int lchrom = 42; //染色体长度
int gen; //当前世代
int maxgen = 50; //最大世代数
int run; //当前运行次数
int maxruns =1; //总运行次数
float max_var = 400 ; //路径最大连接开销!!
FILE *galog;                     /* an output(1) file */
int select_mode=0;


//基因定义(一个城市)
struct Gene
{ 
	string name;
	hash_map<Gene*,float> linkCost; //该城市到其它城市的路程开销
};

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

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

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



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

//计算一条染色体的个体适应度
inline void chromCost(Chrom& chr)
{
	float 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=max_var*(lchrom) - chr.varible;
}

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

//随机初始化一条染色体
inline 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);
}


//计算每一个染色体的累计概率
/*inline void caculatecfns(Pop& pop)
{
	pop.pop_chrom[0].cfitness=pop.pop_chrom[0].fitness/pop.sumfitness;
	for(int i=1;i<popsize;i++){
		pop.pop_chrom[i].cfitness=pop.pop_chrom[i-1].cfitness+pop.pop_chrom[i].fitness/pop.sumfitness;
	}
}*/
//轮盘赌选择,返回种群中被选择的个体编号
inline int 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; //
		}
		/*for(i=0;i<popsize;i++){
			if(pop.pop_chrom[i].cfitness>pick)
				return i;
		}
		return i;*/
	}
	else
		return randomInt(0,pop.pop_chrom.size()); 
}

 ////竞赛选择,返回种群中被选择的个体编号
inline int selecttournament(const Pop& pop)
{
	float fitness=0;
	int fitest=0;
       float pick ;
		
	for(int i=0;i<2;i++){	
	pick = randomInt(0,pop.pop_chrom.size()-1);
              if(fitness<pop.pop_chrom[pick].fitness){
           fitness=pop.pop_chrom[pick].fitness;
		   fitest=pick;}
          
	};
	if(fitness=0) return randomInt(0,pop.pop_chrom.size()); 
	return fitest;
}
//精英策略，返回最优秀的一条染色体
inline int 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 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);
}

//世代进化(由当前种群产生新种群)
void 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;

	//caculatecfns(oldpop);//计算每一个染色体的累计概率
	//产生两条新染色体
       
	do{
		int count = 0;
            /////////////选择模式///////////////   
          if(!select_mode){
		mate1 = selectChrom(oldpop);
	mate2 = selectChrom(oldpop);
             }
         else{
                 mate1 = selecttournament(oldpop);
		mate2 = selecttournament(oldpop);

                 } 
       //  if(select_mode==10) select_mode=0;
              
        //    select_mode++;
////////////////////////////////////////////////
		pick = float(randomInt(0,1000))/1000;
		gene1= oldpop.pop_chrom[mate1];
		gene2= oldpop.pop_chrom[mate2];

		if(pick < pcross) //交叉操作
		{
			/*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> 40)
				{
					newpop.pop_chrom[j] = gene1;
					newpop.pop_chrom[j+1] = gene2;
					break;
				}
				count++;
			}*/ 
			crossover(oldpop.pop_chrom[mate1],oldpop.pop_chrom[mate2],tmp1,tmp2);
			chromCost(tmp1); //计算适应度
			chromCost(tmp2);
			newpop.pop_chrom[j] = tmp1;
			newpop.pop_chrom[j+1] = tmp2;
		}
		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) //变异操作
		{
			/*int count = 0;
			do{
				tmp = newpop.pop_chrom[j].fitness;
				mutation(newpop.pop_chrom[j]);
				chromCost(newpop.pop_chrom[j]); //计算适应度
				count++;
			}while(tmp > newpop.pop_chrom[j].fitness && count < 30);*/
			mutation(newpop.pop_chrom[j]);
			chromCost(newpop.pop_chrom[j]); //计算适应度
		}
		pick = float(randomInt(0,1000))/1000;
		if(pick < pmutation) //变异操作
		{
			/*int count = 0;
			do{
				tmp = newpop.pop_chrom[j+1].fitness;
				mutation(newpop.pop_chrom[j+1]);
				chromCost(newpop.pop_chrom[j+1]); //计算适应度
				count++;
			}while(tmp > newpop.pop_chrom[j+1].fitness && count < 30);*/
			mutation(newpop.pop_chrom[j+1]);
			chromCost(newpop.pop_chrom[j+1]); //计算适应度
		}

		//chromCost(newpop.pop_chrom[j]); //计算适应度
		//chromCost(newpop.pop_chrom[j+1]);

		j += 2; 
	}while(j < popsize-1);

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

//输出一条染色体信息
inline void outChrom(Chrom& chr)
{
	cout<<endl<<"路径:";
	for(int i=0;i<lchrom;i++)
	{
		cout<<chr.chrom_gene[i]->name;
	}
		cout<<endl<<"回路总开销:"<<chr.varible<<endl;
	 fprintf(galog,"\r\n回路总开销: %0f ",chr.varible);
	cout<<"适应度:"<<chr.fitness<<endl;
	 fprintf(galog,"\r\n适应度: %0f ",chr.fitness);

}