当前位置：首页 > news >正文

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

news 2025/5/7 5:56:25

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

算法流程
在这里插入图片描述

旅行商问题
有 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();}
}