1.算法仿真效果
matlab2022a仿真结果如下:
2.算法涉及理论知识概要
蚁群算法是通过对自然界中真实蚂蚁的集体行为的观察,模拟而得到一种仿生优化算法,它具有很好的并行性,分布性.根据蚂蚁群体不同的集体行为特征,蚁群算法可分为受蚂蚁觅食行为启发的模型和受孵化分类启发的模型,受劳动分工和协作运输启发的模型.本文重点研究了前两种蚁群算法模型. 受蚂蚁觅食行为启发的模型又称为蚁群优化算法(ACO),是继模拟退火算法,遗传算法,禁忌搜索等之后又一启发式智能优化算法.目前它已成功应用于求解TSP问题,地图着色,路径车辆调度等优化问题.本文针对蚁群算法收敛时间长,易陷入局部最优的缺点,通过对路径上信息素的更新方式作出动态调整,建立信息素平滑机制,进而使得不同路径上的信息素的更新速度有所不同,从而使改进后算法能够有效地缩短搜索的时间,并能对最终解进行优化,避免过早的陷入局部最优. 聚类是数据挖掘的重要技术之一,它可按照某种规则将数据对象划分为多个类或簇,使同一类的数据对象有较高的相似度,而不同类的数据对象差异较大.
“基本原理 蚁群算法(Ant Colony Optimization,ACO)是一种基于种群寻优的启发式搜索算法,有意大利学者M.Dorigo等人于1991年首先提出。该算 法受到自然界真实蚁群集体在觅食过程中行为的启发,利用真实蚁群通过个体间的信息传递、搜索从蚁穴到食物间的最短路径等集体寻优特 征,来解决一些离散系统优化中的困难问题。
算法基本思想:
(1)根据具体问题设置多只蚂蚁,分头并行搜索。
(2)每只蚂蚁完成一次周游后,在行进的路上释放信息素,信息素量与解的质量成正比。
(3)蚂蚁路径的选择根据信息素强度大小(初始信息素量设为相等),同时考虑两点之间的距离,采用随机的局部搜索策略。这使得距离较短的边,其上的信息素量较大,后来的蚂蚁选择该边的概率也较大。
(4)每只蚂蚁只能走合法路线(经过每个城市1次且仅1次),为此设置禁忌表来控制。
(5)所有蚂蚁都搜索完一次就是迭代一次,每迭代一次就对所有的边做一次信息素更新,原来的蚂蚁死掉,新的蚂蚁进行新一轮搜索。
(6)更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。
(7)达到预定的迭代步数,或出现停滞现象(所有蚂蚁都选择同样的路径,解不再变化),则算法结束,以当前最优解作为问题的最优解。
将各个蚂蚁随机地置于不同的出发地,对每个蚂蚁k ( k = 1 , 2 , ⋯ , m ) ,按照轮盘赌法得到下面的转移概率公式计算其下一个待访问的城市,直到所有蚂蚁访问完所有的城市。
3.MATLAB核心程序
41.38, 2.15; % 巴塞罗那
39.92, 116.42; % 北京
50.87, 4.37; % 布鲁塞尔
30.03, 31.35; % 钙飏o
13.75, 100.50; % 曼谷
14.62, -90.52; % 危地马拉城
23.13, -82.38; % 哈瓦那
60.17, 25.00; % 赫尔辛基
51.53, -0.83; % 隆登
19.43, -99.12; % 墨西哥城
28.58, 77.20; % 新德里
55.75, 37.60; % 莫斯库
41.83, -87.62; % 芝加哥
36.17, -115.20; % 拉斯维加斯
45.50, -73.58; % 蒙特利尔
40.78, -73.97; % 纽约
29.75, -95.35; % 休斯敦
14.67, -17.93; % 达喀尔
21.48, 39.75; % Mekka公司
-34.60, -58.38; % 布宜诺斯艾利斯
-15.78, -47.92; % 巴西利亚
-6.82, 39.28; % 达累斯萨拉姆
-6.13, 106.82; % 雅加达
-26.20, 28.07; % 约翰内斯堡
-4.33, 15.32; % 金沙萨
-12.03, -77.02; % 利马
-17.98, -67.15; % 奥鲁罗
-34.87, -56.16; % 蒙得维的亚
-53.17, -70.93; % 蓬塔阿雷纳斯
51.05, 3.72; % 根特
-33.86, 152.2]; % 悉尼
ParAS.fer0 = 0.00005;
ParAS.n_ants = 50;
ParAS.alfa = 1;
ParAS.beta = 2;
ParAS.rho = 0.1;
ParAS.tmax = 100;
ParAS.e = 30;
beginstad = 4;
[paden, lengtes] = AntSystem(cordi,ParAS,4);
bestePad = paden(:, find(lengtes==min(lengtes),1,'first'));
kortsteLengte = min(lengtes);
lg = 12;
load('World.mat');
figure
step=1;
Ani(1) = getframe;
im = frame2im(Ani(1));
[imind,cm] = rgb2ind(im,256);
for t = 1:ParAS.tmax
clf
hold on
imagesc(-179.875:0.25:179.875,-89.875:0.25:89.875,flipud(World))
axis([-180, 180, -90, 90])
.........................................................
end
figure
plot(1:ParAS.tmax,lengtes/1000,'-bs',...
'LineWidth',2,...
'MarkerSize',8,...
'MarkerEdgeColor','k',...
'MarkerFaceColor',[0.0,0.9,0.0])
xlabel('Iteration')
ylabel('Padlength (10^3 km)')
A319