1.算法仿真效果
matlab2022a仿真結(jié)果如下:
2.算法涉及理論知識概要
蟻群算法是通過對自然界中真實螞蟻的集體行為的觀察,模擬而得到一種仿生優(yōu)化算法,它具有很好的并行性,分布性.根據(jù)螞蟻群體不同的集體行為特征,蟻群算法可分為受螞蟻覓食行為啟發(fā)的模型和受孵化分類啟發(fā)的模型,受勞動分工和協(xié)作運輸啟發(fā)的模型.本文重點研究了前兩種蟻群算法模型. 受螞蟻覓食行為啟發(fā)的模型又稱為蟻群優(yōu)化算法(ACO),是繼模擬退火算法,遺傳算法,禁忌搜索等之后又一啟發(fā)式智能優(yōu)化算法.目前它已成功應(yīng)用于求解TSP問題,地圖著色,路徑車輛調(diào)度等優(yōu)化問題.本文針對蟻群算法收斂時間長,易陷入局部最優(yōu)的缺點,通過對路徑上信息素的更新方式作出動態(tài)調(diào)整,建立信息素平滑機制,進而使得不同路徑上的信息素的更新速度有所不同,從而使改進后算法能夠有效地縮短搜索的時間,并能對最終解進行優(yōu)化,避免過早的陷入局部最優(yōu). 聚類是數(shù)據(jù)挖掘的重要技術(shù)之一,它可按照某種規(guī)則將數(shù)據(jù)對象劃分為多個類或簇,使同一類的數(shù)據(jù)對象有較高的相似度,而不同類的數(shù)據(jù)對象差異較大. ??
“基本原理 蟻群算法(Ant Colony Optimization,ACO)是一種基于種群尋優(yōu)的啟發(fā)式搜索算法,有意大利學者M.Dorigo等人于1991年首先提出固蚤。該算 法受到自然界真實蟻群集體在覓食過程中行為的啟發(fā),利用真實蟻群通過個體間的信息傳遞耍群、搜索從蟻穴到食物間的最短路徑等集體尋優(yōu)特 征,來解決一些離散系統(tǒng)優(yōu)化中的困難問題慢叨。
算法基本思想:
(1)根據(jù)具體問題設(shè)置多只螞蟻,分頭并行搜索。
(2)每只螞蟻完成一次周游后,在行進的路上釋放信息素,信息素量與解的質(zhì)量成正比仑鸥。
(3)螞蟻路徑的選擇根據(jù)信息素強度大小(初始信息素量設(shè)為相等)变屁,同時考慮兩點之間的距離眼俊,采用隨機的局部搜索策略。這使得距離較短的邊粟关,其上的信息素量較大疮胖,后來的螞蟻選擇該邊的概率也較大。
(4)每只螞蟻只能走合法路線(經(jīng)過每個城市1次且僅1次)闷板,為此設(shè)置禁忌表來控制澎灸。
(5)所有螞蟻都搜索完一次就是迭代一次,每迭代一次就對所有的邊做一次信息素更新遮晚,原來的螞蟻死掉性昭,新的螞蟻進行新一輪搜索。
(6)更新信息素包括原有信息素的蒸發(fā)和經(jīng)過的路徑上信息素的增加县遣。
(7)達到預(yù)定的迭代步數(shù)糜颠,或出現(xiàn)停滯現(xiàn)象(所有螞蟻都選擇同樣的路徑,解不再變化)萧求,則算法結(jié)束其兴,以當前最優(yōu)解作為問題的最優(yōu)解。
將各個螞蟻隨機地置于不同的出發(fā)地夸政,對每個螞蟻k ( k = 1 , 2 , ? ?, m ) 元旬,按照輪盤賭法得到下面的轉(zhuǎn)移概率公式計算其下一個待訪問的城市,直到所有螞蟻訪問完所有的城市守问。
3.MATLAB核心程序
cordi=[37.97,23.72;%雅典娜
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; % 約翰內(nèi)斯堡
-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