tsp.h

实现用固定变异概率和自适应变异概率解tsp问题的比较

                
                LowBoundary = fnRndBoundary(0, _CITY_AMOUNT-2);
                HighBoundary= fnRndBoundary(LowBoundary+1, _CITY_AMOUNT-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 = _CITY_AMOUNT -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>
void Csga<T, P>::fnDispaverage()
{
	double average=0;
	int i;
	for (i = 0; i < _GENERATION_AMOUNT; ++i)
		average+= m_vProbability[i] ;
	average=average/ _GENERATION_AMOUNT;
     cout << "\t平均开销为:"<<average<<endl;
}

//测试基因的适应度
template <typename T, typename P>
bool Csga<T, P>::fnEvalAll(int dai)
{
        int i, j;
        m_vProbability.assign( _GENERATION_AMOUNT, 0);
        //cout << "\t基因适应度\n";
        
        //测试每组基因的适应性
        for (i = 0; i < _GENERATION_AMOUNT; ++i)
        {
                for (j = 0; j < _CITY_AMOUNT-1; ++j)
                {
					m_vProbability[i] +=lpCityDistance[ m_GenerationGene[i][j]* _CITY_AMOUNT+m_GenerationGene[i][j+1]]; 
                }//end for (j = 0; j < _CITY_AMOUNT; ++j);        
                m_vProbability[i] +=lpCityDistance[ m_GenerationGene[i][_CITY_AMOUNT-1]*_CITY_AMOUNT+m_GenerationGene[i][0]];
                if (m_vProbability[i] < HistoryMin)
                {
                        HistoryMin = m_vProbability[i];
                        HistoryMinWay = m_GenerationGene[i];
                         mindai=dai;
                }
                
        }//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 < _CITY_AMOUNT-1; ++i)
        {
                iResult +=lpCityDistance[Gene[i]*_CITY_AMOUNT+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 << "\t最小开销为:"; 
#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 << " 路径为:" ;
        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>::fnDispHistoryMindai()
{
	cout << "历史上最短开销出现在:"<<mindai<<"代"<<endl;
}