蚁群算法蚁群算法和迪杰斯特拉还有弗洛伊德算法有什么区别

蚁群算法时间:2021-07-12 阅读:()

蚁群算法的核心是什么，怎么能和传统算法相结合

蚁群算法 (ant colony optimization, ACO，Ant colony optimization algorithms ) 将最优解比喻成食物，而把搜索过程比拟成蚁群在空间中寻找食物的过程，对解空间结构的认知通过“信息素”的“浓度”来表达，较好的解（路径、节点）会吸引更多的搜索力量（蚂蚁）。

ACO 本身是一种进化算法，在调度研究中取得了一些应用，但对于实际规模的问题，通常也是束手无策，解决的关键在于问题本身结构的分析和利用。

蚁群算法与遗传算法的区别？

都属于智能优化算法但是蚁群算法具有一定的记忆性，遗传算法没有蚁群算法有几种原则，比如觅食原则，避障原则等，遗传算法没有蚁群算法属于群智能优化算法，具有并行性，每个粒子都可以主动寻优，遗传算法不行蚁群算法基于信息素在环境中的指示，遗传算法是基于优胜劣汰的生物进化思想遗传算法有选择，交叉，变异三种算子，每种算子又有各自的不同方法，通过对算子方法的修改和搭配，可以得到不同的改进遗传算法蚁群算法则多和其他智能算法相结合，得到改进的蚁群算法

蚁群算法的概念，最好能举例说明一些蚁群算法适用于哪些问题！

概念：蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。

它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值其原理：为什么小小的蚂蚁能够找到食物？他们具有智能么？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。

这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序应用范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内引申：跟着蚂蚁的踪迹，你找到了什么？通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点： 1、多样性 2、正反馈多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。

我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。

正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。

引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。

如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。

这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。

既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。

而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。

而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！蚁群算法的实现下面的程序开始运行之后，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。

其中，‘F’点表示食物，‘H’表示窝，白色块表示障碍物，‘+’就是蚂蚁了。

具体参考/view/539346.htm 希望对你有帮助，谢谢。

蚁群算法由来

蚁群算法的由来： 1. 蚂蚁可以说是人类最常见、数量最庞大的昆虫之一，它们常常成群结队地出现在人类的日常生活环境中。

这些昆虫群体生物智能方面的特征，于是引起了一些学者的注意。

意大利学者M.Dorigo，V.Maniezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。

经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做"信息素"的挥发性化学物质来进行通信和协调的。

通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。

2. 蚁群算法是由Marco Dorigo博士，在1992年他的博士论文中提出的，其主要灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚁群算法是一种模拟进化算法，研究表明该算法具有许多优良的性质。

通过对PID控制器参数优化设计方面的问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比对，数值仿真结果表明，蚁群算法是一种新的模拟进化的优化方法，显示出了其适用于组合优化类问题求解的优越特性。

蚁群算法JAVA版

说明：信息素权重，路径权重和信息素蒸发率对最后的结果影响很大，需要微调。

目前发现2 / 5 / 0.5 能达到稍微让人满意的效果。

本程序离完美的ACO还差很远，仅供参考。

本蚁群算法为AS算法。

用法： 1.new一个对象 ACOforTSP tsp = new ACPforTSP(tsp数据文件名,迭代次数，蚂蚁数量，信息素权重，路径权重，信息素蒸发率）; 2.用go()方法运行 tsp.go(); ACOforTSP.java ___________________________________________________________________ import java.io.File; import static java.lang.Math.pow; import static java.lang.Math.sqrt; import static java.lang.Math.random; import java.util.HashMap; import java.io.FileReader; import java.io.BufferedReader; /** * * @author dvdface */ public class ACOforTSP { //城市的距离表 private double[][] distance; //距离的倒数表 private double[][] heuristic; //启发信息表 private double[][] pheromone; //权重 private int alpha, beta; //迭代的次数 private int iterationTimes; //蚂蚁的数量 private int numbersOfAnt; //蒸发率 private double rate; ACOforTSP (String file, int iterationTimes, int numbersOfAnt, int alpha, int beta, double rate) { //加载文件 this.initializeData(file); //初始化参数 this.iterationTimes = iterationTimes; //设置蚂蚁数量 this.numbersOfAnt = numbersOfAnt; //设置权重 this.alpha = alpha; this.beta = beta; //设置蒸发率 this.rate = rate; } private void initializeData(String filename) { //定义内部类 class City { int no; double x; double y; City(int no, double x, double y) { this.no = no; this.x = x; this.y = y; } private double getDistance(City city) { return sqrt(pow((x - city.x), 2) + pow((y - city.y), 2)); } } try { //定义HashMap保存读取的坐标信息 HashMap<Integer, City> map = new HashMap<Integer, City>(); //读取文件 BufferedReader reader = new BufferedReader(new FileReader(new File(filename))); for (String str = reader.readLine(); str != null; str = reader.readLine()) { //将读到的信息保存入HashMap if (str.matches("([0-9]+)(\s*)([0-9]+)(.?)([0-9]*)(\s*)([0-9]+)(.?)([0-9]*)")) { String[] data = str.split("(\s+)"); City city = new City(Integer.parseInt(data[0]), Double.parseDouble(data[1]), Double.parseDouble(data[2])); map.put(city.no, city); } } //分配距离矩阵存储空间 distance = new double[map.size() + 1][map.size() + 1]; //分配距离倒数矩阵存储空间 heuristic = new double[map.size() + 1][map.size() + 1]; //分配信息素矩阵存储空间 pheromone = new double[map.size() + 1][map.size() + 1]; for (int i = 1; i < map.size() + 1; i++) { for (int j = 1; j < map.size() + 1; j++) { //计算城市间的距离，并存入距离矩阵 distance[i][j] = map.get(i).getDistance(map.get(j)); //计算距离倒数，并存入距离倒数矩阵 heuristic[i][j] = 1 / distance[i][j]; //初始化信息素矩阵 pheromone[i][j] = 1; } } } catch (Exception exception) { System.out.println("初始化数据失败！"); } } class Ant { //已访问城市列表 private boolean[] visited; //访问顺序表 private int[] tour; //已访问城市的个数 private int n; //总的距离 private double total; Ant() { //给访问顺序表分配空间 tour = new int[distance.length+1]; //已存入城市数量为n，刚开始为0 n = 0; //将起始城市1,放入访问结点顺序表第一项 tour[++n] = 1; //给已访问城市结点分配空间 visited = new boolean[distance.length]; //第一个城市为出发城市，设置为已访问 visited[tour[n]] = true; } private int chooseCity() { //用来random的随机数 double m = 0; //获得当前所在的城市号放入j,如果和j相邻的城市没有被访问，那么加入m for (int i = 1, j = tour[n]; i < pheromone.length; i++) { if (!visited[i]) { m += pow(pheromone[j][i], alpha) * pow(heuristic[j][i], beta); } } //保存随机到的数 double p = m * random(); //寻找被随机到的城市 double k = 0; //保存找到的城市 int q = 0; for (int i = 1, j = tour[n]; k < p; i++) { if (!visited[i]) { k += pow(pheromone[j][i], alpha) * pow(heuristic[j][i], beta); q = i; } } return q; } private void constructSolution () { while (n != (distance.length-1) ) { //选取下一个城市 int p = chooseCity(); //计算总的距离 total += distance[tour[n]][p]; //将选取到的城市放入已访问列表 tour[++n] = p; //将选取到的城市标记为已访问 visited[p] = true; } //回到起点 total += distance[tour[1]][tour[n]]; //将起点加入访问顺序表的最后 tour[++n] = tour[1]; } private void releasePheromone() { //释放信息素的大小 double t = 1/total; //释放信息素 for (int i=1;i<tour.length-1;i++) { pheromone[tour[i]][tour[i+1]] += t; pheromone[tour[i+1]][tour[i]] += t; } } } public void go() { //保存最好的路径和路径长度 double bestTotal = Double.MAX_VALUE; int[] bestTour = new int[distance.length+1]; //新建蚂蚁数组，用来引用所创建的蚂蚁 Ant[] ant = new Ant[numbersOfAnt]; //进行iterationTimes次迭代 while (iterationTimes != 0) { //初始化新的一批蚂蚁（这里用构造新的蚂蚁代替重置蚂蚁状态） for (int i=0; i<numbersOfAnt; i++) { ant[i] = new Ant(); } //进行一次迭代（即让所有的蚂蚁构建一条路径） for (int i=0; i<numbersOfAnt; i++) { ant[i].constructSolution(); //如果蚂蚁构建的路径长度比上次最好的还好，那么保存这个长度和它所走的路径 if (ant[i].total<bestTotal) { bestTotal = ant[i].total; System.arraycopy(ant[i].tour, 1, bestTour, 1, bestTour.length-1); } } //蒸发信息素 evaporatePheromone(); //释放信息素 for (int i=0; i<numbersOfAnt; i++) { ant[i].releasePheromone(); } //报告本次迭代的信息 System.out.format("本次为倒数第%d次迭代,当前最优路径长度为%10.2f ",iterationTimes,bestTotal); //迭代总数减去1，进行下次迭代 iterationTimes--; } //输出最好的路径长度 System.out.format("得到的最优的路径长度为:%10.2f ",bestTotal); //输出最好的路径 System.out.println("最优路径如下："); for (int i=1; i<bestTour.length; i++) { System.out.print("→"+bestTour[i]); } } private void evaporatePheromone() { for (int i = 1; i < pheromone.length; i++) for (int j = 1; j < pheromone.length; j++) { pheromone[i][j] *= 1-rate; } } }