one new ga to solve tsp .txt

用vc++程序编的遗传算法解决TSP问题.txt def.h TSP.cpp tsp.h

                /*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));


        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());
                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(_CITY_AMOUNT);                //初始化子女的碱基数
                Child2.reserve(_CITY_AMOUNT);
                Child1.clear();
                Child2.clear();
               
                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)
                {
               &