本站文章信息来源于网络以及网友投稿，本站只负责对文章进行整理、排版、编辑，是出于传递更多信息之目的，并不意味着赞同其观点或证实其内容的真实性。如果您有什么意见或建议，请联系QQ28-！
人脸识别很强大？一副眼镜就能让它认错人！
无人机安防系统 陆空全方位值守你的家
猎户座飞船载人舱第五次回收测试成功进行
黑莓联手福特发展无人驾驶 扩大QNX安全操作系统
据国外媒体报道，在过去两年内，聊天机器人（chatbot）、人工智能以及机器学习的研发和采用取得了巨大进展。许多初创公司正利用人工智能和...
霍金 视觉中国 图 英国著名物理学家霍金（Stephen Hawking）再次就人工智能（AI）发声，他认为：对于人类来说，强大AI的出现可能是最美妙的...
文|郑娟娟 今年，人工智能(AI) 60岁了。在AI60岁的时候，笔者想要介绍一下AI100，一个刚刚2岁的研究项目，但它的预设寿命是100年，甚至更长...
AlphaGo与李世石的人机大战，为大众迅速普及了人工智能的概念。 但对谷歌而言，除了下围棋，现在的人工智能进展到哪一步了？未来，人工智能...蚁群算法(ant colony algorithm)首先由意大利科学家M.Dorigo等人提出,称为蚁群系统(antsystem,AS)。在求解二次分配、图着色问题、车辆调度、集成电路设计以及通信网络负载问题的处理中都取得了较好的结果。旅行商问题(TSP,Traveling Salesman Problem)被认为是一个基本问题,是在1859年由威廉·汉密尔顿爵士首次提出的。所谓TSP问题是指:有N个城市,要求旅行商到达每个城市各一次,且仅一次,并回到起点,且要求旅行路线最短。这是一个典型的优化问题,对一个具有中等顶点规模的图来说,精确求解也是很复杂的,计算量随着城市个数的增加而呈指数级增长,即属于所谓的NP问题。TSP在工程领域有着广泛的应用,并常作为比较算法性能的标志。如网络通讯、货物运输、电气布线、管道铺设、加工调度、专家系统、柔性制造系统等方面,都是TSP广泛应用的领域。求解算法包括贪婪法(GM)、极小代数法(MA)、模拟退火法(SA)和遗传算法...
相关文章推荐
广义旅行商问题(Generalized Traveling Salesman Problem,简称GTSP)是比旅行商问题(Traveling Salesman Problem,简称TSP)更为复杂的一类组合优化问题,TSP可视为GTSP的特例...
《电脑知识与技术(学术交流)》2007年0...
旅行售货商问题(TSP)是组合优化领域的经典问题之一,而考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展。多旅行商问题的特点使其符合许多实际问题,并且通过对...
《系统仿真学报》2009年20期
旅行商问题是数学上的组合优化问题,是一个经典的NP完全问题。该问题在工程上有很强的实用背景;对该问题的研究一直受到众多学者的重视,对其的求解亦提出了各种不同算法;同时...
《中国科教创新导刊》2008年08期
提出一个新的旅行商问题,称之为现实旅行商问题(RLTSP).它更接近于现实生活中的旅行商问题,并且介于传统的旅行商问题(TSP)与图形旅行商问题(GTSP)之间.还给出现实旅行商问题...
《小型微型计算机系统》2005年04期
采用统计方法,以中国旅行商问题为例给出了一个求解旅行商问题的有效算法。首先对每个点到其他各点的距离进行求和,然后对每点的距离之和排序,取距离之和最长的3个点连成一回...
《解放军理工大学学报(自然科学版)》2...
旅行商问题是一个经典的NP完全问题,由于其在许多领域内具有实际的应用价值,一直有众多学者对其进行研究。本文从介绍TSP模型入手,根据旅行商问题的分类,概要介绍了近五年来...
《滁州学院学报》2006年03期
黑白旅行商问题是经典旅行商问题的推广,在基于SONET技术的光纤网络设计、航线调度等领域具有广泛的应用.已有研究工作集中在无向黑白旅行商问题上.文章研究该问题的更一般形...
《计算机学报》2007年03期
在0-1整数规划的基础上建立了数学模型,利用MATLAB 6.5优化工具箱中的linprog函数进行求解,再经过分支定界算法计算,求出了只含有0和1的解.实验结果表明,该算法可以求解小规...
《中北大学学报(自然科学版)》2007年0...
针对热轧批计划问题进行了MTSP(多旅行商问题)建模,并对该问题设计了混合遗传算法,经某大型钢厂实例数据进行了仿真测试。计算结果表明,该算法给出了较优的轧制批计划方案,解...
《计算机应用研究》2007年07期
旅行商问题是一个NP问题。本文在此问题已有的解法的基础上,给出了利用Excel中自带的&规划求解&工具求解旅行商问题的方法,用实例说明了方法的操作过程及有效性。
《重庆职业技术学院学报》2008年01期posts - 17,&
comments - 2,&
trackbacks - 0
&&& 前几天写了个模拟退火算法的程序，然后又陆陆续续看了很多群智能算法，发现很多旅行商问题都采用蚁群算法来求解，于是开始写蚁群算法的模板。网上关于蚁群算法的理论很多就不再这里赘述了，下面直接上代码和进行简单的比较。
&&& c代码：
1 #ifndef _CITY_H
2 #define _CITY_H
3 struct CITY
8 #endif // !_CITY_H
1 #ifndef _OPTION_H
2 #define _OPTION_H
3 const int MAXN = 210;
4 int m = 50; /* 蚂蚁数量 */
5 double Q = 10;
/* 常系数 */
6 double alpha = 1;
/* 信息素重要程度因子 */
7 double beta = 5;
/* 启发函数重要程度因子 */
8 double rho = 0.2;
/* 信息素挥发因子 */
9 int iter = 1;
/* 迭代次数初值 */
10 int iter_max = 200;
/* 最大迭代次数 */
11 #endif // !_OPTION_H
1 #include &cstdio&
2 #include &cmath&
3 #include &ctime&
4 #include &set&
5 #include &vector&
6 #include &windows.h&
7 #include "CITY.h"
8 #include "OPTION.h"
9 using namespace
11 const double eps = 1e-4;
12 const double inf = (1 && 30);
13 const double rand_max = 32767;
citys[MAXN];
/* 保存城市坐标和编号信息 */
city_count = 0;
/* 保存城市数量 */
D[MAXN][MAXN];
/* 城市之间的距离矩阵 */
Heu_F[MAXN][MAXN];
/* 启发函数，Heu_F = 1./D (D为保存城市间距离的矩阵) */
Tau[MAXN][MAXN];
/* 信息素矩阵 */
Table[MAXN][MAXN];
/* 路径记录表 */
Route_best[MAXN][MAXN];/* 各代最佳路径 */
Length_best[MAXN];
/* 各代最佳路径的长度 */
*file = NULL;
/* 数据文件 */
/* 记录开始结束时间 */
25 void put_help();
26 void input();
27 void cal_dist();
28 void travel();
29 int gen_int();
/* 随机生成城市编号 */
30 double gen_rand();
/* 生成0~1之间的随机数 */
31 void show_result();
33 int main(int argc, char **argv)
srand(static_cast&int&(time(NULL)));
if (argc == 1) {
put_help();
/* get the parameters */
file = argv[1];
if (argc & 2)
for (int i = 2; i & i += 2) {
if (strcmp(argv[i], "-m") == 0) {
m = atoi(argv[i + 1]);
else if (strcmp(argv[i], "-Q") == 0) {
Q = atof(argv[i + 1]);
else if (strcmp(argv[i], "-a") == 0){
alpha = atof(argv[i + 1]);
else if (strcmp(argv[i], "-b") == 0) {
beta = atof(argv[i + 1]);
else if (strcmp(argv[i], "-r") == 0) {
rho = atof(argv[i + 1]);
else if (strcmp(argv[i], "-i") == 0) {
iter_max = atoi(argv[i + 1]);
file = argv[1];
freopen(file, "r", stdin);
cal_dist();
/*for (int i = 1; i &= city_ ++i) {
for (int j = 1; j &= city_ ++j) {
printf("%lf ", Heu_F[i][j]);
st = clock();
ed = clock();
show_result();
84 void put_help()
puts("用法: ACA 数据文件绝对路径 &参数设置& ");
puts("格式: ACA C:\\Users\\Administrator\\Desktop\\data.txt");
puts("输入数据格式: 每行为城市的坐标");
puts("参数选项 ");
蚂蚁数量, 默认 50");
-Q &double&
常系数, 默认 10");
-a &double&
信息素重要程度因子, 默认1");
-b &double&
启发函数重要程度因子, 默认5");
-r &double&
信息素挥发因子, 默认0.2");
最大迭代次数, 默认200");
101 void input()
while (~scanf("%lf%lf", &x, &y)) {
citys[city_count].id = city_
citys[city_count].x =
citys[city_count].y =
puts("Data input success!");
113 void cal_dist()
for (int i = 1; i &= city_ ++i) {
for (int j = 1; j &= city_ ++j) {
D[i][j] = sqrt((citys[i].x - citys[j].x)*(citys[i].x - citys[j].x)
+ (citys[i].y - citys[j].y)*(citys[i].y - citys[j].y));
if (i == j)
Heu_F[i][j] = 1 / D[i][j];
126 int gen_int()
return rand() % city_count + 1;
131 void travel()
for (int i = 1; i &= city_ ++i)
for (int j = 1; j &= city_ ++j)
Tau[i][j] = 1;
while (iter &= iter_max) {
/* 随机产生各个蚂蚁的起点城市 */
for (int i = 1; i &= ++i)
Table[i][1] = gen_int();
/* 逐个蚂蚁路径选择 */
for (int i = 1; i &= ++i) {
set&int& /* 待访问城市集合 */
vector&int& v_
/* 禁忌表 */
for (int k = 1; k &= city_ ++k) {
if (k == Table[i][1])
v_tabu.push_back(k);
allow.insert(k);
for (int j = 2; j &= city_ ++j) {
double P[MAXN];
allow_count = allow.size();
auto k_it = allow.begin();
auto tabu_it = v_tabu.end();
/* 计算城市间转移概率 */
for (int k = 1; k &= allow_ ++k) {
P[k] = pow(Tau[*tabu_it][*k_it],alpha)
*pow(Heu_F[*tabu_it][*k_it],beta);
//printf("%lf %lf %d %d\n", Tau[*tabu_it][*k_it], Heu_F[*tabu_it][*k_it], *tabu_it, *k_it);
P[k] += P[k - 1];
//printf("%lf\n", P[k]);
/* 轮盘赌法选择下一个访问城市 */
for (int k = 1; k &= allow_ ++k) {
P[k] /= P[allow_count];
double t_rand = gen_rand();
for (k = 1; k &= allow_ ++k) {
if (P[k] &= t_rand)
auto allow_it = allow.begin();
int cnt = 0;
while (cnt & k-1) {
Table[i][j] = *allow_
v_tabu.push_back(Table[i][j]);
allow.erase(Table[i][j]);
/* 计算每个蚂蚁的路径距离 */
double Length[MAXN];
memset(Length, 0, sizeof Length);
for (int i = 1; i &= ++i) {
int Route[MAXN];
for (int j = 1; j &= city_ ++j) {
Route[j] = Table[i][j];
for (int j = 1; j &= city_count - 1; ++j) {
Length[i] = Length[i] + D[Route[j]][Route[j + 1]];
Length[i] = Length[i] + D[Route[city_count]][Route[1]];
/*for (int i = 1; i &= ++i) {
printf("%lf\n", Length[i]);
/* 计算最短路径距离和求最短路径 */
if (iter == 1) {
double min_Length = static_cast&double&(inf);
for (int i = 1; i &= ++i) {
if (Length[i] & min_Length) {
min_Length = Length[i];
for (int j = 1; j &= city_ ++j) {
Route_best[iter][j] = Table[i][j];
Length_best[iter] = min_L
double min_Length = static_cast&double&(inf);
for (int i = 1; i &= ++i) {
if (Length[i] & min_Length) {
min_Length = Length[i];
for (int j = 1; j &= city_ ++j) {
Route_best[iter][j] = Table[i][j];
Length_best[iter] = min_L
if (Length_best[iter-1] & min_Length) {
Length_best[iter] = Length_best[iter - 1];
for (int j = 1; j &= city_ ++j) {
Route_best[iter][j] = Route_best[iter-1][j];
/* 更新信息素 */
double Delta_Tau[MAXN][MAXN];
memset(Delta_Tau, 0, sizeof Delta_Tau);
for (int i = 1; i &= ++i) {
for (int j = 1; j &= city_count - 1; ++j) {
Delta_Tau[Table[i][j]][Table[i][j + 1]]
= Delta_Tau[Table[i][j]][Table[i][j + 1]] + Q / Length[i];
Delta_Tau[Table[i][city_count]][Table[i][1]]
= Delta_Tau[Table[i][city_count]][Table[i][1]] + Q / Length[i];
for (int i = 1; i &= city_ ++i)
for (int j = 1; j &= city_ ++j)
Tau[i][j] = (1 - rho)*Tau[i][j] + Delta_Tau[i][j];
/*for (int i = 1; i &= city_ ++i) {
for (int j = 1; j &= city_ ++j)
printf("%lf ", Tau[i][j]);
/* 迭代次数加1，清空路径记录表 */
memset(Table, 0, sizeof Table);
259 double gen_rand()
return rand() / rand_
264 void show_result()
printf("求得的最短路径长度为: %lf\n", Length_best[iter_max]);
printf("最短路径为: ");
for (int i = 1; i &= city_ ++i) {
printf("%d ", Route_best[iter_max][i]);
printf("程序运行时间: %lf s\n", static_cast&double&(ed - st) / CLOCKS_PER_SEC);
&&& matlab代码：
1 %% 清空环境变量
2 clear all
4 %% 导入数据
5 citys = [1304
37 %% 计算城市间相互距离
38 n = size(citys,1);
39 D = zeros(n,n);
40 for i = 1:n
for j = 1:n
D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));
D(i,j) = 1e-4;
49 %% 初始化参数
50 m = 50;
% 蚂蚁数量
51 alpha = 1;
% 信息素重要程度因子
52 beta = 5;
% 启发函数重要程度因子
53 rho = 0.2;
% 信息素挥发因子
55 Eta = 1./D;
% 启发函数
56 Tau = ones(n,n);
% 信息素矩阵
57 Table = zeros(m,n);
% 路径记录表
58 iter = 1;
% 迭代次数初值
59 iter_max = 200;
% 最大迭代次数
60 Route_best = zeros(iter_max,n);
% 各代最佳路径
61 Length_best = zeros(iter_max,1);
% 各代最佳路径的长度
62 Length_ave = zeros(iter_max,1);
% 各代路径的平均长度
63 %% 迭代寻找最佳路径
65 while iter &= iter_max
% 随机产生各个蚂蚁的起点城市
start = zeros(m,1);
for i = 1:m
temp = randperm(n);
start(i) = temp(1);
Table(:,1) =
% 构建解空间
citys_index = 1:n;
% 逐个蚂蚁路径选择
for i = 1:m
% 逐个城市路径选择
for j = 2:n
tabu = Table(i,1:(j - 1));
% 已访问的城市集合(禁忌表)
allow_index = ~ismember(citys_index,tabu);
allow = citys_index(allow_index);
% 待访问的城市集合
% 计算城市间转移概率
for k = 1:length(allow)
P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^
P = P/sum(P);
% 轮盘赌法选择下一个访问城市
Pc = cumsum(P);
target_index = find(Pc &= rand);
target = allow(target_index(1));
Table(i,j) =
% 计算各个蚂蚁的路径距离
Length = zeros(m,1);
for i = 1:m
Route = Table(i,:);
for j = 1:(n - 1)
Length(i) = Length(i) + D(Route(j),Route(j + 1));
Length(i) = Length(i) + D(Route(n),Route(1));
% 计算最短路径距离及平均距离
if iter == 1
[min_Length,min_index] = min(Length);
Length_best(iter) = min_L
Length_ave(iter) = mean(Length);
Route_best(iter,:) = Table(min_index,:);
[min_Length,min_index] = min(Length);
Length_best(iter) = min(Length_best(iter - 1),min_Length);
Length_ave(iter) = mean(Length);
if Length_best(iter) == min_Length
Route_best(iter,:) = Table(min_index,:);
Route_best(iter,:) = Route_best((iter-1),:);
% 更新信息素
Delta_Tau = zeros(n,n);
% 逐个蚂蚁计算
for i = 1:m
% 逐个城市计算
for j = 1:(n - 1)
Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);
Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);
Tau = (1-rho) * Tau + Delta_T
% 迭代次数加1，清空路径记录表
iter = iter + 1;
Table = zeros(m,n);
136 %% 结果显示
137 [Shortest_Length,index] = min(Length_best);
138 Shortest_Route = Route_best(index,:);
139 disp(['最短距离:' num2str(Shortest_Length)]);
140 disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);
141 %% 绘图
142 figure(1)
143 plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
145 grid on
146 for i = 1:size(citys,1)
text(citys(i,1),citys(i,2),['
' num2str(i)]);
149 text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'
150 text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'
151 xlabel('城市位置横坐标')
152 ylabel('城市位置纵坐标')
153 title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
154 figure(2)
155 plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')
156 legend('最短距离','平均距离')
157 xlabel('迭代次数')
158 ylabel('距离')
159 title('各代最短距离与平均距离对比')
&&& 【运行结果比较】
&&& 测试数据选用和模拟退火的测试相同：
1304&&&&&&& 23123639&&&&&&& 13154177&&&&&&& 22443712&&&&&&& 13993488&&&&&&& 15353326&&&&&&& 15563238&&&&&&& 12294196&&&&&&& 10044312&&&&&&&& 7904386&&&&&&&& 5703007&&&&&&& 19702562&&&&&&& 17562788&&&&&&& 14912381&&&&&&& 16761332&&&&&&&& 6953715&&&&&&& 16783918&&&&&&& 21794061&&&&&&& 23703780&&&&&&& 22123676&&&&&&& 25784029&&&&&&& 28384263&&&&&&& 29313429&&&&&&& 19083507&&&&&&& 23673394&&&&&&& 26433439&&&&&&& 32012935&&&&&&& 32403140&&&&&&& 35502545&&&&&&& 23572778&&&&&&& 28262370&&&&&&& 2975
&&& c版ACA：
&&&&&&& 可选择设置的相关参数：
&&&&&&& 运行结果：
&&& matlab版ACA：
&&&&&&& 运行结果：
&&& 从时间效率上看，c运行时间比matlab的运行时间少了2/3，在运行之前就想到了，也没什么惊讶的，而且代码被我写搓了，继续优化可以更快。。。
&&& 只测试了这么一组数据，对于参数的选择也没什么心得，等今后接触多了有自己的想法了再来填坑。。
阅读(...) 评论()