MODULE 2

SEARCH ALGORITHMS

Agenda
Solving Problems by Searching
Problem-Solving Agents,
Example Problems,
Searching for Solutions
Uninformed Search Strategies
Breadth-first Search,
Depth-first Search and DFS variations,
Lowest-cost-first Search,
Informed (Heuristic) Search Strategies
Greedy Best-first Search,
A* search,
Recursive Best First Search,
Heuristic Functions.
Beyond Classical Search
Local Search Algorithms and Optimization Problems
Hill-climbing Search and variations to resolve
problems with steepest ascent
Genetic Algorithms.

SOLVING PROBLEMS BY SEARCHING

Problem Solving
Problem solving is a fundamental concept in AI where the systems are designed to identify
challenges, make decisions and find efficient solutions. Problem-solving agents deployed for this
purpose, actively analyze situations, evaluate different options and choose the best action to
reach their goal.

These agents work by:

Perceiving the environment: They collect data about their surroundings such as sensor
inputs or observations.
Defining the problem: They clearly understand the problem including the starting point,
the available actions and the desired goal.
Exploring different possibilities: They consider various ways to solve the problem and
evaluate which approach is likely to succeed.
 Evaluating and deciding: Once they explore options, they assess the outcomes and pick
the best course of action based on factors like time, resources and success likelihood.
Learning and adapting: Many problem-solving agents can learn from past experiences,
improving their decision-making abilities over time.

Steps in Problem Solving

AI problem solving follows a structured, logical process similar to human thinking, it's steps
include:

Problem Definition: First, the problem needs to be clearly defined. This includes
understanding the inputs, constraints and what the solution should look like.
Problem Analysis: Once the problem is defined, analysed in more detail. This helps in
understanding its limitations and possible solutions.
Knowledge Representation: All the important information is organized so the AI can
understand and work with it. This could include creating graphs or using databases.
Problem Solving: AI uses appropriate methods to solve the problem. This often means
comparing different strategies to find the most efficient one.
Testing and Evaluation: Finally, after the solution is implemented, testing and evaluation
ensure the solution meets all requirements and performs as expected.

Key Components of Problem Formulation

Effective problem-solving in AI is dependent on several important components:

Initial State: This is the starting point of the problem where the AI begins its process. It
sets the context and helps identify how the agent will approach the challenge.
Action: At this stage, AI identifies all the possible actions it can take from the initial state.
Each action has an impact on how the system moves closer to solving the problem.
Transition: This refers to how the system changes from one state to another after an action
is taken. Transition modeling helps show how the actions influence the next steps.
Goal Test: Once an action is taken, AI checks if it has reached its goal. If the goal is
achieved, the problem-solving process stops and the solution is considered complete.
Cost Function: This step assigns a numerical value to the cost of achieving the goal. The
cost can include resources like time, energy or money and helps decide the most efficient
way to reach the goal.

Problem Solving by Searching

Problem solving by searching is a process where a person searches through a space of possible
solutions to find one that meets the given criteria or constraints. It involves iteratively exploring
different options, evaluating their feasibility, and selecting the best one to solve the problem at
hand. This approach is often used when the problem does not have a clear or obvious solution,
and the solution space is large or complex. By searching, individuals can narrow down the
options, identify potential solutions, and adapt their approach as needed to arrive at a satisfactory
solution.

Properties of Search Algorithms

1. Completeness

Definition: The algorithm guarantees to find a solution if one exists.

Example: Breadth-First Search (BFS) is complete because it explores all nodes level by
level and will find a solution if it exists.
2. Optimality

Definition: The algorithm finds the best or least-cost solution.

Example: Uniform Cost Search (UCS) is optimal because it always expands the least-
cost node first, ensuring the optimal solution is found.
3. Time Complexity

Definition: The amount of time an algorithm takes to find a solution, often expressed
in terms of input size.
Example: Depth-First Search (DFS) has a worst-case time complexity of O(b^d), where
b is the branching factor and d is the depth of the solution.
4. Space Complexity

Definition: The amount of memory the algorithm consumes during execution.

Example: BFS can consume large amounts of memory because it stores all nodes at the
current level.
5. Admissibility

Definition: For heuristic search algorithms (like A*), the heuristic is admissible if it never
overestimates the true cost to reach the goal.
Example: In route planning, using straight-line distance as a heuristic is admissible
because it never overestimates the actual travel distance.

General search problem examples

1. Pathfinding in a Maze or Grid
Finding the shortest path from a start point to a goal point in a maze or grid map.
Example: Navigating a robot through a warehouse.

2. 8-Puzzle / Sliding Puzzle

Rearranging tiles to reach a specific goal configuration.
 Example: Moving tiles in the 8-puzzle to arrange numbers in order.

3. Traveling Salesman Problem (TSP)

Finding the shortest possible route that visits each city exactly once and returns to the
starting point.

4. Robot Navigation
Planning a sequence of moves for a robot to reach a target location avoiding obstacles.

5. Game Playing (e.g., Chess, Tic-Tac-Toe)

Searching for optimal moves or strategies to win the game.

6. Scheduling Problems
Assigning tasks to resources over time to optimize efficiency or meet constraints.

7. String Matching / Pattern Searching

Finding a specific pattern within a larger string or text.

8. Network Routing
Determining the best path for data packets through a network.

9. Sudoku Solver
Filling in a grid with digits to satisfy the game's rules.

10. Resource Allocation Problems

Distributing limited resources among competing activities to maximize benefits.

AI Search Algorithms
AI search algorithms are methods used to navigate and solve problems by exploring possible states
or solutions systematically. Here's a general overview of the main types:

1. Uninformed (blind) search algorithms

These algorithms do not have any additional information about states beyond the problem
definition. They explore the search space systematically.

Breadth-First Search (BFS): Explores all nodes at the current depth before moving to the
next level. Guarantees the shortest path in terms of the number of steps.
Depth-First Search (DFS): Explores as deep as possible along each branch before
backtracking. Uses less memory but can get stuck in deep or infinite paths.
Uniform Cost Search (UCS): Expands the least costly node first, useful when costs vary.
Iterative Deepening Search: Combines DFS's space efficiency and BFS's completeness by
increasing depth limits iteratively.
2. Informed (heuristic) search algorithms

These algorithms use heuristics additional information about the goal to guide the search
more efficiently.

Greedy Best-First Search: Selects nodes based on the estimated cost to the goal (heuristic).
Fast but may not find the optimal path.
A* Search: Combines the cost to reach the current node and the estimated cost to the goal.
Finds the optimal path efficiently when the heuristic is admissible.

3. Local Search Algorithms

Used for optimization problems where the goal is to find the best solution rather than a path.

Hill Climbing: Moves to neighboring states with better scores.

Simulated Annealing: Allows occasional worse moves to escape local optima, inspired by
cooling in metallurgy.
Genetic Algorithms: Uses techniques inspired by natural evolution (selection, crossover,
mutation) to evolve solutions.

4. Adversarial Search Algorithms

Used in game playing where multiple agents compete.

Minimax Algorithm: Considers the worst-case opponent moves to decide the best move.
Alpha-Beta Pruning: Enhances Minimax by pruning branches that won't affect the final
decision.

UNINFORMED SEARCH STRATEGIES

An uninformed search algorithm is a type of search strategy used in problem-solving and artificial
intelligence that does not have any information about how close the current state is to the goal. It
explores the search space blindly, based solely on the problem's structure, without any heuristic
guidance.
Key Features:
- No knowledge of the goal state beyond the problem definition.
- Explores nodes without estimating their distance to the goal.
- Often used when heuristics are unavailable or unreliable.

1. Breadth First Search

 A. Numerical Example
Suppose we have the following graph with edges: - A-B, A-C, B-D, C-E, D-F, E-F

.
Steps:

Shortest Path:
 B. Advantages
Finds the shortest path in unweighted graphs.
Simple to implement.
Guaranteed to find a solution if one exists.

C. Disadvantages
Can be memory-intensive for large graphs.
Inefficient for very deep or infinite graphs.
Not suitable for weighted graphs (where Dijkstra's algorithm is preferred).

2. Depth First Search

A. Numerical Example
Consider the following graph (represented as adjacency list):

Starting node: A
Traversal steps:
- Start at A, visit A
 - Move to B, visit B
- Move to D, visit D (no further neighbours), backtrack to B
- From B, move to E, visit E
- From E, move to F, visit F
- Backtrack to E, then B, then A
- From A, move to C, visit C
- From C, move to F, but F is already visited
Traversal order:

B. Advantages of DFS
Memory efficient for sparse graphs.
Easy to implement using recursion.
Useful for:
o Detecting cycles
o Topological sorting
o Finding connected components
o Solving puzzles with backtracking (e.g., mazes)

C. Disadvantages of DFS
Not guaranteed to find the shortest path.
Can get trapped exploring deep, irrelevant parts of the graph.
Not suitable for large, complex graphs when optimal solutions are needed.
May not be complete in infinite graphs or graphs with infinite paths.

3. Depth Limited Search

A. Numerical Example

Suppose we are searching for a goal node in a tree:

We set the depth limit to 2.
Search process:
Start at A (depth 0)
Explore B (depth 1)
Explore D (depth 2)

Explore C (depth 1)

Result: The goal G is found at depth 2, which is within the limit.

 4. Iterative Deepening

A. Numerical Example

Suppose we have the following tree:

A
/ \
B C
/\ /\
D EF G

Goal node: E
Branching factor (b): 2 (each node has two children, except leaves)
Depth of goal (d): 2 (A -> B -> E)

Search Steps:

Depth limit = 0:

Explore only root: A (not goal)

Goal not found.

Depth limit = 1:

Explore A (depth 0)
Explore B, C (depth 1) from A
Goal E is at depth 2, not found yet.
Depth limit = 2:

Explore A, B, C
From B: D, E
From C: F, G
Goal E is found at depth 2 from A in the second iteration.

B. Advantages

Complete: Finds the goal if it exists, assuming finite space.

Optimal: Finds the shallowest goal node when path costs are uniform.
Memory-efficient: Uses space proportional to the depth (O(bd)), similar to DFS.
Combines BFS & DFS: Doesn't require large memory like BFS but guarantees
optimality and completeness like BFS.

C. Disadvantages

Repetitive Search: Re-explores nodes multiple times, leading to higher total time in
large trees.
Time Overhead: Slightly slower than BFS in terms of total operations due to
repeated searches.
Not suitable for very deep or infinite spaces unless there is a depth limit.

5. Lowest Cost First Search

A. Numerical Example

Consider the following graph:

Edge costs:

A-B: 1
A-C: 4
B-D: 2
B-E: 3
C-E: 1
C-F: 2

Goal: Reach node F from node A.

Solution: Step-by-step Search

Start at A (cost = 0).

Open list: [(A, cost=0)].

Expand A (lowest cost).

Neighbors: B (cost=1), C (cost=4).
Open list: [(B, cost=1), (C, cost=4)].

Expand B (lowest cost).

Neighbors: D (cost=1+2=3), E (cost=1+3=4).
Open list: [(D, cost=3), (E, cost=4), (C, cost=4)].

Expand D (cost=3).
D has no further neighbors to goal.
Open list: [(E, cost=4), (C, cost=4)].

Expand E (cost=4).
Neighbors: C (already in open with same cost), F (cost=4+2=6).
Open list: [(C, 4), (F, 6)].

Expand C (cost=4).
Neighbors: E (already in open), F (cost=4+2=6).
Open list: [(F, 6), (F, 6)].
Expand F (cost=6).
Goal reached with total cost = 6.

B. Advantages

Finds the least costly path to the goal.

Optimal when all step costs are non-negative.
Works well with variable step costs.

C. Disadvantages

Can be memory-intensive as it stores all generated nodes.

May have high time complexity in large graphs.
Not suitable for very large search spaces without optimization (like pruning).

INFORMED (HEURISTIC) SEARCH STRATEGIES

Informed search strategies, also known as heuristic search strategies, are search algorithms that
leverage domain-specific knowledge (heuristics) to guide the search process toward the goal more
efficiently than uninformed methods.
Properties:

Heuristic Function (h(n)): Estimates the cost from node n to the goal.
Optimality: Many informed search strategies can guarantee the shortest path if the heuristic
is admissible (never overestimates the true cost).
Efficiency: They typically explore fewer nodes compared to uninformed strategies, making
them faster.
Guided Search: Use of heuristics directs the search toward promising paths.

Working Principle:
1. Initialization: Start from the initial node.
2. Evaluation: Use the heuristic function to estimate the total cost (f(n) = g(n) + h(n)) where
g(n) is the cost from the start node to node n.
3. Selection: Choose nodes for expansion based on their estimated total cost.
4. Expansion: Generate successor nodes and evaluate their costs.
5. Termination: Continue until the goal node is reached or no nodes are left to explore.

Common examples include:

A* Search: Combines g(n) and h(n) for optimal and efficient search.
 Greedy Best-First Search: Uses only h(n) to guide the search, faster but not always optimal.

1. Greedy Best-first Search

A. Definition:

Greedy Best First Search is a heuristic search algorithm that expands the node that appears to be
closest to the goal, based on a heuristic function h(n). It "greedily" chooses the path that seems
best at each step, aiming to find the shortest path to the goal efficiently.

B. Properties:

1. Informed Search: Uses a heuristic function to guide the search.

2. Heuristic Function (h(n)): Estimates the cost from node n to the goal.
3. Completeness: Not guaranteed (can get stuck in cycles or dead-ends).
4. Optimality: Not guaranteed unless the heuristic is admissible and consistent.
5. Time Complexity: Varies; often faster than uninformed search but can be
inefficient if heuristic is poor.
6. Space Complexity: O(b^d), where b is branching factor and d is depth of the
shallowest solution.

C. Working Principle:

1. Start at the initial node (start state).

2. Maintain a priority queue (open list) ordered by h(n).
3. Select the node with the lowest h(n) (most promising node).
4. Expand the selected node: generate its successors.
5. Repeat until the goal node is found or no nodes remain.

Note: GBFS only considers the heuristic h(n), ignoring the cost travelled so far (g(n)).

Imagine a graph with nodes, where arrows indicate possible paths, and heuristic values h(n) are
shown at each node:
Step 1: Start at "Start" with h=7.
Step 2: Expand to the node with the lowest h-value: Node B (h=2).
Step 3: From Node B, reach the goal directly.

GBFS prioritizes nodes based solely on heuristic estimates, leading to a potentially quick path if
heuristics are accurate.

D. Advantages:

Fast in practice: Can find a solution quickly if heuristic is good.

Memory-efficient compared to algorithms like A* (which considers g(n) as well).
Simple to implement.

E. Disadvantages:

Not guaranteed to find the shortest path.

Can get stuck in loops or dead ends without cycle detection.
Depends heavily on the heuristic quality; poor heuristics lead to poor performance.
Not complete or optimal in general cases.

2. A* search

A. Definition
A* (A-star) search is a popular and powerful graph traversal and pathfinding algorithm used to
find the shortest path from a start node to a goal node efficiently. It combines features of uniform-
cost search and greedy best-first search by considering both the actual cost to reach a node and an
estimated cost to reach the goal.

B. Properties
 Optimality: A* guarantees the shortest path if the heuristic is admissible (never
overestimates the true cost).
Completeness: It will find a solution if one exists.
Efficiency: Uses heuristics to prune paths and reduce search space.
Heuristic Function (h(n)): Estimates the cost from node n to the goal.
Cost Function (g(n)): Actual cost from start to node n.
Evaluation Function (f(n)): Sum of g(n) and h(n), i.e., `f(n) = g(n) + h(n)`.

C. Working Principle
1. Initialization: Start with a priority queue (open list) containing the start node with
`f(start) = h(start)`.
2. Selection: Pick the node with the lowest `f(n)` from the open list.
3. Expansion: Expand the node, generate its successors.
4. Evaluation: For each successor:
- Calculate `g(n)` (cost from start to successor).
- Estimate `h(n)` (heuristic estimate to the goal).
- Calculate `f(n) = g(n) + h(n)`.
- If the successor is not in the open list or has a lower `f(n)`, add/update it.
5. Termination: Repeat until the goal node is reached or the open list is empty.
6. Path Reconstruction: Trace back from the goal node to start via parent pointers to get
the shortest path.

D. Advantages
Finds the shortest path efficiently with a good heuristic.
More efficient than uniform-cost search when the heuristic is informative.
Complete and optimal with an admissible heuristic.

E. Disadvantages
Performance depends heavily on the quality of the heuristic.
Can be memory-intensive due to storing all generated nodes.
Not suitable if no good heuristic is available.
Can be slow if the heuristic is non-admissible or poorly designed.

F. Numerical Example
Scenario:
in the following grid:
Start node: S (at cost 0)
Goal node: G
Numbers in parentheses are the heuristic estimates (h) to reach G from each node.

Step-by-step Solution:

Heuristic (h) values:

G: 0 (goal)
S: 4
B: 2
C: 3

Step 1: Initialize
Open list: contains start node S with f(S) = g(S) + h(S) = 0 + 4 = 4.
Closed list: empty.
Step 2: Expand S

From S, generate successors:

B with g(B) = 1 (cost from S to B)

C with g(C) = 4

Calculate f:

B: f(B) = g(B) + h(B) = 1 + 2 = 3

C: f(C) = 4 + 3 = 7

Open list now: B (f=3), C (f=7)

Step 3: Expand B (lowest f)

From B, generate successors:

G with g(G) = g(B) + 2 = 1 + 2 = 3
C with g(C) = g(B) + 3 = 1 + 3 = 4 (but C is already in open with higher f, so update if better)

For G:

f(G) = 3 + 0 = 3

For C:

g(C) via B is 4, h(C)=3, so f(C)=4+3=7 (no improvement over existing C in open)

Open list now: G (f=3), C (f=7)

Step 4: Expand G (lowest f)

G is the goal node, with f=3. Path cost to G is 3.

with total cost = 3.

Final Path:

Total cost = 3

3. Recursive Best First Search

A. Definition

Recursive Best-First Search (RBFS) is an informed search algorithm that explores the most
promising path based on an evaluation function (like A*), but it uses limited memory by storing
only a single path from the root to a leaf node, and backtracks when necessary. It recursively
searches down the most promising node, and if it finds that this path exceeds the current bound
(threshold), it backtracks and explores alternative paths.

B. Properties

Informed Search: Uses an evaluation function f(n) to guide the search.

Memory-Efficient: Uses only linear space, unlike A* which can be exponential.
Optimality: Finds an optimal solution if the evaluation function is admissible and
consistent.
Completeness: Complete if the branching factor is finite and the goal is reachable.
Depth-First Nature: Resembles depth-first search but with a heuristic guidance.

C. Working Principle
 1. Start at the root node, compute its f(n) value (heuristic estimate).
2. Recursively explore the child node with the lowest f(n) value.
3. Maintain a threshold (limit) which is the best f(n) value seen so far.
4. If a node's f(n) exceeds the limit, backtrack and update the limit with the next best
alternative.
5. Repeat until the goal node is found or all paths are exhausted.

Imagine a tree with nodes evaluated based on their f(n) scores:

RBFS begins at the root, explores the child with the lowest f(n) (say, node A with f=10).
It recursively explores down to node A's children, updating the limit as it backtracks.
If it encounters a node with f(n) exceeding the limit, it backtracks and tries other paths.

D. Advantages

Memory-efficient: Requires only linear space.

Optimal and Complete with admissible heuristics.
Suitable for large search spaces where memory is limited.
Avoids storing all nodes like in A*.

E. Disadvantages

Re-expansion of nodes: Nodes may be re-expanded multiple times, leading to higher

computational overhead.
Performance depends heavily on heuristic quality.
Can get stuck in deep or complex search spaces if heuristic is poor.
Implementation complexity is higher than simpler algorithms like BFS or DFS.

F. Numerical Example of RBFS

Suppose we want to find a goal node in a tree with the following structure, where each node has
an f(n) value (estimated total cost):
Goal node: C (found at depth 2)

Solution: Step-by-step RBFS process

Initial call: Start at node Start with f=10

Explore children of Start:

A with f=8
B with f=15

Choose the best node to expand: A (lowest f=8).

Recursive exploration of node A:

At node A:
Children: C (f=5) and D (f=9)
Goal: C (f=5), which is promising.

Choose node C (f=5), which is a goal.

Found goal with f=5.

Backtracking and limit updates:

Return success, but as RBFS proceeds, it updates the limit to the next best alternative.
After exploring A's children, compare the f value of D (9) with the current limit.
If the current limit was less than 9, RBFS would backtrack and explore other branches (like
B).

Next, explore node B:

Node B with f=15.

Its children: E (f=7) and F (f=20).

Choose E (f=7), which is promising.

E is not the goal, but it has no children in this example, so backtrack.

4. Heuristic Functions

A. Definition
A heuristic function is an informed guess or estimate used in search algorithms to evaluate how
close a given state is to the goal state. It guides the search process more efficiently by prioritizing
which paths to explore, often leading to faster solutions in complex problems.

B. Properties

Admissibility
The heuristic never overestimates the true cost to reach the goal.
Ensures optimality in algorithms like A*.
Consistency (Monotonicity)
For every node n and successor n', the estimated cost satisfies:

Ensures that the estimated cost is non-decreasing along a path, which is beneficial for
certain algorithms.
Informativeness
The heuristic provides meaningful guidance and distinguishes among different states
effectively.

C. Working Principle

Concept:

Imagine a search space as a graph where nodes are states and edges are actions with associated
costs.
The heuristic function estimates the cost from a node n to the goal node G.

Heuristic estimates:
h(C) = 2
h(D) = 0 (since D is goal)
h(A) = 3
h(B) = 1
How it works:

The search algorithm uses h(n) to prioritize nodes.

For instance, A* will select the node with the lowest f(n)=g(n)+h(n), where:
g(n) = cost from start to node n
h(n) = heuristic estimate from n to goal

D. Advantages of Heuristic Functions

Faster Search: Reduces the number of nodes explored by guiding the search toward
promising paths.
Optimal Solutions (with admissible heuristics): Guarantees finding the best
solution in algorithms like A*.
Efficiency in Complex Problems: Particularly useful in large, complex search spaces
like pathfinding and puzzle solving.

E. Disadvantages of Heuristic Functions

Design Complexity: Creating an effective heuristic can be challenging and problem-

specific.
Computational Cost: Sometimes computing the heuristic is expensive.
Inaccuracy Risks: A poor heuristic can misguide the search, leading to increased
exploration or suboptimal solutions.
Inadmissibility: Non-admissible heuristics may speed up search but at the cost of
optimality.

F. Numerical Example of Heuristic Functions

Problem: Find the shortest path from Start (S) to Goal (G) in the following graph:
Edges are labelled with their costs.
The goal is to find the shortest path from S to G.

Solution

Step 1: Define the heuristic function h(n)

Suppose we estimate the straight-line (Euclidean) distances from each node to the goal G:

Node Estimated Distance ( ) to G

S 4

A 2

B 2

G 0

(These are heuristic estimates based on straight-line distances)

Step 2: Calculate total estimated cost f(n)=g(n)+h(n)

g(n): actual cost from start S to node n.

h(n): heuristic estimate from n to goal G.

Step 3: Search process with A*

Initial State: S
g(S)=0
f(S)=g(S)+h(S)=0+4=4

Step 4: Explore neighbors

Neighbors of S:
A: g(A)=2, f(A)=2+2=4
G: g(G)=1 (direct edge), f(G)=1+0=1
Since f(G)=1 is lowest, we explore G directly.
Result:

Path: S G
Total cost: 1

This is the shortest path, and the heuristic helped guide the search efficiently.

BEYOND CLASSICAL SEARCH

Optimization Problems involve finding the best solution from a set of feasible solutions. These
problems appear in various fields such as logistics, scheduling, machine learning, and network
design. The goal is to optimize a specific objective function, such as minimizing cost or maximizing
efficiency.

Local Search Algorithms are a class of heuristic algorithms used to solve complex optimization
problems, especially when exact methods are computationally infeasible. They iteratively improve
a solution by exploring its neighboring solutions until no further improvement is possible or a
stopping criterion is met.

Key Concepts

Solution Space: The set of all possible solutions. For many problems, this space is vast
and complex.
Neighborhood: The set of solutions that are "close" or "similar" to a current solution,
often defined by small modifications.
Current Solution: The solution being evaluated or improved at each step.
Local Optimum: A solution that is better than all its neighbors but not necessarily the
best overall (global optimum).

How Local Search Works

- Start with an initial solution.

- Iteratively explore neighboring solutions.
- Move to a neighbor if it offers an improvement.
- Repeat until no better neighbors are found (local optimum) or a stopping condition is
met.
 Advantages Disadvantages

Simple to implement. Can get stuck in local optima.

Efficient for large, complex problems. May require techniques like
Can find good solutions quickly. randomization or diversification to
escape local minima.

1. Hill-Climbing Search Algorithm

Hill climbing is a simple and intuitive optimization algorithm used to find a solution to a problem
by iteratively making small changes to the current state and selecting the neighbor that improves
the objective function.

Key Concepts:

Starting Point: Begin with an initial solution or state.

Neighboring States: Explore neighboring solutions that are similar to the current state.
Evaluation: Assess the neighboring states based on a fitness or cost function.
Move: Transition to the neighbor with the best improvement.
Termination: Continue the process until no better neighbor exists or a predefined
condition is met.

Main Steps:

1. Initialize: Start with an initial solution.

2. Repeat:
- Generate neighboring solutions.
- Evaluate each neighbor.
- Move to the neighbor with the highest improvement (or lowest cost).
3. Stop: When no neighbor provides a better solution, or after a certain number of iterations.

Advantages Disadvantages
Simple to implement. Can get stuck in local maxima, minima,
Efficient for problems with smooth or plateaus.
search spaces. Does not guarantee finding the global
optimum.

Variants:

Steepest Ascent Hill Climbing: Considers all neighbors at each step and chooses the best.
Simple Hill Climbing: Considers neighbors one at a time and moves to the first better one
found.
Randomized Hill Climbing: Introduces randomness to escape local optima.
Use Cases:

Optimization problems in scheduling, routing, machine learning parameter tuning, etc.

1.1. Simple Hill-Climbing Search Algorithm

A. Overview
A simple hill-climbing search algorithm is a mathematical optimization technique used to find the
maximum or minimum of a function. It is an iterative algorithm that starts with an arbitrary
solution and then makes small changes to the solution, each time moving in the direction that
improves the objective (either increasing or decreasing the value). The process continues until no
further improvements can be found.
Key idea: "Climb" towards the best solution by local improvements, similar to climbing a hill to
reach the peak.

B. Working Principle:
1. Start with an initial solution (point).
2. Evaluate the neighboring solutions (small changes from current).
3. Move to the neighbor with the best improvement.
Repeat steps 2 and 3 until no neighbor improves the current solution.
The current solution at this point is considered a local optimum.
Note: Hill-climbing can get stuck in local maxima/minima and may not find the global optimum.

C. Simple Numerical Example:

Suppose we want to maximize the function:
2
f(x x +4
which has a maximum at x=3.

Step-by-step Solution:
Initial guess: x=0
Evaluate neighbors: Let's consider neighbors at x
Calculate:
f
f
f
Choose best neighbor: x=1 with f(1)=0
Move to =1
Next neighbors: x=0,2
f
f
Best neighbor: x=2 with f(2)=3
Move to x=2x=2 =2
Next neighbors: x=1,3
2
f
f(1)=0
Best neighbor: x=3 with f(3)=4
Move to =3
Check neighbors: x=2,4
2
f
f(2)=3
Both neighbors give f=3, which is less than current 4, so no improvement.
Result: The algorithm stops at x=3, the local maximum (which is also the global maximum in this
case).

1.2. Steepest-Ascent Hill-Climbing Search Algorithm

A. Overview

Steepest-Ascent Hill-Climbing is a local search algorithm used for solving optimization

problems. It iteratively moves towards better solutions by exploring neighboring states and
selecting the one with the highest improvement (i.e., the steepest ascent). The goal is to
find a peak (local maximum) of the search space, though it may not always find the global
maximum.
Key Features:
- Considers all neighbors (hence "steepest" ascent).
- Can get stuck in local maxima, plateaus, or ridges.
- Simple and efficient for many problems.

B. Working Principle:
1. Start with an initial solution (a point in the search space).
2. Evaluate neighbors: Generate all neighboring solutions (states adjacent to the current
one).
 3. Select the best neighbor: Among all neighbors, choose the one with the highest value
of the objective function (or the greatest improvement).
4. Move to the best neighbor: If this neighbor is better than the current solution, move
to it.
5. Repeat: Continue the process until no neighbor is better than the current solution
(local maximum is reached).

C. Numerical Example

Suppose we want to maximize the function:

f(x)= x2+4x

Search space: x in the range [0, 4]

Initial solution: x=0

Solution: Step-by-step

In this case, when at x=2, the neighbors are x=1 and x=3. The best neighbor is x=3 with f=3,
which is less than f=4 at x=2. Since no neighbor is better than current, the search stops.

Result: The algorithm converges at x=2 with f=4, which is the local maximum (and also the global
maximum for this parabola).

1.3. Stochastic Hill-Climbing Search Algorithm

A. Overview

Stochastic Hill-Climbing is a variant of the hill-climbing algorithm that introduces randomness in

selecting the next move. Unlike the deterministic hill-climbing, which always moves to the best
neighbor, stochastic hill-climbing randomly chooses among better neighbors, which helps in
avoiding local maxima and exploring more of the search space.
 B. Working Principle:

1. Start with an initial solution.

2. Generate neighbors of the current solution.
3. Identify better neighbors (neighbors with higher value or better fitness).
4. Select one of these better neighbors at random.
5. Move to the selected neighbor.
6. Repeat steps 2-5 until a stopping condition is met (e.g., no better neighbors, maximum
iterations).

This randomness allows the search to potentially escape local maxima by not always choosing the
absolute best neighbor.

C. Numerical Example

Suppose we are trying to maximize a function:

f(x) = - (x - 3)2 + 10

This is a parabola with a maximum at x=3, f(3)=10.

Initial solution: x=0

Solution
Iteration Steps
Explanation:

- Starting from x=0, neighbors are x=-1 and x=1.

- Only x=1 improves the function; random choice picks it.
- From x=1, neighbors are 0 and 2. x=2
- Next, from x=2, neighbor x=3 is better, so move there.
- At x=3, maximum is reached; no better neighbors.

Note: The randomness in selecting among better neighbors allows some variation in the path,
potentially helping to escape local maxima if they existed.

Problems of Hill Climbing Search

Problem 1: Local Maximum: A local maximum is a peak state in the landscape which
is better than each of its neighbouring states, but there is another state also present
which is higher than the local maximum.
o Solution: Backtracking technique can be a solution of the local maximum in state space
landscape. Create a list of the promising path so that the algorithm can backtrack the
search space and explore other paths as well.
Problem 2: Plateau: A plateau is the flat area of the search space in which all the
neighbour states of the current state contain the same value, because of this algorithm
does not find any best direction to move. A hill-climbing search might be lost in the
plateau area.
o Solution: The solution for the plateau is to take big steps while searching, to solve the
problem. Randomly select a state which is far away from the current state so it is
possible that the algorithm could find non-plateau region.
Problem 3: Ridges: A ridge is a special form of the local maximum. It has an area
which is higher than its surrounding areas, but itself has a slope, and cannot be
reached in a single move.
o Solution: With the use of bidirectional search, or by moving in different directions,
we can improve this problem.

2. Simulated Annealing

A. Overview

Simulated Annealing is a probabilistic optimization algorithm inspired by the process of

annealing in metallurgy, where a material is heated and then slowly cooled to reduce defects
and find a low-energy state.
Purpose: To find a good approximation to the global minimum (or maximum) of a
complex, often non-convex, function.
B. Key Properties of Simulated Annealing

Probabilistic Acceptance: It can accept worse solutions temporarily to escape local

minima, which distinguishes it from greedy algorithms.
Cooling Schedule: The algorithm uses a temperature parameter that gradually decreases
over time, reducing the likelihood of accepting worse solutions as the process continues.
Convergence: Given a sufficiently slow cooling schedule, SA can theoretically converge
to the global optimum.
Flexibility: It can be applied to various problems, including combinatorial, continuous,
and discrete optimization.

C. Basic Algorithm Steps

Start with an initial solution and initial temperature T.
Generate a neighboring solution.
Calculate the change in the objective function E.
Decide whether to accept the new solution:
If E<0 (better solution), accept it.
If E , accept it with probability e E/T.
Reduce the temperature according to the cooling schedule.
Repeat until stopping criteria are met (e.g., temperature is low, or a maximum number of
iterations).

D. Simple Numerical Example

Suppose we want to minimize the function:

f(x) = (x - 3)2
Initial solution: x=0
Initial temperature: T=10
Cooling schedule: Tnew=0.9×T
Neighbor generation: small random change, e.g., xnew=x +

Iteration 1:
x=0
Generate neighbor: xnew = 0 + 0.5 = 0.5
2 2 2 2
E=f(0.5) f(0) = = = =
Since E<0, accept the new solution.
Update x=0.5

Iteration 2:
T=9
Neighbor: xnew=0.5+0.3=0.8
2 2 2 2
E= = = =
Accept: x = 0.8
And so on, gradually cooling and searching for the minimum near x = 3.
E. Applications of Simulated Annealing
- Traveling Salesman Problem (TSP): Finding the shortest route visiting all cities.
- Job Scheduling: Optimizing task sequences.
- VLSI Design: Circuit layout optimization.
- Machine Learning: Hyperparameter tuning.
- Function Optimization: Complex, multi-modal functions where other methods struggle.

3. Local Beam Search

A. Overview
Local Beam Search is a heuristic search algorithm used for solving optimization problems. It
maintains multiple candidate solutions simultaneously and explores their neighborhoods to find
better solutions.

B. Main Ideas
- Instead of keeping only one solution (like in hill climbing), it keeps a
solutions.
- At each iteration, it generates all neighbors of all current solutions.
-
- The process continues until a stopping criterion is met (e.g., solution quality, max iterations).

C. Properties of Local Beam Search

- Multi-solution approach: Maintains multiple solutions to diversify search.
- Avoids local maxima better than hill climbing, due to multiple paths.
- Prone to stagnation if all solutions converge to the same local maximum.
- Paramete influences exploration vs. exploitation.
- Efficiency: Can be computationally intensive as neighborhood expands with multiple
solutions.

D. Steps
ndom solutions.
2. Repeat:
- Generate all neighbors of current solutions.
-
- Replace current solutions with these selected neighbors.
3. Terminate when a solution meets criteria or after a certain number of iterations.
E. Numerical Example
Suppose you want to maximize the function:
f(x) = - (x - 3)2 + 10
which has a maximum at x=3.

Setup
- Number of solutions (k) = 2
- Starting solutions: (x1 = 0), (x2= 5)
- Neighborhood: For each solution, neighbors are x 1

Solution:

Iteration 1
- Current solutions: 0, 5

Neighbors:
- For 0: neighbors are -1, 1
- For 5: neighbors are 4, 6

Evaluate neighbors:
f(-1) = -(-1-3)^2 + 10 = -16 + 10 = -6
f(1) = - (1-3)^2 + 10 = -4 + 10 = 6
f(4) = - (4-3)^2 + 10 = -1 + 10 = 9
f(6) = - (6-3)^2 + 10 = -9 + 10 = 1

Select top 2:
- 4 (score 9)
- 1 (score 6)

Update solutions:
- 4, 1

Iteration 2
Neighbors of 4: 3, 5
f(3)= -0 + 10=10
f(5)= -4 + 10=6

Neighbors of 1: 0, 2
f(0)= -9 + 10=1
f(2)= -1 + 10=9

All neighbors:
- 3 (10), 5 (6), 0 (1), 2 (9)

Top 2:
- 3 (10)
- 2 (9)
Update solutions:
- 3, 2

Repeat until solutions stabilize or reach maximum.

F. Applications
- Optimization problems: Scheduling, routing, machine learning hyperparameter tuning.
- Artificial Intelligence: Pathfinding, game playing.
- Function maximization/minimization: Engineering design, resource allocation.
- Combinatorial problems: Traveling Salesman, knapsack variants.

4. Tabu Search

A. Overview

Tabu Search is a metaheuristic optimization technique designed to solve complex

combinatorial problems. It guides a local search procedure to explore the solution space
beyond local optimality by using memory structures called tabu lists to avoid cycling back
to recently visited solutions.

B. Main idea:
Start from an initial solution.
Explore neighboring solutions.
Move to the best neighbor, even if it doesn't improve the current solution.
Use a tabu list to forbid or penalize certain moves or solutions to promote exploration.
Continue iterating until stopping criteria are met (like a maximum number of iterations).

C. Properties of Tabu Search

Memory-based: Uses a tabu list to store recent moves or solutions.
Flexible: Can incorporate various neighborhood structures and aspiration criteria.
Escaping local minima: By allowing moves that don't immediately improve the solution,
it can jump out of local optima.
Intensive search: Tends to provide high-quality solutions within reasonable timeframes.

D. Numerical Example
Suppose we want to minimize the function:
f(x) = (x - 3)2
with x being an integer in the range 0 to 6.
Initial solution: x=0

Current Neighbor Chosen New Function Tabu

Step
solution solutions move solution value list

1, -1 (but Move 2
1 0 1 =4 empty
-1 invalid) to 1

Move 2 (move
2 1 0, 2 2 =1
to 2 to 1)

Move 2 (move
3 2 1, 3 3 =0
to 3 to 2)

Suppose after moving to 3, we reach the minimum 000. A more complex example would involve
moves that might be temporarily tabu, but for this simple case, it shows the basic idea.

E. Applications of Tabu Search

Scheduling problems: Job-shop scheduling, timetabling.
Vehicle routing: Optimizing delivery routes.
Network design: Optimizing network topologies.
Graph problems: Max-cut, graph coloring.
Combinatorial optimization: Portfolio selection, resource allocation.

5. Genetic Algorithm

A. Overview
A Genetic Algorithm is a search and optimization technique inspired by the process of natural
selection and evolution. It iteratively improves a set of candidate solutions (called populations) to
find the best or optimal solution to a problem.

B. Main Idea:
- Start with a random population of potential solutions (called individuals or chromosomes).
- Evaluate their fitness according to a fitness function.
- Select the fittest individuals to reproduce.
- Apply genetic operators like crossover (recombination) and mutation to produce new solutions.
- Replace some or all of the population with these new solutions.
- Repeat until a stopping criterion is met (e.g., solution quality or number of generations).
C. Properties of Genetic Algorithms
Population-based: Operates on a set of solutions simultaneously.
Stochastic: Uses randomness in selection, crossover, and mutation.
Evolutionary operators:
- Selection: Picks the fittest solutions.
- Crossover: Combines parts of two solutions to produce offspring.
- Mutation: Randomly alters parts of solutions to maintain diversity.
Good at:
- Handling complex, nonlinear, and multi-modal problems.
- Finding global optima where traditional methods may get stuck in local optima.

D. Numerical Example
Problem: Minimize the function f(x) = x^2 for x [0, 10].
Solution Step-by-Step:

1. Initial Population:
Randomly generate 4 candidates:
x = [2, 8, 5, 1]

2. Evaluate Fitness:
Fitness could be inverse of f(x) :
fitness = 1 / (1 + f(x))
x=2 f=4 fitness = 1/5=0.2
x=8 f=64 1/65 0.015
x=5 f=25 1/26 0.038
x=1 f=1 1/2=0.5

3. Selection:
Select the top 2 solutions based on fitness:
x=1 and 2.

4. Crossover:
Combine parts (e.g., average):
New candidate: (1 + 2)/2 = 1.5.

5. Mutation:
Randomly mutate the new candidate slightly, e.g., add small noise:
x=1.5 + 0.1 = 1.6.

6. Next Generation:
Replace the least fit solutions with new ones; repeat the process.

Over several iterations, the solutions will approach x=0, the minimum point, since f(x)=x^2 is
minimized at 0.
E. Applications of Genetic Algorithms
Optimization Problems:
- Scheduling (e.g., job-shop scheduling)
- Route planning (e.g., Traveling Salesman Problem)
- Design optimization (e.g., aerodynamic shapes)
Machine Learning:
- Feature selection
- Hyperparameter tuning
Engineering:
- Control system design
- Structural design
Bioinformatics:
- Sequence alignment
- Protein folding

---------------------*-END-*---------------------