3702 字
19 分钟

从找最小值到旅行商问题：模拟退火算法的 Java 实现

2026-06-16
碎片技术笔记
算法
/
退火

1. 什么是模拟退火算法？#

WIKI定义：模拟退火 ( Simulated annealing )

冶金学中的退火#

什么是退火 模拟退火的退火源自冶金学术语退火。金属在加热后，原子能量变高，会离开原来的位置随机的在其他位置移动，退火时冷却速度较慢，使得原子有更多可能找到内能比原来位置更低的位置。

由此衍生的模拟退火算法#

图片源自Wiki百科 模拟退火算法的原理与金属退火相似，将待搜索空间内的每一点类比为一个金属原子，定义一个温度类比原子当前的能量，随机的选取一个邻居，计算原子会移动到当前邻居的概率，同时原子的温度会逐渐降低。随着温度降低到临界值，原子也会趋于一个全局的能量最低点。

在模拟退火算法中，需要进行如下的定义：

  1. 状态 & 邻态选择： 模拟退火在每一步都需要基于当前的状态选取一个随机的邻态，并考虑是否要转移到这个邻态。
  2. 温度： 模拟退火定义了一个温度变量，类比冶金退火中的当前温度。随着退火历程逐渐降低。
  3. 接收概率： 是否从当前状态转移到邻态需要由接收概率定义。

当邻态更优于当前状态时，自然会选择转移；而当邻态劣于当前状态时，由于原子自身具备的能量，还是有概率离开当前状态转移到邻态的。

这使得在高能量时，原子能更广泛的检索，而不是被困在当前的局部最优解，这也是模拟退火算法在爬山算法基础上的改进之处。

2. 什么时候用到模拟退火算法？#

当问题满足下面的条件时，可以考虑使用模拟退火算法：

  1. 解空间特别大： 100个任务分配给10台机器；20个城市的旅行商问题；范围内的函数最值问题 无法暴力枚举的问题
  2. 可以定义评分函数： 可以明确判断两个方案哪个好 任务分配问题可以通过总耗时判断；旅行商问题可以根据路线的总时间判断；函数最值问题可以通过比较函数在不同点的值判读
  3. 可以生成邻居解： 交换随机两个任务执行的机器；随机交换旅行商路线中的两个城市；向左或向右移动随机的位置取值 均可以生成一个邻居，进而比较邻居解和当前方案
  4. 存在局部最优方案： 例如旅行商问题，当城市很多时，使用贪心算法容易陷入局部最优，而无法找到其他更优秀方案 函数最值问题，函数图像可能有多个波峰，存在局部最优
  5. 允许得到近似最优解： 模拟退火算法不保证全局最优，但能在可接受时间内得到足够好的近似解，适合问题规模大到无法求精确解的场景。

3. 模拟退火算法求解多峰函数最值#

给定一个函数： f(x)=sin⁡(x)+sin⁡(3x)+0.1x2f(x) = \sin(x) + \sin(3x) + 0.1x^2 ，求这个函数在 [0, 5]区间内的最大值。

函数图像如下： image-20260616143234870

package simulated_annealing;


import java.util.Random;


public class SimulatedAnnealingDemo {


    static Random random = new Random();


    // 定义函数（即条件2中的评分函数）
    static double target(double x){
        return Math.sin(x) + Math.sin(3 * x) + 0.1 * x * x;
    }


    // 定义扰动（即条件3中的获取邻居的方法）
    static double mutate(double curr){


        // 通过Math.min和Math.max把生成的邻居的范围限制在[0, 5]
        return Math.max(0, Math.min(curr + (random.nextDouble() - 0.5), 5));
    }




    // SA主逻辑
    public static void main(String[] args) {


        // 生成初始状态为当前状态，将当前状态的(x, y)设置为最佳状态
        double currX = random.nextDouble() * 6;
        double currY = target(currX);


        double bestX = currX;
        double bestY = currY;


        // 定义温度，最低温度阈值，冷却系数
        double temperature = 1000;
        double minTemperature = 0.0001;
        double coolingRate = 0.995;


        // 退火过程
        while (temperature > minTemperature) {


            // 调用扰动，获取当前状态的邻居态，并求解邻居态的值
            double nextX = mutate(currX);
            double nextY = target(nextX);


            double delta = nextY - currY;


            // 比较当前状态和邻居态的优劣
            if (delta > 0) {


                // 因为要求最大值，因此如果邻居态比当前状态更优，则接受
                currX = nextX;
                currY = nextY;
            } else {


                // SA的核心
                // 如果邻居态比当前状态更劣，则概率接受
                // 接收概率计算方法为：Math.exp(delta / temperature)
                double probability = Math.exp(delta / temperature);
                if (random.nextDouble() < probability) {
                    currX = nextX;
                    currY = nextY;
                }
            }


            // 如果新状态比最佳状态更好，则最佳状态替换为新的当前状态
            if (currY > bestY) {
                bestY = currY;
                bestX = currX;
            }


            // 温度降低
            temperature *= coolingRate;


            // 输出过程状态
            System.out.println(currX + " ==> " + currY);
        }


        // 输出最终结果
        System.out.printf("最优解: x = %.6f, f(x) = %.6f%n", bestX, bestY);
    }
}

运行结果如下：

5.0 ==> 2.1913635654939783
4.663310255727348 ==> 2.1650306949291216
4.932227738744374 ==> 2.247043141298705
4.8347081857352325 ==> 2.2783351972660553
4.609863083298898 ==> 2.083404663625435
4.795880597591812 ==> 2.2723253037868276
4.835759295604256 ==> 2.2783444866281934
5.0 ==> 2.1913635654939783
4.825175791571457 ==> 2.277886007069018
4.625396083392352 ==> 2.1093483021343054
... 此处省略很多行
0.6346640055673788 ==> 1.5781887948289557
0.6346640055673788 ==> 1.5781887948289557
0.6346640055673788 ==> 1.5781887948289557
0.6346640055673788 ==> 1.5781887948289557
最优解: x = 4.836988, f(x) = 2.278345
TIP

其实我们可以观察到最后结果收敛到了(0.6346640055673788, 1.5781887948289557)，通过函数图像我们观察到这并不是全局最优解，而是一个局部最优解
退火末期 currX 卡在某个局部最优附近随机抖动是正常现象，但这不影响最终结果，因为算法全程都在用 bestX/bestY 跟踪目前见过的最优解，二者要分开看，不能拿 currX 最后停留的位置去判断算法有没有找到全局最优。

4. 模拟退火算法求解二维旅行商问题#

简单描述下旅行商问题：
给定一系列城市的位置（有时候是城市间距离）, 请找出一条最短的路线，要求经过每条城市恰好一次，最终回到起点。

package simulated_annealing;


import java.util.Arrays;
import java.util.Random;


public class TravelingSalesmanProblemDemo {


    static Random random = new Random();


    // 定义城市位置
    static int[][] cities = {
            {0, 0},
            {3, 4},
            {6, 1},
            {7, 6},
            {2, 7}
    };


    // 计算城市间距离
    static double distance(int a, int b){
        int dx = cities[a][0] - cities[b][0];
        int dy = cities[a][1] - cities[b][1];
        return Math.sqrt(dx * dx + dy * dy);
    }


    // 定义函数（即条件2中的评分函数）
    static double totalDistance(int[] route){
        double total = 0;
        for (int i = 0; i < route.length - 1; i++) {
            total += distance(route[i], route[i + 1]);
        }
        total += distance(route[route.length - 1], route[0]);
        return total;
    }


    // 定义扰动（即条件3中的获取邻居的方法）
    // 此处扰动的方式是将当前路线中随机两个城市交换，生成新的路线
    static int[] mutate(int[] route){
        int[] next = route.clone();


        // 这里选择范围为random.nextInt(route.length - 1) + 1，因为 TSP 的路线本身是一个环路，起点选哪个城市不影响总距离，所以可以固定
        int i = random.nextInt(route.length - 1) + 1;
        int j = random.nextInt(route.length - 1) + 1;
        int tmp = next[i];
        next[i] = next[j];
        next[j] = tmp;
        return next;
    }


    // SA主逻辑
    public static void main(String[] args) {


        // 生成初始路线为当前状态，将当前路线和当前路线的总距离设置为最佳状态
        int[] currRoute = { 0, 1, 2, 3, 4 };
        double currDist = totalDistance(currRoute);


        int[] bestRoute = currRoute.clone();
        double bestDist = currDist;


        // 定义温度，最低温度阈值，冷却系数
        double temperature = 1000;
        double minTemperature = 0.0001;
        double coolingRate = 0.995;


        // 退火过程
        while (minTemperature < temperature){


            // 调用扰动，根据当前路线生成新的的邻居态路线，并求解邻居态的总路程
            int[] nextRoute = mutate(currRoute);
            double nextDist = totalDistance(nextRoute);


            double delta = nextDist - currDist;


            // 比较当前状态和邻居态的优劣
            if (delta < 0){


                // 因为要求最小值，因此如果邻居态的总距离比当前状态更小则是优，则接受
                currRoute = nextRoute;
                currDist = nextDist;
            } else {


                // SA的核心
                // 如果邻居态比当前状态更劣，则概率接受
                // 接收概率计算方法为：Math.exp(-delta / temperature)
                double probability = Math.exp(-delta / temperature);
                if (random.nextDouble() < probability){
                    currRoute = nextRoute;
                    currDist = nextDist;
                }
            }


            // 如果新状态比最佳状态更好，则最佳状态替换为新的当前状态
            if (currDist < bestDist){
                bestRoute = currRoute.clone();
                bestDist = currDist;
            }


            // 温度降低
            temperature *= coolingRate;
        }


        // 输出最终结果
        System.out.println("最优路线: " + Arrays.toString(bestRoute));
        System.out.println("最短距离: " + bestDist);
    }
}

运行结果如下：

最优路线: [0, 2, 3, 4, 1]
最短距离: 24.44307921765217

5. 模拟退火算法的思路#

总结上面两个例子，我们可以发现模拟退火算法的大致思路是相通的，转换为伪代码如下：

public class Demo{


    static T 扰动方法(T 当前状态){
        T 邻居态 = 随机扰动(当前状态);
        return 邻居态;
    }


    static 评分 评分方法(T 状态){
        return 评分方法的具体逻辑(状态);
    }


    public static void main(String[] args) {
        定义初始状态currX, currY = 评分方法(currX)
        定义最佳状态bestX = currX, 最佳评分bestY = currY


        定义温度T，最低温度阈值TMin，冷却系数coolingRate


        while(T > TMin){
            nextX = 扰动方法(currX);
            nextY = 评分方法(nextX);


            delta = nextY - currY;
            if (nextX 优于 currX){
                currX = nextX;
                currY = nextY;
            } else if {
                double probability = Math.exp(-delta / temperature);
                // 这里是取delta还是-delta取决于求较优的比较方向


                if (random.nextDouble() < probability){
                    currX = nextX;
                    currY = nextY;
                }
            }


            // 这里的大于小于也是取决于求较优的比较方向
            if (currY > bestY) {
                bestY = currY;
                bestX = currX;
            }
        }


        // 输出最终结果
    }
}

6. 参数调优#

模拟退火的效果很大程度上取决于三个参数：初始温度、冷却系数、终止温度。

// 定义温度，最低温度阈值，冷却系数
double temperature = 1000;
double minTemperature = 0.0001;
double coolingRate = 0.995;

1. 初始温度TT#

根据接收概率公式：P=e−ΔTP = e^{-\frac{\Delta}{T}}， 我们不难发现： 如果改变值 Δ\Delta 比当前温度 TT 相比小几个量级时，−ΔT-\frac{\Delta}{T} 趋近 0，总的P{P} 趋近 1，即几乎所有变差的邻居都会被接受。
而如果初始温度 TT 设置的和 Δ\Delta 差不多，甚至比 Δ\Delta 小，则会导致算法在刚起步时就几乎只接受比当前状态更好的邻居态，退化为普通的爬山算法。

TIP

总结：
当初始温度TT设置的较大时，算法的早期会浪费时间在随机的游走上，虽然收敛变慢但是不会影响最终求解的质量。
当初始温度TT设置的较小时，算法会在一开始很难跳出局部最优解，效率快但是可能忽略全局最优解。
实践中可以这样估算：先粗略计算一下评分函数在邻居之间的典型差值大小（比如 TSP 里交换两个城市导致的总距离变化量级），让初始温度比这个量级大上一到两个量级。

2. 冷却系数#

冷却系数控制温度下降的速度，越接近 1 降温越慢。
是否需要调整冷却系数，取决于问题规模。例子中的 TSP 只有 5 个城市，解空间很小，0.995
这个保守的降温速度完全够用；但如果城市数量上升到几十甚至上百个，解空间呈指数级增长，可能需要把冷却系数调得更接近 1（比如 0.999)，或者配合增加每个温度下的迭代次数，否则算法会过早收敛到一个较差的解。

TIP

总结：
当冷却系数设置的较大时，温度很快跌到很低，算法还没来得及探索完解空间就早早收敛，容易陷入局部最优。
当冷却系数设置的较小时，探索更充分，更可能找到全局最优，但需要更多迭代次数才能让温度降到终止阈值，运行时间显著增加。

3. 终止温度#

终止温度只是一个工程上的截断阈值，用来决定循环什么时候停止，本身没有特别的物理意义。
判断终止温度是否合理，可以看对应的接受概率:
当TT降到终止温度时， 即使Δ\Delta很小， P=e−ΔTP = e^{-\frac{\Delta}{T}}也应该已经趋近于 0， 这意味着此时算法基本只接受变好的邻居，跟普通爬山算法没有区别。如果终止温度设得过高，会导致算法在还有一定随机性的时候就提前停止，浪费了继续优化的机会。

7. 总结#

回到文章标题——从找最小值到旅行商问题，这两个例子表面上差异很大：一个在连续的实数区间里找极值，一个在离散的排列组合里找最短路径。但如果把代码并排放在一起看，会发现两者用的是完全相同的退火框架，即##5中的伪代码。
两个例子也分别暴露了 SA 在两类问题上的不同表现。函数最值问题里，在运行结果那里其实说明了一个容易被忽略的点：算法运行过程中的”当前状态”和最终输出的”最佳状态”是两回事，温度降到很低后当前状态会卡在某个点上随机抖动，但真正有意义的答案始终是过程中记录的 bestX/bestY。TSP 问题里，由于解空间是离散的排列组合，邻居的定义（交换两个城市）直接决定了搜索能到达哪些状态，这也是为什么不同问题中”如何定义邻居”往往比调参数更影响最终效果。
当然，模拟退火不是万能的。它不保证找到全局最优解，只能保证大概率找到一个足够好的近似解；它对参数（初始温度、冷却系数、终止温度）比较敏感，调得不好效果可能还不如简单的贪心算法；遇到城市数量上百的 TSP 这类大规模问题，单纯依赖一次退火过程也往往不够，通常需要结合多次重启、自适应降温，或者和遗传算法、禁忌搜索等其他启发式方法配合使用。但对于中小规模、能够明确定义评分函数和邻居关系的优化问题，模拟退火胜在实现简单、思路直观，是一个性价比很高的起点。

从找最小值到旅行商问题：模拟退火算法的 Java 实现
https://yuumiblog.com/posts/dailyknowledge/dailyknowledge01/
作者
悠米的开发笔记
发布于
2026-06-16
许可协议
CC BY-NC-SA 4.0
Astro 博客添加 Waline 评论系统，Waline 的 docker 部署
© 2026 悠米的开发笔记. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari