基于C#的蚁群算法实现
programming homework
Lastmod: 2019-05-31

这学期有门课,最优化与最优控制,任课老师任华玲,虽然在课堂上我什么都没有学到,但是最后任老师让每个人自己选一篇最优化方向的论文,把其中的算法和算例自己实现一下,并讲解。本科时祝凌曦让我研究过蚁群算法,当时没太弄懂,趁这个机会研究了下,弄懂了并用C#实现出来,效果还不错。以下是代码。

代码主要分为三块:Ant.cs,Tsp.cs和DataAndCal.cs,分别为蚂蚁类,tsp类和静态数据储存计算类。

首先是蚂蚁类:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AntColonyOptimization
{
    public class Ant
    {
        public int[] DoneCity;//去过的城市,值是依次经过的城市的编号
        public int DoneCityCount;//去过的城市数量
        public int[] IngCity; //没去过的城市,序号是城市自带的,这里面的值代表是否去过,1去过,0没有去过
        public int NowCityNo; //当前城市编号
        public double LineLength; //路径总长

        // 新建一个蚂蚁,用于储存最优值
        public Ant()
        {
            IngCity = new int[DataAndCal.CityNum];
            DoneCity = new int[DataAndCal.CityNum];
        }

        /// <summary>
        /// 一只蚂蚁完成一次旅行
        /// </summary>
        public void Travel()
        {
            //1. 初始化//2. 选择一个初始城市
            AntInit();

            while (DoneCityCount < DataAndCal.CityNum)
            {
                //3. 选择下一个城市            
                int nextCityNo = SelectNextCity();

                //4. 移动过去,更新数据
                Move(nextCityNo);

            }
            //5. 移动完成后,计算路径总长
            LineLength = 0.0;
            for (int i = 0; i < DataAndCal.CityNum - 1; i++)
            {
                LineLength = LineLength + DataAndCal.DistenceBetween2City(DoneCity[i], DoneCity[i + 1]);
            }
            LineLength = LineLength + DataAndCal.DistenceBetween2City(DoneCity[0], DoneCity[DataAndCal.CityNum - 1]);
        }

        /// <summary>
        /// 蚂蚁初始化
        /// </summary>
        public void AntInit()
        {
            for (int i = 0; i < DataAndCal.CityNum; i++)
            {
                DoneCity[i] = 0;
                IngCity[i] = 0;
            }
            NowCityNo = 0;
            LineLength = 0.0;

            //随机选择一个城市出发并记录
            NowCityNo = DataAndCal.RandInt(1, 51);
            DoneCity[0] = NowCityNo;
            DoneCityCount = 1;
            IngCity[NowCityNo] = 1;
        }
        public int SelectNextCity()
        {
            int SelectNo = 0; //初始化要选择的城市的编号
            double info = 0.0; //统计信息素的总和
            double[] Pos = new double[DataAndCal.CityNum]; //去每个城市的概率

            // 计算去每个城市的概率
            for (int i = 0; i < DataAndCal.CityNum; i++)
            {
                if (IngCity[i] == 0) //没去过该城市
                {
                    Pos[i] = (Math.Pow(DataAndCal.InfoBetwCity[NowCityNo, i], DataAndCal.alpha)) / (Math.Pow(DataAndCal.DistenceBetween2City(NowCityNo, i), DataAndCal.beta));
                    info += Pos[i];
                }
                else
                {
                    Pos[i] = 0.0;
                }
            }

            // 按概率进行选择
            double randInfo = DataAndCal.RandDouble(0, info);
            for (int i = 0; i < DataAndCal.CityNum; i++)
            {
                if (randInfo - Pos[i] > 0)
                {
                    randInfo = randInfo - Pos[i];
                }
                else
                {
                    SelectNo = i;
                    break;
                }
            }

            //如果没有通过计算得到合适的结果,那么直接指定序号中第一个没有去过的城市作为下一个城市
            if (SelectNo == 0)
            {
                for (int i = 0; i < DataAndCal.CityNum; i++)
                {
                    if (IngCity[i] == 0)
                    {
                        SelectNo = i;
                        break;
                    }
                }

            }
            return SelectNo;
        }

        public void Move(int nextCityNo)
        {
            //下一个城市添加到已经途经的路径数组
            DoneCity[DoneCityCount] = nextCityNo;
            //该城市标记为已经去过
            IngCity[nextCityNo] = 1;
            //增加路径总长
            LineLength = LineLength + DataAndCal.DistenceBetween2City(NowCityNo, nextCityNo);
            //移动到下一城市,把下一城市成为当前城市
            NowCityNo = nextCityNo;
            DoneCityCount++;
        }
    }
}

注释都写得比较清楚,就不再解释了,毕竟就是用蚁群算法实现了一个最简单的Tsp问题求解。下面是Tsp类:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AntColonyOptimization
{
    public class Tsp
    {
        public Ant[] Ants;
        public Ant bestAnt;
        public List<Ant> bestAntList;

        public Tsp()
        {
            Ants = new Ant[DataAndCal.AntNum];
            for (int i = 0; i < DataAndCal.AntNum; i++)
            {
                Ants[i] = new Ant();
            }
            bestAnt = new Ant();
            //bestAntList = new List<Ant>();
        }

        // 初始化全部环境
        public void InitEnvironment()
        {
            //最优值先设定为BigNum
            bestAnt.LineLength = DataAndCal.BigNum;

            // 初始化环境信息素
            for (int i = 0; i < DataAndCal.CityNum; i++)
            {
                for (int j = 0; j < DataAndCal.CityNum; j++)
                {
                    DataAndCal.InfoBetwCity[i, j] = 1.0;
                }
            }
        }

        //更新信息素
        public void UpdateInfo()
        {
            double[,] AntInfo = new double[DataAndCal.CityNum, DataAndCal.CityNum];

            //计算妹纸蚂蚁留下的信息素, 先全部清零
            for (int i = 0; i < DataAndCal.CityNum; i++)
            {
                for (int j = 0; j < DataAndCal.CityNum; j++)
                {
                    AntInfo[i, j] = 0;
                }
            }

            //新增的信息素
            for (int i = 0; i < DataAndCal.AntNum; i++)
            {
                for (int j = 0; j < DataAndCal.CityNum - 1; j++)
                {
                    // 第i只蚂蚁,在经过的第j和j+1个城市间留下的信息素,是总信息素/第i只蚂蚁走过的路径总长,并加第i只蚂蚁的信息素叠加到j和j+1个城市上去。
                    AntInfo[Ants[i].DoneCity[j], Ants[i].DoneCity[j + 1]] = AntInfo[Ants[i].DoneCity[j], Ants[i].DoneCity[j + 1]] + DataAndCal.TotalInfo / Ants[i].LineLength;
                    AntInfo[Ants[i].DoneCity[j + 1], Ants[i].DoneCity[j]] = AntInfo[Ants[i].DoneCity[j], Ants[i].DoneCity[j + 1]];
                }

                //最后一个城市和第一个城市
                AntInfo[Ants[i].DoneCity[0], Ants[i].DoneCity[DataAndCal.CityNum - 1]] = AntInfo[Ants[i].DoneCity[0], Ants[i].DoneCity[DataAndCal.CityNum - 1]] + DataAndCal.TotalInfo / Ants[i].LineLength;
                AntInfo[Ants[i].DoneCity[DataAndCal.CityNum - 1], Ants[i].DoneCity[0]] = AntInfo[Ants[i].DoneCity[0], Ants[i].DoneCity[DataAndCal.CityNum - 1]];
            }

            //更新信息素,原始值*挥发+新增值
            for (int i = 0; i < DataAndCal.CityNum; i++)
            {
                for (int j = 0; j < DataAndCal.CityNum; j++)
                {
                    DataAndCal.InfoBetwCity[i, j] = DataAndCal.InfoBetwCity[i, j] * (1 - DataAndCal.rou) + AntInfo[i, j];
                }
            }


        }

        // 全部搜索一遍
        public void Search()
        {
            //迭代次数内循环
            bestAntList = new List<Ant>();
            for (int i = 0; i < DataAndCal.IterateTime; i++)
            {
                //每只蚂蚁都搜索
                for (int j = 0; j < DataAndCal.AntNum; j++)
                {
                    Ants[j].Travel();

                    if (Ants[j].LineLength < bestAnt.LineLength)
                    {
                        bestAnt.LineLength = Ants[j].LineLength;
                        bestAnt.DoneCity = Ants[j].DoneCity;
                        Ant tmp = new Ant();
                        tmp.LineLength = Ants[j].LineLength;
                        tmp.DoneCity = Ants[j].DoneCity;
                        bestAntList.Add(tmp);
                    }
                }
                //更新信息素
                //UpdateInfo();

            }
        }
    }
}

接下来是静态数据储存计算类:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace AntColonyOptimization
{
    public static class DataAndCal
    {
        public static double alpha = 1.0; //信息素重要程度
        public static double beta = 2.0; //城市间距离重要程度
        public static double rou = 0.5; //信息残留程度

        public static int AntNum = 34; //蚂蚁数量
        public static int IterateTime = 1000; //迭代次数

        public static int CityNum = 51; //城市数量
        public static double TotalInfo = 100.0; //总信息素

        public static double[,] InfoBetwCity = new double[CityNum, CityNum]; //两城市间信息素
        public static double[,] DistBetwCity = new double[CityNum, CityNum]; //两城市间距离

        // 城市坐标,用x,y分别表示
        public static double[] xCity = new double[]
        {
	        37,49,52,20,40,21,17,31,52,51,
	        42,31,5,12,36,52,27,17,13,57,
	        62,42,16,8,7,27,30,43,58,58,
	        37,38,46,61,62,63,32,45,59,5,
	        10,21,5,30,39,32,25,25,48,56,
	        30
        };

        public static double[] yCity = new double[]
        {
            52,49,64,26,30,47,63,62,33,21,
            41,32,25,42,16,41,23,33,13,58,
            42,57,57,52,38,68,48,67,48,27,
            69,46,10,33,63,69,22,35,15,6,
            17,10,64,15,10,39,32,55,28,37,
            40
        };

        /// <summary>
        /// 两城市间距离
        /// </summary>
        /// <param name="City1No">第一个城市的序号</param>
        /// <param name="City2No">第二个城市序号</param>
        /// <returns></returns>
        public static double DistenceBetween2City(int City1No, int City2No)
        {
            double x1x2 = Math.Pow((xCity[City1No] - xCity[City2No]), 2);
            double y1y2 = Math.Pow((yCity[City1No] - yCity[City2No]), 2);
            double dis = Math.Pow((x1x2+y1y2),0.5);
            return dis;
        }


        public static Random ran = new Random(System.DateTime.Now.Millisecond);
        public static int BigNum = 65535;
        /// <summary>
        /// 产生一个随机整数,区间是n1,n2
        /// </summary>
        /// <param name="n1"></param>
        /// <param name="n2"></param>
        /// <returns></returns>
        public static int RandInt(int n1, int n2)
        {

            int n = n1 + (n2 - n1) * ran.Next(BigNum) / BigNum;
            return n;
        }

        public static double RandDouble(double n1,double n2)
        {
            double n = n1 + (n2 - n1) * ran.Next(BigNum) / BigNum;
            return n;
        }
    }
}

最后是用C#基于WinForm开发了个窗口进行展示,AntCoOp.cs:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace AntColonyOptimization
{
    public partial class AntCoOp : Form
    {
        public AntCoOp()
        {
            InitializeComponent();
            InitData();

        }


        public static Tsp Calculate()
        {

            Tsp tspant = new Tsp();
            tspant.InitEnvironment();
            tspant.Search();

            return tspant;
        }

        #region
        Tsp tsp = Calculate();

        bool DrawLine = false;
        Ant OneBestAnt = new Ant();
        Pen DotPen = new Pen(Color.Blue, 3);
        Pen LinePen = new Pen(Color.Red, 1);
        double xMax = 0.0;
        double yMax = 0.0;
        double xMin = DataAndCal.BigNum;
        double yMin = DataAndCal.BigNum;

        double[] xxCity = new double[DataAndCal.CityNum];
        double[] yyCity = new double[DataAndCal.CityNum];

        int nextBtni = 0;
        private void InitData()
        {
            //找出城市坐标最大值
            for (int i = 0; i < DataAndCal.CityNum; i++)
            {
                if (DataAndCal.xCity[i] > xMax)
                {
                    xMax = DataAndCal.xCity[i];
                }
                if (DataAndCal.yCity[i] > yMax)
                {
                    yMax = DataAndCal.yCity[i];
                }
                if (DataAndCal.xCity[i] < xMin)
                {
                    xMin = DataAndCal.xCity[i];
                }
                if (DataAndCal.yCity[i] < yMin)
                {
                    yMin = DataAndCal.yCity[i];
                }
            }

            xMax = xMax + 10;
            yMax = yMax + 10;
            //xMin = 0.0;
            //yMin = 0.0;
            //画出所有点,按比例
            for (int i = 0; i < DataAndCal.CityNum; i++)
            {
                xxCity[i] = (DataAndCal.xCity[i] - xMin) / (xMax - xMin) * PaintPanel.Width + xMin;
                yyCity[i] = (DataAndCal.yCity[i] - yMin) / (yMax - yMin) * PaintPanel.Height + yMin;

            }
        }

        #endregion


        private void PaintPanel_Paint(object sender, PaintEventArgs e)
        {

            Graphics g = e.Graphics;

            for (int i = 0; i < DataAndCal.CityNum; i++)
            {
                g.DrawEllipse(DotPen, (int)xxCity[i], (int)yyCity[i], 2, 2);
            }

            if (DrawLine)
            {
                for (int i = 0; i < OneBestAnt.DoneCity.Count() - 1; i++)
                {
                    g.DrawLine(LinePen, new PointF((float)xxCity[OneBestAnt.DoneCity[i]], (float)yyCity[OneBestAnt.DoneCity[i]]), new PointF((float)xxCity[OneBestAnt.DoneCity[i + 1]], (float)yyCity[OneBestAnt.DoneCity[i + 1]]));

                }
                g.DrawLine(LinePen, new PointF((float)xxCity[OneBestAnt.DoneCity[0]], (float)yyCity[OneBestAnt.DoneCity[0]]), new PointF((float)xxCity[OneBestAnt.DoneCity[DataAndCal.CityNum - 1]], (float)yyCity[OneBestAnt.DoneCity[DataAndCal.CityNum - 1]]));

                string strInfo1 = String.Format("当前值:{0},最优值:{1} ", (int)OneBestAnt.LineLength, (int)tsp.bestAntList.Last().LineLength);
                string strInfo2 = String.Format("共有{0}个迭代值,第{1}个 ", tsp.bestAntList.Count(), nextBtni);
                Brush strBru = new SolidBrush(Color.Black);
                Font strFont = new Font("微软雅黑", 14);
                g.DrawString(strInfo1, strFont, strBru, new PointF(20, (float)PaintPanel.Height - 60));
                g.DrawString(strInfo2, strFont, strBru, new PointF(20, (float)PaintPanel.Height - 35));
            }
            DrawLine = false;
        }

        private void PaintPanel_SizeChanged(object sender, EventArgs e)
        {
            Refresh();
        }

        private void RefreshBtn_Click(object sender, EventArgs e)
        {
            tsp = Calculate();
            nextBtni = 0;
            //Refresh();
            //PaintPanel.Paint();
        }

        private void NextBtn_Click(object sender, EventArgs e)
        {
            if (nextBtni < tsp.bestAntList.Count())
            {
                OneBestAnt = tsp.bestAntList[nextBtni];
                DrawLine = true;
                nextBtni++;
                Refresh();
            }

        }

        private void FinalBtn_Click(object sender, EventArgs e)
        {
            OneBestAnt = tsp.bestAntList.Last();
            DrawLine = true;
            nextBtni = tsp.bestAntList.Count();

            Refresh();
        }

        private void ReturnBtn_Click(object sender, EventArgs e)
        {
            OneBestAnt = tsp.bestAntList.First();
            DrawLine = true;
            nextBtni = 1;
            Refresh();
        }
    }
}

运行截图就不再给了,也不是什么很好看的图

以前从来被人碾压习惯了突然变成这样其实也挺不习惯的,要多和更强的人比比才行,不然没有进步的,我可不是混个硕士毕业证就志得意满去工作的人。