近期网站备案中。如遇无法访问、敬请见谅。 酷炫帅气情人节表白利器！
> 基于蚁群算法求解求解TSP问题（JAVA）
编辑日期：
一、TSP问题TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述：V={c1, c2, …, ci, …, cn}，i = 1,2, …, n，是所有城市的集合.ci表示第i个城市，n为城市的数目；E={(r, s): r,s∈ V}是所有城市之间连接的集合；C = {crs: r,s∈ V}是所有城市之间连接的成本度量（一般为城市之间的距离）；如果crs&= csr, 那么该TSP问题为对称的，否则为非对称的。一个TSP问题可以表达为：求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。二、蚁群算法蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚁群算法原理：假如蚁群中所有蚂蚁的数量为m，所有城市之间的信息素用矩阵pheromone表示，最短路径为bestLength，最佳路径为bestTour。每只蚂蚁都有自己的内存，内存中用一个禁忌表（Tabu）来存储该蚂蚁已经访问过的城市，表示其在以后的搜索中将不能访问这些城市；还有用另外一个允许访问的城市表（Allowed）来存储它还可以访问的城市；另外还用一个矩阵（Delta）来存储它在一个循环（或者迭代）中给所经过的路径释放的信息素；还有另外一些数据，例如一些控制参数（α,β,ρ,Q），该蚂蚁行走玩全程的总成本或距离（tourLength），等等。假定算法总共运行MAX_GEN次，运行时间为t。蚁群算法计算过程如下： （1）初始化 （2）为每只蚂蚁选择下一个节点。 （3）更新信息素矩阵 （4）检查终止条件 （5）输出最优值三、蚁群算法求解TSP问题在该JAVA实现中我们选择使用上的数据att48，这是一个对称TSP问题，城市规模为48，其最优值为10628.其距离计算方法下图所示：具体代码如下： [java]& view plain copypackage&import&java.util.Rimport&java.util.Vpublic&class&Ant&implements&Cloneable&{&&&&private&Vector&Integer&&&//&禁忌表&&&&private&Vector&Integer&&allowedC&//&允许搜索的城市&&&&private&float[][]&&//&信息数变化矩阵&&&&private&int[][]&&//&距离矩阵&&&&private&float&&&&&private&float&&&&&private&int&tourL&//&路径长度&&&&private&int&cityN&//&城市数量&&&&private&int&firstC&//&起始城市&&&&private&int&currentC&//&当前城市&&&&public&Ant()&{&&&&&&&&cityNum&=&30;&&&&&&&&tourLength&=&0;&&&&}&&&&/**&&&&&*&Constructor&of&Ant&&&&&*&&&&&*&@param&num&&&&&*&&&&&&&&&&&&蚂蚁数量&&&&&*/&&&&public&Ant(int&num)&{&&&&&&&&cityNum&=&&&&&&&&&tourLength&=&0;&&&&}&&&&/**&&&&&*&初始化蚂蚁，随机选择起始位置&&&&&*&&&&&*&@param&distance&&&&&*&&&&&&&&&&&&距离矩阵&&&&&*&@param&a&&&&&*&&&&&&&&&&&&alpha&&&&&*&@param&b&&&&&*&&&&&&&&&&&&beta&&&&&*/&&&&public&void&init(int[][]&distance,&float&a,&float&b)&{&&&&&&&&alpha&=&a;&&&&&&&&beta&=&b;&&&&&&&&//&初始允许搜索的城市集合&&&&&&&&allowedCities&=&new&Vector&Integer&();&&&&&&&&//&初始禁忌表&&&&&&&&tabu&=&new&Vector&Integer&();&&&&&&&&//&初始距离矩阵&&&&&&&&this.distance&=&&&&&&&&&//&初始信息数变化矩阵为0&&&&&&&&delta&=&new&float[cityNum][cityNum];&&&&&&&&for&(int&i&=&0;&i&&&cityN&i++)&{&&&&&&&&&&&&Integer&integer&=&new&Integer(i);&&&&&&&&&&&&allowedCities.add(integer);&&&&&&&&&&&&for&(int&j&=&0;&j&&&cityN&j++)&{&&&&&&&&&&&&&&&&delta[i][j]&=&0.f;&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&//&随机挑选一个城市作为起始城市&&&&&&&&Random&random&=&new&Random(System.currentTimeMillis());&&&&&&&&firstCity&=&random.nextInt(cityNum);&&&&&&&&//&允许搜索的城市集合中移除起始城市&&&&&&&&for&(Integer&i&:&allowedCities)&{&&&&&&&&&&&&if&(i.intValue()&==&firstCity)&{&&&&&&&&&&&&&&&&allowedCities.remove(i);&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&//&将起始城市添加至禁忌表&&&&&&&&tabu.add(Integer.valueOf(firstCity));&&&&&&&&//&当前城市为起始城市&&&&&&&&currentCity&=&firstC&&&&}&&&&/**&&&&&*&&&&&*&选择下一个城市&&&&&*&&&&&*&@param&pheromone&&&&&*&&&&&&&&&&&&信息素矩阵&&&&&*/&&&&public&void&selectNextCity(float[][]&pheromone)&{&&&&&&&&float[]&p&=&new&float[cityNum];&&&&&&&&float&sum&=&0.0f;&&&&&&&&//&计算分母部分&&&&&&&&for&(Integer&i&:&allowedCities)&{&&&&&&&&&&&&sum&+=&Math.pow(pheromone[currentCity][i.intValue()],&alpha)&&&&&&&&&&&&&&&&&&&&*&Math.pow(1.0&/&distance[currentCity][i.intValue()],&beta);&&&&&&&&}&&&&&&&&//&计算概率矩阵&&&&&&&&for&(int&i&=&0;&i&&&cityN&i++)&{&&&&&&&&&&&&boolean&flag&=&&&&&&&&&&&&&for&(Integer&j&:&allowedCities)&{&&&&&&&&&&&&&&&&if&(i&==&j.intValue())&{&&&&&&&&&&&&&&&&&&&&p[i]&=&(float)&(Math.pow(pheromone[currentCity][i],&alpha)&*&Math&&&&&&&&&&&&&&&&&&&&&&&&&&&&.pow(1.0&/&distance[currentCity][i],&beta))&/&&&&&&&&&&&&&&&&&&&&&flag&=&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&if&(flag&==&false)&{&&&&&&&&&&&&&&&&p[i]&=&0.f;&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&//&轮盘赌选择下一个城市&&&&&&&&Random&random&=&new&Random(System.currentTimeMillis());&&&&&&&&float&sleectP&=&random.nextFloat();&&&&&&&&int&selectCity&=&0;&&&&&&&&float&sum1&=&0.f;&&&&&&&&for&(int&i&=&0;&i&&&cityN&i++)&{&&&&&&&&&&&&sum1&+=&p[i];&&&&&&&&&&&&if&(sum1&&=&sleectP)&{&&&&&&&&&&&&&&&&selectCity&=&i;&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&//&从允许选择的城市中去除select&city&&&&&&&&for&(Integer&i&:&allowedCities)&{&&&&&&&&&&&&if&(i.intValue()&==&selectCity)&{&&&&&&&&&&&&&&&&allowedCities.remove(i);&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&//&在禁忌表中添加select&city&&&&&&&&tabu.add(Integer.valueOf(selectCity));&&&&&&&&//&将当前城市改为选择的城市&&&&&&&&currentCity&=&selectC&&&&}&&&&/**&&&&&*&计算路径长度&&&&&*&&&&&*&@return&路径长度&&&&&*/&&&&private&int&calculateTourLength()&{&&&&&&&&int&len&=&0;&&&&&&&&//禁忌表tabu最终形式：起始城市,城市1,城市2…城市n,起始城市&&&&&&&&for&(int&i&=&0;&i&&&cityN&i++)&{&&&&&&&&&&&&len&+=&distance[this.tabu.get(i).intValue()][this.tabu.get(i&+&1)&&&&&&&&&&&&&&&&&&&&.intValue()];&&&&&&&&}&&&&&&&&return&&&&&}&&&&public&Vector&Integer&&getAllowedCities()&{&&&&&&&&return&allowedC&&&&}&&&&public&void&setAllowedCities(Vector&Integer&&allowedCities)&{&&&&&&&&this.allowedCities&=&allowedC&&&&}&&&&public&int&getTourLength()&{&&&&&&&&tourLength&=&calculateTourLength();&&&&&&&&return&tourL&&&&}&&&&public&void&setTourLength(int&tourLength)&{&&&&&&&&this.tourLength&=&tourL&&&&}&&&&public&int&getCityNum()&{&&&&&&&&return&cityN&&&&}&&&&public&void&setCityNum(int&cityNum)&{&&&&&&&&this.cityNum&=&cityN&&&&}&&&&public&Vector&Integer&&getTabu()&{&&&&&&&&return&&&&&}&&&&public&void&setTabu(Vector&Integer&&tabu)&{&&&&&&&&this.tabu&=&&&&&}&&&&public&float[][]&getDelta()&{&&&&&&&&return&&&&&}&&&&public&void&setDelta(float[][]&delta)&{&&&&&&&&this.delta&=&&&&&}&&&&public&int&getFirstCity()&{&&&&&&&&return&firstC&&&&}&&&&public&void&setFirstCity(int&firstCity)&{&&&&&&&&this.firstCity&=&firstC&&&&}} [java]& view plain copypackage&import&java.io.BufferedRimport&java.io.FileInputSimport&java.io.IOEimport&java.io.InputStreamRpublic&class&ACO&{&&&&private&Ant[]&&//&蚂蚁&&&&private&int&antN&//&蚂蚁数量&&&&private&int&cityN&//&城市数量&&&&private&int&MAX_GEN;&//&运行代数&&&&private&float[][]&&//&信息素矩阵&&&&private&int[][]&&//&距离矩阵&&&&private&int&bestL&//&最佳长度&&&&private&int[]&bestT&//&最佳路径&&&&//&三个参数&&&&private&float&&&&&private&float&&&&&private&float&&&&&public&ACO()&{&&&&}&&&&/**&&&&&*&constructor&of&ACO&&&&&*&&&&&*&@param&n&&&&&*&&&&&&&&&&&&城市数量&&&&&*&@param&m&&&&&*&&&&&&&&&&&&蚂蚁数量&&&&&*&@param&g&&&&&*&&&&&&&&&&&&运行代数&&&&&*&@param&a&&&&&*&&&&&&&&&&&&alpha&&&&&*&@param&b&&&&&*&&&&&&&&&&&&beta&&&&&*&@param&r&&&&&*&&&&&&&&&&&&rho&&&&&*&&&&&**/&&&&public&ACO(int&n,&int&m,&int&g,&float&a,&float&b,&float&r)&{&&&&&&&&cityNum&=&n;&&&&&&&&antNum&=&m;&&&&&&&&ants&=&new&Ant[antNum];&&&&&&&&MAX_GEN&=&g;&&&&&&&&alpha&=&a;&&&&&&&&beta&=&b;&&&&&&&&rho&=&r;&&&&}&&&&//&给编译器一条指令，告诉它对被批注的代码元素内部的某些警告保持静默&&&&@SuppressWarnings(&resource&)&&&&/**&&&&&*&初始化ACO算法类&&&&&*&@param&filename&数据文件名，该文件存储所有城市节点坐标数据&&&&&*&@throws&IOException&&&&&*/&&&&private&void&init(String&filename)&throws&IOException&{&&&&&&&&//&读取数据&&&&&&&&int[]&x;&&&&&&&&int[]&y;&&&&&&&&String&&&&&&&&&BufferedReader&data&=&new&BufferedReader(new&InputStreamReader(&&&&&&&&&&&&&&&&new&FileInputStream(filename)));&&&&&&&&distance&=&new&int[cityNum][cityNum];&&&&&&&&x&=&new&int[cityNum];&&&&&&&&y&=&new&int[cityNum];&&&&&&&&for&(int&i&=&0;&i&&&cityN&i++)&{&&&&&&&&&&&&//&读取一行数据，数据格式1&&&&&&&&&&&&&strbuff&=&data.readLine();&&&&&&&&&&&&//&字符分割&&&&&&&&&&&&String[]&strcol&=&strbuff.split(&&&);&&&&&&&&&&&&x[i]&=&Integer.valueOf(strcol[1]);//&x坐标&&&&&&&&&&&&y[i]&=&Integer.valueOf(strcol[2]);//&y坐标&&&&&&&&}&&&&&&&&//&计算距离矩阵&&&&&&&&//&针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628&&&&&&&&for&(int&i&=&0;&i&&&cityNum&–&1;&i++)&{&&&&&&&&&&&&distance[i][i]&=&0;&//&对角线为0&&&&&&&&&&&&for&(int&j&=&i&+&1;&j&&&cityN&j++)&{&&&&&&&&&&&&&&&&double&rij&=&Math&&&&&&&&&&&&&&&&&&&&&&&&.sqrt(((x[i]&–&x[j])&*&(x[i]&–&x[j])&+&(y[i]&–&y[j])&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&*&(y[i]&–&y[j]))&/&10.0);&&&&&&&&&&&&&&&&//&四舍五入，取整&&&&&&&&&&&&&&&&int&tij&=&(int)&Math.round(rij);&&&&&&&&&&&&&&&&if&(tij&&&rij)&{&&&&&&&&&&&&&&&&&&&&distance[i][j]&=&tij&+&1;&&&&&&&&&&&&&&&&&&&&distance[j][i]&=&distance[i][j];&&&&&&&&&&&&&&&&}&else&{&&&&&&&&&&&&&&&&&&&&distance[i][j]&=&&&&&&&&&&&&&&&&&&&&&distance[j][i]&=&distance[i][j];&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&distance[cityNum&–&1][cityNum&–&1]&=&0;&&&&&&&&//&初始化信息素矩阵&&&&&&&&pheromone&=&new&float[cityNum][cityNum];&&&&&&&&for&(int&i&=&0;&i&&&cityN&i++)&{&&&&&&&&&&&&for&(int&j&=&0;&j&&&cityN&j++)&{&&&&&&&&&&&&&&&&pheromone[i][j]&=&0.1f;&//&初始化为0.1&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&bestLength&=&Integer.MAX_VALUE;&&&&&&&&bestTour&=&new&int[cityNum&+&1];&&&&&&&&//&随机放置蚂蚁&&&&&&&&for&(int&i&=&0;&i&&&antN&i++)&{&&&&&&&&&&&&ants[i]&=&new&Ant(cityNum);&&&&&&&&&&&&ants[i].init(distance,&alpha,&beta);&&&&&&&&}&&&&}&&&&public&void&solve()&{&&&&&&&&//&迭代MAX_GEN次&&&&&&&&for&(int&g&=&0;&g&&&MAX_GEN;&g++)&{&&&&&&&&&&&&//&antNum只蚂蚁&&&&&&&&&&&&for&(int&i&=&0;&i&&&antN&i++)&{&&&&&&&&&&&&&&&&//&i这只蚂蚁走cityNum步，完整一个TSP&&&&&&&&&&&&&&&&for&(int&j&=&1;&j&&&cityN&j++)&{&&&&&&&&&&&&&&&&&&&&ants[i].selectNextCity(pheromone);&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&//&把这只蚂蚁起始城市加入其禁忌表中&&&&&&&&&&&&&&&&//&禁忌表最终形式：起始城市,城市1,城市2…城市n,起始城市&&&&&&&&&&&&&&&&ants[i].getTabu().add(ants[i].getFirstCity());&&&&&&&&&&&&&&&&//&查看这只蚂蚁行走路径距离是否比当前距离优秀&&&&&&&&&&&&&&&&if&(ants[i].getTourLength()&&&bestLength)&{&&&&&&&&&&&&&&&&&&&&//&比当前优秀则拷贝优秀TSP路径&&&&&&&&&&&&&&&&&&&&bestLength&=&ants[i].getTourLength();&&&&&&&&&&&&&&&&&&&&for&(int&k&=&0;&k&&&cityNum&+&1;&k++)&{&&&&&&&&&&&&&&&&&&&&&&&&bestTour[k]&=&ants[i].getTabu().get(k).intValue();&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&//&更新这只蚂蚁的信息数变化矩阵，对称矩阵&&&&&&&&&&&&&&&&for&(int&j&=&0;&j&&&cityN&j++)&{&&&&&&&&&&&&&&&&&&&&ants[i].getDelta()[ants[i].getTabu().get(j).intValue()][ants[i]&&&&&&&&&&&&&&&&&&&&&&&&&&&&.getTabu().get(j&+&1).intValue()]&=&(float)&(1.&/&ants[i]&&&&&&&&&&&&&&&&&&&&&&&&&&&&.getTourLength());&&&&&&&&&&&&&&&&&&&&ants[i].getDelta()[ants[i].getTabu().get(j&+&1).intValue()][ants[i]&&&&&&&&&&&&&&&&&&&&&&&&&&&&.getTabu().get(j).intValue()]&=&(float)&(1.&/&ants[i]&&&&&&&&&&&&&&&&&&&&&&&&&&&&.getTourLength());&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&//&更新信息素&&&&&&&&&&&&updatePheromone();&&&&&&&&&&&&//&重新初始化蚂蚁&&&&&&&&&&&&for&(int&i&=&0;&i&&&antN&i++)&{&&&&&&&&&&&&&&&&ants[i].init(distance,&alpha,&beta);&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&//&打印最佳结果&&&&&&&&printOptimal();&&&&}&&&&//&更新信息素&&&&private&void&updatePheromone()&{&&&&&&&&//&信息素挥发&&&&&&&&for&(int&i&=&0;&i&&&cityN&i++)&&&&&&&&&&&&for&(int&j&=&0;&j&&&cityN&j++)&&&&&&&&&&&&&&&&pheromone[i][j]&=&pheromone[i][j]&*&(1&–&rho);&&&&&&&&//&信息素更新&&&&&&&&for&(int&i&=&0;&i&&&cityN&i++)&{&&&&&&&&&&&&for&(int&j&=&0;&j&&&cityN&j++)&{&&&&&&&&&&&&&&&&for&(int&k&=&0;&k&&&antN&k++)&{&&&&&&&&&&&&&&&&&&&&pheromone[i][j]&+=&ants[k].getDelta()[i][j];&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&}&&&&private&void&printOptimal()&{&&&&&&&&System.out.println(&The&optimal&length&is:&&&+&bestLength);&&&&&&&&System.out.println(&The&optimal&tour&is:&&);&&&&&&&&for&(int&i&=&0;&i&&&cityNum&+&1;&i++)&{&&&&&&&&&&&&System.out.println(bestTour[i]);&&&&&&&&}&&&&}&&&&/**&&&&&*&@param&args&&&&&*&@throws&IOException&&&&&*/&&&&public&static&void&main(String[]&args)&throws&IOException&{&&&&&&&&System.out.println(&Start….&);&&&&&&&&ACO&aco&=&new&ACO(48,&10,&100,&1.f,&5.f,&0.5f);&&&&&&&&aco.init(&c://data.txt&);&&&&&&&&aco.solve();&&&&}}运行结果截图：四、总结蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力，但是也正是由于其并行性的本质，蚁群算法的搜索时间较长，在求解小规模的NP问题时耗费的计算资源相比其他启发式算法要多，因而显得效率很低下，而当问题趋向于大规模时，蚁群算法还是存在难收敛的问题，个人感觉除非你真想耗费大量计算资源来干一件事情，否则还是慎用蚁群算法。关注,获取最新文章资讯。 | 本文由玩赚乐( )整理分享。本文固定链接: 转载请注明:
作者：晨风????AiJava 交流吧！
如果您觉得这篇文章有用处，请支持作者！鼓励作者写出更好更多的文章！
，，，，，
您可能还会对这些文章感兴趣！求解求解求求解。_百度知道
求解求解求求解。
我有更好的答案
五、2、愿久千共婵娟另外书找找
还有呢？！
另外的自己书里应该有的找找吧，因为现在教材不一样了，我也不知道了
其他类似问题
为您推荐：
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁要生的放进冰箱才能保存很久。
您的举报已经提交成功，我们将尽快处理，谢谢！
这个问题很早就被解决了：
首先将冰箱门打开，然后将大象放进去，最后将冰箱门关好。
就是如此简单。
做好的肉丸子应熟制后冷却至常温时入冰箱保存，保存时间不宜久，最好以原汤浸泡着冷藏，以不结冰为度，时间请尽量不超过三天为好。
大家还关注
(window.slotbydup=window.slotbydup || []).push({
id: '2081942',
container: s,
size: '1000,60',
display: 'inlay-fix'}