Local Search Algorithms in AI

Local Search Algorithm is an optimization technique which starts from one solution and at every step goes to a better neighbor until it cannot improve any further. It optimizes and makes decisions without exploring the whole search space. Local search algorithms are used in scheduling, routing, robotics planning, and machine learning.

In this article, we will understand what is a local search algorithm, types of local search algorithms with their Python implementation code and finally the output of benchmarking these algorithms.

What Is a Local Search Algorithm?

A local search algorithm is a heuristic algorithm where improvement of one solution occurs by evaluating and moving to another solution in the neighborhood of the solution, without forming the whole search space. In contrast to an exhaustive algorithm where all states are evaluated, a local search algorithm considers only the states accessible from its current state.

The local search algorithms are based on the following six principles.

Term	Definition
State	A possible solution to the problem
Current state	The solution being evaluated at a given step
Neighbor state	A solution created by making a small change to the current state
Objective function	A function that measures the quality of a solution
Local optimum	The best solution among a state’s immediate neighbors
Global optimum	The best possible solution across the entire search space

Local search algorithms do not provide any guarantee of finding a global optimum. In a local search algorithm, a state may be reached which is a local optimum but worse than the global optimum because only neighboring states are compared.

How Local Search Algorithms Work

The process of a local search includes the following six steps.

• Choose an initial state. The initial state is randomly selected in most cases, but there exist approaches that apply rules when selecting the initial state.
• Compute neighbors for the current state. Neighbors appear due to the application of small and specified changes to the current state.
• Calculate the value of the objective function for all neighbors.
• Compare values. The algorithm examines whether any of the neighbors has a higher value than the current state.
• Select the best neighbor as the new current state.
• Continue iterating until the stopping criteria are fulfilled. The algorithm finishes its work when there is no neighbor that is better than the current state or the maximum number of iterations is reached.

For instance, in a routing problem, the neighbor state appears due to changing the order of two points of the route. The objective function in this case takes into account the total distance traveled.

Local Search vs. Other AI Search Strategies

Local search is one of four major search strategy families used in AI. Each family differs in scope, memory use, and optimality guarantee.

Search Strategy	Scope	Memory Use	Optimality Guarantee	Typical Use Case
Local search	Neighboring states only	Low — stores current state (plus a limited history for some variants)	No — can settle at a local optimum	Large-scale optimization, scheduling, routing
Global/exhaustive search	Entire search space	High — stores multiple paths or states	Yes — finds the global optimum if one exists	Small, well-defined problems
A* search	Guided path search using a heuristic and path cost	Moderate — stores open and closed node lists	Yes, with an admissible heuristic	Pathfinding, navigation
Breadth-first / depth-first search	Systematic traversal of the full search tree	BFS: high; DFS: low	Yes, for BFS on unweighted graphs	Graph traversal, small state spaces

Local search algorithms use less memory than A*, breadth-first search, or exhaustive search, because they store only the current state and, in some variants, a short list of recently visited states. This memory efficiency is the primary reason local search algorithms scale to problems where the state space is too large to store or search exhaustively.

The 5 Types of Local Search Algorithms in AI

There are five major types of local search algorithms used in AI: Hill Climbing, Simulated Annealing, Genetic Algorithms, Tabu Search, and Random Restart / Stochastic Local Search. Each of these algorithms follows a distinct approach for balancing solution quality with processing time.

1. Hill Climbing

Hill Climbing is a type of local search algorithm that involves moving from one state to another state that is best among the neighbors of the current state. It is the most basic local search algorithm.

Process:

1. Begin with an initial solution.
2. Explore all neighboring solutions.
3. Choose the neighbor which gives a better value than the current one.
4. Repeat Step 2 until all neighbors give worse values than the current one.

Time complexity: O(i × b), where i is the number of iterations and b is the number of neighbors checked per iteration. Space complexity: O(1), because Hill Climbing requires constant space.

import random

def objective(x):

    return -(x - 3) ** 2 + 5

def hill_climbing(step_size=0.1, max_iterations=100):

    current_x = random.uniform(0, 6)

    for _ in range(max_iterations):

        neighbors = [current_x + step_size, current_x - step_size]

        neighbors = [x for x in neighbors if 0 <= x <= 6]

        best_neighbor = max(neighbors, key=objective)

        if objective(best_neighbor) > objective(current_x):

            current_x = best_neighbor

        else:

            break

    return current_x, objective(current_x)

result_x, result_value = hill_climbing()

print(f"Best solution: x={result_x:.2f}, value={result_value:.2f}")

Advantages: Hill Climbing needs very little memory and is quick for small or smooth search spaces. Limitations: Hill Climbing gets stuck at the first local optimum encountered and does not start the search process again from another position.

2. Simulated Annealing

Simulated Annealing is an iterative local search algorithm that accepts lower-value neighbors with a decreasing probability over time to help get out of local minima. The algorithm was developed by Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi was first described in a 1983 article in the journal Science.

Process:

1. Choose an initial state and an initial temperature value.
2. Compute a neighbor state.
3. If the neighbor is in a better state, accept it. Otherwise, accept it with a certain probability that depends on the current temperature.
4. Lower the temperature value using a cooling schedule.
5. Repeat until the temperature falls below a certain minimum.

Time complexity: O(i), where i is the number of iterations, since Simulated Annealing evaluates one neighbor per iteration. Space complexity: O(1).

import math

import random

def objective(x):

    return -(x - 3) ** 2 + 5

def simulated_annealing(temp=10.0, cooling_rate=0.995, min_temp=0.01):

    current_x = random.uniform(0, 6)

    best_x, best_value = current_x, objective(current_x)

    while temp > min_temp:

        candidate_x = current_x + random.uniform(-0.1, 0.1)

        candidate_x = max(0, min(6, candidate_x))

        delta = objective(candidate_x) - objective(current_x)

        if delta > 0 or random.random() < math.exp(delta / temp):

            current_x = candidate_x

            if objective(current_x) > best_value:

                best_x, best_value = current_x, objective(current_x)

        temp *= cooling_rate

    return best_x, best_value

result_x, result_value = simulated_annealing()

print(f"Best solution: x={result_x:.2f}, value={result_value:.2f}")

Advantages: Simulated Annealing is better at avoiding local optima than Hill Climbing and is capable of exploring a larger part of the search space. Disadvantages: Simulated Annealing involves tuning the starting temperature and cooling factor and yields varying outputs due to its probabilistic acceptance method.

3. Genetic Algorithms

Genetic Algorithm is an example of a local search algorithm which generates an evolving population of candidate solutions across many generations through selection, crossover, and mutation. The genetic algorithm was developed by John Holland and first appeared in the book Adaptation in Natural and Artificial Systems (1975) by the University of Michigan Press.

Process:

1. Generate a random initial population of candidate solutions.
2. Calculate fitness of all candidates via the objective function.
3. Choose the fittest candidates for breeding.
4. Crossover selected pairs of candidates to generate offspring.
5. Mutation of the offspring introduces variation.
6. Create a new generation from the offspring.

Time complexity: O(g × p), where g is the number of generations and p is the population size. Space complexity: O(p), since the algorithm stores the entire population at each generation.

import random

def fitness(x):

    return -(x - 3) ** 2 + 5

def genetic_algorithm(pop_size=20, generations=50):

    population = [random.uniform(0, 6) for _ in range(pop_size)]

    for _ in range(generations):

        scores = [fitness(x) for x in population]

        best = population[scores.index(max(scores))]

        new_population = [best]

        while len(new_population) < pop_size:

            p1, p2 = random.sample(population, 2)

            child = (p1 + p2) / 2

            if random.random() < 0.3:

                child += random.uniform(-0.2, 0.2)

            child = max(0, min(6, child))

            new_population.append(child)

        population = new_population

    scores = [fitness(x) for x in population]

    best = population[scores.index(max(scores))]

    return best, fitness(best)

result_x, result_value = genetic_algorithm()

print(f"Best solution: x={result_x:.2f}, value={result_value:.2f}")

Advantages: Genetic Algorithms consider multiple parts of the solution space simultaneously and solve problems that are high-dimensional and nonlinear.  Limitations: Genetic Algorithms need to be tuned for their population size, mutation probability, and selection method.

4. Tabu Search

Tabu Search is a local search algorithm that utilizes a memory list of recently visited solutions to avoid visiting the same solutions again. The concept of Tabu Search was developed by Fred Glover in 1986 in his paper titled “Future Paths for Integer Programming and Links to Artificial Intelligence” in Computers & Operations Research.

Process:

1. Start with an initial solution and an empty tabu list.
2. Create neighboring solutions but exclude any solution present in the tabu list.
3. Move to the best non-tabu neighbor.
4. Put the previous solution in the tabu list while deleting the oldest one when the list exceeds its capacity.
5. Permit tabu-listed moves in case the move gives a better solution than the current best solution (aspiration criterion).
6. Repeat until the termination criteria is met.

Time complexity: O(i × b), where i is the number of iterations and b is the number of neighbors evaluated per iteration. Space complexity: O(t), where t is the size of the tabu list.

import random

def objective(x):

    return -(x - 3) ** 2 + 5

def tabu_search(step_size=0.1, tabu_size=5, max_iterations=100):

    current_x = random.uniform(0, 6)

    best_x, best_value = current_x, objective(current_x)

    tabu_list = []

    for _ in range(max_iterations):

        neighbors = [current_x + step_size, current_x - step_size]

        neighbors = [x for x in neighbors if 0 <= x <= 6 and x not in tabu_list]

        if not neighbors:

            break

        best_neighbor = max(neighbors, key=objective)

        if objective(best_neighbor) > best_value:

            best_x, best_value = best_neighbor, objective(best_neighbor)

        tabu_list.append(current_x)

        if len(tabu_list) > tabu_size:

            tabu_list.pop(0)

        current_x = best_neighbor

    return best_x, best_value

result_x, result_value = tabu_search()

print(f"Best solution: x={result_x:.2f}, value={result_value:.2f}")

Advantages: Tabu Search decreases the risk of cycling through the same states and performs better in exploring larger search spaces compared to Hill Climbing.  Limitations: The Tabu Search algorithm needs careful handling of the tabu-list size and aspiration condition and has a higher computational expense per iteration compared to Hill Climbing.

5. Random Restart and Stochastic Local Search

Random Restart Local Search executes the basic local search procedure, like Hill Climbing, multiple times starting from different random initial states and returns the best solution found through all the executions. Stochastic Local Search incorporates randomness in the process of selecting the neighbors themselves and is not based solely on the objective function value.

Process:

1. Execute the basic local search procedure starting from a random initial state.
2. Store the solution obtained and its value.
3. Repeat starting from a new random initial state a predetermined number of times.
4. Return the best solution among all solutions obtained through the above steps.

def random_restart_hill_climbing(restarts=10):

    best_solution, best_value = None, float("-inf")

    for _ in range(restarts):

        x, value = hill_climbing()

        if value > best_value:

            best_solution, best_value = x, value

    return best_solution, best_value

Advantages: Random Restart lowers the probability of ending up with a bad local minimum solution and does not involve any modifications to the basic algorithm. Limitations: Random Restart increases the computational complexity as it is multiplied by the number of restarts and relies heavily on the number of restarts performed.

Local Search Algorithm Benchmark: Real Results on a 25-City Routing Problem

Below is the outcome of benchmarking this article, and not from any third party. In the benchmark, 25 cities are randomly placed on a 100 by 100 grid (same random seed for reproducibility purposes) and all four algorithms are run on the exact same Traveling Salesman Problem. For the Hill Climbing and Tabu Search algorithm, the 2-opt neighborhood is used with 300 neighboring candidates per step (for 25 cities).

Algorithm	Best Distance Found	Iterations	Solution Evaluations	Time (seconds)
Hill Climbing	386.71	22	6,600	0.052
Simulated Annealing	387.43	1,838	1,838	0.015
Genetic Algorithm	489.05	200 generations	12,000	0.133
Tabu Search	386.71	2,000	600,000	4.252
Nearest-neighbor baseline (non-local-search heuristic)	485.77	—	—	—

There are three findings that can be derived directly from the above data.

Both Hill Climbing and Tabu Search found the same tour length of 386.71 for this particular case, meaning both algorithms found the same local optimum. It took Hill Climbing just 22 iterations to achieve this result, while for Tabu Search it took the maximum allowed number of 2,000 iterations, which made Hill Climbing faster when obtaining an equivalent result for this problem size.

Simulated Annealing returned a very similar value of 387.43 in 1,838 iterations, however, in this case each iteration evaluated just one candidate, making Simulated Annealing the most efficient algorithm of all four in terms of evaluations needed (1,838) and time (0.015 seconds).

Genetic Algorithm generated the worst result (489.05), beating even the nearest neighbor approach (485.77) in terms of tour length. It illustrates a well-known weakness of Genetic Algorithms, in which solution quality strongly depends on population size, mutation rate and number of generations, and by default cannot compete with simpler local search approaches in quality.

Where Local Search Algorithms Are Used in AI Systems

Local search algorithms apply in six different domains in artificial intelligence and operations research: 

• Scheduling & Planning: Local search algorithms construct timetables, exam schedules, and job shop schedules while avoiding conflicts. An airline crew scheduling algorithm uses local search to create duty schedules using availability and compliance with regulations.
• Routing: Local search algorithms tackle problems of vehicle routing and the Traveling Salesman Problem by switching around stop order to lower travel distances.
• Resource allocation: Local search algorithms allocate restricted resources like machines, rooms, or workers to tasks to minimize costs and delays.
• Robotics: Local search algorithms plan robot motion and routes, updating them when new obstacles or priorities arise.
• Game AI: Local search algorithms consider moves in games like chess where offensive and defensive positioning must be balanced under time constraint.
• Machine learning: Local search algorithms tune model parameters like the learning rate and strength of the regularization.

Local Search in 2026 AI Systems

Local search principles extend into two areas of current AI system design.

LLM agent planning loops. Autonomous AI agents that utilize large language models for planning their multi-step tasks select an action, assess the result of this action, and modify the next action according to the outcome. This sequence of actions, evaluation, and revision of the next step repeats the same cycle as the local search loop discussed in this article previously.

Beam search in LLM token decoding. The algorithm used by most large language models to decode the output tokens is called beam search; it maintains a limited number of highest scoring candidate sequences at each decoding step while abandoning all other candidates. Beam search operates similarly to the local search algorithm with regard to the key idea of evaluation of nearby states and retaining the best of them, although it processes several candidates at once.

Advantages and Limitations of Local Search Algorithms

Advantages:

• Local search techniques need less memory compared to exhaustive search approaches because many versions keep only the current state.
• Local search strategies generate solutions within a short time period even for large-scale search domains like scheduling scenarios involving thousands of states.
• Local search strategies can be employed in real-life optimization scenarios where calculating the best solution is practically impossible due to computation complexity.

Limitations:

• Local search algorithms might stop at a local optimum, which is an optimum solution where the route cannot be improved by making any single-stop exchange yet is not the optimal route in its entirety.
• Local search algorithms will not lead to a global optimum.
• The performance of local search algorithms is dependent on the starting state, so the results can differ from one run to another.
• There are some local search algorithms like Simulated Annealing and Genetic Algorithms which need to be tuned before they give reliable results.

Frequently Asked Questions