精华内容
下载资源
问答
  • 列举了蚁群算法与粒子群算法的优缺点,以及对比,提供了一个较为完善的优化思路
  • 蚁群算法发展;蚂蚁的生物学特征;蚁群算法起源;...基本蚁群算法优缺点; 蚁群优化算法研究进展;蚁群算法的应用;蚁群算法的应用;蚁群算法的发展趋势;谢谢;此课件下载可自行编辑修改仅供参考 感谢您的支持
  • 基于蚁群算法的TSP问题研究的开题报告 1.1 蚁群算法的发展和应用 1.2 蚁群算法求解TSP问题 1.3 蚁群算法优缺点 1.4 蚁群算法的展望 参考文献 毕业设计任务要研究或解决的问题和拟采用的方法
  • 蚁群算法发展.pptx

    2020-06-20 07:58:01
    蚁群算法;蚂蚁的生物学特征;蚂蚁的生物学特征;蚁群算法起源;蚁群算法的基本原理;蚁群算法的基本原理;...基本蚁群算法优缺点; 蚁群优化算法研究进展;蚁群算法的应用;蚁群算法的应用;蚁群算法的发展趋势;谢谢
  • 1. 蚁群算法简介 蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求
    原文地址为:蚁群算法java实现以及TSP问题蚁群算法求解

    1. 蚁群算法简介

         蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。经过20多年的发展,蚁群算法在理论以及应用研究上已经得到巨大的进步。

          蚁群算法是一种仿生学算法,是由自然界中蚂蚁觅食的行为而启发的。在自然界中,蚂蚁觅食过程中,蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图(1)显示了这样一个觅食的过程。

    image

    图(1)蚂蚁觅食

     

         在图1(a)中,有一群蚂蚁,假如A是蚁巢,E是食物源(反之亦然)。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了一个障碍物(图1(b)),那么,在B点(或D点)的蚂蚁将要做出决策,到底是向左行驶还是向右行驶?由于一开始路上没有前面蚂蚁留下的信息素(pheromone),蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时,它将会在它行进的路上释放出信息素,并且这种信息素会议一定的速率散发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度,做出决策,往左还是往右。很明显,沿着短边的的路径上信息素将会越来越浓(图1(c)),从而吸引了越来越多的蚂蚁沿着这条路径行驶。

    2. TSP问题描述

          蚁群算法最早用来求解TSP问题,并且表现出了很大的优越性,因为它分布式特性,鲁棒性强并且容易与其它算法结合,但是同时也存在这收敛速度慢,容易陷入局部最优(local optimal)等缺点。

          TSP问题(Travel Salesperson Problem,即旅行商问题或者称为中国邮递员问题),是一种,是一种NP-hard问题,此类问题用一般的算法是很大得到最优解的,所以一般需要借助一些启发式算法求解,例如遗传算法(GA),蚁群算法(ACO),微粒群算法(PSO)等等。

          TSP问题可以分为两类,一类是对称TSP问题(Symmetric TSP),另一类是非对称问题(Asymmetric TSP)。所有的TSP问题都可以用一个图(Graph)来描述:

    $V=\{c_1,c_2,\ldots,c_i,\ldots,c_n\},i=1,2,\ldots,n$是所有城市的集合. $c_i$表示第i个城市, $n$为城市的数目;

    $E=\{(r,s):r,s \in V\}$是所有城市之间连接的集合;

    $C=\{c_{rs}:r,s \in V\}$是所有城市之间连接的成本度量(一般为城市之间的距离);

    如果$c_{rs} = c_{sr}$, 那么该TSP问题为对称的,否则为非对称的。

    一个TSP问题可以表达为:

    求解遍历图$G=(V,E,C)$所有的节点一次并且回到起始节点,使得连接这些节点的路径成本最低。

    3. 蚁群算法原理

          假如蚁群中所有蚂蚁的数量为m,所有城市之间的信息素用矩阵pheromone表示,最短路径为bestLength,最佳路径为bestTour。每只蚂蚁都有自己的内存,内存中用一个禁忌表(Tabu)来存储该蚂蚁已经访问过的城市,表示其在以后的搜索中将不能访问这些城市;还有用另外一个允许访问的城市表(Allowed)来存储它还可以访问的城市;另外还用一个矩阵(Delta)来存储它在一个循环(或者迭代)中给所经过的路径释放的信息素;还有另外一些数据,例如一些控制参数$(\alpha,\beta,\rho,Q)$,该蚂蚁行走玩全程的总成本或距离(tourLength),等等。假定算法总共运行MAX_GEN次,运行时间为t

    蚁群算法计算过程如下:

    (1)初始化

    t=0,初始化bestLength为一个非常大的数(正无穷),bestTour为空。初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点。

    (2)为每只蚂蚁选择下一个节点。

    为每只蚂蚁选择下一个节点,该节点只能从Allowed中以某种概率(公式1)搜索到,每搜到一个,就将该节点加入到Tabu中,并且从Allowed中删除该节点。该过程重复n-1次,直到所有的城市都遍历过一次。遍历完所有节点后,将起始节点加入到Tabu中。此时Tabu表元素数量为n+1(n为城市数量),Allowed元素数量为0。接下来按照(公式2)计算每个蚂蚁的Delta矩阵值。最后计算最佳路径,比较每个蚂蚁的路径成本,然后和bestLength比较,若它的路径成本比bestLength小,则将该值赋予bestLength,并且将其Tabu赋予BestTour。

    (公式1)

    (公式2)

    其中$p_{ij}^{(t)}$表示选择城市j的概率,$k$表示第$k$个蚂蚁,$\tau_{ij}^{(t)}$表示城市$i,j$在第$t$时刻的信息素浓度,$\eta_{ij}$表示从城市i到城市j的可见度,

    $\eta_{ij} = \frac 1 {d_{ij}}$,$d_{ij}$表示城市$i,j$之间的成本(或距离)。由此可见$d_{ij}$越小,$\eta_{ij}$越大,也就是从城市$i$到$j$的可见性就越大。$\Delta \tau_{ij}^k$表示蚂蚁$k$在城市$i$与$j$之间留下的信息素。

    $L_k$表示蚂蚁$k$经过一个循环(或迭代)锁经过路径的总成本(或距离),即tourLength.$\alpha, \beta, Q$ 均为控制参数。

    (3)更新信息素矩阵

    令$t=t+n$t,按照(公式3)更新信息素矩阵phermone。

    \[ \tau_{ij}(t+n) = \rho \cdot \tau_{ij}(t) + \Delta \tau_{ij} \]

    (公式3)

    $\tau_{ij}(t+n)$为$t+n$时刻城市$i$与$j$之间的信息素浓度。$\rho$为控制参数,$Delta_ij$为城市$i$与$j$之间信息素经过一个迭代后的增量。并且有

    \[ \Delta \tau_{ij} = \sum_{k=1}^m \Delta \tau_{ij}^k\]

    (公式4)

    其中$\Delta \tau_{ij}^k$由公式计算得到。

    (4)检查终止条件

    如果达到最大代数MAX_GEN,算法终止,转到第(5)步;否则,重新初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点,重复执行(2),(3),(4)步。

    (5)输出最优值

    4. Java实现

          在该java实现中我们选择使用tsplib上的数据att48,这是一个对称tsp问题,城市规模为48,其最优值为10628.其距离计算方法如图(2)所示:

    image

    图(2)att48距离计算方法

          实现中,使用了两个java类,一个Ant类,一个ACO类。

    具体实现代码如下(此代码借鉴了蚁群优化算法的JAVA实现):

    Ant类:

      1: import java.util.Random;
      2: import java.util.Vector;
      3: 
      4: /**
      5:  * 
      6:  * @author BIAO YU
      7:  *
      8:  */
      9: public class Ant implements Cloneable {
     10: 
     11:   private Vector<Integer> tabu; //禁忌表
     12:   private Vector<Integer> allowedCities; //允许搜索的城市
     13:   private float[][] delta; //信息数变化矩阵
     14:   private int[][] distance; //距离矩阵
     15:   
     16:   private float alpha; 
     17:   private float beta;
     18:   
     19:   private int tourLength; //路径长度
     20:   private int cityNum; //城市数量
     21:   
     22:   private int firstCity; //起始城市
     23:   private int currentCity; //当前城市
     24:   
     25:   public Ant(){
     26:     cityNum = 30;
     27:     tourLength = 0;
     28:     
     29:   }
     30:   
     31:   /**
     32:    * Constructor of Ant
     33:    * @param num 蚂蚁数量
     34:    */
     35:   public Ant(int num){
     36:     cityNum = num;
     37:     tourLength = 0;
     38:     
     39:   }
     40:   
     41:   /**
     42:    * 初始化蚂蚁,随机选择起始位置
     43:    * @param distance 距离矩阵
     44:    * @param a alpha
     45:    * @param b beta
     46:    */
     47:   public void init(int[][] distance, float a, float b){
     48:     alpha = a;
     49:     beta = b;
     50:     allowedCities = new Vector<Integer>();
     51:     tabu = new Vector<Integer>();
     52:     this.distance = distance;
     53:     delta = new float[cityNum][cityNum];
     54:     for (int i = 0; i < cityNum; i++) {
     55:       Integer integer = new Integer(i);
     56:       allowedCities.add(integer);
     57:       for (int j = 0; j < cityNum; j++) {
     58:         delta[i][j] = 0.f;
     59:       }
     60:     }
     61:     
     62:     Random random = new Random(System.currentTimeMillis());
     63:     firstCity = random.nextInt(cityNum);
     64:     for (Integer i:allowedCities) {
     65:       if (i.intValue() == firstCity) {
     66:         allowedCities.remove(i);
     67:         break;
     68:       }
     69:     }
     70:     
     71:     tabu.add(Integer.valueOf(firstCity));
     72:     currentCity = firstCity;
     73:   }
     74:   
     75:   /**
     76:    * 选择下一个城市
     77:    * @param pheromone 信息素矩阵
     78:    */
     79:   public void selectNextCity(float[][] pheromone){
     80:     float[] p = new float[cityNum];
     81:     float sum = 0.0f;
     82:     //计算分母部分
     83:     for (Integer i:allowedCities) {
     84:       sum += Math.pow(pheromone[currentCity][i.intValue()], alpha)*Math.pow(1.0/distance[currentCity][i.intValue()], beta);
     85:     }
     86:     //计算概率矩阵
     87:     for (int i = 0; i < cityNum; i++) {
     88:       boolean flag = false;
     89:       for (Integer j:allowedCities) {
     90:         
     91:         if (i == j.intValue()) {
     92:           p[i] = (float) (Math.pow(pheromone[currentCity][i], alpha)*Math.pow(1.0/distance[currentCity][i], beta))/sum;
     93:           flag = true;
     94:           break;
     95:         }
     96:       }
     97:       
     98:       if (flag == false) {
     99:         p[i] = 0.f;
    100:       }
    101:     }
    102:     
    103:     //轮盘赌选择下一个城市
    104:     Random random = new Random(System.currentTimeMillis());
    105:     float sleectP = random.nextFloat();
    106:     int selectCity = 0;
    107:     float sum1 = 0.f;
    108:     for (int i = 0; i < cityNum; i++) {
    109:       sum1 += p[i];
    110:       if (sum1 >= sleectP) {
    111:         selectCity = i;
    112:         break;
    113:       }
    114:     }
    115:     
    116:     //从允许选择的城市中去除select city
    117:     for (Integer i:allowedCities) {
    118:       if (i.intValue() == selectCity) {
    119:         allowedCities.remove(i);
    120:         break;
    121:       }
    122:     }
    123:     //在禁忌表中添加select city
    124:     tabu.add(Integer.valueOf(selectCity));
    125:     //将当前城市改为选择的城市
    126:     currentCity = selectCity;
    127:     
    128:   }
    129:   
    130:   /**
    131:    * 计算路径长度
    132:    * @return 路径长度
    133:    */
    134:   private int calculateTourLength(){
    135:     int len = 0;
    136:     for (int i = 0; i < cityNum; i++) {
    137:       len += distance[this.tabu.get(i).intValue()][this.tabu.get(i+1).intValue()];
    138:     }
    139:     return len;
    140:   }
    141:   
    142:   
    143:   
    144:   public Vector<Integer> getAllowedCities() {
    145:     return allowedCities;
    146:   }
    147: 
    148:   public void setAllowedCities(Vector<Integer> allowedCities) {
    149:     this.allowedCities = allowedCities;
    150:   }
    151: 
    152:   public int getTourLength() {
    153:     tourLength = calculateTourLength();
    154:     return tourLength;
    155:   }
    156:   public void setTourLength(int tourLength) {
    157:     this.tourLength = tourLength;
    158:   }
    159:   public int getCityNum() {
    160:     return cityNum;
    161:   }
    162:   public void setCityNum(int cityNum) {
    163:     this.cityNum = cityNum;
    164:   }
    165: 
    166:   public Vector<Integer> getTabu() {
    167:     return tabu;
    168:   }
    169: 
    170:   public void setTabu(Vector<Integer> tabu) {
    171:     this.tabu = tabu;
    172:   }
    173: 
    174:   public float[][] getDelta() {
    175:     return delta;
    176:   }
    177: 
    178:   public void setDelta(float[][] delta) {
    179:     this.delta = delta;
    180:   }
    181: 
    182:   public int getFirstCity() {
    183:     return firstCity;
    184:   }
    185: 
    186:   public void setFirstCity(int firstCity) {
    187:     this.firstCity = firstCity;
    188:   }
    189:   
    190: }
    191: 

    ACO类:

      1: import java.io.BufferedReader;
      2: import java.io.FileInputStream;
      3: import java.io.IOException;
      4: import java.io.InputStreamReader;
      5: 
      6: /**
      7:  * 
      8:  * @author BIAO YU
      9:  * 
     10:  *
     11:  */
     12: public class ACO {
     13: 
     14:   private Ant[] ants; //蚂蚁
     15:   private int antNum; //蚂蚁数量
     16:   private int cityNum; //城市数量
     17:   private int MAX_GEN; //运行代数
     18:   private float[][] pheromone; //信息素矩阵
     19:   private int[][] distance; //距离矩阵
     20:   private int bestLength; //最佳长度
     21:   private int[] bestTour; //最佳路径
     22:   
     23:   //三个参数
     24:   private float alpha; 
     25:   private float beta;
     26:   private float rho;
     27:   
     28:   
     29:   public ACO(){
     30:     
     31:   }
     32:   /** constructor of ACO
     33:    * @param n 城市数量
     34:    * @param m 蚂蚁数量
     35:    * @param g 运行代数
     36:    * @param a alpha
     37:    * @param b beta
     38:    * @param r rho
     39:    * 
     40:   **/
     41:   public ACO(int n, int m, int g, float a, float b, float r) {
     42:     cityNum = n;
     43:     antNum = m;
     44:     ants = new Ant[antNum];
     45:     MAX_GEN = g;
     46:     alpha = a;
     47:     beta = b;
     48:     rho = r;
     49:     
     50:   }
     51:   
     52:   @SuppressWarnings("resource")
     53:   /**
     54:    * 初始化ACO算法类
     55:    * @param filename 数据文件名,该文件存储所有城市节点坐标数据
     56:    * @throws IOException
     57:    */
     58:   private void init(String filename) throws IOException{
     59:     //读取数据  
     60:         int[] x;  
     61:         int[] y;  
     62:         String strbuff;  
     63:         BufferedReader data = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));  
     64:         
     65:         distance = new int[cityNum][cityNum];  
     66:         x = new int[cityNum];  
     67:         y = new int[cityNum];  
     68:         for (int i = 0; i < cityNum; i++) {  
     69:             strbuff = data.readLine(); 
     70:             String[] strcol = strbuff.split("");  
     71:             x[i] = Integer.valueOf(strcol[1]);  
     72:             y[i] = Integer.valueOf(strcol[2]);  
     73:         }  
     74:         //计算距离矩阵 ,针对具体问题,距离计算方法也不一样,此处用的是att48作为案例,它有48个城市,距离计算方法为伪欧氏距离,最优值为10628 
     75:         for (int i = 0; i < cityNum - 1; i++) {  
     76:             distance[i][i] = 0;  //对角线为0
     77:             for (int j = i + 1; j < cityNum; j++) {  
     78:               double rij = Math.sqrt(((x[i] - x[j]) * (x[i] - x[j])+ (y[i] - y[j]) * (y[i] - y[j]))/10.0);
     79:               int tij = (int) Math.round(rij);
     80:               if (tij < rij) {
     81:                 distance[i][j] = tij + 1;  
     82:                     distance[j][i] = distance[i][j];  
     83:         }else {
     84:           distance[i][j] = tij;  
     85:                     distance[j][i] = distance[i][j]; 
     86:         }
     87:             }  
     88:         }  
     89:         distance[cityNum - 1][cityNum - 1] = 0;  
     90:         
     91:         //初始化信息素矩阵  
     92:         pheromone=new float[cityNum][cityNum];  
     93:         for(int i=0;i<cityNum;i++)  
     94:         {  
     95:             for(int j=0;j<cityNum;j++){  
     96:                 pheromone[i][j]=0.1f;  //初始化为0.1
     97:             }  
     98:         }  
     99:         bestLength=Integer.MAX_VALUE;  
    100:         bestTour=new int[cityNum+1];  
    101:         //随机放置蚂蚁  
    102:         for(int i=0;i<antNum;i++){  
    103:             ants[i]=new Ant(cityNum);  
    104:             ants[i].init(distance, alpha, beta);  
    105:         }  
    106:   }
    107:   
    108:   public void solve(){
    109:     
    110:     for (int g = 0; g < MAX_GEN; g++) {
    111:       for (int i = 0; i < antNum; i++) {
    112:         for (int j = 1; j < cityNum; j++) {
    113:           ants[i].selectNextCity(pheromone);
    114:         }
    115:         ants[i].getTabu().add(ants[i].getFirstCity());
    116:         if (ants[i].getTourLength() < bestLength) {
    117:           bestLength = ants[i].getTourLength();
    118:           for (int k = 0; k < cityNum + 1; k++) {
    119:             bestTour[k] = ants[i].getTabu().get(k).intValue();
    120:           }
    121:         }
    122:         for (int j = 0; j < cityNum; j++) {
    123:           ants[i].getDelta()[ants[i].getTabu().get(j).intValue()][ants[i].getTabu().get(j+1).intValue()] = (float) (1./ants[i].getTourLength());
    124:           ants[i].getDelta()[ants[i].getTabu().get(j+1).intValue()][ants[i].getTabu().get(j).intValue()] = (float) (1./ants[i].getTourLength());
    125:         }
    126:       }
    127:       
    128:       //更新信息素
    129:       updatePheromone();
    130:       
    131:        //重新初始化蚂蚁
    132:           for(int i=0;i<antNum;i++){  
    133:              
    134:               ants[i].init(distance, alpha, beta);  
    135:           }  
    136:     }
    137:     
    138:     //打印最佳结果
    139:     printOptimal();
    140:   }
    141:   
    142:   //更新信息素
    143:   private void updatePheromone(){
    144:     //信息素挥发  
    145:         for(int i=0;i<cityNum;i++)  
    146:             for(int j=0;j<cityNum;j++)  
    147:                 pheromone[i][j]=pheromone[i][j]*(1-rho);  
    148:         //信息素更新  
    149:         for(int i=0;i<cityNum;i++){  
    150:             for(int j=0;j<cityNum;j++){  
    151:                 for (int k = 0; k < antNum; k++) {
    152:           pheromone[i][j] += ants[k].getDelta()[i][j];
    153:         } 
    154:             }  
    155:         }  
    156:   }
    157:   
    158:   private void printOptimal(){
    159:     System.out.println("The optimal length is: " + bestLength);
    160:     System.out.println("The optimal tour is: ");
    161:     for (int i = 0; i < cityNum + 1; i++) {
    162:       System.out.println(bestTour[i]);
    163:     }
    164:   }
    165:   
    166:   public Ant[] getAnts() {
    167:     return ants;
    168:   }
    169: 
    170:   public void setAnts(Ant[] ants) {
    171:     this.ants = ants;
    172:   }
    173: 
    174:   public int getAntNum() {
    175:     return antNum;
    176:   }
    177: 
    178:   public void setAntNum(int m) {
    179:     this.antNum = m;
    180:   }
    181: 
    182:   public int getCityNum() {
    183:     return cityNum;
    184:   }
    185: 
    186:   public void setCityNum(int cityNum) {
    187:     this.cityNum = cityNum;
    188:   }
    189: 
    190:   public int getMAX_GEN() {
    191:     return MAX_GEN;
    192:   }
    193: 
    194:   public void setMAX_GEN(int mAX_GEN) {
    195:     MAX_GEN = mAX_GEN;
    196:   }
    197: 
    198:   public float[][] getPheromone() {
    199:     return pheromone;
    200:   }
    201: 
    202:   public void setPheromone(float[][] pheromone) {
    203:     this.pheromone = pheromone;
    204:   }
    205: 
    206:   public int[][] getDistance() {
    207:     return distance;
    208:   }
    209: 
    210:   public void setDistance(int[][] distance) {
    211:     this.distance = distance;
    212:   }
    213: 
    214:   public int getBestLength() {
    215:     return bestLength;
    216:   }
    217: 
    218:   public void setBestLength(int bestLength) {
    219:     this.bestLength = bestLength;
    220:   }
    221: 
    222:   public int[] getBestTour() {
    223:     return bestTour;
    224:   }
    225: 
    226:   public void setBestTour(int[] bestTour) {
    227:     this.bestTour = bestTour;
    228:   }
    229: 
    230:   public float getAlpha() {
    231:     return alpha;
    232:   }
    233: 
    234:   public void setAlpha(float alpha) {
    235:     this.alpha = alpha;
    236:   }
    237: 
    238:   public float getBeta() {
    239:     return beta;
    240:   }
    241: 
    242:   public void setBeta(float beta) {
    243:     this.beta = beta;
    244:   }
    245: 
    246:   public float getRho() {
    247:     return rho;
    248:   }
    249: 
    250:   public void setRho(float rho) {
    251:     this.rho = rho;
    252:   }
    253: 
    254: 
    255:   /**
    256:    * @param args
    257:    * @throws IOException 
    258:    */
    259:   public static void main(String[] args) throws IOException {
    260:     ACO aco = new ACO(48, 100, 1000, 1.f, 5.f, 0.5f);
    261:     aco.init("c://data.txt");
    262:     aco.solve();
    263:   }
    264: 
    265: }
    266: 

    5. 总结

          蚁群算法和其它的启发式算法一样,在很多场合都得到了应用,并且取得了很好的结果。但是同样存在着很多的缺点,例如收敛速度慢,容易陷入局部最优,等等。对于这些问题,还需要进一步的研究和探索,另外蚁群算法的数学机理至今还没有得到科学的解释,这也是当前研究的热点和急需解决的问题之一。注:TSP数据文件以及两篇早期的关于蚁群算法的文章包含在附件中,请点击此处下载附件


    转载请注明本文地址:蚁群算法java实现以及TSP问题蚁群算法求解
    展开全文
  • 蚁群算法原理概要介绍;蚁群算法的基本规则;蚁群算法优缺点进;蚁群算法与遗传算法比较;MATLAB范例
  • 蚁群算法

    2020-11-18 11:46:05
    1.蚁群算法简介 蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法是一...

    1.蚁群算法简介

    蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
    蚁群算法是一种仿生学算法,是由自然界中蚂蚁觅食的行为而启发的。在自然界中,蚂蚁觅食过程中,蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图(1)显示了这样一个觅食的过程。
    这里写图片描述

    在图1(a)中,有一群蚂蚁,假如A是蚁巢,E是食物源(反之亦然)。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了一个障碍物(图1(b)),那么,在B点(或D点)的蚂蚁将要做出决策,到底是向左行驶还是向右行驶?由于一开始路上没有前面蚂蚁留下的信息素(pheromone),蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时,它将会在它行进的路上释放出信息素,并且这种信息素会以一定的速率散发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度,做出决策,往左还是往右。很明显,沿着短边的的路径上信息素将会越来越浓(图1(c)),从而吸引了越来越多的蚂蚁沿着这条路径行驶。

    2.TSP问题描述

    蚁群算法最早用来求解TSP问题,并且表现出了很大的优越性,因为它分布式特性,鲁棒性强并且容易与其它算法结合,但是同时也存在这收敛速度慢,容易陷入局部最优(local optimal)等缺点。
    TSP问题(Travel Salesperson Problem,即旅行商问题或者称为中国邮递员问题),是一种NP-hard问题,此类问题用一般的算法是很大得到最优解的,所以一般需要借助一些启发式算法求解,例如遗传算法(GA),蚁群算法(ACO),微粒群算法(PSO)等等。
    TSP问题可以分为两类,一类是对称TSP问题(Symmetric TSP),另一类是非对称问题(Asymmetric TSP)。所有的TSP问题都可以用一个图(Graph)来描述:
    令V={C1,C2,…,Ci,…,Cn},i=1,2,…,n是所有城市的集合,Ci表示第i个城市,n为城市的数目;
    E={(r,s):r,s∈V}是所有城市之间连接的集合;
    C={Crs:r,s∈V}是所有城市之间连接的成本度量(一般为城市之间的距离);
    如果Crs=Csr,那么该TSP问题为对称的,否则为非对称的。
    一个TSP问题可以表达为:
    求解遍历图G=(V,E,C),所有的节点一次并且回到起始节点,使得连接这些节点的路径成本最低。

    3.蚁群算法原理

    假如蚁群中所有蚂蚁的数量为m,所有城市之间的信息素用矩阵pheromone表示,最短路径为bestLength,最佳路径为bestTour。每只蚂蚁都有自己的内存,内存中用一个禁忌表(Tabu)来存储该蚂蚁已经访问过的城市,表示其在以后的搜索中将不能访问这些城市;还有用另外一个允许访问的城市表(Allowed)来存储它还可以访问的城市;另外还用一个矩阵(Delta)来存储它在一个循环(或者迭代)中给所经过的路径释放的信息素;还有另外一些数据,例如一些控制参数(α,β,ρ,Q),该蚂蚁行走完全程的总成本或距离(tourLength),等等。假定算法总共运行MAX_GEN次,运行时间为t。
    蚁群算法计算过程如下:
    (1)初始化
    设t=0,初始化bestLength为一个非常大的数(正无穷),bestTour为空。初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点。
    (2)为每只蚂蚁选择下一个节点。
    为每只蚂蚁选择下一个节点,该节点只能从Allowed中以某种概率(公式1)搜索到,每搜到一个,就将该节点加入到Tabu中,并且从Allowed中删除该节点。该过程重复n-1次,直到所有的城市都遍历过一次。遍历完所有节点后,将起始节点加入到Tabu中。此时Tabu表元素数量为n+1(n为城市数量),Allowed元素数量为0。接下来按照(公式2)计算每个蚂蚁的Delta矩阵值。最后计算最佳路径,比较每个蚂蚁的路径成本,然后和bestLength比较,若它的路径成本比bestLength小,则将该值赋予bestLength,并且将其Tabu赋予BestTour。
    这里写图片描述
    (公式1)
    这里写图片描述
    (公式2)
    这里写图片描述
    (公式3)

    其中pij(t)表示选择城市j的概率,k表示第k个蚂蚁,τij (t)表示城市i,j在第t时刻的信息素浓度,ηij表示从城市i到城市j的可见度,ηij=1/dij,dij表示城市i,j之间的成本(或距离)。由此可见dij越小,ηij越大,也就是从城市i到j的可见性就越大。
    Δτkij表示蚂蚁k在城市i与j之间留下的信息素。
    Lk表示蚂蚁k经过一个循环(或迭代)锁经过路径的总成本(或距离),即tourLength,α,β,Q 均为控制参数。
    (3)更新信息素矩阵
    令t=t+nt,按照(公式3)更新信息素矩阵phermone。
    这里写图片描述(公式4)

    τij(t+n)为t+n时刻城市i与j之间的信息素浓度。ρ为控制参数,Deltaij为城市i与j之间信息素经过一个迭代后的增量。并且有
    这里写图片描述(公式5)

    其中Δτkij由公式计算得到。
    (4)检查终止条件
    如果达到最大代数MAX_GEN,算法终止,转到第(5)步;否则,重新初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点,重复执行(2),(3),(4)步。
    (5)输出最优值

    4.算法流程图

    这里写图片描述

    5.java实现

    在该java实现中我们选择使用tsplib上的数据att48,这是一个对称tsp问题,城市规模为48,其最优值为10628.其距离计算方法如图(2)所示:
    这里写图片描述
    图2 att48距离计算方法

    实现中,使用了两个java类,一个Ant类,一个ACO类。
    Ant类

    package com.gbs.bean;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collection;
    import java.util.Collections;
    import java.util.Random;
    /**
     * 蚂蚁类
     * Cloneable这个类为克隆类,使用Object的clone()方法
     * @author gbs
     *
     */
    public class Ant implements Cloneable{
    
        /**
         * Vector与ArrayList一样,也是通过数组实现的,不同的是它支持线程的同步,
         * 即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,
         * 但实现同步需要很高的花费,因此,访问它比访问ArrayList慢。
         */
        private ArrayList<Integer> allowedCities;//允许访问的城市
    
        private ArrayList<Integer> tabu;//禁忌表,记录已经访问过的城市
    
        private int [][] distance;//距离矩阵
    
        private double[][] delta; //信息素变化矩阵
    
        private double alpha;
    
        private double beta;
    
        private int cityNum;//城市数量
    
        private int tourLength;//路径的长度
    
        private int firstCity; //起始城市
    
        private int currentCity; //当前城市
    
        public Ant(int cityNum) {
            this.cityNum = cityNum;
            this.tourLength = 0;
        }
    
        public Ant() {
            this.cityNum = 30;
            this.tourLength = 0;
        }
    
        /**
         * 初始化蚂蚁,并为蚂蚁随机选择第一个城市
         * @param distance
         * @param a
         * @param b
         */
        public void init(int[][] distance,double a,double b) {
            this.alpha = a;
            this.beta = b;
            this.distance = distance;
            this.allowedCities = new ArrayList<Integer>();
            this.tabu = new ArrayList<Integer>();
            this.delta = new double[cityNum][cityNum];
            for(int i = 0;i < this.cityNum;i++) {
                Integer city = new Integer(i);
                this.allowedCities.add(city);
                for (int j = 0;j < this.cityNum;j++) {
                    this.delta[i][j] = 0.d;
                }
            }
    
            Random random = new Random(System.currentTimeMillis());
            this.firstCity = random.nextInt(this.cityNum);
    
            for (Integer city:this.allowedCities) {
                if(city.intValue() == this.firstCity) {
                    this.allowedCities.remove(city);
                    this.tabu.add(city);
                    break;
                }
            }
    
            this.currentCity = this.firstCity;
        }
    
        /**
         * 选择下一个城市
         * @param pheromone 信息素矩阵
         */
        public void selectNextCity(double[][] pheromone) {
            double[] p = new double[this.cityNum];//转移概率
            double sum = 0.d;//转移概率的分母
            for (Integer city : this.allowedCities) {
                sum += Math.pow(pheromone[this.currentCity][city.intValue()],
                        this.alpha)*Math.pow(1.d/this.distance[this.currentCity][city.intValue()], this.beta);
            }
            for (int i = 0; i < this.cityNum; i++) {
                boolean flag = false;
                for (Integer city : this.allowedCities) {
                    if(i == city.intValue()) {
                         p[i] = (double) ((Math.pow(pheromone[this.currentCity][i], 
                                 this.alpha)*Math.pow(1.d/this.distance[this.currentCity][i], this.beta))/sum);
                         flag = true;
                         break;
                    }
                }
                if(!flag)
                    p[i] = 0.d;
            }
    
            /**
             * 如果每次都直接选择最大概率的城市作为下一个城市,就会使算法过早收敛,
             * 最后停止搜索可能获得的仅仅是次优解,而使用轮盘赌可以提高算法的全局搜索能力,又不失局部搜索
             * 所以这里选择轮盘赌选择下一个城市。参考《计算智能》清华大学出版社
             */
            //轮盘赌选择下一个城市
             double sumSelect = 0.d;
             int selectCity = -1;
             Random random = new Random(System.currentTimeMillis());
             double selectP = random.nextDouble();
             while(selectP == 0.f) {
                 selectP = random.nextDouble();
             }
             for(int i = 0;i < this.cityNum;i++) {
                 sumSelect += p[i];
                 if(sumSelect >= selectP) {
                     selectCity = i;
                    //从允许选择的城市中去除select city
                     this.allowedCities.remove(Integer.valueOf(selectCity));
                    //在禁忌表中添加select city
                     this.tabu.add(Integer.valueOf(selectCity));
                    //将当前城市改为选择的城市
                     this.currentCity = selectCity;
                     break;
                 }
             }
        }
    
        /**
         * 计算路径长度
         * @return
         */
        public int calculateTourLength() {
            int length = 0;
    
            for(int i = 0;i < this.tabu.size()-1;i++) {
                length += this.distance[this.tabu.get(i).intValue()][this.tabu.get(i+1).intValue()];
            }
            return length;
        }
    
        public ArrayList<Integer> getAllowedCities() {
            return allowedCities;
        }
    
        public void setAllowedCities(ArrayList<Integer> allowedCities) {
            this.allowedCities = allowedCities;
        }
    
        public ArrayList<Integer> getTabu() {
            return tabu;
        }
    
        public void setTabu(ArrayList<Integer> tabu) {
            this.tabu = tabu;
        }
    
        public int[][] getDistance() {
            return distance;
        }
    
        public void setDistance(int[][] distance) {
            this.distance = distance;
        }
    
        public double[][] getDelta() {
            return delta;
        }
    
        public void setDelta(double[][] delta) {
            this.delta = delta;
        }
    
        public double getAlpha() {
            return alpha;
        }
    
        public void setAlpha(double alpha) {
            this.alpha = alpha;
        }
    
        public double getBeta() {
            return beta;
        }
    
        public void setBeta(double beta) {
            this.beta = beta;
        }
    
        public int getCityNum() {
            return cityNum;
        }
    
        public void setCityNum(int cityNum) {
            this.cityNum = cityNum;
        }
    
        public int getTourLength() {
            return tourLength;
        }
    
        public void setTourLength(int tourLength) {
            this.tourLength = tourLength;
        }
    
        public int getFirstCity() {
            return firstCity;
        }
    
        public void setFirstCity(int firstCity) {
            this.firstCity = firstCity;
        }
    
        public int getCurrentCity() {
            return currentCity;
        }
    
        public void setCurrentCity(int currentCity) {
            this.currentCity = currentCity;
        }
    
        @Override
        public String toString() {
            return "Ant [allowedCities=" + allowedCities + ", tabu=" + tabu + ", distance=" + Arrays.toString(distance)
                    + ", delta=" + Arrays.toString(delta) + ", alpha=" + alpha + ", beta=" + beta + ", cityNum=" + cityNum
                    + ", tourLength=" + tourLength + ", firstCity=" + firstCity + ", currentCity=" + currentCity + "]";
        }
    
    }

    ACO类

    package com.gbs.bean;
    
    import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    
    /**
     * 蚁群算法类
     * @author gbs
     *
     */
    public class ACO {
    
        private Ant[] ants; //蚂蚁
        private int antNum; //蚂蚁数量
        private int cityNum; //城市数量
        private int MAX_GEN; //运行代数
        private double[][] pheromone; //信息素矩阵
        private int[][] distance; //距离矩阵
        private int bestLength; //最佳长度
        private int[] bestTour; //最佳路径
        //三个参数
        private double alpha;
        private double beta;
        private double rho;
    
        public ACO() {
    
        }
    
        public ACO(int antNum, int cityNum, int mAX_GEN, double alpha, double beta, double rho) {
            this.antNum = antNum;
            this.cityNum = cityNum;
            this.MAX_GEN = mAX_GEN;
            this.alpha = alpha;
            this.beta = beta;
            this.rho = rho;
            this.ants = new Ant[this.antNum];
        }
    
        public void init(String path) {
            int []x;
            int []y;
            String buffer;
            BufferedReader br;
            try {
                br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
                this.distance = new int[this.cityNum][this.cityNum];
                x = new int[cityNum];  
                y = new int[cityNum];  
                //读取城市的坐标
                for (int i = 0; i < cityNum; i++) {  
                    buffer = br.readLine();
                    String[] str = buffer.split(" ");  
                    x[i] = Integer.valueOf(str[1]);  
                    y[i] = Integer.valueOf(str[2]);  
                } 
                /**
                 * 计算距离矩阵 ,针对具体问题,距离计算方法也不一样,此处用的是att48作为案例,
                 * 它有48个城市,距离计算方法为伪欧氏距离,最优值为10628
                 */
                for(int i = 0;i < this.cityNum - 1;i++) {
                    for(int j = i + 1;j < this.cityNum;j++) {
                        double rij = Math.sqrt(((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]))/10.0);
                        int tij = (int)Math.round(rij);
                        if(tij < rij)
                            tij++;
                        this.distance[i][j] = tij;
                        this.distance[j][i] = tij;
                    }
                }
                this.distance[this.cityNum-1][this.cityNum-1] = 0;
                //初始化信息素矩阵
                this.pheromone=new double[this.cityNum][this.cityNum];
                for(int i = 0;i < this.cityNum;i++) {
                    for(int j = 0;j < this.cityNum;j++) {
                        this.pheromone[i][j] = 0.1d;
                    }
                }
                //初始化最优路径的长度
                this.bestLength=Integer.MAX_VALUE;
                //初始化最优路径
                this.bestTour=new int[this.cityNum+1];  
                //随机放置蚂蚁  
                for(int i = 0;i < this.antNum;i++){  
                    this.ants[i]=new Ant(this.cityNum);  
                    this.ants[i].init(this.distance, this.alpha, this.beta);  
                }  
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    
        /**
         * 更新信息素
         */
        private void updatePheromone() {
            //信息素挥发  
            for(int i = 0;i < this.cityNum;i++)  
                for(int j = 0;j < this.cityNum;j++)  
                    this.pheromone[i][j] = this.pheromone[i][j] * (1 - this.rho);
            //信息素更新
            for(int i = 0;i < this.cityNum;i++) {
                for(int j = 0;j < this.cityNum;j++) {
                    for(int k = 0;k < this.antNum;k++) {
                        this.pheromone[i][j] += this.ants[k].getDelta()[i][j];
                    }
                }
            }
        }
    
        public void solve() {
            for (int g = 0; g < this.MAX_GEN; g++) {
                //每一只蚂蚁移动的过程
                for (int i = 0; i < this.antNum; i++) {
                    for (int j = 0; j < this.cityNum; j++) {
                        this.ants[i].selectNextCity(this.pheromone);
                    }
                    this.ants[i].getTabu().add(this.ants[i].getFirstCity());
                    //计算蚂蚁获得的路径长度  
                    this.ants[i].setTourLength(this.ants[i].calculateTourLength());  
                    if(this.ants[i].getTourLength() < this.bestLength){  
                        //保留最优路径  
                        this.bestLength = this.ants[i].getTourLength();  
                        System.out.println("第"+g+"代,发现新的解"+this.bestLength); 
                        for(int k = 0;k < this.ants[i].getTabu().size();k++)  
                            this.bestTour[k] = this.ants[i].getTabu().get(k).intValue();;  
                    }
                    //更新信息素变化矩阵
                    for (int j = 0; j < this.ants[i].getTabu().size()-1; j++) {
                        this.ants[i].getDelta()[this.ants[i].getTabu().get(j).intValue()][this.ants[i].getTabu().get(j+1).intValue()] = (double) (1.0/this.ants[i].getTourLength());
                        this.ants[i].getDelta()[this.ants[i].getTabu().get(j+1).intValue()][this.ants[i].getTabu().get(j).intValue()] = (double) (1.0/this.ants[i].getTourLength());
                    }
                }
                //更新信息素
                this.updatePheromone();
                //重新初始化蚂蚁
                for(int i = 0;i < this.antNum;i++){  
                    this.ants[i].init(this.distance, this.alpha, this.beta);
                }
            }
            //打印最佳结果
            this.printOptimal();
        }
    
        public void printOptimal() {
             System.out.println("The optimal length is: " + this.bestLength);
             System.out.println("The optimal tour is: ");
             for (int i = 0; i < this.bestTour.length; i++) {
                 System.out.println(this.bestTour[i]);
             }
        }
    
        public Ant[] getAnts() {
            return ants;
        }
    
        public void setAnts(Ant[] ants) {
            this.ants = ants;
        }
    
        public int getAntNum() {
            return antNum;
        }
    
        public void setAntNum(int antNum) {
            this.antNum = antNum;
        }
    
        public int getCityNum() {
            return cityNum;
        }
    
        public void setCityNum(int cityNum) {
            this.cityNum = cityNum;
        }
    
        public int getMAX_GEN() {
            return MAX_GEN;
        }
    
        public void setMAX_GEN(int mAX_GEN) {
            MAX_GEN = mAX_GEN;
        }
    
        public double[][] getPheromone() {
            return pheromone;
        }
    
        public void setPheromone(double[][] pheromone) {
            this.pheromone = pheromone;
        }
    
        public int[][] getDistance() {
            return distance;
        }
    
        public void setDistance(int[][] distance) {
            this.distance = distance;
        }
    
        public int getBestLength() {
            return bestLength;
        }
    
        public void setBestLength(int bestLength) {
            this.bestLength = bestLength;
        }
    
        public int[] getBestTour() {
            return bestTour;
        }
    
        public void setBestTour(int[] bestTour) {
            this.bestTour = bestTour;
        }
    
        public double getAlpha() {
            return alpha;
        }
    
        public void setAlpha(double alpha) {
            this.alpha = alpha;
        }
    
        public double getBeta() {
            return beta;
        }
    
        public void setBeta(double beta) {
            this.beta = beta;
        }
    
        public double getRho() {
            return rho;
        }
    
        public void setRho(double rho) {
            this.rho = rho;
        }
    
        @Override
        public String toString() {
            return "ACO [ants=" + Arrays.toString(ants) + ", antNum=" + antNum + ", cityNum=" + cityNum + ", MAX_GEN="
                    + MAX_GEN + ", pheromone=" + Arrays.toString(pheromone) + ", distance=" + Arrays.toString(distance)
                    + ", bestLength=" + bestLength + ", bestTour=" + Arrays.toString(bestTour) + ", alpha=" + alpha
                    + ", beta=" + beta + ", rho=" + rho + "]";
        }
    
    }

    Test类:

    package com.gbs.test;
    
    import com.gbs.bean.ACO;
    
    public class Test {
        public static void main(String[] args) {
            ACO aco = new ACO(200, 48, 2000, 1.d, 5.d, 0.5d);
            aco.init("d://cities.txt");
            aco.solve();
        }
    }

    注:调试代码时遇到一个致命的问题就是忽略了float和double的精度。浪费了三四个小时debug居然是这个错误引起的,float的精度一旦不够,在java中会出现NAN和INFINITY。
    https://www.cnblogs.com/zhisuoyu/archive/2016/03/24/5314541.html(此网址讲述了NAN和INFINITY的区别)。

    6.存在问题

    (1)对于大规模组合优化问题,算法的计算时间而且复杂。由于蚁群算法的时间复杂度是,因此在处理较大规模的组合优化问题时,运算量较大,时间较长。
    (2)算法容易在某个或某些局部最优解的邻域附近发生停滞现象,造成早熟收敛,即搜索进行到一定程度后,所有蚂蚁发现的解完全一致,不能继续对解空间进一步搜索,不利于发现全局最优解。
    (3)不能较好的解决连续域问题。
    (4)由于蚁群算法中蚂蚁个体的运动过程的随机性,当群体规模设置较大时,很难在较短时间内从杂乱无章的路径中找出一条较好的路径。
    (5)信息素更新策略,路径搜索策略和最优解保留策略都带有经验性,没有经过严格的理论论证。因此基本蚁群算法的求解效率不高、收敛性较差、求解结果具有较大的分散性。

    附件:https://download.csdn.net/download/msc694955868/13123019

     

    展开全文
  • 蚁群算法总结

    千次阅读 2019-02-04 12:14:22
    蚁群算法简介 蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的方法。 蚁群算法是一种...

    蚁群算法简介

    蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的方法。
    蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。

    蚁群算法最早用来求解TSP问题,并且表现出了很大的优越性,因为它分布式特性,鲁棒性强并且容易与其它算法结合,但是同时也存在这收敛速度慢,容易陷入局部最优(local optimal)等缺点。

    蚂蚁寻找食物

    蚂蚁在行走过程中会释放一种称为“信息素”的物质,用来标识自己的行走路径。在寻找食物的过程中,根据信息素的浓度选择行走的方向,并最终到达食物所在的地方。

    信息素会随着时间的推移而逐渐挥发,所以在一开始的时候,由于地面上没有信息素,因此蚂蚁们的行走路径是随机的。蚂蚁们在行走的过程中会不断释放信息素,标识自己的行走路径。随着时间的推移,有若干只蚂蚁找到了食物,此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为轨迹是随机分布的,因此在单位时间内,短路径上的蚂蚁数量比长路径上的蚂蚁数量要多,从而蚂蚁留下的信息素浓度也就越高。这为后面的蚂蚁们提供了强有力的方向指引,越来越多的蚂蚁聚集到最短的路径上去。

    示意图

    优化问题与蚂蚁寻找食物的关系

    蚁群算法 自然界的蚂蚁
    可行解 蚂蚁行走的路径
    最优解 待寻找的最短路径
    解空间 所有可能的路径
    信息素矩阵 某条途径上的信息素浓度
    轮盘赌选择路径 根据信息素浓度来选择路径

    蚁群算法基本操作

    初始化参数

    蚁群算法所需要的参数:

    • 蚁群规模(蚂蚁数量)mm
    • 信息素重要程度因子 α\alpha
    • 启发函数重要程度因子 β\beta
    • 信息素挥发因子 ρ\rho
    • 信息素释放总量 QQ
    • 最大迭代次数 itermaxiter_{max}

    另外,设节点i与节点j之间的距离(权)为dij (i,j=1,2,...,n)d_{ij} \ (i,j=1,2,...,n)tt时刻节点i与节点j连接路径上的信息素浓度为τij(t)\tau_{ij}(t),在初始时刻各路径上信息素浓度相同,即τij(0)=τ0\tau_{ij}(0) = \tau_0

    构建解空间

    • 随机将蚂蚁置于所有出发点
    • 蚂蚁按规则访问所有节点
    • 计算每个蚂蚁经过的路径和长度,求出最优路径

    访问规则:蚂蚁k (k=1,2,...,m)k \ (k = 1,2,...,m)根据各个节点连接路径上的信息素浓度和路径距离(权)决定其下一个要访问的节点。t时刻蚂蚁k从节点i访问节点j的概率(蚂蚁已经在节点i)为:

    Pijk=[τij(t)]α[ηij(t)]βsallowk[τij(t)]α[ηij(t)]βsallowk P^k_{ij} = \frac{[\tau_{ij}(t)]^\alpha*[\eta_{ij}(t)]^\beta}{\sum_{s \in allow_k}[\tau_{ij}(t)]^\alpha*[\eta_{ij}(t)]^\beta} \qquad s \in allow_k
    其中ηij\eta_{ij}为启发函数,ηij=1dij\eta_{ij} = \frac{1}{d_{ij}},表示蚂蚁从节点i转移到节点j的期望程度;allowkallow_k表示蚂蚁k剩余待访问的节点集合。

    更新信息素

    蚂蚁访问完所有城市之后,进行信息素的更新。信息素的更新包括挥发和蚂蚁的产生,由以下公式决定:

    τij(t+1)=(1ρ)τij(t)+Δτij \tau_{ij}(t+1) = (1-\rho)\tau_{ij}(t)+\Delta\tau_{ij}

    前一部分是信息素的挥发,后一部分表示每只蚂蚁在这一段路上新差生的信息素。

    Δτij=k=1nΔτijk \Delta\tau_{ij} = \sum_{k=1}^n \Delta\tau_{ij}^k
    即对每只蚂蚁在该段路上释放信息素浓度之和。而对于蚂蚁k在i到j之间所释放的信息素Δτijk\Delta\tau_{ij}^k的计算,有三种不同的模型:

    • 蚁周模型:释放总量一定,利用路径整体信息计算:(LkL_k为第k只蚂蚁经过路径的总长)
      Δτijk=QLk \Delta\tau_{ij}^k = \frac{Q}{L_k}
    • 蚁量模型:释放总量一定,利用路径局部信息计算:
      Δτijk=Qdij \Delta\tau_{ij}^k = \frac{Q}{d_{ij}}
    • 蚁密模型:每段路释放量一定:
      Δτijk=Q \Delta\tau_{ij}^k = Q

    判断终止与迭代

    递增迭代次数计数器,如果达到了最大代数则输出,否则清空路径记录表继续迭代。

    代码实现

    代码使用蚁群算法计算中国TSP问题的最优解。

    % 使用蚁群算法解决旅行商(TSP)问题的优化
    % 中国31个省会城市的坐标数据保存在文件city_data.mat中
    
    %导入数据
    load city_data.mat
    
    %计算城市之间的相互距离矩阵
    n = size(city_data,1); %城市数目为n
    D = zeros(n,n); %距离矩阵为D
    for i = 1:n
        for j = 1:n
            if i ~= j
                D(i,j) = sqrt((city_data(i,1)-city_data(j,1))^2+(city_data(i,2)-city_data(j,2))^2);
            else
                D(i,j) = 1e-4; %为了不使启发函数变成inf
            end
        end
    end
    
    %初始化蚁群算法各个参数
    eta = 1./D; %启发函数
    m = 31; %蚂蚁个数31
    alpha = 1; %信息素重要程度因子
    beta = 5; %启发函数重要程度因子
    rho = 0.5; %信息素挥发因子
    Q = 1; %信息素释放总量
    iter_max = 400; %最大迭代次数
    iter = 0; %代数初值
    Table = zeros(m,n); %每只蚂蚁的路径记录表
    tau = ones(n,n); %各节点间路径上的信息素含量记录表(tau0 = 1)
    
    %开始迭代
    while 1
        
        %结束迭代的条件
        iter = iter + 1;
        if iter >= iter_max
            break
        end
        
        %清空路径记录表
        Table = zeros(m,n);
        
        %构建解空间
        city = 1:n;
        
        %随机将蚂蚁置于所有出发点
        start = floor(n*rand(m,1))+1;
        Table(:,1) = start;
        
        %逐个蚂蚁进行路径选择
        for i = 1:m
            %对于每个蚂蚁,逐个节点进行访问
            for j = 2:n
                %初始化以访问的节点(禁忌表)
                tabu = Table(i,1:(j-1));
                allow = city(~ismember(city,tabu));
                %计算节点间转移概率
                P = zeros(size(allow));
                for k = 1:length(allow)
                    P(k) = tau(tabu(end),allow(k))^alpha * eta(tabu(end),allow(k))^beta;
                end
                P = P/sum(P);
                %轮盘赌法选择下一个访问的城市
                P_sum = cumsum(P);
                target = allow(find(P_sum >= rand,1));
                Table(i,j) = target;
            end
        end
        
        %计算每个蚂蚁经过的路径
        Length = zeros(m,1);
        for i = 1:m
            Route = Table(i,:);
            for j = 1:(n-1)
                Length(i) = Length(i) + D(Route(j),Route(j+1));
            end
            Length(i) = Length(i) + D(Route(n),Route(1));
        end
        
        %更新信息素
        Delta_tau = zeros(n,n);
        for i = 1:m
            for j = 1:(n-1)
                Delta_tau(Table(i,j),Table(i,j+1)) = Delta_tau(Table(i,j),Table(i,j+1)) + Q/Length(i);
            end
            Delta_tau(Table(i,n),Table(i,1)) = Delta_tau(Table(i,n),Table(i,1)) + Q/Length(i);
        end
        tau = (1-rho)*tau + Delta_tau;
        
    end
    
    min(Length)
    

    代码输出结果为:

    output

    而中国TSP问题的最新研究结果为15377km,因此该算法寻求到的是一个局部最优解。

    展开全文
  • 针对蚁群算法收敛速度慢,容易陷入局部极值的缺点,提出将量子进化算法与蚁群算法相融合的新算法。在该算法中,蚂蚁当前位置用量子比特的两个概率幅表示,与普通蚁群算法相比,个体数量相等时,新算法的搜索空间将加倍,...
  • 蚁群算法是优化领域中新出现的一种仿生进化算法. 该算法采用分布式并行计算机制, 易与其他方法结合, 具有较强的鲁棒性; 但搜索时间长、易限入局部最解是其突出的缺点. 针对蚁群算法, 首先介绍其基本原理; ...
  • 针对PSO算法与蚁群算法优缺点, 提出一种融合 算法与蚁群算法的混合随机搜索算法。该算法充分利用PSO算法的快速、全局收敛性和蚁群算法的信息素正反馈机制,达到优势互补, 将这种优化方法拓展到求解连续空间问题, 并...
  • 概述 智能理论算法的优点是无需先验知识,不需要分析数据内部的规律和内在关联,只需要对数据本身进行学习,自组织、自适应的完成优化问题的求解,缺点是采用这种模型的收敛速度往往极慢,处理...粒子群算法 产生早熟

    概述

    算法本质

    优化算法是一种给定方向的遍历

    定义

    群体智能优化算法主要模拟了昆虫、兽群、鸟群和鱼群的群体行为,这些群体按照一种合作的方式寻找食物,群体中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索的方向。任何一种由昆虫群体或者其他动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群体智能(Swarm Intelligence)

    白话解释

    模仿昆虫或者一些动物的觅食或者其他行为,这些动物群体按照一中合作的方式寻找食物,不断的交流食物信息,能够很快的找到更多的食物。通过对他们的行为的研究抽象出来的一种算法,就是群体智能优化算法。(例如,一个个体找到了食物,就会通知其他个体来这个有食物的地方,这就是一种行为)

    算法原则

    1. 邻近原则:群体能够进行简单的空间和时间计算;
    2. 品质原则:群体能够响应环境中的品质因子;
    3. 多样性反应原则:群体的行动范围不应该太窄;
    4. 稳定性原则:群体不应在每次环境变化时都改变自身的行为;
    5. 适应性原则:在所需代价不太高的情况下,群体能够在适当的时候改变自身的行为。

    1、遗传算法(GA)

    全局搜索能力强,局部搜索能力较弱,往往只能得到次优解而不是最优解。

    研究发现,遗传算法可以用极快的速度达到最优解的90%以上,但是要达到真正的最优解需要花费很长时间,即局部搜索能力不足。

    2、粒子群算法(PSO)

    产生早熟收敛并被证明算法不是全局收敛
    未加权重——收敛速度快但容易陷入局部最优解

    3、 蚁群算法

    参数设置复杂,如果参数设置不当,容易偏离优质解

    4、 模拟退火算法

    全局寻优,适合搭配粒子群、鲸鱼优化算法等容易陷入局部最优解的

    5、 鱼群算法

    参数设置复杂,如果参数设置不当,容易偏离优质解.(同蚁群)

    6、鲸鱼优化算法

    6.1问题

    算法陷入局部极值和收敛速度问题
    陷入局部最优解
    结合模拟退火算法,通过接受较差点来提升全局寻优能力
    收敛速度慢
    引入自适应权重,提升算法的局部寻优能力

    展开全文
  • 这写都是一些关于蚁群算法和遗传算法的核心期刊论文,希望对这方面研究的人有所帮助!
  • 针对蚁群算法在求解大规模优化问题时存在的3个缺点:消耗时间长、蚂蚁在下次搜索时目标导向不强导致搜索随机性大、寻路径上的信息素过度增强导致得到假的最解。本文提出了基于边缘初始化和自适应全局信息素的...
  • * * 算法流程 * * 程序伪代码 For each particle Initialize particle End Do For each particle Calculate fitness value If the fitness value is better than the best fitness value (pbest) in history set ...
  • 提出了一种改进的蚁群算法,利用遗传算法加入了变异因子使最优路径产生变异,从而降低了蚁群算法陷入局部极小的可能性,同时改善了基本蚁群算法不收敛或收敛速度比较慢的缺点,加快了收敛速度,增加了最解的多样性...
  • 智能集群蚁群算法初见 第一次写CSDN博客,学习感受一下如何去编写自己的博客,也算作为激励自己学习的一种手段,慢慢的去积累这方面的一些能力。这里粗浅的学习了一下集群智能的简单概念,具体的详细原理代码后面...
  • 作者:莫石 ...来源:知乎 著作权归作者所有,转载请联系作者获得...基本思想都是模拟自然界生物群体行为来构造随机优化算法的,不同的是粒子群算法模拟鸟类群体行为,而蚁群算法模拟蚂蚁觅食原理。 1.相同点 (1)都是
  • 蚁群算法解决TSP问题

    2020-11-05 16:52:52
    蚁群算法简介 蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,859
精华内容 743
关键字:

蚁群算法的优缺点