Repository navigation
Module 4a ‐ Local Search Optimization
In traditional search algorithms (such as Breadth-First Search, Depth-First Search, or
Conversely, a major class of optimization problems in Artificial Intelligence focuses strictly on finding a valid final state that satisfies a set of domain constraints or optimizes a given objective function. In these State Search (or Configuration Search) problems, the sequence of actions or transitions used to reach the goal state is entirely irrelevant. The search algorithm does not retain or evaluate the trajectory through the search space; it evaluates only the structural quality and validity of candidate configurations
-
Solution Representation: An ordered sequence of actions
$\langle a_1, a_2, \dots, a_k \rangle$ leading from initial state$s_0$ to goal state$s_g$ . -
Evaluation Metric: Path cost function
$g(n) = \sum\limits_{i=1}^{k} c(s_{i-1}, a_i, s_i)$ , where$c(s_{i-1}, a_i, s_i)$ represents the step cost of executing action$a_i$ . - Primary Objective: Answering the question "How do we get to an optimal goal state from the starting state?"
- Memory Requirement: Algorithms must maintain path histories (e.g., frontier queues or tree nodes) to reconstruct the action sequence upon termination.
-
Solution Representation: A single state configuration
$s \in S$ representing a complete assignment of values to system variables. -
Evaluation Metric: Objective function
$f(s)$ or heuristic evaluation function$h(s)$ assessing state quality or constraint satisfaction. - Primary Objective: Answering the question "What does an optimal or valid state configuration look like?"
- Memory Requirement: Search algorithms operate directly on candidate states, typically storing only the current state (and potentially a small neighborhood), eliminating the need for search tree maintenance.
To formally specify a configuration problem in local search optimization, we define the mathematical components governing the state space and evaluation criteria.
A configuration problem is formally defined by a triple
-
State Space (
$S$ ): The set of all possible complete encodings representing candidate configurations of the system. -
Goal Test ($G(s)$): A boolean function
$G: S \to {0, 1}$ that evaluates whether a given state$s \in S$ satisfies all mandatory domain constraints:
-
Objective / Heuristic Function (
$f(s)$ or$h(s) $ ): A real-valued function$f: S \to \mathbb{R}$ mapping each state$s$ to a quantitative score. In minimization problems (such as constraint violation counting),$h(s)$ quantifies the degree of conflict in configuration$s$ , where$h(s) = 0$ indicates a fully valid solution:
Unlike classical path search models, configuration formulations do not include an explicit path cost function
The choice of state encoding directly influences the size of the state space
Consider the classic 8-Queens problem to place
To optimize this representation, we apply domain knowledge: since no valid solution can contain two queens in the same column, we construct a compact array representation
This array encoding guarantees exactly one queen per column by design, completely excluding duplicate column placements.
To compute the size of the reduced state space
Complexity Intuition: Although the compact array encoding reduces the search space by a factor of over
-
Configuration Vector:
$\overrightarrow{s} = [r_1, r_2, \dots, r_8]^T \in {1, \dots, 8}^8$ . - Constraint: No two queens may attack each other along rows, columns, or diagonals.
-
Objective Function
$h(s)$ : Number of pairs of queens attacking each other. A pair$(i, j)$ with$1 \le i < j \le 8$ is in conflict if:
-
Goal Condition: Find
$s^*$ such that$h(s^*) = 0$ .
-
Input: An undirected graph
$G = (V, E)$ with vertex set$V = {v_1, v_2, \dots, v_n}$ and edge set$E$ , alongside a color palette$C = {1, 2, \dots, k}$ . -
Configuration State: A mapping vector
$\overrightarrow{c} = [c_1, c_2, \dots, c_n]^T \in C^n$ , assigning color$c_i \in C$ to vertex$v_i$ . - Adjacency Constraint: No two adjacent vertices may share the same color.
- Objective Function: Count of monochromatic edges (conflict edges):
where
-
Variables: Course sections
$U = {u_1, u_2, \dots, u_m}$ , classrooms$R = {r_1, r_2, \dots, r_p}$ , and time slots$T = {t_1, t_2, \dots, t_q}$ . -
Configuration State: An assignment mapping tuple
$\overrightarrow{s}_i = (r_j, t_k)$ for each course section$u_i$ . -
Constraints:
-
Room Capacity & Non-Overlap: No two large courses assigned to the same room
$r_j$ at time$t_k$ . - Instructor Allocation: Instructors cannot be double-booked across multiple locations simultaneously.
-
Cohort Non-Overlap: Mandatory courses for the same student academic year must not conflict in time slot
$t_k$ .
-
Room Capacity & Non-Overlap: No two large courses assigned to the same room
-
Goal: Discover a complete schedule assignment satisfying all hard constraints (
$h(s) = 0$ ).
The abstract mathematical structure of configuration search directly mirrors major industrial optimization challenges in computer systems and operational engineering.
In modern data centers, cloud orchestrators must assign thousands of virtual machines (VMs) and containerized microservices to physical host servers containing multi-core CPU and GPU clusters.
-
Configuration State: Mapping vector
$\overrightarrow{m}$ , where$m_i$ designates the physical host node assigned to task$i$ . -
Constraints & Objectives:
- Avoid overloading physical host CPU/RAM capacity.
- Minimize network latency by co-locating interdependent tasks.
- Minimize overall cluster energy consumption by consolidating workloads onto fewer host nodes.
Logistics platforms optimize fleet delivery operations originating from central distribution warehouses.
- Configuration State: Assignment matrix specifying driver-to-route pairings, package staging orders inside trucks, and distribution center staging schedules.
-
Constraints & Objectives:
- Time-window constraints (e.g., guaranteed delivery before 12:00 PM).
- Vehicle capacity, refrigerated cargo ordering, and driver shift hour limits.
- Minimize multi-objective route cost, factoring in distance, traffic congestion, and fuel consumption.
Cellular base stations and Wi-Fi access points must assign radio channel frequencies to transmitters to maximize throughput across geographical coverage regions.
-
Configuration State: Frequency channel assignment vector
$\overrightarrow{f}$ mapping frequency channels to transmitters. -
Structural Isomorphism: This problem is structurally isomorphic to the Graph Coloring Problem, where base stations correspond to vertices
$V$ , potential signal interference regions correspond to edges$E$ , and radio frequency channels correspond to colors$C$ . - Objective: Allocate non-interfering channel frequencies to neighboring transmitters while ensuring fair bandwidth distribution across the network.
Traditional search algorithms (e.g., Breadth-First Search, Depth-First Search,
In contrast, local search algorithms operate under a single-state model. Rather than expanding a search tree, local search evaluates and modifies a single complete candidate configuration
-
Space Complexity: The memory required is
$O(1)$ relative to the search depth, as the algorithm only stores the current state$\overrightarrow{s}$ (and optionally its immediate neighbors or best-known state). -
Path Irrelevance: Intermediate transitions used to reach a state are discarded. Search progression relies entirely on the evaluation of candidate configurations via an objective function
$f(\overrightarrow{s})$ or heuristic function$h(\overrightarrow{s})$ .
Local search moves through the state space by exploring the neighborhood of the current state
A neighborhood function
At each iteration
where
Hill Climbing (also referred to as Greedy Local Search or Steepest-Ascent / Steepest-Descent) is the foundational local search procedure. It continually moves in the direction of increasing quality (or decreasing cost).
-
Initialization: Generate an initial complete configuration
$\overrightarrow{s}_0 \in S$ (typically generated at random). -
Neighborhood Evaluation: Construct the full neighborhood
$N(\overrightarrow{s})$ . Evaluate the objective function$h(\overrightarrow{s}')$ for all$\overrightarrow{s}' \in N(\overrightarrow{s})$ . -
Greedy Move Selection: Find the neighbor
$\overrightarrow{s}^* \in N(\overrightarrow{s})$ that yields the maximum improvement over$h(\overrightarrow{s})$ .-
For a minimization problem (where
$h(\overrightarrow{s})$ measures constraint violations or cost):$$\overrightarrow{s}^* = \underset{\overrightarrow{s}' \in N(\overrightarrow{s})} {\mathrm{argmax}}~h(\overrightarrow{s}')$$
-
-
Termination Criterion:
- If
$h(\overrightarrow{s}^*) < h(\overrightarrow{s}) $ , set$\overrightarrow{s} \leftarrow \overrightarrow{s}^*$ and repeat from Step 2. - If
$h(\overrightarrow{s}^*) \ge h(\overrightarrow{s}) $ , terminate search and return$\overrightarrow{s}$ as a local optimum.
- If
function HILL-CLIMBING(problem) returns a state that is a local optimum
current = MAKE-NODE(problem.INITIAL-STATE)
loop do
neighbor = HIGHEST-VALUED-NEIGHBOR(current)
if VALUE(neighbor) <= VALUE(current) then return VALUE(current)
current = neighbor
Recall the compact array representation
The evaluation metric
The standard neighborhood operator for the 8-Queens problem generates a neighbor by picking a single column
For any state
At each step, Hill Climbing evaluates all
If the current state has
In the Traveling Salesman Problem (TSP) extended for fleet logistics, a vehicle starts and ends at a central warehouse while visiting a set of
Unlike pure constraint satisfaction problems where any valid state is equivalent, TSP is a quantitative optimization problem where configurations differ in overall quality and route cost. Real-world extensions incorporate multi-objective penalties:
-
Dynamic Traffic & Travel Time: Time-dependent travel costs
$c_{ij}(t)$ between location$i$ and location$j$ . -
Time Windows: Delivery must occur within specified interval
$[t_{\text{start}}, t_{\text{end}}]$ . - Road & Vehicle Constraints: One-way streets, vehicle load capacities, and perishable goods rules (e.g., refrigerated trucks delivering perishable items first).
The total objective cost function
where
Given a route configuration
-
Pairwise Swap Operator (2-Opt Vertex Swap): Select two delivery stops in the route and swap their positions.
$$\overrightarrow{s} = (A, B, C, D, E, A) \implies \overrightarrow{s}' = (A, E, C, D, B, A)$$ -
Segment Reversal Operator (2-Opt Edge Sub-route Inversion): Select a contiguous sub-path and reverse the sequence of stops.
$$\overrightarrow{s} = (A, B, C, D, E, A) \implies \overrightarrow{s}' = (A, D, C, B, E, A)$$ -
Insertion Operator: Remove a stop from its current position and insert it into a different location in the sequence.
$$\overrightarrow{s} = (A, B, C, D, E, A) \implies \overrightarrow{s}' = (A, C, D, B, E, A)$$
The neighbor route
The execution of local search can be conceptualized as navigating a multi-dimensional objective surface (landscape) where elevation corresponds to the evaluation function
A local optimum (local maximum for maximization, local minimum for minimization) is a state
while there exists a global optimum
Because standard Hill Climbing evaluates only immediate neighbors
A plateau is a region of the search landscape where neighboring states share identical evaluation values:
- Flat Local Maxima / Minima: A plateau that sits higher or lower than surrounding regions.
- Shoulder: A flat region that eventually connects to an ascending slope.
On a plateau, the gradient of the objective function vanishes (
A ridge is a topography where the search landscape slopes upwards along a direction that does not align with the individual coordinate moves defined by the neighborhood operator
To ascend a narrow ridge, an agent must take a sequence of non-greedy or multi-step intermediate moves—such as moving slightly downhill or sideways along one dimension before climbing along another. Because standard Hill Climbing strictly forbids moves that do not yield an immediate improvement (
Basic hill climbing offers extreme computational and memory efficiency, operating in
Understanding why standard hill climbing fails requires analyzing the interplay between local vision and global topography. Because local search evaluates state quality strictly within an immediate neighborhood
A local maximum (or local minimum in conflict-minimization problems) is a state
while there exists some global optimum
The lecture illustrates this limitation using the Fog Analogy: imagine a climber attempting to reach the highest mountain peak in a dense fog. The climber can only test terrain within a single step radius. Upon reaching the summit of a minor hill, every immediate step in all
A plateau (or flat region) is a subset of states
Plateaus severely impair local search in two ways:
- Flat Local Maxima: A plateau that sits higher than all surrounding non-plateau neighbors, from which no strictly improving move exists.
-
Shoulders: A flat region that eventually leads to an upward slope. Standard hill climbing cannot distinguish a shoulder from a flat local maximum because every adjacent state yields an identical score change (
$\Delta h = 0$ ). As a result, standard steepest-ascent search either halts prematurely or wanders aimlessly without direction.
A ridge is a narrow sequence of elevated states surrounded by steep downward drops in primary coordinate directions. To navigate along a ridge toward its apex, the optimal trajectory often requires moving diagonally or making a sequence of temporary non-greedy or multi-step coordinate modifications.
Because standard single-variable neighbor generators modify one variable at a time (e.g., moving a single queen in one column or swapping two TSP stops), every immediate 1-step neighbor off the current ridge point drops strictly downhill. Basic hill climbing refuses to accept intermediate downhill moves (
To prevent search paralysis, local search algorithms balance exploitation (aggressively climbing local gradients) with exploration (sampling diverse, unexplored regions of
Random-Restart Hill Climbing conducts a series of independent hill-climbing searches, each initialized from a uniformly sampled random state
Let
Assuming independent and identically distributed (i.i.d.) random restarts, the probability of failing to reach the global optimum in
As
If
When the neighborhood size
First-Choice Hill Climbing optimizes per-iteration evaluation cost by sampling neighbors sequentially in random order. It immediately accepts and moves to the first generated neighbor
This strategy reduces the average neighbor evaluation cost from
Unlike standard steepest-ascent hill climbing (which deterministically picks the absolute best neighbor) or first-choice search (which takes the first improving neighbor), Stochastic Hill Climbing evaluates all improving neighbors
The selection probability
By maintaining greedy bias toward steeper slopes while introducing selection randomness, Stochastic Hill Climbing avoids committing prematurely to a single local trajectory, improving performance on rugged terrains.
To navigate plateaus and shoulders, Sideways Move Hill Climbing relaxes the strict improvement condition, permitting transitions to neighboring states with equal objective values (
If a plateau is a flat local maximum without any adjacent upward slopes, allowing unrestricted sideways moves causes the search to wander infinitely in an
To enforce algorithmic termination and convergence, a maximum allowable consecutive sideways step limit
In empirical benchmarks (e.g., 8-Queens), allowing up to
When local adjustments are insufficient, metaheuristic frameworks introduce advanced mechanisms such as population memory, temperature-guided stochastic acceptance, tabu memory, and parallel beam tracking.
Rather than maintaining a single state vector
In Genetic Algorithms (GA), new candidate configurations are created by combining pieces of high-fitness parents through crossover (recombination) and applying random mutation:
-
Selection: Parents are chosen from
$P_t$ biased by fitness score$f(\overrightarrow{s})$ . -
Crossover (Recombination): Sub-structures of two parent vectors
$\overrightarrow{s}_A$ and$\overrightarrow{s}_B$ are spliced to form offspring$\overrightarrow{s}_{\text{child}}$ . - Mutation: Small random perturbations are applied to individual variables to maintain genetic diversity.
If one candidate branch becomes trapped in a local optimum, other population members across different landscape regions continue exploring, significantly improving overall global convergence.
Advanced single-state frameworks escape local optima by deliberately accepting non-improving or downhill moves under controlled conditions:
-
Simulated Annealing: Inspired by physical metallurgy, the algorithm accepts non-improving moves (
$\Delta h > 0$ ) probabilistically according to the Metropolis criterion:$$P(\text{accept downhill move}) = \exp\left( - \dfrac{\Delta h}{T_k} \right)$$ where
$T_k$ represents a system temperature parameter that monotonically decays over time according to a cooling schedule. At high initial temperatures$T_0$ , the algorithm explores broadly; as$T_k \to 0$ , it transitions into pure greedy hill climbing. -
Tabu Search: Maintains a short-term memory structure (a Tabu List) recording recently visited states or operators, forbidding reversal moves to prevent cyclic looping on plateaus.
-
Local Beam Search: Maintains
$k$ parallel search states. At each iteration, all neighbors of all$k$ states are generated, and the top$k$ overall performers across the joint pool are retained, sharing information across parallel search threads.