遗传算法解决旅行商问题（附C++代码）

大连海事大学智能科学与技术专业课程设计福利

写法说明

该实验通过调整：生成地图的类型（1.随机边权抽象图。2.满足三角形不等式规则的实际二维平面地图），种群数量，迭代代数，变异概率等相关影响结果的因素，分别对随机生成的地图进行求解。并通过dfs暴力搜索对点数比较少的地图暴力求解最优解。经过比较发现，种群数量以及迭代次数都和求解所得路径的长度成负相关关系。

附代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 150
#define UNIT 2052
#define inf 0x3f3f3f3f
const double Pacs=0.8;//杂交概率
const double Pvan=0.05;//变异概率
struct way
{
    int q[maxn];
    double val;
}ans;
vector<way>a;
bool operator < (way a,way b)
{
    return a.val>b.val;
}
int n,m,T_T;///n为点数，m为个体数
double dis[maxn][maxn];
int make_data(int n,int kind)//生成n个点的无向边权完全图
{
    memset(dis,0,sizeof(dis));
    if(kind==1)//生成平面n点，满足三角形不等式
    {
        double x[maxn],y[maxn];
        for(int i=1;i<=n;i++)
        {
            x[i]=rand();
            y[i]=rand();
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                double sx=x[i]-x[j],sy=y[i]-y[j];
                dis[j][i]=dis[i][j]=sqrt(sx*sx+sy*sy);
            }
        }
    }
    if(kind==2)//随机生成完全图
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                double sx=rand(),sy=rand();
                dis[j][i]=dis[i][j]=sqrt(sx*sx+sy*sy);
            }
        }
    }
    return n;
}
void outmap()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%.5lf ",dis[i][j]);
        }
        printf("\n");
    }
}
void outway(way x)
{
    printf("%lf : ",x.val);
    for(int i=0;i<n;i++)
    {
        printf("%d -> ",x.q[i]);
    }
    printf("%d\n",x.q[0]);
}
double Get_val(way x)
{
    double ret=0;
    for(int i=0;i<n-1;i++)
    {
        ret+=dis[x.q[i]][x.q[i+1]];
    }
    ret+=dis[x.q[n-1]][x.q[0]];
    return ret;
}
int creat_way(int x)//随机生成x个路径
{
    a.clear();
    way now;
    int m=0;
    x--;
    for(int i=0;i<n;i++) now.q[i]=i+1;
    now.val=Get_val(now);
    a.push_back(now);
    ans=now;
    outway(ans);
    while(x--)
    {
        for(int i=0;i<n;i++)
        {
            now.q[i]=a[m].q[i];
        }
        m++;
        random_shuffle(now.q,now.q+n);
        now.val=Get_val(now);
        a.push_back(now);
        //outway(now);
        if(ans<now)ans=now;
    }
    return a.size();
}
void variation(way &x)
{
    int p1=rand()%n,p2=rand()%n;
    int temp=x.q[p1]; x.q[p1]=x.q[p2]; x.q[p2]=temp;
    x.val=Get_val(x);
}
way across(way a,way b)
{
    bool vis[maxn]={0};
    way ret;
    int p1=rand()%n,p2=rand()%n;
    int l=min(p1,p2),r=max(p1,p2),cnt=0;
    for(int i=l;i<=r;i++)
    {
        ret.q[cnt++]=a.q[i];
        vis[a.q[i]]=1;
    }
    for(int i=0;i<n;i++)
    {
        if(!vis[b.q[i]])
        {
            ret.q[cnt++]= b.q[i];
        }
    }
    //outway(ret);
    ret.val=Get_val(ret);
    return ret;
}
vector<way> work_Ga()//一次迭代
{
    double s[UNIT]={0};
    vector<way>ret;
    int e=a.size(),i,j;
    for(i=0;i<e;i++)
    {
        s[i+1]=s[i]+a[i].val;
    }
    for(i=0,j=e;i+1<e;i +=2)//杂交生成子代
    {
        if((rand()%1000) > Pacs*1000)continue;
        way temp=across(a[i],a[i+1]);
        if((rand()%1000) < Pvan*1000 )variation(temp);
        s[j+1]=s[j]+temp.val;
        j++;
        a.push_back(temp);
        if(ans<temp)
        {
            ans=temp;
            //outway(ans);
        }
    }
    double limit=s[a.size()-1];
    int aim_num=m;//下一代个数
    while(aim_num--)
    {
        double pos=limit+1;
        while(pos>limit)
        {
            pos=0.0001*(rand()%10000)+((long long int)rand()*rand())%((int)floor(limit)+1);
        }
        int l=0,r=a.size()-1;
        //printf("pos=%lf %d limit=%lf %d\n",pos,r,limit,(int)floor(limit));
        //for(int i=0;i<r;i++)printf("%lf ",s[i]);printf("\n\n\n");
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(s[mid]>=pos)r=mid-1;
            else l=mid+1;
        }
        if(ans<a[r+1])
        {
            ans=a[r+1];
            //outway(ans);
        }
        ret.push_back(a[r+1]);
    }
    return ret;
}
bool test_vis[maxn];
way test_best;
void dfs(int x,way now)
{
    if(x==n)
    {
        now.val=Get_val(now);
        if(test_best<now)test_best=now;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!test_vis[i])
        {
            test_vis[i]=1;
            now.q[x]=i;
            dfs(x+1,now);
            test_vis[i]=0;
        }
    }
}
way BM_test()
{
    memset(test_vis,0,sizeof(test_vis));
    test_best.val=inf;
    way now;
    dfs(0,now);
    return test_best;
}
void OutInformation()
{
    printf("交叉概率：%.2lf\n变异概率： %.2lf\n完全图点数：%d\n种群个数： %d\n迭代次数： %d\n",
           Pacs,Pvan,n,m,T_T);
}
int main()
{
    srand(19980720);
    n=make_data(50,1);
    //outmap();
    printf("按顺序遍历结果：");
    m=creat_way(1000);
    //printf("暴力搜索最优结果：");outway( BM_test() );///暴力测试n个点的最优解
    T_T = 100;//迭代次数
    OutInformation();
    while(T_T--)
    {
        //printf("s");
        a=work_Ga();
        //if(T_T%10)outway(ans);
    }
    printf("遗传算法得到结果：");
    outway(ans);
    while(1)getchar();
    return 0;
}