实例介绍
【实例简介】旅行商问题,常被称为旅行推销员问题,是指一名推销员要拜访多个地点时,如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单,但在地点数目增多后求解却极为复杂。
【实例截图】
【实例截图】
【核心代码】
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 } }
好例子网口号:伸出你的我的手 — 分享!
相关软件
小贴士
感谢您为本站写下的评论,您的评论对其它用户来说具有重要的参考价值,所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字,对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙,所以请不要反馈意义不大的重复字符,也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明,或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦,又没人会搭理,于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享,对搜索内容的合法性不具有预见性、识别性、控制性,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论平台是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定,若资源存在侵权或相关问题请联系本站客服人员,点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论