前几天写了个模拟退火算法的程序，然后又陆陆续续看了很多群智能算法，发现很多旅行商问题都采用蚁群算法来求解，于是开始写蚁群算法的模板。网上关于蚁群算法的理论很多就不再这里赘述了，下面直接上代码和进行简单的比较。
c代码：
#ifndef _CITY_H
#define _CITY_H
struct CITY
{
int id;
double x, y;
};
#endif // !_CITY_H
CITY.h
#ifndef _OPTION_H #define _OPTION_H ; ; /* 蚂蚁数量 */ ; /* 常系数 */ ; /* 信息素重要程度因子 */ ; /* 启发函数重要程度因子 */ double rho = 0.2; /* 信息素挥发因子 */ ; /* 迭代次数初值 */ ; /* 最大迭代次数 */ #endif // !_OPTION_H
OPTION.h
#include <cstdio>
#include <cmath>
#include <ctime>
#include <set>
#include <vector>
#include <windows.h>
#include "CITY.h"
#include "OPTION.h"
using namespace std;
;
<< );
;
CITY citys[MAXN]; /* 保存城市坐标和编号信息 */
; /* 保存城市数量 */
double D[MAXN][MAXN]; /* 城市之间的距离矩阵 */
double Heu_F[MAXN][MAXN]; /* 启发函数，Heu_F = 1./D (D为保存城市间距离的矩阵) */
double Tau[MAXN][MAXN]; /* 信息素矩阵 */
int Table[MAXN][MAXN]; /* 路径记录表 */
int Route_best[MAXN][MAXN];/* 各代最佳路径 */
double Length_best[MAXN]; /* 各代最佳路径的长度 */
char *file = NULL; /* 数据文件 */
time_t st, ed; /* 记录开始结束时间 */
void put_help();
void input();
void cal_dist();
void travel();
int gen_int(); /* 随机生成城市编号 */
double gen_rand(); /* 生成0~1之间的随机数 */
void show_result();
int main(int argc, char **argv)
{
srand(static_cast<int>(time(NULL)));
) {
put_help();
goto end;
}
/* get the parameters */
file = argv[];
)
{
; i < argc; i += ) {
) {
m = atoi(argv[i + ]);
}
) {
Q = atof(argv[i + ]);
}
){
alpha = atof(argv[i + ]);
}
) {
beta = atof(argv[i + ]);
}
) {
rho = atof(argv[i + ]);
}
) {
iter_max = atoi(argv[i + ]);
}
}
}
file = argv[];
freopen(file, "r", stdin);
input();
cal_dist();
/*for (int i = 1; i <= city_count; ++i) {
for (int j = 1; j <= city_count; ++j) {
printf("%lf ", Heu_F[i][j]);
}
puts("");
}*/
st = clock();
travel();
ed = clock();
show_result();
end:
;
}
void put_help()
{
puts("用法: ACA 数据文件绝对路径 <参数设置> ");
puts("格式: ACA C:\\Users\\Administrator\\Desktop\\data.txt");
puts("输入数据格式: 每行为城市的坐标");
puts(" 1 2");
puts(" 3 1");
puts(" 5 6");
puts("参数选项 ");
puts(" -m <int> 蚂蚁数量, 默认 50");
puts(" -Q <double> 常系数, 默认 10");
puts(" -a <double> 信息素重要程度因子, 默认1");
puts(" -b <double> 启发函数重要程度因子, 默认5");
puts(" -r <double> 信息素挥发因子, 默认0.2");
puts(" -i <int > 最大迭代次数, 默认200");
}
void input()
{
double x, y;
while (~scanf("%lf%lf", &x, &y)) {
++city_count;
citys[city_count].id = city_count;
citys[city_count].x = x;
citys[city_count].y = y;
}
puts("Data input success!");
}
void cal_dist()
{
; i <= city_count; ++i) {
; j <= city_count; ++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)
D[i][j] = eps;
Heu_F[i][j] = / D[i][j];
}
}
}
int gen_int()
{
;
}
void travel()
{
; i <= city_count; ++i)
; j <= city_count; ++j)
Tau[i][j] = ;
while (iter <= iter_max) {
/* 随机产生各个蚂蚁的起点城市 */
; i <= m; ++i)
Table[i][] = gen_int();
/* 逐个蚂蚁路径选择 */
; i <= m; ++i) {
set<int> allow; /* 待访问城市集合 */
vector<int> v_tabu; /* 禁忌表 */
; k <= city_count; ++k) {
])
v_tabu.push_back(k);
else
allow.insert(k);
}
; j <= city_count; ++j) {
double P[MAXN];
P[] = ;
int allow_count = allow.size();
auto k_it = allow.begin();
auto tabu_it = v_tabu.end();
--tabu_it;
/* 计算城市间转移概率 */
; k <= allow_count; ++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 - ];
//printf("%lf\n", P[k]);
++k_it;
}
/* 轮盘赌法选择下一个访问城市 */
; k <= allow_count; ++k) {
P[k] /= P[allow_count];
}
double t_rand = gen_rand();
int k;
; k <= allow_count; ++k) {
if (P[k] >= t_rand)
break;
}
auto allow_it = allow.begin();
;
) {
++cnt;
++allow_it;
}
Table[i][j] = *allow_it;
v_tabu.push_back(Table[i][j]);
allow.erase(Table[i][j]);
}
}
/* 计算每个蚂蚁的路径距离 */
double Length[MAXN];
memset(Length, , sizeof Length);
; i <= m; ++i) {
int Route[MAXN];
; j <= city_count; ++j) {
Route[j] = Table[i][j];
}
; j <= city_count - ; ++j) {
Length[i] = Length[i] + D[Route[j]][Route[j + ]];
}
Length[i] = Length[i] + D[Route[city_count]][Route[]];
}
/*for (int i = 1; i <= m; ++i) {
printf("%lf\n", Length[i]);
}*/
/* 计算最短路径距离和求最短路径 */
) {
double min_Length = static_cast<double>(inf);
; i <= m; ++i) {
if (Length[i] < min_Length) {
min_Length = Length[i];
; j <= city_count; ++j) {
Route_best[iter][j] = Table[i][j];
}
}
}
Length_best[iter] = min_Length;
}
else {
double min_Length = static_cast<double>(inf);
; i <= m; ++i) {
if (Length[i] < min_Length) {
min_Length = Length[i];
; j <= city_count; ++j) {
Route_best[iter][j] = Table[i][j];
}
}
}
Length_best[iter] = min_Length;
] < min_Length) {
Length_best[iter] = Length_best[iter - ];
; j <= city_count; ++j) {
Route_best[iter][j] = Route_best[iter-][j];
}
}
}
/* 更新信息素 */
double Delta_Tau[MAXN][MAXN];
memset(Delta_Tau, , sizeof Delta_Tau);
; i <= m; ++i) {
; j <= city_count - ; ++j) {
Delta_Tau[Table[i][j]][Table[i][j + ]]
= Delta_Tau[Table[i][j]][Table[i][j + ]] + Q / Length[i];
}
Delta_Tau[Table[i][city_count]][Table[i][]]
= Delta_Tau[Table[i][city_count]][Table[i][]] + Q / Length[i];
}
; i <= city_count; ++i)
; j <= city_count; ++j)
Tau[i][j] = ( - rho)*Tau[i][j] + Delta_Tau[i][j];
/*for (int i = 1; i <= city_count; ++i) {
for (int j = 1; j <= city_count; ++j)
printf("%lf ", Tau[i][j]);
puts("");
}*/
/* 迭代次数加1，清空路径记录表 */
++iter;
memset(Table, , sizeof Table);
}
}
double gen_rand()
{
return rand() / rand_max;
}
void show_result()
{
printf("求得的最短路径长度为: %lf\n", Length_best[iter_max]);
printf("最短路径为: ");
; i <= city_count; ++i) {
printf("%d ", Route_best[iter_max][i]);
}
puts("");
printf("程序运行时间: %lf s\n", static_cast<double>(ed - st) / CLOCKS_PER_SEC);
}
main.cpp
matlab代码：
%% 清空环境变量
clear all
clc
%% 导入数据
citys = [
];
%% 计算城市间相互距离
n = size(citys,);
D = zeros(n,n);
:n
:n
if i ~= j
D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^));
else
D(i,j) = 1e-;
end
end
end
%% 初始化参数
m = ; % 蚂蚁数量
alpha = ; % 信息素重要程度因子
beta = ; % 启发函数重要程度因子
rho = 0.2; % 信息素挥发因子
Q = ; % 常系数
Eta = ./D; % 启发函数
Tau = ones(n,n); % 信息素矩阵
Table = zeros(m,n); % 路径记录表
iter = ; % 迭代次数初值
iter_max = ; % 最大迭代次数
Route_best = zeros(iter_max,n); % 各代最佳路径
Length_best = zeros(iter_max,); % 各代最佳路径的长度
Length_ave = zeros(iter_max,); % 各代路径的平均长度
%% 迭代寻找最佳路径
tic
while iter <= iter_max
% 随机产生各个蚂蚁的起点城市
start = zeros(m,);
:m
temp = randperm(n);
start(i) = temp();
end
Table(:,) = start;
% 构建解空间
citys_index = :n;
% 逐个蚂蚁路径选择
:m
% 逐个城市路径选择
:n
tabu = Table(i,:(j - )); % 已访问的城市集合(禁忌表)
allow_index = ~ismember(citys_index,tabu);
allow = citys_index(allow_index); % 待访问的城市集合
P = allow;
% 计算城市间转移概率
:length(allow)
P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;
end
P = P/sum(P);
% 轮盘赌法选择下一个访问城市
Pc = cumsum(P);
target_index = find(Pc >= rand);
target = allow(target_index());
Table(i,j) = target;
end
end
% 计算各个蚂蚁的路径距离
Length = zeros(m,);
:m
Route = Table(i,:);
:(n - )
Length(i) = Length(i) + D(Route(j),Route(j + ));
end
Length(i) = Length(i) + D(Route(n),Route());
end
% 计算最短路径距离及平均距离
[min_Length,min_index] = min(Length);
Length_best(iter) = min_Length;
Length_ave(iter) = mean(Length);
Route_best(iter,:) = Table(min_index,:);
else
[min_Length,min_index] = min(Length);
Length_best(iter) = min(Length_best(iter - ),min_Length);
Length_ave(iter) = mean(Length);
if Length_best(iter) == min_Length
Route_best(iter,:) = Table(min_index,:);
else
Route_best(iter,:) = Route_best((iter-),:);
end
end
% 更新信息素
Delta_Tau = zeros(n,n);
% 逐个蚂蚁计算
:m
% 逐个城市计算
:(n - )
Delta_Tau(Table(i,j),Table(i,j+)) = Delta_Tau(Table(i,j),Table(i,j+)) + Q/Length(i);
end
Delta_Tau(Table(i,n),Table(i,)) = Delta_Tau(Table(i,n),Table(i,)) + Q/Length(i);
end
Tau = (-rho) * Tau + Delta_Tau;
% 迭代次数加1，清空路径记录表
iter = iter + ;
Table = zeros(m,n);
end
toc
%% 结果显示
[Shortest_Length,index] = min(Length_best);
Shortest_Route = Route_best(index,:);
disp(['最短距离:' num2str(Shortest_Length)]);
disp([)])]);
%% 绘图
figure()
plot([citys(Shortest_Route,);citys(Shortest_Route(),)],...
[citys(Shortest_Route,);citys(Shortest_Route(),)],'o-');
grid on
:size(citys,)
text(citys(i,),citys(i,),[' ' num2str(i)]);
end
text(citys(Shortest_Route(),),citys(Shortest_Route(),),' 起点');
text(citys(Shortest_Route(end),),citys(Shortest_Route(end),),' 终点');
xlabel('城市位置横坐标')
ylabel('城市位置纵坐标')
title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
figure()
plot(:iter_max,Length_best,:iter_max,Length_ave,'r:')
legend('最短距离','平均距离')
xlabel('迭代次数')
ylabel('距离')
title('各代最短距离与平均距离对比')
ACA.m
【运行结果比较】
测试数据选用和模拟退火的测试相同：
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975
c版ACA：
可选择设置的相关参数：
运行结果：
matlab版ACA：
运行结果：
从时间效率上看，c运行时间比matlab的运行时间少了2/3，在运行之前就想到了，也没什么惊讶的，而且代码被我写搓了，继续优化可以更快。。。
只测试了这么一组数据，对于参数的选择也没什么心得，等今后接触多了有自己的想法了再来填坑。。