爬山算法（Hill Climbing）是最经典的局部搜索算法之一，以其简洁的实现和直观的思想广泛应用于函数优化、组合优化、机器学习超参数调优等领域。本文用Java实现多种爬山算法变体，包括最陡上升、随机重启和模拟退火融合策略。
一、算法原理
1.1 基本思想
爬山算法模拟登山过程：从当前解出发，在其邻域中寻找更优的解，如果找到则移动到该解，重复此过程直到无法找到更优解为止。
1.2 算法变体
- 简单爬山（Simple Hill Climbing）：选择第一个更优的邻居
- 最陡上升爬山（Steepest-Ascent Hill Climbing）：选择所有邻居中最优的一个
- 随机重启爬山（Random-Restart Hill Climbing）：多次从不同初始点出发，取最优结果
- 随机爬山（Stochastic Hill Climbing）：以概率选择更好的邻居
1.3 局限性
爬山算法容易陷入局部最优。随机重启和模拟退火是常用的改进策略。
二、Java实现
import java.util.*;
import java.util.function.Function;
/**
* 爬山算法系统实现
* 支持多种变体：简单爬山、最陡上升、随机重启
*/
public class HillClimbing {
private final Random random = new Random(42);
/**
* 解的表示接口
*/
public interface Solution {
double evaluate();
List<Solution> getNeighbors();
Solution copy();
}
/**
* N皇后问题的解表示
*/
public static class NQueensSolution implements Solution {
private final int[] queens; // queens[i]表示第i行皇后所在的列
private final int n;
private double cachedScore = Double.NaN;
public NQueensSolution(int n) {
this.n = n;
this.queens = new int[n];
}
public NQueensSolution(int[] queens) {
this.queens = queens.clone();
this.n = queens.length;
}
public static NQueensSolution random(int n, Random rand) {
NQueensSolution sol = new NQueensSolution(n);
for (int i = 0; i < n; i++) {
sol.queens[i] = rand.nextInt(n);
}
return sol;
}
/**
* 评估函数：冲突数越少越好
* 返回负的冲突数（越大越好）
*/
@Override
public double evaluate() {
if (!Double.isNaN(cachedScore)) {
return cachedScore;
}
int conflicts = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 检查是否在同一列或对角线
if (queens[i] == queens[j] ||
Math.abs(queens[i] - queens[j]) == Math.abs(i - j)) {
conflicts++;
}
}
}
cachedScore = -conflicts; // 冲突越少，分数越高
return cachedScore;
}
@Override
public List<Solution> getNeighbors() {
List<Solution> neighbors = new ArrayList<>();
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
if (col != queens[row]) {
NQueensSolution neighbor = new NQueensSolution(queens);
neighbor.queens[row] = col;
neighbors.add(neighbor);
}
}
}
return neighbors;
}
@Override
public Solution copy() {
return new NQueensSolution(queens);
}
public boolean isOptimal() {
return evaluate() == 0; // 无冲突
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sb.append(queens[i] == j ? "Q " : ". ");
}
sb.append("\n");
}
sb.append("冲突数: ").append((int)(-evaluate()));
return sb.toString();
}
}
/**
* 简单爬山算法
* 找到第一个更优邻居就移动
*/
public Solution simpleHillClimbing(Solution initial, int maxIterations) {
Solution current = initial.copy();
double currentScore = current.evaluate();
for (int iter = 0; iter < maxIterations; iter++) {
List<Solution> neighbors = current.getNeighbors();
boolean improved = false;
for (Solution neighbor : neighbors) {
double neighborScore = neighbor.evaluate();
if (neighborScore > currentScore) {
current = neighbor.copy();
currentScore = neighborScore;
improved = true;
break; // 找到第一个更优解就移动
}
}
if (!improved) {
break; // 到达局部最优
}
}
return current;
}
/**
* 最陡上升爬山算法
* 选择所有邻居中最优的一个
*/
public Solution steepestAscentHillClimbing(Solution initial, int maxIterations) {
Solution current = initial.copy();
double currentScore = current.evaluate();
for (int iter = 0; iter < maxIterations; iter++) {
List<Solution> neighbors = current.getNeighbors();
Solution bestNeighbor = null;
double bestScore = currentScore;
for (Solution neighbor : neighbors) {
double neighborScore = neighbor.evaluate();
if (neighborScore > bestScore) {
bestScore = neighborScore;
bestNeighbor = neighbor.copy();
}
}
if (bestNeighbor == null) {
break; // 到达局部最优
}
current = bestNeighbor;
currentScore = bestScore;
}
return current;
}
/**
* 随机重启爬山算法
* 多次从随机初始解出发，返回最优结果
*/
public Solution randomRestartHillClimbing(
Function<Random, Solution> generator,
int restarts,
int maxIterationsPerRun) {
Solution bestOverall = null;
double bestScore = Double.NEGATIVE_INFINITY;
for (int run = 0; run < restarts; run++) {
Solution initial = generator.apply(random);
Solution result = steepestAscentHillClimbing(initial, maxIterationsPerRun);
double score = result.evaluate();
if (score > bestScore) {
bestScore = score;
bestOverall = result.copy();
}
// 如果找到最优解，提前结束
if (bestScore >= 0) {
break;
}
}
return bestOverall;
}
/**
* 随机爬山算法
* 以概率选择更好的邻居，增加探索性
*/
public Solution stochasticHillClimbing(Solution initial, int maxIterations, double temperature) {
Solution current = initial.copy();
double currentScore = current.evaluate();
for (int iter = 0; iter < maxIterations; iter++) {
List<Solution> neighbors = current.getNeighbors();
// 按分数加权随机选择
List<Solution> betterNeighbors = new ArrayList<>();
List<Double> scores = new ArrayList<>();
double totalWeight = 0;
for (Solution neighbor : neighbors) {
double score = neighbor.evaluate();
if (score > currentScore) {
betterNeighbors.add(neighbor.copy());
double weight = Math.exp((score - currentScore) / temperature);
scores.add(weight);
totalWeight += weight;
}
}
if (betterNeighbors.isEmpty()) {
break; // 局部最优
}
// 轮盘赌选择
double r = random.nextDouble() * totalWeight;
double cumulative = 0;
int selected = 0;
for (int i = 0; i < betterNeighbors.size(); i++) {
cumulative += scores.get(i);
if (cumulative >= r) {
selected = i;
break;
}
}
current = betterNeighbors.get(selected);
currentScore = current.evaluate();
}
return current;
}
/**
* 首先选择法（First-Choice Hill Climbing）
* 随机采样邻居，接受第一个更优解
* 适合邻居数量巨大的情况
*/
public Solution firstChoiceHillClimbing(Solution initial, int maxIterations, int samplesPerIter) {
Solution current = initial.copy();
double currentScore = current.evaluate();
for (int iter = 0; iter < maxIterations; iter++) {
boolean improved = false;
for (int s = 0; s < samplesPerIter; s++) {
// 随机采样一个邻居
List<Solution> neighbors = current.getNeighbors();
Solution randomNeighbor = neighbors.get(random.nextInt(neighbors.size()));
double neighborScore = randomNeighbor.evaluate();
if (neighborScore > currentScore) {
current = randomNeighbor.copy();
currentScore = neighborScore;
improved = true;
break;
}
}
if (!improved) {
break;
}
}
return current;
}
/**
* 连续函数优化的爬山算法（以Rosenbrock函数为例）
*/
public static class ContinuousSolution implements Solution {
private final double[] x;
private final Function<double[], Double> objective;
private final double stepSize;
public ContinuousSolution(double[] x, Function<double[], Double> objective, double stepSize) {
this.x = x.clone();
this.objective = objective;
this.stepSize = stepSize;
}
@Override
public double evaluate() {
return objective.apply(x);
}
@Override
public List<Solution> getNeighbors() {
List<Solution> neighbors = new ArrayList<>();
Random rand = new Random();
for (int i = 0; i < x.length; i++) {
// 正负两个方向
for (int sign = -1; sign <= 1; sign += 2) {
double[] newX = x.clone();
newX[i] += sign * stepSize;
neighbors.add(new ContinuousSolution(newX, objective, stepSize));
}
}
// 添加随机扰动邻居
for (int k = 0; k < 5; k++) {
double[] newX = x.clone();
for (int i = 0; i < x.length; i++) {
newX[i] += (rand.nextDouble() - 0.5) * 2 * stepSize;
}
neighbors.add(new ContinuousSolution(newX, objective, stepSize));
}
return neighbors;
}
@Override
public Solution copy() {
return new ContinuousSolution(x, objective, stepSize);
}
public double[] getX() {
return x.clone();
}
}
/**
* Rosenbrock测试函数（香蕉函数）
* 全局最小值在(1,1)，f(1,1)=0
*/
public static double rosenbrock(double[] x) {
double a = 1.0, b = 100.0;
double term1 = Math.pow(a - x[0], 2);
double term2 = b * Math.pow(x[1] - x[0] * x[0], 2);
return -(term1 + term2); // 取负转化为最大化问题
}
public static void main(String[] args) {
HillClimbing hc = new HillClimbing();
// === N皇后问题测试 ===
System.out.println("=== N皇后问题 (n=8) ===\n");
int n = 8;
// 简单爬山
System.out.println("--- 简单爬山 ---");
NQueensSolution initial = NQueensSolution.random(n, hc.random);
Solution simpleResult = hc.simpleHillClimbing(initial, 1000);
System.out.println(simpleResult);
// 最陡上升
System.out.println("\n--- 最陡上升爬山 ---");
Solution steepResult = hc.steepestAscentHillClimbing(
NQueensSolution.random(n, hc.random), 1000);
System.out.println(steepResult);
// 随机重启
System.out.println("\n--- 随机重启爬山 (10次重启) ---");
Solution rrResult = hc.randomRestartHillClimbing(
r -> NQueensSolution.random(n, r), 10, 1000);
System.out.println(rrResult);
// 首先选择
System.out.println("\n--- 首先选择爬山 ---");
Solution fcResult = hc.firstChoiceHillClimbing(
NQueensSolution.random(n, hc.random), 1000, 20);
System.out.println(fcResult);
// === 连续函数优化测试 ===
System.out.println("\n\n=== Rosenbrock函数优化 ===");
ContinuousSolution contInitial = new ContinuousSolution(
new double[]{-1.0, -1.0}, HillClimbing::rosenbrock, 0.1);
System.out.println("初始点: (" + contInitial.getX()[0] + ", " + contInitial.getX()[1] + ")");
System.out.println("初始值: " + contInitial.evaluate());
Solution contResult = hc.steepestAscentHillClimbing(contInitial, 1000);
double[] finalX = ((ContinuousSolution) contResult).getX();
System.out.println("最优解: (" + String.format("%.6f", finalX[0]) + ", " +
String.format("%.6f", finalX[1]) + ")");
System.out.println("最优值: " + String.format("%.6f", contResult.evaluate()));
}
}
三、复杂度分析
| 算法变体 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 简单爬山 | O(I × N) | O(1) | 容易陷入局部最优 |
| 最陡上升 | O(I × N) | O(N) | 需要评估所有邻居 |
| 随机重启 | O(R × I × N) | O(1) | R为重启次数，逃脱局部最优 |
| 首先选择 | O(I × S) | O(1) | S为每轮采样数，适合大邻域 |
| 随机爬山 | O(I × N) | O(N) | 增加随机性，平衡探索与开发 |
其中I为最大迭代次数，N为邻居数量，R为重启次数。
四、应用场景
- 组合优化：旅行商问题、调度问题、装箱问题的近似求解
- 函数优化：机器学习损失函数最小化、参数调优
- N皇后问题：经典的约束满足问题
- 电路设计：逻辑最小化、布局优化
- 超参数优化：网格搜索的替代方案
五、总结
本文系统实现了爬山算法的多种变体，并以N皇后问题和Rosenbrock函数为例进行了测试。爬山算法虽然简单，但在实际问题中非常有效，尤其是配合随机重启策略后，可以显著提高找到全局最优的概率。理解局部搜索算法的特性，有助于在工程实践中选择合适的优化策略。
