旅行商问题 最短路径算法源码下载(群蚁)

【核心代码】

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AcaSolution
{
    /// <summary>
    /// 信息素增强过程：蚂蚁一轮完成后，进行更新，只更新路径长度相关的，和挥发无关
    /// </summary>
    public class BaseTspAntSystem
    {
        #region 属性
        /// <summary>城市数量,N</summary>
        public Int32 NCity { get; set; }
        /// <summary>蚂蚁数量,M</summary>
        public Int32 AntCount { get; set; }
        /// <summary>信息启发式因子a,表征信息素重要程度的参数</summary>
        public Double Alpha { get; set; }
        /// <summary>期望启发式因子b,表征启发式因子重要程度的参数</summary>
        public Double Beta { get; set; }
        /// <summary>信息素蒸发的参数p</summary>
        public Double Rho { get; set; }
        /// <summary>距离数据，不一定是对称矩阵,D=d(ij)</summary>
        public Double[,] Distance { get; set; }
        /// <summary>最大迭代次数NC</summary>
        public Int32 NcMax { get; set; }
        /// <summary>最好的解个数，取最优解列表中个数的数目，可以作为备用方案</summary>
        public Int32 BetterPlanCount { get; set; }
        private List<Ant> planList;
        /// <summary>信息素浓度</summary>
        public double[,] InfoT { get; set; }
        #endregion

        #region 构造函数
        /// <summary>构造函数</summary>
        /// <param name="m">蚂蚁数量</param>
        /// <param name="a">信息启发式因子</param>
        /// <param name="b">期望启发式因子</param>
        /// <param name="p">信息素蒸发的参数</param>
        /// <param name="distance">距离数据</param>
        /// <param name="NCMax">最大迭代次数</param>
        /// <param name="planCount">最优解的个数</param>
        public BaseTspAntSystem(double[,]distance,Int32 m,double a,double b,double p,int NCMax,int planCount=10)
        {
            this.AntCount = m;
            this.Alpha = a;
            this.Beta = b;
            this.Rho = p;
            this.Distance = distance;
            this.NcMax = NCMax;
            this.BetterPlanCount = planCount;
            planList = new List<Ant>();
            NCity = Distance.GetLength(0);//所有的城市个数
            InfoT = new double[NCity, NCity];//初始化信息素矩阵
        }
        #endregion

        #region 核心求解算法
        public void TspSolution()
        {
            #region 初始化计算
            //计算初始信息素的值，可直接指定，或者贪婪算法计算
            double Cnn = GreedyAlgorithm();
            double t0 = (double)AntCount / Cnn;//信息素初始化
            for (int i = 0; i < NCity; i  )
            {
                for (int j = 0; j < NCity; j  )
                {
                    //每条可行的路径的信息素初始值
                    if (Distance[i, j] != 0) InfoT[i, j] = t0;
                }
            }
            //为每个蚂蚁随机选择出发城市,List的长度为蚂蚁个数，内部List长度为路径    
            List<Int32> allNodes = new List<int>();
            for (int i = 0; i < NCity; i  ) allNodes.Add(i);//所有路径节点
            //迭代次数
            Int32 NC = 0;
            #endregion

            while (NC<NcMax)
            {
                //生成蚂蚁及初始访问城市，并设置对应禁忌表和路径列表
                List<Ant> antList = new List<Ant>();
                for (int i = 0; i < AntCount; i  )
                    antList.Add(new Ant(i, allNodes.DeepCopy(), false));
                //所有蚂蚁依次寻找下一个节点，直到本轮完成
                antList.ForEach(n => n.NextCityUntilFinished(InfoT,Distance,Alpha,Beta,Rho));
                //并行计算
                //Parallel.ForEach(antList, n => n.NextCityUntilFinished(infoT, Distance, Alpha, Beta, Rho));
                //统计最优解
                planList.AddRange(antList);//先添加
                planList = planList.OrderBy(n => n.CpathLength).ToList();//排序
                //取出前面指定的几条最短路径
                if (planList.Count > BetterPlanCount) 
                    planList.RemoveRange(BetterPlanCount, planList.Count - BetterPlanCount);
                NC  ;
                //更新信息素的值：循环所有路径，依次进行添加
                //先挥发
                for (int i = 0; i < NCity; i  ) //挥发过程
                {
                    for (int j = 0; j < NCity; j  ) InfoT[i, j] *= (1.0 - Rho);
                }
                //再增强,循环所有蚂蚁
                foreach (var item in antList)
                {
                    var temp =  1.0 / item.CpathLength;
                    foreach (var edge in item.Edge) InfoT[edge.Key, edge.Value]  = temp;    
                }
            }
        }
        #endregion

        #region 辅助算法-贪婪算法实现
        /// <summary>贪婪算法实现，为了计算初始信息素的值</summary>
        private double GreedyAlgorithm()
        {
            double sum = 0;//总距离，初始为0
            //默认从0个点开始
            int current = 0;
            //下一步可供选择的点的编号列表，会动态改变
            List<Int32> canSelect = new List<int>();
            //初始化可选择列表
            for (int i = 1; i < Distance.GetLength(0); i  ) canSelect.Add(i);
            //循环直到所有点都走完
            while(canSelect.Count >0)
            {                
                //计算当前点到其他可供选择点列表的最短距离，这是贪婪算法的思想
                Int32 minPoint = 0;//最短的编号
                double minLenth = double.MaxValue;//最短的距离
                foreach (var item in canSelect)
                {
                    if(Distance[current,item]<minLenth )
                    {
                        minPoint = item;
                        minLenth = Distance[current, item];
                    }
                }
                sum  = minLenth;
                canSelect.Remove(minPoint);//移除最小的节点
            }
            return sum;
        }
        #endregion

        #region 测试例子，按照PPT进行
        public static void Test()
        {
            double[,] D = { { 0, 3, 1, 2 }, { 3, 0, 5, 4 }, { 1, 5, 0, 2 }, { 2, 4, 2, 0 } };
            BaseTspAntSystem tsp = new BaseTspAntSystem(D, 3, 1, 2, 0.5, 500, 3);
            tsp.TspSolution();
        }
        #endregion
    }

    /// <summary>蚂蚁类</summary>
    public class Ant
    {
        #region 属性
        /// <summary>蚂蚁编号</summary>
        public Int32 Id { get; set; }
        /// <summary>当前蚂蚁已经走过的路径节点列表，也就是禁忌表
        /// 最后1个就是当前所处的位置
        /// </summary>
        public List<Int32> PathNodes { get; set; }
        /// <summary>当前蚂蚁下一步可供选择的节点列表</summary>
        public List<Int32> selectNodes { get; set; }
        /// <summary>该蚂蚁旅行的总长度</summary>
        public Double CpathLength { get; set; }
        /// <summary>当前蚂蚁走过的边，key为起点,value为终点</summary>
        public Dictionary<int, int> Edge;
        private Random rand;
        int N;
        #endregion

        #region 构造函数
        /// <summary>构造函数</summary>
        /// <param name="id">蚂蚁编号</param>
        /// <param name="allNodes">所有节点名称列表</param>
        /// <param name="isFixStart">是否固定起点</param>
        public Ant(Int32 id,List<Int32> allNodes,Boolean isFixStart)
        {
            this.Id = id;
            this.selectNodes = allNodes;
            this.PathNodes = new List<int> ();
            //isFixStart为false给蚂蚁随机1个起点，否则都为0
            if (isFixStart)
            {
                this.PathNodes.Add(0);
                this.selectNodes.RemoveAt(0);
            }
            else
            {
                var temp = new Random().Next(0, allNodes.Count - 1);
                this.PathNodes.Add(temp);
                this.selectNodes.RemoveAt(temp);
            }
            this.CpathLength = 0;
            rand = new Random();
        }
        #endregion

        #region 蚂蚁行为-依次按概率选择下一个城市，直到走完
        public void NextCityUntilFinished(double[,] info,double[,] distance,double a,double b,double p)
        {
            N = distance.GetLength(0);
            Edge = new Dictionary<int, int>();//经过的边：起点-终点
            //为空，就不需要计算了
            while(selectNodes.Count >0)
            {
                double sumt = 0;//分母的和值
                Int32 current = PathNodes.Last();
                //依次计算当前点到其他点可选择点的 值
                Dictionary<Int32, double> dic = new Dictionary<int, double>();
                foreach (var item in selectNodes)
                {
                    var temp = Math.Pow(info[current, item], a) * Math.Pow(1.0 / distance[current, item], b);
                    sumt  = temp;
                    dic.Add(item, temp);
                }
                //计算各个点的概率
                var ratio = dic.ToDictionary(n => n.Key, n => n.Value / sumt);
                //产生1个随机数，并按概率确定下一个城市
                Int32 nextCity = GetNextCityByRandValue(ratio, rand.NextDouble());
                //修改列表
                this.PathNodes.Add(nextCity);
                this.selectNodes.Remove(nextCity);
                this.CpathLength  = distance[current, nextCity];
                Edge.Add(current, nextCity);//信息素增强辅助计算
            }
            //最后1条路径的问题，额外增加，直接 回原点
            this.CpathLength  = distance[PathNodes.Last(), PathNodes.First()];
            Edge.Add(PathNodes.Last(), PathNodes.First());
            this.PathNodes.Add(PathNodes.First());//最后才添加           
        }

        /// <summary>按照dic中按照顺序的节点的概率值，和随机数rnd的值，确定哪一个为下一个城市</summary>
        /// <param name="dic"></param>
        /// <param name="rnd"></param>
        /// <returns></returns>
        int GetNextCityByRandValue(Dictionary<Int32,double> dic,double rnd)
        {
            double sum = 0;
            foreach (var item in dic)
            {
                sum  = item.Value;
                if (rnd < sum) return item.Key;
                else continue;
            }
            throw new Exception("无法选择城市");
        }
        #endregion
    }
}