启发式算法-模拟退火算法

模拟退火算法是一种基于概率的启发式优化算法，用于解决大规模组合优化问题，其灵感来源于金属退火过程中的物理现象。其基本原理是从一个初始解开始，然后在当前解的邻域内随机生成一个新解，如果新解的目标函数值优于当前解，那么就将新解作为当前解，如果新解的目标函数值比当前解差，那么以一定的概率选择新解，这个概率随着算法的进行而逐渐降低，类似于退火过程中温度逐渐降低，物质逐渐趋于稳定状态，通过这种方式算法可以在一定程度上避免陷入局部最优解，搜索到全局最优解。

算法流程

旅行商问题
有 10 个城市A、B、C、D、E…J，旅行商需要从一个城市出发，遍历所有城市且每个城市只经过一次，最后回到起始城市，要求找到最短的旅行路线，城市距离矩阵如下，最优路线 H->I->E->A->G->B->D->F->C->J->H

模拟退火代码

public class SATSP {
    // 城市数量
    private static final int NUM_CITIES = 10;
    // 初始温度
    private static final double INITIAL_TEMPERATURE = 1000;
    // 冷却率
    private static final double COOLING_RATE = 0.99;
    // 终止温度
    private static final double FINAL_TEMPERATURE = 0.1;

    // 城市距离矩阵
    private static int[][] distanceMatrix;

    public static void main(String[] args) {
        // 初始化距离矩阵
        initializeDistanceMatrix();
        // 初始化路线
        List<Integer> currentRoute = generateInitialRoute();
        // 计算当前路线的距离
        double currentDistance = calculateDistance(currentRoute);

        // 初始温度
        double temperature = INITIAL_TEMPERATURE;

        // 记录最优路线
        List<Integer> bestRoute = new ArrayList<>(currentRoute);
        double bestDistance = currentDistance;

        // 模拟退火过程
        while (temperature > FINAL_TEMPERATURE) {
            // 生成新的邻域路线
            List<Integer> newRoute = getNeighborRoute(currentRoute);
            // 计算新路线的距离
            double newDistance = calculateDistance(newRoute);

            // 计算距离差
            double deltaDistance = newDistance - currentDistance;

            // 如果新路线更优或者满足概率条件，则接受新路线
            if (deltaDistance < 0 || Math.exp(-deltaDistance / temperature) > Math.random()) {
                currentRoute = newRoute;
                currentDistance = newDistance;
            }

            // 如果新路线是目前最优的，更新最优路线
            if (currentDistance < bestDistance) {
                bestRoute = new ArrayList<>(currentRoute);
                bestDistance = currentDistance;
            }

            // 降温
            temperature *= COOLING_RATE;
        }

        // 输出具体路线
        String routeString = convertRouteToLetters(bestRoute);
        System.out.println("最优路线: " + routeString);
        System.out.println("最短距离: " + bestDistance);
    }

    // 初始化距离矩阵
    private static void initializeDistanceMatrix() {
        distanceMatrix = new int[NUM_CITIES][NUM_CITIES];
        Random random = new Random();
        for (int i = 0; i < NUM_CITIES; i++) {
            for (int j = 0; j < NUM_CITIES; j++) {
                if (i == j) {
                    distanceMatrix[i][j] = 0;
                } else {
                    // 随机生成城市之间的整数距离
                    distanceMatrix[i][j] = random.nextInt(100);
                    distanceMatrix[j][i] = distanceMatrix[i][j];
                }
            }
        }

        // 距离矩阵
        System.out.println("城市距离矩阵:");
        System.out.print("  ");
        for (int i = 0; i < NUM_CITIES; i++) {
            System.out.print((char) ('A' + i) + "  ");
        }
        System.out.println();
        for (int i = 0; i < NUM_CITIES; i++) {
            System.out.print((char) ('A' + i) + " ");
            for (int j = 0; j < NUM_CITIES; j++) {
                System.out.printf("%2d ", distanceMatrix[i][j]);
            }
            System.out.println();
        }
    }

    // 生成初始路线
    private static List<Integer> generateInitialRoute() {
        List<Integer> route = new ArrayList<>();
        for (int i = 0; i < NUM_CITIES; i++) {
            route.add(i);
        }
        // 生成初始路线
        Collections.shuffle(route);
        return route;
    }

    // 计算路线的总距离
    private static double calculateDistance(List<Integer> route) {
        double distance = 0;
        for (int i = 0; i < route.size() - 1; i++) {
            int from = route.get(i);
            int to = route.get(i + 1);
            distance += distanceMatrix[from][to];
        }
        // 回到起点
        distance += distanceMatrix[route.get(route.size() - 1)][route.get(0)];
        return distance;
    }

    // 生成邻域路线
    private static List<Integer> getNeighborRoute(List<Integer> route) {
        List<Integer> newRoute = new ArrayList<>(route);
        Random random = new Random();
        int index1 = random.nextInt(NUM_CITIES);
        int index2 = random.nextInt(NUM_CITIES);
        // 交换两个城市的位置
        Collections.swap(newRoute, index1, index2);
        return newRoute;
    }

    private static String convertRouteToLetters(List<Integer> route) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < route.size(); i++) {
            char city = (char) ('A' + route.get(i));
            sb.append(city);
            if (i < route.size() - 1) {
                sb.append("->");
            }
        }
        // 回到起点
        char startCity = (char) ('A' + route.get(0));
        sb.append("->").append(startCity);
        return sb.toString();
    }
}