tsp.h

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

	}
	if (szDist[i][j] > szDist[i][k])
	{
		m = j;
	}
	else
	{
		m = k;
	}
	j = 0;
	while (szAnti[j] != newj)
	{
		j++;
	}
	//szAnti[m]和szAnti[j]交换
	k = szAnti[m];
	szAnti[m] = szAnti[j];
	szAnti[j] = k;

//	funOutput(szAnti,n);

	//新抗体的总距离
	nDisTmp = funDistCompute(szAnti,n);
	if (nDisTmp < nDist)
	{
		nDist = nDisTmp;
		fprintf(fpProc,"%s%d\n","COST:",nDist); //just for debug
		for (i=0;i<n;i++)
		{
			szAnswer[i] = szAnti[i];
			fprintf(fpProc,"%d ",szAnswer[i]); //just for debug
		}
		fputs("\n",fpProc); //just for debug
	}
}
*/

inline int fnRndBoundary(int iBegin, int iEnd)
{     
     
     return rand()%(iEnd-iBegin) + iBegin;
}

//基因交叉产生新的个体并淘汰适应度低的个体
template <typename T, typename P>
bool Csga<T, P>::fnGeneMix()
{
     srand(time(0));
     std::vector<int> temp;                 //选择池
     P vProbabilityBk;                     //临时保存适应度
     vProbabilityBk = m_vProbability;
     temp.reserve( ((_GENERATION_AMOUNT+1)*_GENERATION_AMOUNT)/2 );
     
     P::iterator pos;
     
     for (int i = _GENERATION_AMOUNT; i > 0; --i)
     {
         pos  = std::min_element(vProbabilityBk.begin(), vProbabilityBk.end());
         temp.insert( temp.end(), i, (int)(pos-vProbabilityBk.begin()) );
         *pos = _INFINITE; 
     }
     
     /**************************************************************************
     fnDispProbability();
     cout << "\ttemp\n" << std::endl;                     //调试用

         copy( temp.begin(), temp.end(), std::ostream_iterator<int>(cout," ") );
         cout << std::endl;                                 //调试用


     **************************************************************************/
     #define _MIN_ELEMENT     std::min_element(m_vProbability.begin(), m_vProbability.end())
     m_GenerationGeneBk[_GENERATION_AMOUNT-1] = m_GenerationGene[_MIN_ELEMENT - m_vProbability.begin()];
     
     int iFather;                         //父亲的代号
     int iMother;                         //母亲的代号
     T Child1, Child2;                     //父亲与母亲杂交出的子女的基因
//     T::iterator tempIter;
     int LowBoundary;
     int HighBoundary;
     //int iChild1Probability,iChild2Probability;
     T fatherBk,motherBk;
     T::iterator V_iter;
//     P::iterator P_iter;
     int iDistance;

     srand(time(0));

#ifndef _ITEMP
#define _ITEMP rand()%(((_GENERATION_AMOUNT+1)*_GENERATION_AMOUNT)/2)
#endif

     for (i = 0; i < _P_GENE_MIX; ++i) //杂交_P_GENE_MIX/10次
     {
         iFather = temp[_ITEMP];
         do
         {
             iMother = temp[_ITEMP];
         }while(iMother == iFather);

         Child1.reserve(n);         //初始化子女的碱基数
         Child2.reserve(n);
         Child1.clear();
         Child2.clear();
         
         LowBoundary = fnRndBoundary(0, n-2);
         HighBoundary= fnRndBoundary(LowBoundary+1, n-1);

         /**********************************************************************
         cout << "iMother:" << iMother << std::endl;
         cout << "iFather:" << iFather << std::endl;
         cout << "LowBoundary:"  << LowBoundary  << std::endl;
         cout << "HighBoundary:" << HighBoundary << std::endl;
         **********************************************************************/

         fatherBk = m_GenerationGene[iFather];
         motherBk = m_GenerationGene[iMother];

         std::copy (fatherBk.begin()+LowBoundary, fatherBk.begin()+HighBoundary+1, 
                                     std::back_inserter(Child1));

         std::copy (motherBk.begin()+LowBoundary, motherBk.begin()+HighBoundary+1,
                                     std::back_inserter(Child2));
         /**********************************************************************
         cout << "Child1:" ;
         for (tempIter=Child1.begin(); tempIter!=Child1.end(); ++tempIter)
             cout << *tempIter << " ";
         cout << std::endl;
         cout << "Child2:" ;
         for (tempIter=Child2.begin(); tempIter!=Child2.end(); ++tempIter)
             cout << *tempIter << " ";
         cout << std::endl;
         **********************************************************************/

         std::rotate (fatherBk.begin(), fatherBk.begin()+HighBoundary+1, fatherBk.end());
         std::rotate (motherBk.begin(), motherBk.begin()+HighBoundary+1, motherBk.end());
         /**********************************************************************
         cout << "fatherBk:" ;
         copy (fatherBk.begin(),fatherBk.end(), std::ostream_iterator<int>(cout, " "));
         cout << std::endl;
         cout << "motherBk:" ;
         copy (motherBk.begin(), motherBk.end(), std::ostream_iterator<int>(cout, " "));
         cout << std::endl;
         **********************************************************************/
         for (V_iter = m_GenerationGene[iFather].begin()+LowBoundary;
             V_iter != m_GenerationGene[iFather].begin()+HighBoundary+1; ++V_iter)
         {
             motherBk.erase(std::remove(motherBk.begin(), motherBk.end(), *V_iter),
                                         motherBk.end());
         }
         
         for (V_iter = m_GenerationGene[iMother].begin()+LowBoundary;
             V_iter != m_GenerationGene[iMother].begin()+HighBoundary+1; ++V_iter)
         {
             
             fatherBk.erase(std::remove(fatherBk.begin(), fatherBk.end(), *V_iter),
                                         fatherBk.end());
         }
         /**********************************************************************
         cout << "fatherBk:" ;
         copy (fatherBk.begin(),fatherBk.end(), std::ostream_iterator<int>(cout, " "));
         cout << std::endl;
         cout << "motherBk:" ;
         copy (motherBk.begin(), motherBk.end(), std::ostream_iterator<int>(cout, " "));
         cout << std::endl;
         **********************************************************************/

         iDistance = n -HighBoundary - 1;
         std::copy(motherBk.begin(), motherBk.begin()+iDistance, std::back_inserter(Child1));
         std::copy(motherBk.begin()+iDistance, motherBk.end(), std::inserter(Child1,Child1.begin()));

         std::copy(fatherBk.begin(), fatherBk.begin()+iDistance, std::back_inserter(Child2));
         std::copy(fatherBk.begin()+iDistance, fatherBk.end(), std::inserter(Child2,Child2.begin()));

         /**********************************************************************
         cout << "Child1:";
         copy (Child1.begin(), Child1.end(), std::ostream_iterator<int>(cout, " "));
         
         cout << "iChild1Probability:" << iChild1Probability << std::endl;
         cout << "Child2:" ;
         copy (Child2.begin(), Child2.end(), std::ostream_iterator<int>(cout, " "));
         cout << "iChild2Probability:" << iChild2Probability << std::endl;
         **********************************************************************/
         /*iChild1Probability = fnEvalOne(Child1);
         //iChild2Probability = fnEvalOne(Child2);

         
         P_iter = std::max_element(m_vProbability.begin(), m_vProbability.end());

         if (iChild1Probability < *P_iter)
         {
             m_GenerationGene[P_iter-m_vProbability.begin()] = Child1;
             *P_iter = iChild1Probability;
         }

         P_iter = std::max_element(m_vProbability.begin(), m_vProbability.end());
         if (iChild2Probability < *P_iter)
         {
             m_GenerationGene[P_iter-m_vProbability.begin()] = Child2;
             *P_iter = iChild2Probability;
         }
         */
         m_GenerationGeneBk[2*i]  = Child1;
         m_GenerationGeneBk[2*i+1] = Child2;
     }             
     for (i = 0; i < _GENERATION_AMOUNT; ++i)
     {
         m_GenerationGene[i] = m_GenerationGeneBk[i];
     }
     return true;
}

//测试基因的适应度
template <typename T, typename P>
bool Csga<T, P>::fnEvalAll()
{
     int i, j;
     m_vProbability.assign( _GENERATION_AMOUNT, 0);
     //cout << "\t基因适应度\n";
     
     //测试每组基因的适应性
     for (i = 0; i < _GENERATION_AMOUNT; ++i)
     {
         for (j = 0; j < n-1; ++j)
         {
             m_vProbability[i] += _P(lpCityDistance, 
                 m_GenerationGene[i][j], m_GenerationGene[i][j+1]);
         }//end for (j = 0; j < n; ++j);     
         m_vProbability[i] += _P(lpCityDistance, 
                 m_GenerationGene[i][n-1], m_GenerationGene[i][0]);
         if (m_vProbability[i] < HistoryMin)
         {
             HistoryMin = m_vProbability[i];
             HistoryMinWay = m_GenerationGene[i];
         }
         
     }//end for (int j, i = 0; i < _GENERATION_AMOUNT; ++i)
     //copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator<int>(cout," "));
     //cout << std::endl;

     //m_vProbability[_GENERATION_AMOUNT-1] = fnEvalOne(m_GenerationGeneBk[_GENERATION_AMOUNT-1]);
     return true;
}

//测试某个基因的适应度并返回适应度
template <typename T, typename P>
int Csga<T, P>::fnEvalOne(T &Gene)
{
     int iResult = 0;
     
   for (int i = 0; i < n-1; ++i)
     {
         iResult += _P(lpCityDistance, Gene[i], Gene[i + 1]);
     }
     
     return iResult;
}

template <typename T, typename P>
void Csga<T, P>::fnDispProbability()
{
     
     /*cout << "\t个体基因序列" <<std::endl;                     //调试用
     for (int i = 0; i < _GENERATION_AMOUNT; ++i)
     {
         cout << " 个体" << i+1 << "的基因:";
         copy( m_GenerationGene[i].begin(), m_GenerationGene[i].end(),
                                         std::ostream_iterator<int>(cout," ") );
         if (i%2 == 1)
             cout << std::endl;
     }
     */
     cout << "总路程为:"; 
#define _VECT_TEMP     std::min_element(m_vProbability.begin(), m_vProbability.end())
     
     cout << *_VECT_TEMP << std::endl;//+_GENERATION_AMOUNT
     
     //cout << "各个方案的路程分别为:" ;
     //copy (m_vProbability.begin(), m_vProbability.end(), std::ostream_iterator<int>(cout, " "));
     cout << std::endl;
//     cout << "*******************************************************" << std::endl;
}

template <typename T, typename P>
void Csga<T, P>::fnDispHistoryMin()
{
    cout << "历史上最短总路程为:" << HistoryMin << endl;
	cout << " 路径为:" ;
    std::copy (HistoryMinWay.begin(), HistoryMinWay.end(), std::ostream_iterator<int>(cout, " ->"));
    cout << *HistoryMinWay.begin();
    cout <<std::endl;
}


template <typename T, typename P>
void Csga<T, P>::fnOutputFile()
{
		FILE * fpout;
	int i=0;

	fpout = fopen("result.txt","w");
	
	while (i < 2) 
	{
		fputs(szTspInfo[i++],fpout);
	}
	i = 0;
	while (szTspInfo[2][i] != '\0') 
	{
		i++;
	}
	szTspInfo[2][i-1] = '\0';
	fprintf(fpout,"%s",szTspInfo[2]);
//	cout << szTspInfo[2] << endl;
	fprintf(fpout,"(%d)\n",HistoryMin);
	fprintf(fpout,"%s%d\n","DIMENSION: ",n);
	fputs("TOUR_SECTION\n",fpout);

	for (i=0;i<n;i++)
	{
		fprintf(fpout,"%d ",HistoryMinWay[i]);
	}

	fputs("\n-1\n",fpout);
	fputs("EOF\n",fpout);

	fclose(fpout);
}