旅行商问题模拟退火Java

以下是旅行商问题的模拟退火算法的Java代码示例：

import java.util.ArrayList;
import java.util.Random;

public class TravelingSalesmanSA {
    private static final double INITIAL_TEMPERATURE = 1000; // 初始温度
    private static final double COOLING_RATE = 0.99; // 降温速率
    private static final int MAX_ITERATIONS = 1000; // 最大迭代次数

    public static void main(String[] args) {
        // 初始化城市坐标
        ArrayList<City> cities = new ArrayList<>();
        cities.add(new City(0, 0));
        cities.add(new City(1, 2));
        cities.add(new City(3, 1));
        cities.add(new City(5, 4));
        cities.add(new City(2, 3));

        // 初始化路径
        ArrayList<Integer> currentSolution = new ArrayList<>();
        for (int i = 0; i < cities.size(); i++) {
            currentSolution.add(i);
        }

        // 计算初始路径长度
        double currentDistance = calculateDistance(cities, currentSolution);

        // 模拟退火算法
        double temperature = INITIAL_TEMPERATURE;
        Random random = new Random();
        int iteration = 0;
        while (temperature > 1 && iteration < MAX_ITERATIONS) {
            // 生成新解
            ArrayList<Integer> newSolution = generateNeighbor(currentSolution, random);

            // 计算新解的路径长度
            double newDistance = calculateDistance(cities, newSolution);

            // 判断是否接受新解
            if (acceptNewSolution(currentDistance, newDistance, temperature)) {
                currentSolution = newSolution;
                currentDistance = newDistance;
            }

            // 降温
            temperature *= COOLING_RATE;

            iteration++;
        }

        // 输出最优解
        System.out.println("Optimal solution: " + currentSolution);
        System.out.println("Optimal distance: " + currentDistance);
    }

    // 计算路径长度
    private static double calculateDistance(ArrayList<City> cities, ArrayList<Integer> solution) {
        double distance = 0;
        for (int i = 0; i < solution.size() - 1; i++) {
            int cityIndex1 = solution.get(i);
            int cityIndex2 = solution.get(i + 1);
            City city1 = cities.get(cityIndex1);
            City city2 = cities.get(cityIndex2);
            distance += calculateDistanceBetweenCities(city1, city2);
        }
        return distance;
    }

    // 计算两个城市之间的距离
    private static double calculateDistanceBetweenCities(City city1, City city2) {
        int xDiff = city1.getX() - city2.getX();
        int yDiff = city1.getY() - city2.getY();
        return Math.sqrt(xDiff * xDiff + yDiff * yDiff);
    }

    // 生成邻解
    private static ArrayList<Integer> generateNeighbor(ArrayList<Integer> solution, Random random) {
        ArrayList<Integer> neighbor = new ArrayList<>(solution);
        int index1 = random.nextInt(neighbor.size());
        int index2 = random.nextInt(neighbor.size());
        int temp = neighbor.get(index1);
        neighbor.set(index1, neighbor.get(index2));
        neighbor.set(index2, temp);
        return neighbor;
    }

    // 判断是否接受新解
    private static boolean acceptNewSolution(double currentDistance, double newDistance, double temperature) {
        if (newDistance < currentDistance) {
            return true;
        }
        double acceptanceProbability = Math.exp((currentDistance - newDistance) / temperature);
        return Math.random() < acceptanceProbability;
    }
}

class City {
    private int x;
    private int y;

    public City(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}