【C#代码实战】群蚁算法理论与实践全攻略

 1 /// <summary>城市数量,N</summary>
 2 public Int32 NCity { get; set; }
 3 /// <summary>蚂蚁数量,M</summary>
 4 public Int32 AntCount { get; set; }
 5 /// <summary>信息启发式因子a,表征信息素重要程度的参数</summary>
 6 public Double Alpha { get; set; }
 7 /// <summary>期望启发式因子b,表征启发式因子重要程度的参数</summary>
 8 public Double Beta { get; set; }
 9 /// <summary>信息素蒸发的参数p</summary>
10 public Double Rho { get; set; }
11 /// <summary>距离数据，不一定是对称矩阵,D=d(ij)</summary>
12 public Double[,] Distance { get; set; }
13 /// <summary>最大迭代次数NC</summary>
14 public Int32 NcMax { get; set; }
15 /// <summary>最好的解个数，取最优解列表中个数的数目，可以作为备用方案</summary>
16 public Int32 BetterPlanCount { get; set; }
17 private List<Ant> planList;
18 /// <summary>信息素浓度</summary>
19 public double[,] InfoT { get; set; }

 1 /// <summary>构造函数</summary>
 2 /// <param name="m">蚂蚁数量</param>
 3 /// <param name="a">信息启发式因子</param>
 4 /// <param name="b">期望启发式因子</param>
 5 /// <param name="p">信息素蒸发的参数</param>
 6 /// <param name="distance">距离数据</param>
 7 /// <param name="NCMax">最大迭代次数</param>
 8 /// <param name="planCount">最优解的个数</param>
 9 public BaseTspAntSystem(double[,]distance,Int32 m,double a,double b,double p,int NCMax,int planCount=10)
10 {
11     this.AntCount= m;
12     this.Alpha= a;
13     this.Beta= b;
14     this.Rho= p;
15     this.Distance= distance;
16     this.NcMax= NCMax;
17     this.BetterPlanCount= planCount;
18     planList=new List<Ant>();
19     NCity=Distance.GetLength(0);//所有的城市个数
20     InfoT=new double[NCity, NCity];//初始化信息素矩阵
21 }

 1 public void TspSolution()
 2 {
 3     #region 初始化计算
 4     //计算初始信息素的值，可直接指定，或者贪婪算法计算
 5     double Cnn= GreedyAlgorithm();
 6     double t0=(double)AntCount / Cnn;//信息素初始化
 7     for (int i=0; i < NCity; i++)
 8     {
 9         for (int j=0; j < NCity; j++)
10         {
11             //每条可行的路径的信息素初始值
12             if (Distance[i, j] !=0) InfoT[i, j]= t0;
13         }
14     }
15     //为每个蚂蚁随机选择出发城市,List的长度为蚂蚁个数，内部List长度为路径    
16     List<Int32> allNodes=new List<int>();
17     for (int i=0; i < NCity; i++) allNodes.Add(i);//所有路径节点
18     //迭代次数
19     Int32 NC=0;
20     #endregion
21 
22     while (NC<NcMax)
23     {
24         //生成蚂蚁及初始访问城市，并设置对应禁忌表和路径列表
25         List<Ant> antList=new List<Ant>();
26         for (int i=0; i < AntCount; i++)
27             antList.Add(new Ant(i, allNodes.DeepCopy(), false));
28         //所有蚂蚁依次寻找下一个节点，直到本轮完成
29         antList.ForEach(n=> n.NextCityUntilFinished(InfoT,Distance,Alpha,Beta,Rho));               
30         //统计最优解
31         planList.AddRange(antList);//先添加
32         planList=planList.OrderBy(n=> n.CpathLength).ToList();//排序
33         //取出前面指定的几条最短路径
34         if (planList.Count > BetterPlanCount) 
35             planList.RemoveRange(BetterPlanCount, planList.Count - BetterPlanCount);
36         NC++;
37         //更新信息素的值：循环所有路径，依次进行添加
38         //先挥发
39         for (int i=0; i < NCity; i++) //挥发过程
40         {
41             for (int j=0; j < NCity; j++) InfoT[i, j] *=(1.0 - Rho);
42         }
43         //再增强,循环所有蚂蚁
44         foreach (var item in antList)
45         {
46             var temp=1.0 / item.CpathLength;
47             foreach (var edge in item.Edge) InfoT[edge.Key, edge.Value] += temp;    
48         }
49     }
50 }

 1 public class Ant
 2 {
 3     #region 属性
 4     /// <summary>蚂蚁编号</summary>
 5     public Int32 Id { get; set; }
 6     /// <summary>当前蚂蚁已经走过的路径节点列表，也就是禁忌表
 7     /// 最后1个就是当前所处的位置
 8     /// </summary>
 9     public List<Int32> PathNodes { get; set; }
10     /// <summary>当前蚂蚁下一步可供选择的节点列表</summary>
11     public List<Int32> selectNodes { get; set; }
12     /// <summary>该蚂蚁旅行的总长度</summary>
13     public Double CpathLength { get; set; }
14     /// <summary>当前蚂蚁走过的边，key为起点,value为终点</summary>
15     public Dictionary<int, int> Edge;
16     private Random rand;
17     int N;
18     #endregion
19 
20     #region 构造函数
21     /// <summary>构造函数</summary>
22     /// <param name="id">蚂蚁编号</param>
23     /// <param name="allNodes">所有节点名称列表</param>
24     /// <param name="isFixStart">是否固定起点</param>
25     public Ant(Int32 id,List<Int32> allNodes,Boolean isFixStart)
26     {
27         this.Id= id;
28         this.selectNodes= allNodes;
29         this.PathNodes=new List<int> ();
30         //isFixStart为false给蚂蚁随机1个起点，否则都为0
31         if (isFixStart)
32         {
33             this.PathNodes.Add(0);
34             this.selectNodes.RemoveAt(0);
35         }
36         else
37         {
38             var temp=new Random().Next(0, allNodes.Count - 1);
39             this.PathNodes.Add(temp);
40             this.selectNodes.RemoveAt(temp);
41         }
42         this.CpathLength=0;
43         rand=new Random();
44     }
45     #endregion
46 }

 1 #region 蚂蚁行为-依次按概率选择下一个城市，直到走完
 2 public void NextCityUntilFinished(double[,] info,double[,] distance,double a,double b,double p)
 3 {
 4     N=distance.GetLength(0);
 5     Edge=new Dictionary<int, int>();//经过的边：起点-终点
 6     //为空，就不需要计算了
 7     while(selectNodes.Count >0)
 8     {
 9         double sumt=0;//分母的和值
10         Int32 current= PathNodes.Last();
11         //依次计算当前点到其他点可选择点的 值
12         Dictionary<Int32, double> dic=new Dictionary<int, double>();
13         foreach (var item in selectNodes)
14         {
15             var temp=Math.Pow(info[current, item], a) * Math.Pow(1.0 / distance[current, item], b);
16             sumt += temp;
17             dic.Add(item, temp);
18         }
19         //计算各个点的概率
20         var ratio=dic.ToDictionary(n=> n.Key, n=> n.Value / sumt);
21         //产生1个随机数，并按概率确定下一个城市
22         Int32 nextCity= GetNextCityByRandValue(ratio, rand.NextDouble());
23         //修改列表
24         this.PathNodes.Add(nextCity);
25         this.selectNodes.Remove(nextCity);
26         this.CpathLength += distance[current, nextCity];
27         Edge.Add(current, nextCity);//信息素增强辅助计算
28     }
29     //最后1条路径的问题，额外增加，直接 回原点
30     this.CpathLength += distance[PathNodes.Last(), PathNodes.First()];
31     Edge.Add(PathNodes.Last(), PathNodes.First());
32     this.PathNodes.Add(PathNodes.First());//最后才添加           
33 }
34 
35 /// <summary>按照dic中按照顺序的节点的概率值，和随机数rnd的值，确定哪一个为下一个城市</summary>
36 /// <param name="dic"></param>
37 /// <param name="rnd"></param>
38 /// <returns></returns>
39 int GetNextCityByRandValue(Dictionary<Int32,double> dic,double rnd)
40 {
41     double sum=0;
42     foreach (var item in dic)
43     {
44         sum += item.Value;
45         if (rnd < sum) return item.Key;
46         else continue;
47     }
48     throw new Exception("无法选择城市");
49 }
50 #endregion