one new ga to solve tsp .txt

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

//遗传算法解决TSP问题
//http://www.nrmen.com/1/viewspace-15958.html

***********************************************************************/
def.h

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－


#ifndef                _GENERATION_AMOUNT

#define                _GENERATION_AMOUNT                        201                                //每一代的生存数
#define                _CITY_AMOUNT                                10                                           //城市数,等于基因数

//#define                _XCHG_GENE_AMOUNT_WHEN_MIX        2                            //每次杂交所交换的碱基数量                       

#define                _TIMES                                                50                                          //定义进化次数
#define                _DISP_INTERVAL                                5                                         //每隔多少次显示基因中的最高适应度
#define                _CONTAINER                                        std::vector<int>             //定义个体基因容器类型
#define                _CONTAINER_P                                std::vector<int>               //定义适应度容器类型
#define                _P(a,x,y)                                        *(a+(x)+(y)*_CITY_AMOUNT)       
#define                _P_GENE_ABERRANCE                        10                                //变异概率1%
#define                _P_GENE_MIX                                        (_GENERATION_AMOUNT-1)/2                //杂交次数
#define                _INFINITE                                        100000

typedef                int                                                        DISTANCE;                          //距离矩阵的数据存储类型

#endif





___________________________________________________________________________

TSP.cpp

____________________________________________________________________________


#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
#include "def.h"
#include "TSP.h"




void main()
{
       
        const static DISTANCE distance[][_CITY_AMOUNT]
                                                                =        {
                                                                                0, 1, 4, 6, 8, 1, 3, 7, 2, 9,
                                                                                1, 0, 7, 5, 3, 8, 3, 4, 2, 4,
                                                                                4, 7, 0, 3, 8, 3, 7, 9, 1, 2,
                                                                                6, 5, 3, 0, 3, 1, 5, 2, 9, 1,
                                                                                8, 3, 8, 3, 0, 2, 3, 1, 4, 6,
                                                                                1, 8, 3, 1, 2, 0, 3, 3, 9, 5,
                                                                                3, 3, 7, 5, 3, 3, 0, 7, 5, 9,
                                                                                7, 4, 9, 2, 1, 3, 7, 0, 1, 3,
                                                                                2, 2, 1, 9, 4, 9, 5, 1, 0, 1,
                                                                                9, 4, 2, 1, 6, 5, 9, 3, 1, 0
                                                                        };                                                        //城市间的距离矩阵
                                                                                                                                //distance[i][j]代表i城市与j城市的距离

        /*
        const static DISTANCE distance[][_CITY_AMOUNT]
                                                                                                ={
                                                                0, 1, 4, 6, 8, 1, 3, 7, 2, 9, 7, 3, 4, 5, 8, 9, 2, 8, 2, 8,
                                                                1, 0, 7, 5, 3, 8, 3, 4, 2, 4, 4, 6, 2, 8, 2, 9, 4, 5, 2, 1,
                                                                4, 7, 0, 3, 8, 3, 7, 9, 1, 2, 5, 8, 1, 8, 9, 4, 7, 4, 8, 4,
                                                                6, 5, 3, 0, 3, 1, 5, 2, 9, 1, 3, 5, 7, 3, 4, 7, 3, 4, 5, 2,
                                                                8, 3, 8, 3, 0, 2, 3, 1, 4, 6, 3, 8, 4, 5, 2, 8, 1, 7, 4, 7,
                                                                1, 8, 3, 1, 2, 0, 3, 3, 9, 5, 4, 5, 2, 7, 3, 6, 2, 3, 7, 1,
                                                                3, 3, 7, 5, 3, 3, 0, 7, 5, 9, 3, 4, 5, 9, 3, 7, 3, 2, 8, 1,
                                                                7, 4, 9, 2, 1, 3, 7, 0, 1, 3, 4, 5, 2, 7, 6, 3, 3, 8, 3, 5,
                                                                2, 2, 1, 9, 4, 9, 5, 1, 0, 1, 3, 4, 7, 3, 7, 5, 9, 2, 1, 7,
                                                                9, 4, 2, 1, 6, 5, 9, 3, 1, 0, 3, 7, 3, 7, 4, 9, 3, 5, 2, 5,
                                                                7, 4, 5, 3, 3, 4, 3, 4, 3, 3, 0, 5, 7, 8, 4, 3, 1, 5, 9, 3,
                                                                3, 6, 8, 5, 8, 5, 4, 5, 4, 7, 5, 0, 8, 3, 1, 5, 8, 5, 8, 3,
                                                                4, 2, 1, 7, 4, 2, 5, 2, 7, 3, 7, 8, 0, 5, 7, 4, 8, 3, 5, 3,
                                                                5, 8, 8, 3, 5, 7, 9, 7, 3, 7, 8, 3, 5, 0, 8, 3, 1, 8, 4, 5,
                                                                8, 2, 9, 4, 2, 3, 3, 6, 7, 4, 4, 1, 7, 8, 0, 4, 2, 1, 8, 4,
                                                                9, 9, 4, 7, 8, 6, 7, 3, 5, 9, 3, 5, 4, 3, 4, 0, 4, 1, 8, 4,
                                                                2, 4, 7, 3, 1, 2, 3, 3, 9, 3, 1, 8, 8, 1, 2, 4, 0, 4, 3, 7,
                                                                8, 5, 4, 4, 7, 3, 2, 8, 2, 5, 5, 5, 3, 8, 1, 1, 4, 0, 2, 6,
                                                                2, 2, 8, 5, 4, 7, 8, 3, 1, 2, 9, 8, 5, 4, 8, 8, 3, 2, 0, 4,
                                                                8, 1, 4, 2, 7, 1, 1, 5, 7, 5, 3, 3, 3, 5, 4, 4, 7, 6, 4, 0
                                                                                                };
*/

        Csga<_CONTAINER, _CONTAINER_P> CUnit((DISTANCE *)distance);        //初始化
       
        //开始遗传算法
        if(!CUnit.fnCreateRandomGene())                                                                //产生随机的基因
        {
                exit(0);
        }
       
        //循环基因编译,杂交,淘汰过程
        CUnit.fnEvalAll();
        for ( int i = 0; i < _TIMES; ++i )
        {
                //CUnit.fnDispProbability();
                CUnit.fnGeneAberrance();                                                                //基因变异
                //CUnit.fnDispProbability();
                CUnit.fnGeneMix();                                                                                //基因杂交
               
                CUnit.fnEvalAll();                                                                               

               
                //每隔_DISP_INTERVAL显示一次结果
                if ( (i+1)%_DISP_INTERVAL == 0 || i == 0)
                {
                        cout << "第" << i+1 << "代" << std::endl;
                        CUnit.fnDispProbability();
                        CUnit.fnDispHistoryMin();
                }
       
        }

        CUnit.fnDispHistoryMin();
       

       


}
___________________________________________________________________________

tsp.h

___________________________________________________________________________

#include "def.h"
using namespace std;


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

        bool fnCreateRandomGene();                                                        //产生随机基因
        bool fnGeneAberrance();                                                                //基因变异
        bool fnGeneMix();                                                                        //基因交叉产生新的个体测试并淘汰适应度低的个体
       
        bool fnEvalAll();                                                                        //测试所有基因的适应度
        int  fnEvalOne(T &Gene);                                                        //测试某一个基因的适应度

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

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];
       
       
};


//构造函数
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(_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