Local Search Algorithm in Artificial Intelligence

Local Search Algorithm in Artificial Intelligence

Local search algorithms in artificial intelligence are optimization methods that refine a candidate solution by repeatedly stepping to a stronger neighboring state. Rather than enumerating every path, they aim for efficient, practical answers to difficult problems.

• Refine solutions by moving among neighboring states
• Well suited to optimization and decision-making tasks
• Frequently applied in scheduling, routing, and machine learning

Basic Terminologies

• State: A candidate solution to the problem
• Current State: The solution under evaluation right now
• Neighbour State: A solution obtained by a small change to the current state
• Objective Function: A measure of how good a solution is
• Local Optimum: The best solution among nearby states
• Global Optimum: The best solution across the whole search space

Working

• Pick a starting point: Begin with a candidate solution—often random, sometimes rule-based.

• Find the Neighbours:

• Neighbours are similar solutions produced by small, simple edits to the current one.
• For example, in a puzzle, swapping two pieces yields a neighbour.
• Compare: Inspect all neighbors to see whether any improve on the current solution.

• Move: If a better neighbor exists, adopt it as the new current solution.

• Repeat: Continue from the new point using the same steps.

• Stop: Halt when no neighbor is better, or after a sufficient number of attempts.

Types of Local Search Algorithms

1. Hill-Climbing Search Algorithm

The hill-climbing search algorithm is a basic local search method that keeps moving to a better neighbor until further improvement is impossible.

Process:

• Start: Begin with an initial solution.
• Evaluate: Assess the neighboring solutions.
• Move: Shift to the neighbor with the highest objective value when that neighbor improves the current solution.
• Repeat: Keep going until no better neighbor remains.

Pros:

• Easy to implement.
• Works well in small or smooth search spaces.

Cons:

• May get stuck in local optima.
• Limited exploration of the search space.

import random

def f(x):
    return - (x - 3)**2 + 5

def hill_climb():
    current_x = random.uniform(0, 6)
    step_size = 0.1
    max_iterations = 100
    for i in range(max_iterations):
        neighbors = [current_x + step_size, current_x - step_size]
        neighbors = [x for x in neighbors if 0 <= x <= 6]
        neighbor_scores = [f(x) for x in neighbors]
        best_neighbor_idx = neighbor_scores.index(max(neighbor_scores))
        best_neighbor = neighbors[best_neighbor_idx]
        if f(best_neighbor) > f(current_x):
            current_x = best_neighbor
        else:
            break
    return current_x, f(current_x)

result_x, result_value = hill_climb()
print(f"Found maximum at x = {result_x:.2f}, value = {result_value:.2f}")