基于Python实现模拟退火求解百位美元挑战第4题含噪函数全局最小值的问题求助

I see you're struggling to get simulated annealing to find the global minimum of that notoriously tricky Hundred Digit Challenge function—let's break down what's going wrong with your current implementation and fix it step by step.

Key Issues in Your Current Code #

1. Mutation Function Is Too Random (Not a Proper Neighborhood Search) #

Your mutate function adds a full -4 to 4 random value each time, which is essentially a random restart rather than exploring the local neighborhood of the current point. Simulated annealing relies on small, controlled moves to balance early-stage exploration and late-stage exploitation. Jumping across the entire search space defeats the algorithm's purpose—you're basically doing random search with temperature-based acceptance, which won't efficiently navigate the function's thousands of local minima.

2. Linear Temperature Scheduling Has Predictability Issues #

While linear cooling is valid, your implementation has a subtle flaw: you calculate temp_Delta as (initial_temp - final_temp)/num_of_steps, but your loop runs until current_temp > final_temp—this might not actually execute the full num_of_steps iterations if temperature drops faster than expected. For this highly multi-modal function, linear cooling often cools too quickly in early stages, preventing the algorithm from escaping deep local minima.

3. No Adaptive Step Size #

Even when you tried smaller mutation ranges, you didn't tie the step size to the current temperature. Early on (high temp), you want larger steps to explore broadly; later (low temp), smaller steps to refine promising regions.

4. Missing Optimal Coordinate Tracking #

You only track the best_state (function value), but not the corresponding (x,y) coordinates. This makes it hard to verify if you've actually found the global minimum (which sits around f(x,y) ≈ -3.306868647 at roughly (0.02440295, 0.21061243)).

Fixed Implementation & Improvements #

Let's rewrite the critical parts to address these issues:

1. Adaptive Mutation Function #

We'll make the mutation step size scale with temperature, and use a normal distribution (instead of uniform) for more natural local exploration:

import math
import random

def mutate(x, y, current_temp, max_step=4.0):
    # Scale step size with temperature: larger steps at high temp, smaller at low temp
    step_scale = current_temp / 100  # Normalize to initial temp (100)
    step_x = random.gauss(0, max_step * step_scale)
    step_y = random.gauss(0, max_step * step_scale)
    
    # Clamp to [-4, 4] search bounds
    new_x = max(min(x + step_x, 4.0), -4.0)
    new_y = max(min(y + step_y, 4.0), -4.0)
    
    return [new_x, new_y]

Using a Gaussian distribution means most moves are small, with occasional larger jumps—perfect for balancing exploration and exploitation.

2. Refined Linear Temperature Scheduling #

Let's adjust the temperature calculation to run exactly num_of_steps iterations (more predictable) and ensure linear cooling works as intended:

def linear_cooling(initial_temp, final_temp, num_steps, step):
    return initial_temp - (initial_temp - final_temp) * (step / num_steps)

This ensures each step cools the temperature linearly from start to end over the exact number of iterations.

3. Updated Simulated Annealing Core #

We'll track the best coordinates, refine the acceptance probability logic, and integrate the adaptive mutation:

def simulated_annealing(f):
    # Initialize current state (random point in [-4,4])
    current_x = random.uniform(-4, 4)
    current_y = random.uniform(-4, 4)
    current_val = f(current_x, current_y)
    
    # Track best state (value + coordinates)
    best_val = current_val
    best_x, best_y = current_x, current_y
    
    initial_temp = 100.0
    final_temp = 0.001  # Lower final temp for better late-stage exploitation
    num_steps = 2_000_000  # More iterations to navigate the function's complexity
    
    for step in range(num_steps):
        current_temp = linear_cooling(initial_temp, final_temp, num_steps, step)
        
        # Generate neighbor with adaptive step size
        neighbor_x, neighbor_y = mutate(current_x, current_y, current_temp)
        neighbor_val = f(neighbor_x, neighbor_y)
        
        delta_e = neighbor_val - current_val
        
        # Acceptance logic
        if delta_e <= 0:
            # Accept better state
            current_x, current_y = neighbor_x, neighbor_y
            current_val = neighbor_val
            # Update best if needed
            if current_val < best_val:
                best_val = current_val
                best_x, best_y = current_x, current_y
        else:
            # Accept worse state with probability exp(-delta_e / temp)
            acceptance_prob = math.exp(-delta_e / current_temp)
            if random.uniform(0, 1) < acceptance_prob:
                current_x, current_y = neighbor_x, neighbor_y
                current_val = neighbor_val
    
    print(f"Best found: f({best_x:.8f}, {best_y:.8f}) = {best_val:.8f}")
    return best_val, best_x, best_y

4. The Noisy Function (For Reference) #

def noisy_func(x, y): 
    return (math.exp(math.sin(50*x)) + 
            math.sin(60*math.exp(y)) + 
            math.sin(70*math.sin(x)) + 
            math.sin(math.sin(80*y)) - 
            math.sin(10*(x + y)) + 
            0.25*(math.pow(x, 2) + math.pow(y, 2)))

Additional Tips for Better Results #

• Try Exponential Cooling: Once you get linear working, experiment with exponential cooling (more common for simulated annealing). The formula is current_temp = initial_temp * (alpha ** step), where alpha is between 0.999 and 0.9999 for slow cooling. This keeps the temperature higher longer, allowing more exploration of the search space.
• Add a Restart Mechanism: If the algorithm gets stuck in a local minimum, reset the current state to a random point and continue annealing with a slightly lower initial temperature.
• Tune Parameters: Play with initial/final temperature, number of iterations, and max step size. For this function, 2-5 million iterations is a good starting point to navigate its thousands of local minima.
• Noise Handling (If Applicable): If your actual function has real noise, average multiple evaluations of f(x,y) to reduce variance when calculating state values.

When you run this updated code, you should consistently get values close to the global minimum (-3.306868647). The key changes are the adaptive mutation step size, predictable linear cooling, and proper tracking of the best coordinates.

内容的提问来源于stack exchange，提问作者Harel