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;//城市名
int x; //城市相对横坐标
int y; //城市相对纵坐标
};
struct coordinate city = { {'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;//储存城市之间的距离的邻接矩阵,自己到自己记作MAX
double phe;//每条路径上的信息素的量
double add;//代表相应路径上的信息素的增量
double yita; //启发函数,yita=1/graph
int vis;//标记已经走过的城市
int map;//map记录第K只蚂蚁走的路线
double solution; //记录某次循环中每只蚂蚁走的路线的距离
int bestway; //记录最近的那条路线
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 = MAX; //自己到自己标记为无穷大
for (j = i + 1; j < N; ++j)
{
d = (double)((city.x - city.x) * (city.x - city.x) + (city.y - city.y) * (city.y - city.y));
graph = graph = sqrt(d);
}
}
graph = 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].name);
fprintf(fl, "%s", city].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 = IN; //信息素初始化
if (i != j)
yita = 100.0 / graph;//期望值,与距离成反比
}
}
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 + NC) % N; //给每只蚂蚁分配一个起点,并且保证起点在N个城市里
vis] = 1; //将起点标记为已经访问
}
s = 1;
while (s < N)
{
for (k = 0; k < M; ++k)
{
psum = 0;
for (j = 0; j < N; ++j)
{
if (vis == 0)
{
psum += pow(phe], alpha) * pow(yita], betra);
}
}
drand = (double)(rand());
drand /= 5000.0;//生成一个小于1的随机数
pro = 0;
for (j = 0; j < N; ++j)
{
if (vis == 0)
pro += pow(phe], alpha) * pow(yita], betra) / psum;
if (pro > drand)
break;
H.:
}
vis = 1;//将走过的城市标记起来
map = j;//记录城市的顺序
}
s++;
}
memset(add, 0, sizeof(add));
for (k = 0; k < M; ++k)//计算本次中的最短路径//
{
solution = Distance(map);//蚂蚁k所走的路线的总长度
if (solution < bestsolution)
{
bestsolution = solution;
for (i = 0; i < N; ++i)
bestway = map;
}
}
for (k = 0; k < M; ++k)
{
for (j = 0; j < N - 1; ++j)
{
add]] += Q / solution;
}
add += Q / solution;
}
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
phe = phe * rou + add;
if (phe < 0.0001)//设立一个下界
phe = 0.0001;
else if (phe > 20)//设立一个上界,防止启发因子的作用被淹没
phe = 20;
}
}
memset(vis, 0, sizeof(vis));
memset(map, -1, sizeof(map));
}
Result();
printf("Result is saved in out.txt\n");
return 0;
}
呜呜呜不知道为什么最短路径过程和长度大小一直错误
两个问题：
1、你在城市数组初始化中城市名用的是字符，所以城市结构体定义中，城市名应该使用char类型而不是char[]。
将结构体定义更改为：
struct coordinate {
char name;//城市名
int x; //城市相对横坐标
int y; //城市相对纵坐标
};
2、在输出结果时，需要将城市名作为字符输出。将Result函数中的fprintf语句更改为：
for (i = 0; i < N; ++i)
fprintf(fl, "%c →", city].name);
fprintf(fl, "%c", city].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 = { {'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;//储存城市之间的距离的邻接矩阵,自己到自己记作MAX
double phe;//每条路径上的信息素的量
double add;//代表相应路径上的信息素的增量
double yita; //启发函数,yita=1/graph
int vis;//标记已经走过的城市
int map;//map记录第K只蚂蚁走的路线
double solution; //记录某次循环中每只蚂蚁走的路线的距离
int bestway; //记录最近的那条路线
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 = MAX; //自己到自己标记为无穷大
for (j = i + 1; j < N; ++j)
{
d = (double)((city.x - city.x) * (city.x - city.x) + (city.y - city.y) * (city.y - city.y));
graph = graph = sqrt(d);
}
}
graph = 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].name);
fprintf(fl, "%c", city].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 = IN; //信息素初始化
if (i != j)
yita = 100.0 / graph;//期望值,与距离成反比
}
}
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 + NC) % N; //给每只蚂蚁分配一个起点,并且保证起点在N个城市里
vis] = 1; //将起点标记为已经访问
}
s = 1;
while (s < N)
{
for (k = 0; k < M; ++k)
{
psum = 0;
for (j = 0; j < N; ++j)
{
if (vis == 0)
{
psum += pow(phe], alpha) * pow(yita], betra);
}
}
drand = (double)(rand());
drand /= 5000.0;//生成一个小于1的随机数
pro = 0;
for (j = 0; j < N; ++j)
{
if (vis == 0)
pro += pow(phe], alpha) * pow(yita], betra) / psum;
if (pro > drand)
break;
}
vis = 1;//将走过的城市标记起来
map = j;//记录城市的顺序
}
s++;
}
memset(add, 0, sizeof(add));
for (k = 0; k < M; ++k)//计算本次中的最短路径//
{
solution = Distance(map);//蚂蚁k所走的路线的总长度
if (solution < bestsolution)
{
bestsolution = solution;
for (i = 0; i < N; ++i)
bestway = map;
}
}
for (k = 0; k < M; ++k)
{
for (j = 0; j < N - 1; ++j)
{
add]] += Q / solution;
}
add += Q / solution;
}
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
{
phe = phe * rou + add;
if (phe < 0.0001)//设立一个下界
phe = 0.0001;
else if (phe > 20)//设立一个上界,防止启发因子的作用被淹没
phe = 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;
// 计算每个未访问城市的得分
for (j = 0; j < N; ++j)
{
if (vis == 1) // 已访问过的城市不考虑
{
P = 0;
}
else
{
P = pow(phe], alpha) * pow(yita], betra);
}
}
// 按得分从高到低排序
int index;
for (j = 0; j < N; ++j)
{
index = j;
}
for (i = 0; i < N - 1; ++i)
{
for (j = i + 1; j < N; ++j)
{
if (P] < P])
{
int t = index;
index = index;
index = t;
}
}
}
// 选择下一个城市
if (drand <= randChooseProb)
{
j = index;
}
else
{
double proSum = 0;
for (j = 0; j < N - 1; ++j)
{
proSum += P];
}
double threshold = drand * proSum;
pro = 0;
for (j = 0; j < N - 1; ++j)
{
pro += P];
if (pro >= threshold)
{
break;
}
}
j = index;
}
```
其中，alpha和beta分别为信息素和启发式信息的权重系数，randChooseProb是以一定概率随机选择下一个城市的概率。
页:
[1]