蚁群算法解决TSP旅行商问题 C# (转)

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Text;
 4  
 5 namespace ant_C
 6 {
 7     public static class Common
 8     {
 9        public static double ALPHA = 1.0; //启发因子，信息素的重要程度
10        public static double BETA = 2.0;   //期望因子，城市间距离的重要程度
11        public static double ROU = 0.5; //信息素残留参数
12  
13        public static int N_ANT_COUNT = 50; //蚂蚁数量
14        public static int N_IT_COUNT = 10000; //迭代次数
15        public static int N_CITY_COUNT = 51; //城市数量
16  
17        public static double DBQ = 100.0; //总的信息素
18        public static double DB_MAX = 10e9; //一个标志数，10的9次方
19  
20        public static double[,] g_Trial = new double[N_CITY_COUNT, N_CITY_COUNT]; //两两城市间信息素，就是环境信息素
21        public static double[,] g_Distance=new double[N_CITY_COUNT,N_CITY_COUNT]; //两两城市间距离
22  
23        //eil51.tsp城市坐标数据
24        public static double[]  x_Ary=new double[]
25        {
26       37,49,52,20,40,21,17,31,52,51,
27       42,31,5,12,36,52,27,17,13,57,
28       62,42,16,8,7,27,30,43,58,58,
29       37,38,46,61,62,63,32,45,59,5,
30       10,21,5,30,39,32,25,25,48,56,
31       30
32        };
33     
34        public static double[] y_Ary=new double[]
35        {
36           52,49,64,26,30,47,63,62,33,21,
37           41,32,25,42,16,41,23,33,13,58,
38           42,57,57,52,38,68,48,67,48,27,
39           69,46,10,33,63,69,22,35,15,6,
40           17,10,64,15,10,39,32,55,28,37,
41            40
42        };
43  
44        
45        static int RAND_MAX = 0x7fff; //随机数最大值
46  
47        static Random rand = new Random(System.DateTime.Now.Millisecond);
48  
49        ////返回指定范围内的随机整数
50        public static int rnd(int nLow, int nUpper)
51        {
52            return nLow + (nUpper - nLow) * rand.Next(RAND_MAX) / (RAND_MAX + 1);
53        }
54  
55        //返回指定范围内的随机浮点数
56        public static double rnd(double dbLow, double dbUpper)
57        {
58            double dbTemp = (double)rand.Next(RAND_MAX) / ((double)RAND_MAX + 1.0);
59            return dbLow + dbTemp * (dbUpper - dbLow);
60        }
61  
62        //返回浮点数四舍五入取整后的浮点数
63        public static double ROUND(double dbA)
64        {
65            return (double)((int)(dbA + 0.5));
66        }
67  
68     }
69 }

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Text;
  4  
  5 namespace ant_C
  6 {
  7     class CAnt
  8     {        
  9    public int[] m_nPath; //蚂蚁走的路径
 10        int[] m_nAllowedCity;//没去过的城市
 11        
 12    int m_nCurCityNo; //当前所在城市编号
 13    int m_nMovedCityCount; //已经去过的城市数量
 14        public double m_dbPathLength; //蚂蚁走过的路径长度
 15  
 16        public CAnt()
 17        {
 18           m_nPath=new int[Common.N_CITY_COUNT];
 19           m_nAllowedCity=new int[Common.N_CITY_COUNT]; //没去过的城市
 20        }
 21  
 22        //初始化函数，蚂蚁搜索前调用
 23        public void Init()
 24        {
 25  
 26            for (int i = 0; i < Common.N_CITY_COUNT; i++)
 27       {
 28       m_nAllowedCity[i]=1; //设置全部城市为没有去过
 29       m_nPath[i]=0; //蚂蚁走的路径全部设置为0
 30       }
 31  
 32       //蚂蚁走过的路径长度设置为0
 33       m_dbPathLength=0.0; 
 34  
 35       //随机选择一个出发城市
 36           m_nCurCityNo = Common.rnd(0, Common.N_CITY_COUNT);
 37  
 38       //把出发城市保存入路径数组中
 39       m_nPath[0]=m_nCurCityNo;
 40  
 41       //标识出发城市为已经去过了
 42       m_nAllowedCity[m_nCurCityNo]=0; 
 43  
 44       //已经去过的城市数量设置为1
 45       m_nMovedCityCount=1; 
 46  
 47        }
 48  
 49        //选择下一个城市
 50        //返回值 为城市编号
 51        public int ChooseNextCity()
 52        {
 53       int nSelectedCity=-1; //返回结果，先暂时把其设置为-1
 54  
 55       //==============================================================================
 56       //计算当前城市和没去过的城市之间的信息素总和
 57       
 58       double dbTotal=0.0;
 59       double[] prob=new double[Common.N_CITY_COUNT]; //保存各个城市被选中的概率
 60  
 61       for (int i=0;i
 62       {
 63       if (m_nAllowedCity[i] == 1) //城市没去过
 64       {
 65                  prob[i] = System.Math.Pow(Common.g_Trial[m_nCurCityNo,i], Common.ALPHA) * System.Math.Pow(1.0 / Common.g_Distance[m_nCurCityNo,i], Common.BETA); //该城市和当前城市间的信息素
 66       dbTotal=dbTotal+prob[i]; //累加信息素，得到总和
 67       }
 68       else //如果城市去过了，则其被选中的概率值为0
 69       {
 70       prob[i]=0.0;
 71       }
 72       }
 73  
 74       //==============================================================================
 75       //进行轮盘选择
 76       double dbTemp=0.0;
 77       if (dbTotal > 0.0) //总的信息素值大于0
 78       {
 79       dbTemp=Common.rnd(0.0,dbTotal); //取一个随机数
 80  
 81       for (int i=0;i
 82       {
 83       if (m_nAllowedCity[i] == 1) //城市没去过
 84       {
 85       dbTemp=dbTemp-prob[i]; //这个操作相当于转动轮盘，如果对轮盘选择不熟悉，仔细考虑一下
 86       if (dbTemp < 0.0) //轮盘停止转动，记下城市编号，直接跳出循环
 87       {
 88       nSelectedCity=i;
 89       break;
 90       }
 91       }
 92       }
 93       }
 94  
 95       //==============================================================================
 96       //如果城市间的信息素非常小 ( 小到比double能够表示的最小的数字还要小 )
 97       //那么由于浮点运算的误差原因，上面计算的概率总和可能为0
 98       //会出现经过上述操作，没有城市被选择出来
 99       //出现这种情况，就把第一个没去过的城市作为返回结果
100       
101       //题外话：刚开始看的时候，下面这段代码困惑了我很长时间，想不通为何要有这段代码，后来才搞清楚。
102       if (nSelectedCity == -1)
103       {
104               for (int i = 0; i < Common.N_CITY_COUNT; i++)
105       {
106       if (m_nAllowedCity[i] == 1) //城市没去过
107       {
108       nSelectedCity=i;
109       break;
110       }
111       }
112       }
113  
114       //==============================================================================
115       //返回结果，就是城市的编号
116       return nSelectedCity;
117        }
118  
119        //蚂蚁在城市间移动
120        public void Move()
121        {
122       int nCityNo=ChooseNextCity(); //选择下一个城市
123  
124       m_nPath[m_nMovedCityCount]=nCityNo; //保存蚂蚁走的路径
125       m_nAllowedCity[nCityNo]=0;//把这个城市设置成已经去过了
126       m_nCurCityNo=nCityNo; //改变当前所在城市为选择的城市
127       m_nMovedCityCount++; //已经去过的城市数量加1
128        }
129  
130        //计算蚂蚁走过的路径长度
131        public void CalPathLength()
132        {
133  
134       m_dbPathLength=0.0; //先把路径长度置0
135       int m=0;
136       int n=0;
137  
138       for (int i=1;i
139       {
140       m=m_nPath[i];
141       n=m_nPath[i-1];
142       m_dbPathLength=m_dbPathLength+Common.g_Distance[m,n];
143       }
144  
145       //加上从最后城市返回出发城市的距离
146       n=m_nPath[0];
147           m_dbPathLength = m_dbPathLength + Common.g_Distance[m,n];
148  
149        }
150  
151  
152        //蚂蚁进行搜索一次
153        public void Search()
154        {
155       Init(); //蚂蚁搜索前，先初始化
156  
157       //如果蚂蚁去过的城市数量小于城市数量，就继续移动
158       while (m_nMovedCityCount < Common.N_CITY_COUNT)
159       {
160       Move();
161       }
162  
163       //完成搜索后计算走过的路径长度
164       CalPathLength();
165        }
166  
167  
168     }
169 }

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Text;
  4  
  5 namespace ant_C
  6 {
  7     class CTsp
  8     {
  9        CAnt []m_cAntAry; //蚂蚁数组
 10        public CAnt m_cBestAnt; //定义一个蚂蚁变量，用来保存搜索过程中的最优结果
 11                              //该蚂蚁不参与搜索，只是用来保存最优结果
 12  
 13        public CTsp()
 14        {
 15           m_cAntAry=new CAnt[Common.N_ANT_COUNT];
 16            for (int i = 0; i < Common.N_ANT_COUNT; i++)
 17            {
 18               m_cAntAry[i] = new CAnt();
 19            }
 20           m_cBestAnt=new CAnt();
 21        }
 22  
 23        //初始化数据
 24        public void InitData()
 25        {
 26  
 27           //先把最优蚂蚁的路径长度设置成一个很大的值
 28           m_cBestAnt.m_dbPathLength = Common.DB_MAX;
 29  
 30           //计算两两城市间距离
 31            double dbTemp = 0.0;
 32            for (int i = 0; i < Common.N_CITY_COUNT; i++)
 33            {
 34               for (int j = 0; j < Common.N_CITY_COUNT; j++)
 35               {
 36                  dbTemp = (Common.x_Ary[i] - Common.x_Ary[j]) * (Common.x_Ary[i] - Common.x_Ary[j]) + (Common.y_Ary[i] - Common.y_Ary[j]) * (Common.y_Ary[i] - Common.y_Ary[j]);
 37                  dbTemp = System.Math.Pow(dbTemp, 0.5);
 38                  Common.g_Distance[i,j] = Common.ROUND(dbTemp);
 39               }
 40            }
 41  
 42           //初始化环境信息素，先把城市间的信息素设置成一样
 43           //这里设置成1.0，设置成多少对结果影响不是太大，对算法收敛速度有些影响
 44            for (int i = 0; i < Common.N_CITY_COUNT; i++)
 45            {
 46               for (int j = 0; j < Common.N_CITY_COUNT; j++)
 47               {
 48                  Common.g_Trial[i,j] = 1.0;
 49               }
 50            }
 51        
 52        }
 53  
 54  
 55        //更新环境信息素
 56        public void UpdateTrial()
 57        {
 58       //临时数组，保存各只蚂蚁在两两城市间新留下的信息素
 59            double[,] dbTempAry = new double[Common.N_CITY_COUNT, Common.N_CITY_COUNT];
 60  
 61           //先全部设置为0
 62            for (int i = 0; i < Common.N_ANT_COUNT; i++) //计算每只蚂蚁留下的信息素
 63            {
 64               for (int j = 1; j < Common.N_CITY_COUNT; j++)
 65               {
 66                  dbTempAry[i, j] = 0.0;
 67               }
 68            }
 69  
 70  
 71       //计算新增加的信息素,保存到临时数组里
 72       int m=0;
 73       int n=0;
 74            for (int i = 0; i < Common.N_ANT_COUNT; i++) //计算每只蚂蚁留下的信息素
 75       {
 76               for (int j = 1; j < Common.N_CITY_COUNT; j++)
 77       {
 78       m=m_cAntAry[i].m_nPath[j];
 79       n=m_cAntAry[i].m_nPath[j-1];
 80                     dbTempAry[n, m] = dbTempAry[n, m] + Common.DBQ / m_cAntAry[i].m_dbPathLength;
 81       dbTempAry[m,n]=dbTempAry[n,m];
 82       }
 83  
 84       //最后城市和开始城市之间的信息素
 85       n=m_cAntAry[i].m_nPath[0];
 86                  dbTempAry[n, m] = dbTempAry[n, m] + Common.DBQ / m_cAntAry[i].m_dbPathLength;
 87       dbTempAry[m,n]=dbTempAry[n,m];
 88  
 89       }
 90  
 91       //==================================================================
 92       //更新环境信息素
 93            for (int i = 0; i < Common.N_CITY_COUNT; i++)
 94       {
 95               for (int j = 0; j < Common.N_CITY_COUNT; j++)
 96       {
 97                  Common.g_Trial[i,j] = Common.g_Trial[i,j] * Common.ROU + dbTempAry[i,j];  //最新的环境信息素 = 留存的信息素 + 新留下的信息素
 98       }
 99       }
100  
101        }
102  
103  
104        //开始搜索
105        public void Search()
106        {
107  
108       //char cBuf[256]; //打印信息用
109            string strInfo="";
110           
111            bool blFlag = false;
112  
113       //在迭代次数内进行循环
114       for (int i=0;i
115       {
116               blFlag = false;
117  
118       //每只蚂蚁搜索一遍
119               for (int j = 0; j < Common.N_ANT_COUNT; j++)
120       {
121       m_cAntAry[j].Search(); 
122       }
123  
124       //保存最佳结果
125               for (int j = 0; j < Common.N_ANT_COUNT; j++)
126       {
127       if (m_cAntAry[j].m_dbPathLength < m_cBestAnt.m_dbPathLength)
128       {       
129                     m_cBestAnt.m_dbPathLength=m_cAntAry[j].m_dbPathLength;
130                     m_cBestAnt.m_nPath = m_cAntAry[j].m_nPath;
131  
132                      blFlag = true;
133  
134                  }
135       }
136  
137       //更新环境信息素
138       UpdateTrial();
139  
140       //输出目前为止找到的最优路径的长度
141               if (blFlag == true)
142               {
143                  strInfo = String.Format("[{0}] {1}", i + 1, m_cBestAnt.m_dbPathLength);
144                  Console.WriteLine(strInfo);
145               }
146  
147  
148       }
149  
150        }
151  
152  
153  
154     }
155 }