Applies the simulated annealing algorithm to search for an optimal solution in a large search space.

# Simulated Annealing - Optimization Heuristic # Description: Applies the simulated annealing algorithm to search for an optimal solution in a large search space. import random import math def simulated_annealing( initial_state, evaluate, neighbor, temperature=1000, cooling_rate=0.995, min_temp=0.1, max_iterations=1000 ): """ Simulated Annealing: An optimization algorithm inspired by metallurgy. This algorithm explores a search space by probabilistically accepting worse solutions to escape local optima, with decreasing probability as the "temperature" cools down. Args: initial_state (any): Starting point in the search space. evaluate (function): Measures the quality of a state (cost function). Lower cost is considered better. neighbor (function): Generates a nearby alternative state. temperature (float): Initial exploration intensity. cooling_rate (float): Rate of reducing exploration probability. min_temp (float): Stopping temperature threshold. max_iterations (int): Limit on total iterations to prevent infinite loops. Returns: tuple: (best_state, best_cost) found during the search. Key Characteristics: - Probabilistically accepts worse solutions early on - Becomes more selective as temperature decreases - Helps escape local optima in complex search spaces Time Complexity: O(max_iterations) Space Complexity: O(1) """ # Initialize the current state and its evaluation current_state = initial_state best_state = current_state current_cost = evaluate(current_state) best_cost = current_cost # Track iterations to prevent potential infinite loops iterations = 0 # Simulated annealing main loop while temperature > min_temp and iterations < max_iterations: # Generate a neighboring state candidate_state = neighbor(current_state) candidate_cost = evaluate(candidate_state) # Calculate the cost difference cost_delta = candidate_cost - current_cost # Determine if we should accept the new state # Accept better states unconditionally # Accept worse states with decreasing probability if (cost_delta < 0 or random.random() < math.exp(-cost_delta / temperature)): current_state = candidate_state current_cost = candidate_cost # Update the best state if needed if current_cost < best_cost: best_state = current_state best_cost = current_cost # Cool down the temperature temperature *= cooling_rate iterations += 1 return best_state, best_cost # Helpful example of how to use the algorithm def example_usage(): """ Example demonstrating simulated annealing for finding a near-optimal solution in a simple problem space. """ def target_sum_evaluate(state): """Evaluate how close the sum is to a target value.""" target = 15 return abs(sum(state) - target) def neighbor_generator(state): """Generate a neighboring state by slightly modifying one element.""" new_state = state.copy() index = random.randint(0, len(state) - 1) new_state[index] += random.randint(-2, 2) return new_state # Initial random state initial_state = [random.randint(1, 5) for _ in range(3)] # Run simulated annealing best_solution, best_cost = simulated_annealing( initial_state, target_sum_evaluate, neighbor_generator ) print(f"Best Solution: {best_solution}") print(f"Best Cost: {best_cost}")

Mar 28, 2025 - 04:49

Applies the simulated annealing algorithm to search for an optimal solution in a large search space.

# Simulated Annealing - Optimization Heuristic
# Description: Applies the simulated annealing algorithm to search for an optimal solution in a large search space.

import random
import math

def simulated_annealing(
    initial_state, 
    evaluate, 
    neighbor, 
    temperature=1000, 
    cooling_rate=0.995, 
    min_temp=0.1, 
    max_iterations=1000
):
    """
    Simulated Annealing: An optimization algorithm inspired by metallurgy.

    This algorithm explores a search space by probabilistically accepting 
    worse solutions to escape local optima, with decreasing probability 
    as the "temperature" cools down.

    Args:
        initial_state (any): Starting point in the search space.
        evaluate (function): Measures the quality of a state (cost function).
            Lower cost is considered better.
        neighbor (function): Generates a nearby alternative state.
        temperature (float): Initial exploration intensity.
        cooling_rate (float): Rate of reducing exploration probability.
        min_temp (float): Stopping temperature threshold.
        max_iterations (int): Limit on total iterations to prevent infinite loops.

    Returns:
        tuple: (best_state, best_cost) found during the search.

    Key Characteristics:
    - Probabilistically accepts worse solutions early on
    - Becomes more selective as temperature decreases
    - Helps escape local optima in complex search spaces

    Time Complexity: O(max_iterations)
    Space Complexity: O(1)
    """
    # Initialize the current state and its evaluation
    current_state = initial_state
    best_state = current_state
    current_cost = evaluate(current_state)
    best_cost = current_cost

    # Track iterations to prevent potential infinite loops
    iterations = 0

    # Simulated annealing main loop
    while temperature > min_temp and iterations < max_iterations:
        # Generate a neighboring state
        candidate_state = neighbor(current_state)
        candidate_cost = evaluate(candidate_state)

        # Calculate the cost difference
        cost_delta = candidate_cost - current_cost

        # Determine if we should accept the new state
        # Accept better states unconditionally
        # Accept worse states with decreasing probability
        if (cost_delta < 0 or 
            random.random() < math.exp(-cost_delta / temperature)):
            current_state = candidate_state
            current_cost = candidate_cost

            # Update the best state if needed
            if current_cost < best_cost:
                best_state = current_state
                best_cost = current_cost

        # Cool down the temperature
        temperature *= cooling_rate
        iterations += 1

    return best_state, best_cost

# Helpful example of how to use the algorithm
def example_usage():
    """
    Example demonstrating simulated annealing for finding 
    a near-optimal solution in a simple problem space.
    """
    def target_sum_evaluate(state):
        """Evaluate how close the sum is to a target value."""
        target = 15
        return abs(sum(state) - target)

    def neighbor_generator(state):
        """Generate a neighboring state by slightly modifying one element."""
        new_state = state.copy()
        index = random.randint(0, len(state) - 1)
        new_state[index] += random.randint(-2, 2)
        return new_state

    # Initial random state
    initial_state = [random.randint(1, 5) for _ in range(3)]

    # Run simulated annealing
    best_solution, best_cost = simulated_annealing(
        initial_state, 
        target_sum_evaluate, 
        neighbor_generator
    )

    print(f"Best Solution: {best_solution}")
    print(f"Best Cost: {best_cost}")