本文主要是介绍旅行商问题(TSP)的启发式求解算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、TSP问题
TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
二、求解算法
从图论的角度来看，TSP问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。
早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。
下面使用遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法 对TSP问题求近似解。
我们使用的TSP问题来自于TSPLIB上的att48，这是一个对称TSP问题，城市规模为48，其最优值为10628.其距离计算方法下所示：
首先定义几个通用类，类City表示城市，类CityManager表示旅行商需要拜访的所有城市，类Tour表示旅行商的行走路线。
public class City {int x; //城市坐标xint y; //城市坐标ypublic City(int x, int y){this.x = x;this.y = y;}public int getX(){return this.x;}public int getY(){return this.y;}/*** 计算两个城市之间的距离，距离计算方法由上图提供* @param city* @return*/public int distanceTo(City city){int xd = Math.abs(getX() - city.getX());int yd = Math.abs(getY() - city.getY());double rij = Math.sqrt( ( xd*xd + yd*yd ) / 10.0 );int tij = (int)Math.round(rij);if (tij < rij)return tij + 1;elsereturn tij;}@Overridepublic String toString(){return "(" + getX()+ "," + getY() + ")";}
}
import java.util.ArrayList;public class CityManager {//保存所有的目的城市private static ArrayList destinationCities = new ArrayList<City>();public static void addCity(City city) {destinationCities.add(city);}public static City getCity(int index){return (City)destinationCities.get(index);}// 获得城市的数量public static int numberOfCities(){return destinationCities.size();}}import java.util.ArrayList;
import java.util.Collections;public class Tour{// 访问路线，保存需要访问的城市private ArrayList tour = new ArrayList<City>();// 构建一个空的路线public Tour(){for (int i = 0; i < CityManager.numberOfCities(); i++) {tour.add(null);}}// 用路线tour构建当前路线public Tour(ArrayList tour){this.tour = (ArrayList) tour.clone();}// 返回当前路线信息public ArrayList getTour(){return tour;}// 创建一个城市路线public void generateIndividual() {// 将目的城市一个个添加到当前路线中for (int cityIndex = 0; cityIndex < CityManager.numberOfCities(); cityIndex++) {setCity(cityIndex, CityManager.getCity(cityIndex));}// 把路线上城市的顺序打乱Collections.shuffle(tour);}// 从当前路线中获取指定位置的城市public City getCity(int tourPosition) {return (City)tour.get(tourPosition);}// 将一个目的城市放置到当前路线的指定位置public void setCity(int tourPosition, City city) {tour.set(tourPosition, city);}// 获得当前路线上所有城市距离的总和public int getDistance(){int tourDistance = 0;for (int cityIndex=0; cityIndex < tourSize(); cityIndex++) {City fromCity = getCity(cityIndex);City destinationCity;if(cityIndex+1 < tourSize()){destinationCity = getCity(cityIndex+1);}else{destinationCity = getCity(0);}tourDistance += fromCity.distanceTo(destinationCity);}return tourDistance;}// 获得路线上城市的数量public int tourSize() {return tour.size();}@Overridepublic String toString() {String geneString = "|";for (int i = 0; i < tourSize(); i++) {geneString += getCity(i)+"|";}return geneString;}
}
1. 模拟退火算法
模拟退火算法其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。模拟退火算法是一种随机算法，并不一定能找到全局的最优解，但可以比较快的找到问题的近似最优解。
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;public class SimulatedAnnealing {// Calculate the acceptance probabilitypublic static double acceptanceProbability(int energy, int newEnergy, double temperature) {// If the new solution is better, accept itif (newEnergy < energy) {return 1.0;}// If the new solution is worse, calculate an acceptance probabilityreturn Math.exp((energy - newEnergy) / temperature);}public static void initCities() throws IOException {BufferedReader br = new BufferedReader(new FileReader("att48.tsp"));String line = null;while ( (line = br.readLine()) != null ) {String[] token = line.split(" ");City city = new City(Integer.parseInt(token[1]), Integer.parseInt(token[2]));CityManager.addCity(city);}}public static void main(String[] args) {try {initCities();} catch (IOException e) {// TODO Auto-generated catch blocke.printStackTrace();return;}// Set initial tempdouble temp = 1000;// Cooling ratedouble coolingRate = 0.002;// Initialize intial solutionTour currentSolution = new Tour();currentSolution.generateIndividual();System.out.println("Initial solution distance: " + currentSolution.getDistance());// Set as current bestTour best = new Tour(currentSolution.getTour());// Loop until system has cooledwhile (temp > 1) {// Create new neighbour tourTour newSolution = new Tour(currentSolution.getTour());// Get a random positions in the tourint tourPos1 = (int) (newSolution.tourSize() * Math.random());int tourPos2 = (int) (newSolution.tourSize() * Math.random());while (tourPos1 == tourPos2 ) {tourPos2 = (int) (newSolution.tourSize() * Math.random());}// Get the cities at selected positions in the tourCity citySwap1 = newSolution.getCity(tourPos1);City citySwap2 = newSolution.getCity(tourPos2);// Swap themnewSolution.setCity(tourPos2, citySwap1);newSolution.setCity(tourPos1, citySwap2);// Get energy of solutionsint currentEnergy = currentSolution.getDistance();int neighbourEnergy = newSolution.getDistance();// Decide if we should accept the neighbourif (acceptanceProbability(currentEnergy, neighbourEnergy, temp) > Math.random()) {currentSolution = new Tour(newSolution.getTour());}// Keep track of the best solution foundif (currentSolution.getDistance() < best.getDistance()) {best = new Tour(currentSolution.getTour());}// Cool systemtemp *= 1-coolingRate;}System.out.println("Final solution distance: " + best.getDistance());System.out.println("Tour: " + best);}
}这篇关于旅行商问题(TSP)的启发式求解算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
