tsp_iga.cpp

C++实现的免疫遗传算法

// TSP_IGA.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include<time.h>
using std::cout;
using std::cin;
using std::endl;

//城市连接矩阵
int city[10][10]={0,25,34,13,32,15,16,29,9,26,
                  25,0,4,19,65,23,76,58,6,22,
				  34,4,0,29,13,8,88,33,53,21,
				  13,19,29,0,66,43,6,25,99,49,
                  32,65,13,66,0,78,21,43,11,30,
				  15,23,8,43,78,0,20,17,91,73,
				  16,76,88,6,21,20,0,36,24,62,
				  29,58,33,25,43,17,36,0,39,40,
                  9,6,53,99,11,91,24,39,0,31,
				  26,22,21,49,30,73,62,40,31,0};
int generation;                  //当前代数      
int D[40][40];                   //抗体之间的多样性程度,
int Dbg[40];                     //抗体与抗原之间的多样性程度
double fitness[40][40];          //抗体之间的亲和力
int Dc[40];						 //
double r=0.9;					 //抗体之间的亲和力阈值

double Pc=0.2;					 // 交叉概率
double Pm=0.02;		             // 变异概率
double Ins[3];					 //优势肽链

typedef struct A                 // 抗体、抗原结构
{
	 int chrom[10];              //采用路径表示方法来实现抗体基因编码
	 int leng;                   //抗体的路径长度
	 double fitness;             //抗体对抗原的亲和力
	 double fc;                  //抗体的浓度
} A;
A Ag,Ab[40],AE[8];               //Ag抗原，Ab抗体群，AE较优越的抗体群

//查找抗体群中路径最短的一条
int findshortest()
{
	int i,j=0,leng=Ab[0].leng; 
	for(i=1;i<40;i++)
	{
		if(leng>Ab[i].leng)
		{leng=Ab[i].leng;j=i;}
	}
	return j;
}
//初始化群体
void GenerateInitial()
{
	int i=0,j;
	//初始化抗体路径
	for(;i<40;i++)
	{
		Ab[i].chrom[0]=0;      //为简化，均从城市0开始出发
		Ab[i].leng=0;
		for(j=1;j<10;j++)
		{
			int ture=1;
			int temp;
			while(ture==1)
			{
				int k=0;
				ture=0;
			    temp=(rand()/32768.0)*10;
				for(;k<j;k++)
					if(Ab[i].chrom[k]==temp) ture=1;
			}
			Ab[i].chrom[j]=temp;
			Ab[i].leng+=city[(Ab[i].chrom[j-1])][(Ab[i].chrom[j])];
			//cout<<Ab[i].chrom[j]<<"   ";
		}
	}
    //初始定义抗原为抗体中路径最短的一条
	j=findshortest();
	for(i=0;i<10;i++)
	{
		Ag.chrom[i]=Ab[j].chrom[i];
	}
	Ag.leng=Ab[j].leng;
}

//评价群体
void Evaluate()
{
	//计算亲和力
	int i,j,k;
	for(i=0;i<40;i++)
	{
		//计算路径长度
		Ab[i].leng=0;
		for(j=1;j<10;j++)
			Ab[i].leng+=city[(Ab[i].chrom[j-1])][(Ab[i].chrom[j])];
		//计算抗体与抗原之间的亲和力
		Dbg[i]=0;Dc[i]=-1;
		for(j=0;j<10;j++)
			if(Ag.chrom[j]!=Ab[i].chrom[j]) Dbg[i]++;
		Ab[i].fitness=1.0/(1+Dbg[i]);
		
		for(j=0;j<40;j++)
		{
			//计算抗体间的多样性程度
			D[i][j]=0;
			if(i<j)
			{	
				for(k=0;k<10;k++)
					if(Ab[i].chrom[k]!=Ab[j].chrom[k]) D[i][j]++;
			}
			else if(i==j)
				D[i][j]=0;
			else if(i>j)	D[i][j]=D[j][i];
			//cout<<D[i][j]<<"   ";
			//计算抗体之间的亲和力
			fitness[i][j]=1.0/(1+D[i][j]);
			if(fitness[i][j]>r) Dc[i]++;
		}
		//计算抗体浓度
		Ab[i].fc=Dc[i]/40.0;
		//cout<<endl<<Ab[i].fitness<<" "<<Dc[i]<<"  "<<Ab[i].fc<<endl;
	}
	//更新抗原Ag
	j=findshortest();
	for(i=0;i<10;i++)
		Ag.chrom[i]=Ab[j].chrom[i];
	Ag.leng=Ab[j].leng;
}

//交叉
void Crossover()
{
	int pos,i,j,k,temp[10],t;
	double p;
	for(i=0;i<40;i+=2)
	{		
		p=rand()%1000/1000.0;
		if(p<Pc)
		{
			pos=(rand()/32768.0)*10;
			while(pos==0||pos==9)	pos=(rand()/32768.0)*10;
			//cout<<pos<<"   ";
			t=pos;
			for(j=0;j<10;j++)
				temp[j]=Ab[i].chrom[j];
			for(k=1;k<10;k++)
			{
				for(j=1;j<pos;j++)
					if(Ab[i+1].chrom[k]==Ab[i].chrom[j]) break;
				if(j<pos) continue;
				Ab[i].chrom[pos]=Ab[i+1].chrom[k];
				pos++;
			}
			pos=t;
			for(k=1;k<10;k++)
			{
				for(j=1;j<pos;j++)
					if(Ab[i+1].chrom[j]==temp[k]) break;
				if(j<pos) continue;
				Ab[i+1].chrom[pos]=temp[k];
				pos++;
			}
			//cout<<i<<"  In the Crossover"<<endl;
		}
	}
}
//倒序变异
void Mutation()
{
	int begin,end,temp,i;
	double p;
	for(i=0;i<40;i++)
	{
		p=rand()%1000/1000.0;
		if(p<Pm)
		{
			begin=(rand()/32768.0)*10;
			while(begin==0)		begin=(rand()/32768.0)*10;
			end=(rand()/32768.0)*10;
			while(end==0||end==begin)	end=(rand()/32768.0)*10;
			if(begin>end)
			{
				temp=begin;
				begin=end;
				end=temp;
			}
			//cout<<begin<<"  "<<end<<"  ";
			for(;begin<end;begin++,end--)
			{
				temp=Ab[i].chrom[begin];
				Ab[i].chrom[begin]=Ab[i].chrom[end];
				Ab[i].chrom[end]=temp;
			}
		//cout<<i<<"  In the Mutation"<<endl;
		}
	}
	
}
//克隆操作
void Clone()
{
	int i,j,k;
	double best,worst;
	best=worst=Ab[0].fitness;
	for(i=j=k=1;i<40;i++)
	{	
		if(best<Ab[i].fitness)
		{
			best=Ab[i].fitness;
			j=i;
		}
		if(worst>Ab[i].fitness)
		{
			worst=Ab[i].fitness;
			k=i;
		}
	}
	if(j!=k&&Ab[i].fc<0.2)
	{
		for(i=0;i<10;i++)
			Ab[k].chrom[i]=Ab[j].chrom[i];
		//cout<<j<<"   "<<k<<"In the Clone"<<endl;
	}
	//修改亲和力
	Dbg[k]=-1;
	for(i=0;i<10;i++)
		if(Ag.chrom[i]!=Ab[k].chrom[i]) Dbg[k]++;
	Ab[k].fitness=1.0/(1+Dbg[k]);
}
//将植入优势肽链的路径加入到群体中
void Insert()
{
	int i,t,j=0,fitness=Ab[0].fitness;
	//取优势基因段 
	t=findshortest();
	for(i=0;i<3;i++)
		Ins[i]=Ab[t].chrom[i];
	//植入优势肽链，取代亲和力最低的个体
	for(i=1;i<40;i++)
	{
		if(fitness>Ab[i].fitness)
		{fitness=Ab[i].fitness;j=i;}
	}
	//第j个个体为亲和力最低的个体
	Ab[j].leng=0;
	for(i=1;i<3;i++)
		Ab[j].chrom[i]=Ins[i];
	for(;i<10;i++)
	{
		int ture=1;
		int temp;
		while(ture==1)
		{
			int k=0;
			ture=0;
		    temp=(rand()/32768.0)*10;
			for(;k<i;k++)
				if(Ab[j].chrom[k]==temp) ture=1;
		}
		Ab[j].chrom[i]=temp;
		//Ab[j].leng+=city[(Ab[j].chrom[i-1])][(Ab[j].chrom[i])];
	}
	//修改亲和力
	Dbg[j]=-1;
	for(i=0;i<10;i++)
		if(Ag.chrom[i]!=Ab[j].chrom[i]) Dbg[j]++;
	Ab[j].fitness=1.0/(1+Dbg[j]);
}
int main(int argc, _TCHAR* argv[])
{
	char a;
	int i,j;
	srand( (unsigned)time( NULL ) );
	GenerateInitial();
	Evaluate();
	generation=0;
	while(generation<1000)
	{
		generation++;
		Insert();
		Clone();
		Crossover();
		Mutation();
		Insert();
		Evaluate();
		//cout<<generation<<":  "<<Ag.leng<<endl;
		//cin>>a;
	}
	for(int i=0;i<10;i++)
		cout<<Ag.chrom[i]<<"  ";
	cout<<Ag.leng<<endl;
	cout<<"Press any key to continue......"<<endl;
	cin>>a;
	return 0;
}