注册功能的网站怎么做,wordpress站点维护,wordpress个人唯美主题,站长工具特级a免费好像是看罗胖的罗辑思维#xff0c;看到过一种说法#xff0c;越是准入门槛高的#xff0c;难以取代的行业#xff0c;所需的工具是越简单的。摄影师需要昂贵的镜头#xff0c;而画家却只需要简单的纸笔#xff0c;尽管照片比画逼真得多#xff0c;但是却无法取代绘画的…好像是看罗胖的罗辑思维看到过一种说法越是准入门槛高的难以取代的行业所需的工具是越简单的。摄影师需要昂贵的镜头而画家却只需要简单的纸笔尽管照片比画逼真得多但是却无法取代绘画的地位而且通常优秀的射影作品的价值远远比不上优秀绘画作品的价值。在CS行业中也一样写代码需要各种IDE硬件环境但是算法却早在计算机诞生之前就有了应该说想要解决问题就会有算法有了算法才能计算。所以只会函数调用调参是不够的要自己写代码有自己的风格有自己的想法自己的算法。我也刚开始学习算法开始啃《算法导论》算是转行吧学习图像处理也需要各种算法今天就先研究与自己做的图像配准有关的蚁群算法。
很早就宣扬说21世纪是生物科学的世纪没想到目前确是互联网的世纪。但互联网中确实运用了很多生物的思想。比如大热的神经网络就是利用加权网络模拟神经和突触。在算法中也一样遗传进化算法借鉴生物进化论将问题模拟成一个生物进化的过程通过复制、交叉、突变等操作产生下一代的解。旅行商问题TSP(Travel Salesperson Problem)中通常运用遗传算法求解这在看算法导论的时候再好好研究。蚁群算法则是模拟蚂蚁觅食的过程在1991年由意大利学者Marco Dorigo提出。我们就看看这个算法到底是怎么模拟的。
在蚁群算法中一个关键词是信息素它是一种激素蚂蚁找到食物回家时释放关于食物的信息素在出去找食物时在路径上留下关于家的信息素浓度随着时间逐渐降低更新机制。但信息素有正反馈性它会吸引附近的蚂蚁来到这条路径选择机制从而释放更多的信息素更新机制。这个选择的过程称为蚂蚁的自催化行为。值得一提的是对单个蚂蚁来说是不存在所谓的最优路径的蚂蚁根据概率随机选择一条路径但蚁群会互相通信、协同工作协调机制会在客观上找到了最优路径这就是群体智能。为了防止蚂蚁都选择当前信息素浓度最高的路径只得到局部最优解总有个别蚂蚁走向其他路径从而跳出最优解这就是出错机制。可以通过一个H5实验直观地观察一下在这里。
以TSP问题为例对蚁群算法建模。除了城市的数量蚁群的数量还有很多数据这就凸显了数据结构的重要性。说一下我理解的蚁群算法的整个流程。第一步当然是初始化对每条边的信息素浓度初始化为常数信息素改变量初始化为0。然后把蚂蚁分散到各个城市他们依次开始周游。我们把从当前城市到下一个城市的概率称为转移概率通过转移概率计算转移概率综合考虑了信息素的吸引力和对城市间距离的衡量权重通过、体现。每到过一个城市会在禁忌表中添加该点防止重复达到同一个城市。当该蚂蚁完成一次周游记录这次周游的路径总长度这里考虑蚂蚁一次周游释放的信息素总量是一定的所以均匀分布在每次的转移路径中这部分新增的信息素和之前的信息素残留构成了下次迭代的初始信息素浓度。迭代是指所有的蚂蚁都完成了周游每次迭代过程中每只蚂蚁计算转移概率时认为信息素浓度暂时不变只是当所有蚂蚁周游完即下一次迭代开始时才对信息素浓度进行更新更新时会对各个蚂蚁走过的路径累加计算信息素浓度。这样当迭代到一定次数因为某一条路径信息素浓度足够高会进行收敛从而找到最优的路径。
从公式中可以得到更加清楚的认识$$\Delta \tau _{ij}^k \frac{Q}{{\sum {{L_k}} }}{L_{ij}}$$ 公式1
Q为信息素质量系数是一个正的常数表示蚂蚁一次释放的信息素绝对质量。分母表示蚂蚁k在本次周游中所走的路径总长度。Lij表示转移路径ij得到的信息素浓度。
$${\tau _{ij}}(t n) (1 - \rho ) \cdot {\tau _{ij}}(t) \Delta {\tau _{ij}}$$ 公式2
这个是每次迭代时信息素浓度的更新公式。综合考虑了原来的信息素浓度残留和刚才式1求得的新增的信息素浓度。
$$p_{ij}^k \frac{{{\tau _{ij}}^\alpha \eta _{ij}^\beta }}{{\sum\limits_{j \in \Lambda } {\tau _{ij}^\alpha \eta _{ij}^\beta } }}$$ 公式3
公式3是概率转移公式。得到概率之后按照轮盘赌的方式选择下一步的城市。只需要知道轮盘赌是一种随机性的选择方式就可以了当然还是概率大的更容易被选中。之后可以写文章研究一下。
下面是matlab代码来自https://blog.csdn.net/longxinghaofeng/article/details/77740480
%蚁群算法求解TSP问题的matlab程序
clear all
close all
clc%初始化蚁群
m31;%蚁群中蚂蚁的数量当m接近或等于城市个数n时本算法可以在最少的迭代次数内找到最优解
C[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];%城市的坐标矩阵
Nc_max200;%最大循环次数即算法迭代的次数亦即蚂蚁出动的拨数每拨蚂蚁的数量当然都是m
alpha1;%蚂蚁在运动过程中所积累信息即信息素在蚂蚁选择路径时的相对重要程度alpha过大时算法迭代到一定代数后将出现停滞现象
beta5;%启发式因子在蚂蚁选择路径时的相对重要程度
rho0.5;%0rho1,表示路径上信息素的衰减系数亦称挥发系数、蒸发系数1-rho表示信息素的持久性系数
Q100;%蚂蚁释放的信息素量对本算法的性能影响不大%变量初始化
nsize(C,1);%表示TSP问题的规模亦即城市的数量
Dones(n,n);%表示城市完全地图的赋权邻接矩阵记录城市之间的距离
for i1:nfor j1:nif ijD(i,j)sqrt((C(i,1)-C(j,1))^2(C(i,2)-C(j,2))^2);endD(j,i)D(i,j);end
end
eta1./D;%启发式因子这里设为城市之间距离的倒数
pheromoneones(n,n);%信息素矩阵,这里假设任何两个城市之间路径上的初始信息素都为1
tabu_listzeros(m,n);%禁忌表记录蚂蚁已经走过的城市蚂蚁在本次循环中不能再经过这些城市。当本次循环结束后禁忌表被用来计算蚂蚁当前所建立的解决方案即经过的路径和路径的长度
Nc0;%循环次数计数器
routh_bestzeros(Nc_max,n);%各次循环的最短路径
length_bestones(Nc_max,1);%各次循环最短路径的长度
length_averageones(Nc_max,1);%各次循环所有路径的平均长度while NcNc_max%将m只蚂蚁放在n个城市上rand_position[];for i1:ceil(m/n) %朝正无穷方向取整 蚂蚁数量/城市数量rand_position[rand_position,randperm(n)];endtabu_list(:,1)(rand_position(1:m));%将蚂蚁放在城市上之后的禁忌表第i行表示第i只蚂蚁第i行第一列元素表示第i只蚂蚁所在的初始城市%m只蚂蚁按概率函数选择下一座城市在本次循环中完成各自的周游for j2:nfor i1:mcity_visitedtabu_list(i,1:(j-1));%已访问的城市city_remainedzeros(1,(n-j1));%待访问的城市probabilitycity_remained;%待访问城市的访问概率cr1;%for循环用于求待访问的城市。比如如果城市个数是5而已访问的城市city_visited[2 4],则经过此for循环后city_remanied[1 3 5]for k1:nif length(find(city_visitedk))0city_remained(cr)k;crcr1;endend%for循环计算待访问城市的访问概率分布此概率和两个参数有关一是蚂蚁当前所在城市即city_visited(end))和待访问城市即city_remainedk))路径上的信息素一是这两者之间的启发因子即距离的倒数 for k1:length(city_remained)probability(k)(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;endprobabilityprobability/sum(probability);%按概率选取下一个要访问的城市pcumcumsum(probability);%返回各列的累加值selectfind(pcumrand);to_visitcity_remained(select(1));tabu_list(i,j)to_visit;endendif Nc0tabu_list(1,:)routh_best(Nc,:);%将上一代的最优路径最优解保留下来保证上一代中的最适应个体的信息不会丢失end%记录本次循环的最佳路线total_lengthzeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度for i1:mrtabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径for j1:(n-1)total_length(i)total_length(i)D(r(j),r(j1));%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度endtotal_length(i)total_length(i)D(r(1),r(n));%最终得到第i只蚂蚁在本次循环中所走过的路径长度endlength_best(Nc1)min(total_length);%把m只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度positionfind(total_lengthlength_best(Nc1));%找到最短路径的位置即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的routh_best(Nc1,:)tabu_list(position(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径length_average(Nc1)mean(total_length);%计算本次循环中m只蚂蚁所走路径的平均长度NcNc1%更新信息素delta_pheromonezeros(n,n);for i1:mfor j1:(n-1)delta_pheromone(tabu_list(i,j),tabu_list(i,j1))delta_pheromone(tabu_list(i,j),tabu_list(i,j1))Q/total_length(i);%total_length(i)为第i只蚂蚁在本次循环中所走过的路径长度蚁周系统区别于蚁密系统和蚁量系统的地方enddelta_pheromone(tabu_list(i,n),tabu_list(i,1))delta_pheromone(tabu_list(i,n),tabu_list(i,1))Q/total_length(i);%至此把第i只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去end%至此把m只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去pheromone(1-rho).*pheromonedelta_pheromone;%本次循环后所有路径上的信息素%禁忌表清零准备下一次循环蚂蚁在下一次循环中又可以自由地进行选择tabu_listzeros(m,n);
end%输出结果绘制图形
positionfind(length_bestmin(length_best));
shortest_pathrouth_best(position(1),:)
shortest_lengthlength_best(position(1))
%绘制最短路径
figure(1)
set(gcf,Name,Ant Colony Optimization——Figure of shortest_path,Color,r)
Nlength(shortest_path);
scatter(C(:,1),C(:,2),50,filled);
hold on
plot([C(shortest_path(1),1),C(shortest_path(N),1)],[C(shortest_path(1),2),C(shortest_path(N),2)])
set(gca,Color,g)
hold on
for i2:Nplot([C(shortest_path(i-1),1),C(shortest_path(i),1)],[C(shortest_path(i-1),2),C(shortest_path(i),2)])hold on
end
%绘制每次循环最短路径长度和平均路径长度
figure(2)
set(gcf,Name,Ant Colony Optimization——Figure of length_best and length_average,Color,r)
plot(length_best,r)
set(gca,Color,g)
hold on
plot(length_average,k)
这是结果找到的最佳路线图。原网址的代码写得很好注释也很详细就是图的配色有一点辣眼睛。Reference
1.https://blog.csdn.net/lzhf1122/article/details/72668977
2.https://blog.csdn.net/zhushuai1221/article/details/51076156 ACO应用、问题、趋势
3.https://blog.csdn.net/wang_Number_1/article/details/52467567
4.https://www.cnblogs.com/Leo_wl/p/5665715.html
5.https://www.cnblogs.com/tao-alex/p/6094483.html 表中的最后一列不理解
