tsp.h

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

using namespace std;
std::vector<double> lpCityDistance;
template <typename T, typename P>
class Csga
{
        
public:
        Csga();
        Csga(int times,int GENERATION_AMOUNT,int CITY_AMOUNT);         //构造函数
        ~Csga();                                                                                        //析构函数                
        

        bool fnCreateRandomGene();          //产生随机基因
        bool fnGeneAberrance();              //基因变异
        bool fnGeneMix();                     //基因交叉产生新的个体测试并淘汰适应度低的个体
        
        bool fnEvalAll(int dai);                     //测试所有基因的适应度
        int  fnEvalOne(T &Gene);              //测试某一个基因的适应度
        void Crossover( int nFatherA, int nFatherB);
        void fnDispProbability();       //显示每个个体的权值
        void fnDispHistoryMin();
		void fnDispaverage();
        void fnDispHistoryMindai();
        

private:
        bool fnGeneAberranceOne(const int &i, const int &j);//变异某个基因
        T m_GenerationGene[MAX_GENERATION_AMOUNT];      //定义每个群体的基因
        P m_vProbability;         //定义每个群体的适应度
        int mindai;
		 int  _TIMES  ;
		 int _GENERATION_AMOUNT;
		 int _CITY_AMOUNT;
        double HistoryMin;
        T    HistoryMinWay;
        T m_GenerationGeneBk[MAX_GENERATION_AMOUNT];
};


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

template <typename T, typename P>
Csga<T, P>::Csga(int times,int GENERATION_AMOUNT,int CITY_AMOUNT)
{
	     _TIMES=times;
         _GENERATION_AMOUNT=GENERATION_AMOUNT;
         _CITY_AMOUNT=CITY_AMOUNT;
        m_vProbability.reserve(_CITY_AMOUNT);
        HistoryMin = _INFINITE;
        
        //cout << _P(lpCityDistance, 3, 2);                                        //调试用
}

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


//产生随机基因
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(_CITY_AMOUNT);
                

                for (j = 0; j < _CITY_AMOUNT; ++j)
                {
                        do
                        {
                                temp = rand()%_CITY_AMOUNT;
                        }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 < _CITY_AMOUNT; ++j)
                {
                        temp = rand()%10000;
                        if ( temp > 0 && temp <= _P_GENE_ABERRANCE)
                        {
                                //随机抽选到的基因进行变异
                                if(!fnGeneAberranceOne(i, j)) {exit(0);}
                        }//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()% _CITY_AMOUNT;
        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;
}

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());//pos等于适应度最小值
                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())
        if(_GENERATION_AMOUNT%2!=0)
			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));

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


        for (i = 0; i <_GENERATION_AMOUNT/2 ; ++i) //杂交_P_GENE_MIX/10次
        {

                iFather = temp[_ITEMP];
                do
                {
                        iMother = temp[_ITEMP];
                }while(iMother == iFather);

                

                Child1.reserve(_CITY_AMOUNT);                //初始化子女的碱基数
                Child2.reserve(_CITY_AMOUNT);
                Child1.clear();
                Child2.clear();