模拟退火算法

1. 概念

模拟退火算法（Simulated Annealing）是一种元启发式优化算法，通常用于解决组合优化问题，如旅行商问题、排课问题等。该算法的名称源于固体物质退火过程中的晶格结构变化。模拟退火算法模拟了晶体在高温下随机摆动、然后逐渐冷却以实现结晶过程的特点。
模拟退火算法的核心思想是通过在解空间中随机搜索，逐渐减小温度，以便在搜索过程中逐渐收敛到更优的解。算法允许在搜索过程中接受劣质解的概率，以避免陷入局部最优解。

虽然模拟退火算法不保证找到全局最优解，但它通常能够在合理的时间内找到较好的解决方案。它的性能受到参数设置、冷却计划和邻域搜索策略的影响，需要根据具体问题进行调优。这一算法在许多组合优化问题上都表现出色。

2. 基本步骤

1. 初始化：随机生成或者通过某种启发式方法产生一个初始解，这通常是问题的一个潜在解决方案。

2. 冷却计划：定义一个温度下降的计划，以模拟冷却过程。通常，温度会从高到低逐渐降低。

3. 迭代：在每个温度下，进行一定数量的迭代，每次迭代中，对当前解进行小的随机扰动，产生一个邻域解。

4. 接受或拒绝邻域解：根据一定的概率策略，决定是否接受邻域解。通常，如果邻域解更好（即更小）或在一定概率内，会接受邻域解，否则拒绝。

5. 降温：根据冷却计划，降低温度。

6. 终止条件：根据一定的终止条件，例如达到最大迭代次数或温度降低到阈值以下，决定是否终止算法。

7. 返回最佳解：返回在搜索过程中找到的最佳解。

3. 使用模拟退火解决实际问题

3.1 求解0-1背包问题

0-1背包问题是经典的组合优化问题，目标是在给定背包容量下选择一组物品，使得它们的总价值最大，同时不超过背包的容量。

import java.util.Random;

public class SimulatedAnnealingKnapsackSolver {
    private static final int NUM_ITERATIONS = 1000;
    private static final double INITIAL_TEMPERATURE = 1000;
    private static final double COOLING_RATE = 0.95;

    public static void main(String[] args) {
        int[] weights = {2, 5, 7, 3, 9};
        int[] values = {7, 10, 13, 5, 15};
        int maxWeight = 15;

        int[] bestSolution = solveKnapsackProblem(weights, values, maxWeight);
        int bestValue = calculateValue(bestSolution, values);
        
        System.out.println("Best Solution: " + Arrays.toString(bestSolution));
        System.out.println("Best Value: " + bestValue);
    }

    public static int[] solveKnapsackProblem(int[] weights, int[] values, int maxWeight) {
        int[] currentSolution = generateRandomSolution(weights.length);
        int[] bestSolution = currentSolution;

        double temperature = INITIAL_TEMPERATURE;

        for (int iteration = 0; iteration < NUM_ITERATIONS; iteration++) {
            int[] neighborSolution = generateNeighborSolution(currentSolution);
            int currentValue = calculateValue(currentSolution, values);
            int neighborValue = calculateValue(neighborSolution, values);
            int bestValue = calculateValue(bestSolution, values);

            if (neighborValue > bestValue || Math.random() < acceptanceProbability(currentValue, neighborValue, temperature)) {
                currentSolution = neighborSolution;
                if (neighborValue > bestValue) {
                    bestSolution = neighborSolution;
                }
            }

            temperature *= COOLING_RATE;
        }

        return bestSolution;
    }

    private static int[] generateRandomSolution(int length) {
        int[] solution = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            solution[i] = random.nextInt(2); // 0 or 1
        }
        return solution;
    }

    private static int[] generateNeighborSolution(int[] solution) {
        int[] neighbor = solution.clone();
        Random random = new Random();
        int index = random.nextInt(neighbor.length);
        neighbor[index] = 1 - neighbor[index]; // Flip 0 to 1 or 1 to 0
        return neighbor;
    }

    private static int calculateValue(int[] solution, int[] values) {
        int value = 0;
        for (int i = 0; i < solution.length; i++) {
            value += solution[i] * values[i];
        }
        return value;
    }

    private static double acceptanceProbability(int currentValue, int neighborValue, double temperature) {
        if (neighborValue > currentValue) {
            return 1.0;
        }
        return Math.exp((neighborValue - currentValue) / temperature);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

3.2 求解旅行商问题

解决旅行商问题（Traveling Salesman Problem，TSP）是一个典型的组合优化问题，涉及寻找访问一组城市并返回起始城市的最短路径，使得每个城市仅访问一次。模拟退火算法可以用于寻找近似最优解。
使用一个简化的TSP问题，包含四个城市

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class SimulatedAnnealingTSPSolver {
    private static final int NUM_ITERATIONS = 1000;
    private static final double INITIAL_TEMPERATURE = 1000;
    private static final double COOLING_RATE = 0.95;

    public static void main(String[] args) {
        List<City> cities = new ArrayList<>();
        cities.add(new City("A", 0, 0));
        cities.add(new City("B", 2, 1));
        cities.add(new City("C", 3, 3));
        cities.add(new City("D", 1, 2));

        List<City> bestTour = solveTSP(cities);
        double bestTourLength = calculateTourLength(bestTour);

        System.out.println("Best Tour: " + bestTour);
        System.out.println("Best Tour Length: " + bestTourLength);
    }

    public static List<City> solveTSP(List<City> cities) {
        List<City> currentTour = new ArrayList<>(cities);
        Collections.shuffle(currentTour); // Random initial tour
        List<City> bestTour = currentTour;

        double temperature = INITIAL_TEMPERATURE;

        for (int iteration = 0; iteration < NUM_ITERATIONS; iteration++) {
            List<City> neighborTour = generateNeighborTour(currentTour);
            double currentTourLength = calculateTourLength(currentTour);
            double neighborTourLength = calculateTourLength(neighborTour);

            if (neighborTourLength < currentTourLength || Math.random() < acceptanceProbability(currentTourLength, neighborTourLength, temperature)) {
                currentTour = neighborTour;
                if (neighborTourLength < calculateTourLength(bestTour)) {
                    bestTour = neighborTour;
                }
            }

            temperature *= COOLING_RATE;
        }

        return bestTour;
    }

    private static List<City> generateNeighborTour(List<City> tour) {
        List<City> neighbor = new ArrayList<>(tour);
        Random random = new Random();
        int index1 = random.nextInt(neighbor.size());
        int index2 = random.nextInt(neighbor.size());
        Collections.swap(neighbor, index1, index2);
        return neighbor;
    }

    private static double calculateTourLength(List<City> tour) {
        double length = 0;
        for (int i = 0; i < tour.size(); i++) {
            City currentCity = tour.get(i);
            City nextCity = tour.get((i + 1) % tour.size());
            length += currentCity.distanceTo(nextCity);
        }
        return length;
    }

    private static double acceptanceProbability(double currentLength, double neighborLength, double temperature) {
        if (neighborLength < currentLength) {
            return 1.0;
        }
        return Math.exp((currentLength - neighborLength) / temperature);
    }
}

class City {
    private String name;
    private double x;
    private double y;

    public City(String name, double x, double y) {
        this.name = name;
        this.x = x;
        this.y = y;
    }

    public double distanceTo(City other) {
        double dx = x - other.x;
        double dy = y - other.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    @Override
    public String toString() {
        return name;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99