dalao看看 蚁群算法求解TSP问题

其奈公何

H.:
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<time.h>

#define M 30  //蚂蚁的数量
#define N 20  //城市的数量
#define R 100 //迭代次数
#define IN 1  //初始化的信息素的量
#define MAX 0x7fffffff //定义最大值

struct coordinate {
    char name[15];  //城市名
    int x;        //城市相对横坐标
    int y;        //城市相对纵坐标
};
struct coordinate city[20] = { {'a',88,16},{'b',42,76},{'c',5.76},{'d',69,13},{'e',73,56},{'f',100,100},{'g',22,92},{'h',48,74},{'i',73,46},{'j',39,1},{'k',51,75},{'l',92,2},{'m',101,44},{'n',55,26},{'o',71,27},{'p',42,81},{'q',51,91},{'r',89,54},{'s',33,18},{'t',40,78} };


double graph[N][N];  //储存城市之间的距离的邻接矩阵,自己到自己记作MAX
double phe[N][N];  //每条路径上的信息素的量
double add[N][N];  //代表相应路径上的信息素的增量
double yita[N][N]; //启发函数,yita[i][j]=1/graph[i][j]
int vis[M][N];  //标记已经走过的城市
int map[M][N];  //map[K][N]记录第K只蚂蚁走的路线
double solution[M]; //记录某次循环中每只蚂蚁走的路线的距离
int bestway[N]; //记录最近的那条路线
double bestsolution = MAX;
int NcMax; //代表迭代次数,理论上迭代次数越多所求的解更接近最优解,最具有说服力
double alpha, betra, rou, Q;

void Initialize(); //信息初始化
void GreateGraph(); //根据坐标信息建图
double Distance(int* p); //计算蚂蚁所走的路线的总长度
void Result(); //将结果保存到out.txt中

void Initialize()//信息初始化
{
    alpha = 4; betra = 5; rou = 0.5; Q = 100;
    NcMax = R;
    return;
}

void GreateGraph()//根据坐标信息建图
{
    int i, j;
    double d;
    for (i = 0; i < N - 1; ++i)
    {
        graph[i][i] = MAX;   //自己到自己标记为无穷大
        for (j = i + 1; j < N; ++j)
        {
            d = (double)((city[i].x - city[j].x) * (city[i].x - city[j].x) + (city[i].y - city[j].y) * (city[i].y - city[j].y));
            graph[j][i] = graph[i][j] = sqrt(d);
        }
    }
    graph[N - 1][N - 1] = MAX;
    return;
}

double Distance(int* p)//计算蚂蚁所走总长度
{
    double d = 0;
    int i;
    for (i = 0; i < N - 1; ++i)
    {
        d += graph[*(p + i)][*(p + i + 1)];
    }
    d += graph[*(p + i)][*(p)];
    return d;
}void Result()//将结果保存到out.txt中
{
    FILE* fl;
    int i;
    fl = fopen("ou

H.:
fl = fopen("out.txt", "a");  //将结果保存在out.txt这个文件里面
    fprintf(fl, "%s\n", "本次算法中的各参数如下:");
    fprintf(fl, "alpha=%.3lf, betra=%.3lf, rou=%.3lf, Q=%.3lf\n", alpha, betra, rou, Q);
    fprintf(fl, "%s %d\n", "本次算法迭代次数为:", NcMax);
    fprintf(fl, "%s %.4lf\n", "本算法得出的最短路径长度为:", bestsolution);
    fprintf(fl, "%s\n", "本算法求得的最短路径为:");
    for (i = 0; i < N; ++i)
        fprintf(fl, "%s →  ", city[bestway[i]].name);
    fprintf(fl, "%s", city[bestway[0]].name);
    fprintf(fl, "\n\n\n");
    fclose(fl);
    return;
}

int main()
{
    int NC = 0;
    int i, j, k;
    int s;
    double drand, pro, psum;
    Initialize();//信息初始化
    GreateGraph();//根据坐标信息建图
    for (i = 0; i < N; ++i)
    {
        for (j = 0; j < N; ++j)
        {
            phe[i][j] = IN; //信息素初始化
            if (i != j)
                yita[i][j] = 100.0 / graph[i][j];  //期望值,与距离成反比
        }
    }
    memset(map, -1, sizeof(map));  //把蚂蚁走的路线置空
    memset(vis, 0, sizeof(vis));  //0表示未访问,1表示已访问
    srand(time(NULL));
    while (NC++ <= NcMax)
    {
        for (k = 0; k < M; ++k)
        {
            map[k][0] = (k + NC) % N; //给每只蚂蚁分配一个起点,并且保证起点在N个城市里
            vis[k][map[k][0]] = 1; //将起点标记为已经访问
        }
        s = 1;
        while (s < N)
        {
            for (k = 0; k < M; ++k)
            {
                psum = 0;

                for (j = 0; j < N; ++j)
                {
                    if (vis[k][j] == 0)
                    {
                        psum += pow(phe[map[k][s - 1]][j], alpha) * pow(yita[map[k][s - 1]][j], betra);
                    }
                }
                drand = (double)(rand());
                drand /= 5000.0;  //生成一个小于1的随机数
                pro = 0;
                for (j = 0; j < N; ++j)
                {
                    if (vis[k][j] == 0)
                        pro += pow(phe[map[k][s - 1]][j], alpha) * pow(yita[map[k][s - 1]][j], betra) / psum;
                    if (pro > drand)
                        break;

H.:
}
                vis[k][j] = 1;  //将走过的城市标记起来
                map[k][s] = j;  //记录城市的顺序
            }
            s++;
        }
        memset(add, 0, sizeof(add));
        for (k = 0; k < M; ++k)  //计算本次中的最短路径//
        {
            solution[k] = Distance(map[k]);  //蚂蚁k所走的路线的总长度
            if (solution[k] < bestsolution)
            {
                bestsolution = solution[k];
                for (i = 0; i < N; ++i)
                    bestway[i] = map[k][i];
            }
        }
        for (k = 0; k < M; ++k)
        {
            for (j = 0; j < N - 1; ++j)
            {
                add[map[k][j]][map[k][j + 1]] += Q / solution[k];
            }
            add[N - 1][0] += Q / solution[k];
        }
        for (i = 0; i < N; ++i)
        {
            for (j = 0; j < N; ++j)
            {
                phe[i][j] = phe[i][j] * rou + add[i][j];
                if (phe[i][j] < 0.0001)  //设立一个下界
                    phe[i][j] = 0.0001;
                else if (phe[i][j] > 20)  //设立一个上界,防止启发因子的作用被淹没
                    phe[i][j] = 20;
            }
        }
        memset(vis, 0, sizeof(vis));
        memset(map, -1, sizeof(map));
    }
    Result();
    printf("Result is saved in out.txt\n");
    return 0;
}

其奈公何

呜呜呜不知道为什么最短路径过程和长度大小一直错误

isdkz

两个问题：

1、你在城市数组初始化中城市名用的是字符，所以城市结构体定义中，城市名应该使用char类型而不是char[]。

将结构体定义更改为：

1. struct coordinate {
   
2.     char name;  //城市名
   
3.     int x;      //城市相对横坐标
   
4.     int y;      //城市相对纵坐标
   
5. };

复制代码

2、在输出结果时，需要将城市名作为字符输出。将Result函数中的fprintf语句更改为：

1. for (i = 0; i < N; ++i)
   
2.     fprintf(fl, "%c →  ", city[bestway[i]].name);
   
3. fprintf(fl, "%c", city[bestway[0]].name);

复制代码

其奈公何

isdkz 发表于 2023-4-1 02:48
两个问题：

1、你在城市数组初始化中城市名用的是字符，所以城市结构体定义中，城市名应该使用char类型 ...

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<time.h>
#include<string.h>

#define M 30  //蚂蚁的数量
#define N 20  //城市的数量
#define R 100 //迭代次数
#define IN 1  //初始化的信息素的量
#define MAX 0x7fffffff //定义最大值

struct coordinate {
    char name;  //城市名
    int x;      //城市相对横坐标
    int y;      //城市相对纵坐标
};
struct coordinate city[20] = { {'a',88,16},{'b',42,76},{'c',5.76},{'d',69,13},{'e',73,56},{'f',100,100},{'g',22,92},{'h',48,74},{'i',73,46},{'j',39,1},{'k',51,75},{'l',92,2},{'m',101,44},{'n',55,26},{'o',71,27},{'p',42,81},{'q',51,91},{'r',89,54},{'s',33,18},{'t',40,78} };


double graph[N][N];  //储存城市之间的距离的邻接矩阵,自己到自己记作MAX
double phe[N][N];  //每条路径上的信息素的量
double add[N][N];  //代表相应路径上的信息素的增量
double yita[N][N]; //启发函数,yita[i][j]=1/graph[i][j]
int vis[M][N];  //标记已经走过的城市
int map[M][N];  //map[K][N]记录第K只蚂蚁走的路线
double solution[M]; //记录某次循环中每只蚂蚁走的路线的距离
int bestway[N]; //记录最近的那条路线
double bestsolution = MAX;
int NcMax; //代表迭代次数,理论上迭代次数越多所求的解更接近最优解,最具有说服力
double alpha, betra, rou, Q;

void Initialize(); //信息初始化
void GreateGraph(); //根据坐标信息建图
double Distance(int* p); //计算蚂蚁所走的路线的总长度
void Result(); //将结果保存到out.txt中

void Initialize()//信息初始化
{
    alpha = 4; betra = 5; rou = 0.5; Q = 100;
    NcMax = R;
    return;
}

void GreateGraph()//根据坐标信息建图
{
    int i, j;
    double d;
    for (i = 0; i < N - 1; ++i)
    {
        graph[i][i] = MAX;   //自己到自己标记为无穷大
        for (j = i + 1; j < N; ++j)
        {
            d = (double)((city[i].x - city[j].x) * (city[i].x - city[j].x) + (city[i].y - city[j].y) * (city[i].y - city[j].y));
            graph[j][i] = graph[i][j] = sqrt(d);
        }
    }
    graph[N - 1][N - 1] = MAX;
    return;
}

double Distance(int* p)//计算蚂蚁所走总长度
{
    double d = 0;
    int i;
    for (i = 0; i < N - 1; ++i)
    {
        d += graph[*(p + i)][*(p + i + 1)];
    }
    d += graph[*(p + i)][*(p)];
    return d;
}
void Result()//将结果保存到out.txt中
{
    FILE* fl;
    int i;
        fl = fopen("out.txt", "a");  //将结果保存在out.txt这个文件里面
    fprintf(fl, "%s\n", "本次算法中的各参数如下:");
    fprintf(fl, "alpha=%.3lf, betra=%.3lf, rou=%.3lf, Q=%.3lf\n", alpha, betra, rou, Q);
    fprintf(fl, "%s %d\n", "本次算法迭代次数为:", NcMax);
    fprintf(fl, "%s %.4lf\n", "本算法得出的最短路径长度为:", bestsolution);
    fprintf(fl, "%s\n", "本算法求得的最短路径为:");  
   for (i = 0; i < N; i++)
    fprintf(fl, "%c →  ", city[bestway[i]].name);
fprintf(fl, "%c", city[bestway[0]].name);
    fprintf(fl, "\n\n\n");                  
    fclose(fl);
    return;
}

int main()
{
    int NC = 0;
    int i, j, k;
    int s;
    double drand, pro, psum;
    Initialize();//信息初始化
    GreateGraph();//根据坐标信息建图
    for (i = 0; i < N; ++i)
    {
        for (j = 0; j < N; ++j)
        {
            phe[i][j] = IN; //信息素初始化
            if (i != j)
                yita[i][j] = 100.0 / graph[i][j];  //期望值,与距离成反比
        }
    }
    memset(map, -1, sizeof(map));  //把蚂蚁走的路线置空
    memset(vis, 0, sizeof(vis));  //0表示未访问,1表示已访问
    srand(time(NULL));
    while (NC++ <= NcMax)
    {
        for (k = 0; k < M; ++k)
        {
            map[k][0] = (k + NC) % N; //给每只蚂蚁分配一个起点,并且保证起点在N个城市里
            vis[k][map[k][0]] = 1; //将起点标记为已经访问
        }
        s = 1;
        while (s < N)
        {
            for (k = 0; k < M; ++k)
            {
                psum = 0;

                for (j = 0; j < N; ++j)
                {
                    if (vis[k][j] == 0)
                    {
                        psum += pow(phe[map[k][s - 1]][j], alpha) * pow(yita[map[k][s - 1]][j], betra);
                    }
                }
                drand = (double)(rand());
                drand /= 5000.0;  //生成一个小于1的随机数
                pro = 0;
                for (j = 0; j < N; ++j)
                {
                    if (vis[k][j] == 0)
                        pro += pow(phe[map[k][s - 1]][j], alpha) * pow(yita[map[k][s - 1]][j], betra) / psum;
                    if (pro > drand)
                        break;


}
                vis[k][j] = 1;  //将走过的城市标记起来
                map[k][s] = j;  //记录城市的顺序
            }
            s++;
        }
        memset(add, 0, sizeof(add));
        for (k = 0; k < M; ++k)  //计算本次中的最短路径//
        {
            solution[k] = Distance(map[k]);  //蚂蚁k所走的路线的总长度
            if (solution[k] < bestsolution)
            {
                bestsolution = solution[k];
                for (i = 0; i < N; ++i)
                    bestway[i] = map[k][i];
            }
        }
        for (k = 0; k < M; ++k)
        {
            for (j = 0; j < N - 1; ++j)
            {
                add[map[k][j]][map[k][j + 1]] += Q / solution[k];
            }
            add[N - 1][0] += Q / solution[k];
        }
        for (i = 0; i < N; ++i)
        {
            for (j = 0; j < N; ++j)
            {
                phe[i][j] = phe[i][j] * rou + add[i][j];
                if (phe[i][j] < 0.0001)  //设立一个下界
                    phe[i][j] = 0.0001;
                else if (phe[i][j] > 20)  //设立一个上界,防止启发因子的作用被淹没
                    phe[i][j] = 20;
            }
        }
        memset(vis, 0, sizeof(vis));
        memset(map, -1, sizeof(map));
    }
    Result();
    printf("Result is saved in out.txt\n");
    return 0;
}
不知道为什么过程的路径还是打不出来

歌者文明清理员

这段程序实现了蚁群优化算法来解决旅行商问题。根据题目描述，程序的问题可能出现在计算路径长度的函数Distance和选择下一个城市的过程中。

在Distance函数中，需要确保每只蚂蚁都走完所有城市并回到起点。当前程序的实现方式是在s=N-1时，循环结束，但此时蚂蚁还没有回到起点，因此应该将计算距离的代码块放在while循环外面，并且最后需要加上回到起点的距离。以下是修改后的代码：

```c
double Distance(int* p) // 计算蚂蚁所走的路线的总长度
{
    double d = 0;
    int i;
    for (i = 0; i < N - 1; ++i)
    {
        d += graph[*(p + i)][*(p + i + 1)];
    }
    d += graph[*(p + i)][*(p)];
    return d;
}
```

在选择下一个城市的过程中，程序采用轮盘赌的方式，但可能存在一些细节问题导致选择不够合理。可以尝试使用其他选择策略，例如贪心选择、最大信息素选择等。这里给出一种基于信息素和启发式信息的选择方法：在未访问的城市中，按照信息素和启发式信息的加权得分进行排序，然后以一定概率选择得分较高的城市。以下是代码实现：

```c
double P[N];

// 计算每个未访问城市的得分
for (j = 0; j < N; ++j)
{
    if (vis[k][j] == 1) // 已访问过的城市不考虑
    {
        P[j] = 0;
    }
    else
    {
        P[j] = pow(phe[map[k][s - 1]][j], alpha) * pow(yita[map[k][s - 1]][j], betra);
    }
}

// 按得分从高到低排序
int index[N];
for (j = 0; j < N; ++j)
{
    index[j] = j;
}
for (i = 0; i < N - 1; ++i)
{
    for (j = i + 1; j < N; ++j)
    {
        if (P[index[i]] < P[index[j]])
        {
            int t = index[i];
            index[i] = index[j];
            index[j] = t;
        }
    }
}

// 选择下一个城市
if (drand <= randChooseProb)
{
    j = index[0];
}
else
{
    double proSum = 0;
    for (j = 0; j < N - 1; ++j)
    {
        proSum += P[index[j]];
    }
    double threshold = drand * proSum;
    pro = 0;
    for (j = 0; j < N - 1; ++j)
    {
        pro += P[index[j]];
        if (pro >= threshold)
        {
            break;
        }
    }
    j = index[j];
}
```

其中，alpha和beta分别为信息素和启发式信息的权重系数，randChooseProb是以一定概率随机选择下一个城市的概率。