tsp.h

很好的遗传面算法 欢迎大家下载

#include "def.h"
using namespace std;
char szTspInfo[10][128]; //存储TSP文件信息
int n;

template <typename T, typename P>
class Csga
{
     
public:
	Csga();
	Csga(DISTANCE *lpDistance);              //构造函数
	~Csga();                                 //析构函数         

	void funSortDist();                      //将距离从小到大排序，用作免疫疫苗提取。
	void funImOperator();                    //构造免疫算子

	bool fnCreateRandomGene();               //产生随机基因
	bool fnGeneAberrance();                  //基因变异
	bool fnGeneMix();                        //基因交叉产生新的个体测试并淘汰适应度低的个体

	bool fnEvalAll();                        //测试所有基因的适应度
	int  fnEvalOne(T &Gene);                 //测试某一个基因的适应度

	void fnDispProbability();                //显示每个个体的权值
	void fnDispHistoryMin();
	void fnOutputFile();


private:
	bool fnGeneAberranceOne(const int &i, const int &j);    //变异某个基因
	T m_GenerationGene[_GENERATION_AMOUNT];                 //定义每个群体的基因
	P m_vProbability;                                       //定义每个群体的适应度
	DISTANCE *lpCityDistance;
	int HistoryMin;
	T  HistoryMinWay;

	T m_GenerationGeneBk[_GENERATION_AMOUNT];

	struct vacci{
		int i,j;
		int Dij;
	}sctVac[N]; 

	vector< vector<int> > vec2ImOperator;   //二维向量，存放免疫算子。
};

//构造函数
template <typename T, typename P>
Csga<T, P>::Csga()
{
}

template <typename T, typename P>
Csga<T, P>::Csga(DISTANCE *lpDistance)
{
     lpCityDistance = lpDistance;
     m_vProbability.reserve(n);
     HistoryMin = _INFINITE;
     
     //cout << _P(lpCityDistance, 3, 2);                     //调试用
}

//析构函数
template <typename T, typename P>
Csga<T, P>::~Csga()
{
}

template <typename T, typename P>
void Csga<T, P>::funSortDist()     //将距离从小到大排序
{
	vacci sctTmp;
	int i,j,k;
	k = 0;
//	nDistCount = n*(n+1)/2-1;

	for (i=0;i<n-1;i++)
	{
		j=i+1;
		sctVac[k].i = i;
		sctVac[k].j = j;
		sctVac[k].Dij = szDist[i][j];
		for (j=i+2;j<n;j++)
		{
			if (szDist[i][j] < sctVac[k].Dij) 
			{
				sctVac[k].j = j;
				sctVac[k].Dij = szDist[i][j];
			}			
		}
		k++;
	}
	
	nDistCount = k;

	//按距离从小到大排序
	for (i=0;i<nDistCount-1;i++)
	{	
		k = i;
		for (j=i+1;j<nDistCount;j++)
		{
			if (sctVac[j].Dij<sctVac[k].Dij) k=j;
		}
		sctTmp = sctVac[k];
		sctVac[k] = sctVac[i];
		sctVac[i] = sctTmp;
	}
	
	//for debug.
//	for (i=0;i<nDistCount;i++)
//	{
//		//printf("%d(%d,%d) ",sctVac[i].Dij,sctVac[i].i+1,sctVac[i].j+1);
//		printf("%d(%d,%d) ",sctVac[i].Dij,sctVac[i].i,sctVac[i].j);
//	}
//	printf("\n\n");
}

template <typename T, typename P>
void Csga<T, P>::funImOperator()   //构造免疫算子
{
	vector < int > vecTemp;
	vector <int> ::iterator posi;
	int k,i,j;
	int size,nTemp;
	bool bExist=false;

	for (k=0;k<n;k++)
	{
		//当第一次或两两相连的情况出现时，增加一维。
		if ( vec2ImOperator.empty() || 
			((k+1 < n) && (sctVac[k].i == sctVac[k+1].j) && (sctVac[k].j == sctVac[k+1].i)))
		{
			vecTemp.clear();
			vecTemp.push_back(sctVac[k].i);
			vecTemp.push_back(sctVac[k].j);
			vec2ImOperator.push_back(vecTemp);
			k++;
			continue;
		}

		//处理不是两两相连的情况
		size = vec2ImOperator.size();
		for (i=0;i<size;i++)
		{
			//nTemp = vec2ImOperator[i][nSize-1];
			if (vec2ImOperator[i][0] == sctVac[k].i)
			{
				vec2ImOperator[i].push_back(sctVac[k].j);
				for (j=vec2ImOperator[i].size()-1;j>0;j--)
				{
					vec2ImOperator[i][j] = vec2ImOperator[i][j-1];
				}
				vec2ImOperator[i][0] = sctVac[k].j;
			}
			else if (vec2ImOperator[i][0] == sctVac[k].j)
			{
				vec2ImOperator[i].push_back(sctVac[k].i);
				for (j=vec2ImOperator[i].size()-1;j>0;j--)
				{
					vec2ImOperator[i][j] = vec2ImOperator[i][j-1];
				}
				vec2ImOperator[i][0] = sctVac[k].i;
			}
			else if (vec2ImOperator[i][vec2ImOperator[i].size()-1] == sctVac[k].i)
				vec2ImOperator[i].push_back(sctVac[k].j);
			else if (vec2ImOperator[i][vec2ImOperator[i].size()-1] == sctVac[k].j)
				vec2ImOperator[i].push_back(sctVac[k].i);
		}
	}
	for (i=0;i<n;i++) 
	{
		bExist = false;
		for (j=0;j<vec2ImOperator.size();j++) 
		{
			posi = find(vec2ImOperator[j].begin(),vec2ImOperator[j].end(),i);
			if (posi != vec2ImOperator[j].end()) 
			{
				bExist = true;
				break;
			}
		}
		if (!bExist)
		{
			vecTemp.clear();
			vecTemp.push_back(i);
			vec2ImOperator.push_back(vecTemp);
		}

	}			
/****************************************************Debug ****************************/
	cout << endl << "免疫算子：" << endl ;
	for (i=0;i<vec2ImOperator.size();i++)
	{
		copy(vec2ImOperator[i].begin(),vec2ImOperator[i].end(),ostream_iterator<int>(cout," "));
		cout << endl;
	}
/**************************************************************************************/
}


//产生随机基因
template <typename T, typename P>
bool Csga<T, P>::fnCreateRandomGene()
{
     srand( time(0) );                                         //初始化随机数

     //cout << "\t基因序列" << std::endl;                     //调试用
     
     //生成随机基因
     for(int j, temp, i = 0; i < _GENERATION_AMOUNT; ++i)
     {
         m_GenerationGene[i].reserve(n);
         

         for (j = 0; j < n; ++j)
         {
             do
             {
                 temp = rand()%n;
             }while (find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp)
                             != m_GenerationGene[i].end());

             m_GenerationGene[i].push_back(temp);
         
         }//end for

         /*copy( m_GenerationGene[i].begin(), m_GenerationGene[i].end(),
                                 std::ostream_iterator<int>(cout," ") );
         cout << std::endl;     */                             //调试用
     }
     return true;
}


//变异
template <typename T, typename P>
bool Csga<T, P>::fnGeneAberrance()
{
     int i, j;
     int temp;
     srand(time(0));
     
     //抽选一代中的某个基因进行变异
     for (i = 0; i < _GENERATION_AMOUNT; ++i)
     {
         for (j = 0; j < n; ++j)
         {
             temp = rand()%10000;
             if ( temp > 0 && temp <= _P_GENE_ABERRANCE)
             {
                 //随机抽选到的基因进行变异
                 //if(!fnGeneAberranceOne(i, j)) {exit(0);}
				 fnGeneAberranceOne(i, j);
             }//end if
         }//end for j
     }//end for i     
     return true;
}

//变异第i个基因的第j位染色体
//template <typename T, typename P>
//bool Csga<T, P>::fnGeneAberranceOne(const int &i, const int &j)
//{
//     int temp;                                             //基因变异结果
//
//     srand(time(0));
//	 temp = rand()%n;
//     T::iterator pos;
//
//     //找到变异位与另外一位交换
//     pos = std::find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp);
//
//     if (pos != m_GenerationGene[i].end())
//     {
//         *pos = m_GenerationGene[i][j];
//         m_GenerationGene[i][j] = temp;
//         return true;
//     }
//     return false;
//}

template <typename T, typename P>
bool Csga<T, P>::fnGeneAberranceOne(const int &i, const int &j)
{
    int temp;  //基因变异结果
//	int nDisTmp;
	T::iterator pos;
//	vacci *pSct;      //指向sctVac[N]，由小到大选择路径

	srand(time(0));
	temp = rand()%n;

	//debug
//	for (k=0;k<n;k++)
//	{
//		cout << endl;
//		cout << sctVac[k].Dij <<"("<<sctVac[k].i<<",";
//		cout << sctVac[k].j << ")" <<endl;
//	}
	
	//找到变异位与另外一位交换
	pos = std::find(m_GenerationGene[i].begin(), m_GenerationGene[i].end(), temp);

	if (pos != m_GenerationGene[i].end())
	{
		*pos = m_GenerationGene[i][j];
		m_GenerationGene[i][j] = temp;
		return true;
	}
	return false;
}
/*
void funMutation(int newi,int newj)
{
	int i,j,k,m;
	int nDisTmp;
	i = 0;
	while (szAnti[i] != newi) 
	{
		i++;
	}
	j = i-1;
	k = i+1;
	if (j == -1)
	{
		j = n-1;
	}
	if (k == n)
	{
		k = 0;