遗传算法解决TSP问题

基本原理在代码中有注释：

#include<iostream>
#include<string>
#include <cstdlib>
#include<ctime>
#include <cmath>
using  std::string;

struct Position
{
    string EID;
    double x;
    double y;
    double z;

};

double TSP(int n, struct Position* position,int T,int population_num,int top_num,int * sort)
{
    //T;//迭代次数；
    //population_num//种群个数
    //top_num 选取前边多少个
    int *population;//存放种群编码
    int *p;
    int getPerm(int *b, int n);
    population=(int*)malloc(sizeof(int)*population_num*n);//一维数组存放
    double *dis;
    dis=(double*)malloc(sizeof(double)*n*n);
    double *fitness;
    fitness=(double*)malloc(sizeof(double)*population_num);

    int *b;
    b=(int*)malloc(sizeof(int)*population_num);


    int *population1;
    population1=(int*)malloc(sizeof(int)*population_num*n);

    int* bb;
    bb=(int*)malloc(sizeof(int)*n);

    int* bbb;
    bbb=(int*)malloc(sizeof(int)*n);

    p=population;
    //产生50个初始种群
    srand(time(0));
    for(int i=0;i<population_num;i++)
    {
        getPerm(p,n);
        p=p+n;
    }
    //以上生成了50个初始种群，放在population

    //准备好距离矩阵

    int getDis(struct Position* position,double *dis,int n);
    getDis(position,dis,n);
    
    
    

for(int t=0;t<T;t++)
{
    //a计算适应度
    for(int i=0;i<population_num;i++)
    {
        fitness[i]=0;
        
        for(int j=i*n;j<n+i*n-1;j++)
        {
            int ii=population[j];
            int jj=population[j+1];

            fitness[i]+=dis[ii*n+jj];
        }
        int ii=population[i*n+n-1];
        int jj=population[i*n];
        fitness[i]+=dis[ii*n+jj];
    }

    
    //b对适应度进行排序
    int getIndex_double(double *a, int *b,int n);


    getIndex_double(fitness, b,population_num);



    //c选择比较好的个体，放入一个新的矩阵population1
    for(int i=0;i<population_num;i++)
    {
        memcpy(&population1[b[i]*n],&population[i*n],4*n);
    }





    //选取比较好的top_num个体，进行交叉操作，放在从top_num+1开始的top_num/2个
    for(int i=top_num;i<population_num;i=i+2)
    {
        memcpy(&population1[i*n],&population1[(i-top_num)*n],n);
        memcpy(&population1[(i+1)*n],&population1[(i+1-top_num)*n],n);

        //选择交叉位置
        int pos=rand()%n;
        int tmp=population1[i*n+pos];
        population1[i*n+pos]=population1[(i+1)*n+pos];
        population1[(i+1)*n+pos]=tmp;

        //重新生成排列
        int getIndex(int *a, int *b,int n);
        getIndex(&population1[i*n],bb,n);
        memcpy(&population1[i*n],bb,4*n);

        getIndex(&population1[(i+1)*n],bb,n);
        memcpy(&population1[(i+1)*n],bb,4*n);

    }


    //变异操作
    //随机选取其中的以为进行变异
    int pos_population=rand()%population_num;
    int pos=rand()%n;
    int value=rand()%n;
    population1[pos_population*n+pos]=value;
    int getIndex(int *a, int *b,int n);

    getIndex(&population1[pos_population*n],bbb,n);
    memcpy(&population1[pos_population*n],bbb,4*n);



    memcpy(population,population1,n*population_num*4);


}
    //保存在population1中，适应度在fitness中，排序在b
    int i;
    for(i=0;i<population_num;i++)
    {
        if(b[i]==0)
            break;
    }

    memcpy(sort,&population[i*n],n*4);
    return fitness[i];
     
}

int getDis(struct Position* position,double *dis,int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            dis[i*n+j]=sqrt((position[i].x-position[j].x)*(position[i].x-position[j].x)+
                (position[i].y-position[j].y)*(position[i].y-position[j].y)+
                (position[i].z-position[j].z)*(position[i].z-position[j].z));
            
        }
    }
    return 0;
}

int getPerm(int *b, int n)
{
    //得到一个随机排列
    int getIndex(int *a, int *b,int n); 
    int* a;
    a=(int*)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
        a[i]=rand()%n;
    getIndex(a, b,n);

    return 0;
}

//产生排列
int getIndex(int *a, int *b,int n)
{
    for(int i=0;i<n;i++)
    {
        b[i]=0;
    }
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(a[i]>=a[j])
                b[i]++;
            else
                b[j]++;
        }
    }
    return 0;
}

int getIndex_double(double *a, int *b,int n)
{
    for(int i=0;i<n;i++)
    {
        b[i]=0;
    }
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if((a[i]-a[j])>=0.0001)
                b[i]++;
            else
                b[j]++;
        }
    }
    return 0;
}

调用函数为：

#include"tsp.h";

int main()
{
    int n=6,i;
    struct Position* person;
    struct Position* p;
    int *sort;
    sort=(int*)malloc(sizeof(int)*n);
    person=(struct Position*)malloc(sizeof(Position)*n);
    p=person;

    p->x=0;p->y=0;p->z=0;p=p+1;
    p->x=2;p->y=0;p->z=0;p=p+1;
    p->x=3;p->y=1;p->z=0;p=p+1;
    p->x=2;p->y=2;p->z=0;p=p+1;
    p->x=0;p->y=2;p->z=0;p=p+1;
    p->x=0;p->y=1;p->z=0;p=p+1;

    double dis=TSP(n, person,10,20,10,sort);

    printf("%.1f
顺序为：",dis);

    for(int i=0;i<n;i++)
    {
        printf("%d ",sort[i]);
    }
    printf("
");

    system("pause"); 
    return 0;
}

原创文章，转载请注明出处，谢谢！