SOLUTION 2023
Que 1:
Simulated Annealing Probability Calculation
In simulated annealing, the probability PPP of accepting a move is given by the formula:
P=eΔETP = e^{\frac{\Delta E}{T}}P=eTΔE where:
• ΔE\Delta EΔE is the change in evaluation (difference between the neighborhood
evaluation and the current evaluation),
• TTT is the current temperature.
Given:
• Current Evaluation (CE) = 16
• Neighborhood Evaluation (NE) = 15
• Current Temperature (T) = 20
The change in evaluation: ΔE=NE−CE=15−16=−1\Delta E = NE - CE = 15 - 16 = -
1ΔE=NE−CE=15−16=−1
The probability of accepting the move: P=e−120P = e^{\frac{-1}{20}}P=e20−1
Using the exponential function: P≈e−0.05≈0.9512P \approx e^{-0.05} \approx
0.9512P≈e−0.05≈0.9512
So, the probability of accepting the move is approximately 0.9512 or 95.12%.
Steepest-Ascent Hill Climbing: Improvements and Advantages
Steepest-ascent hill climbing gets stuck 86% of the time, solving only 14% of problem instances.
Despite this, it has some advantages:
1. Simplicity and Efficiency: It is easy to implement and requires less computational effort
compared to more complex algorithms.
2. Speed: When it does not get stuck, it can find solutions very quickly.
3. Deterministic: Given the same initial state, it will always produce the same result,
making debugging and analysis straightforward.
Improvements:
1. Random Restarts: Restart the algorithm from different random initial states multiple
times to increase the chance of finding a global optimum.
2. Allowing Sideways Moves: Permit moves that do not improve the evaluation to escape
from plateaus, though this may need to be controlled to prevent infinite loops.
3. Stochastic Hill Climbing: Choose among uphill moves at random rather than always
selecting the steepest ascent to avoid local maxima.
4. Simulated Annealing: Incorporate a probability of accepting worse solutions to escape
local maxima, gradually reducing this probability over time.
Mutation Operations in Genetic Algorithms
Mutation operations introduce diversity into the population by making random changes to
individual solutions. Different types of mutation operations include:
1. Bit Flip Mutation:
o Typically used for binary representations.
o A randomly chosen bit in a bit-string is flipped from 0 to 1 or from 1 to 0.
2. Swap Mutation:
o Two randomly chosen positions in the individual's chromosome are swapped.
o Commonly used for permutation-based problems, like the Traveling Salesman
Problem (TSP).
3. Scramble Mutation:
o A subset of genes in the chromosome is randomly shuffled.
o Effective for permutation representations where the order of elements is crucial.
4. Inversion Mutation:
o A segment of the chromosome is selected and its order is reversed.
o Useful in permutation-based representations to introduce significant changes
while maintaining the solution structure.
5. Gaussian Mutation:
o Primarily used for real-valued representations.
o A small Gaussian-distributed value is added to a randomly selected gene.
o Suitable for continuous optimization problems.
6. Uniform Mutation:
o A selected gene is replaced with a uniformly random value from the gene’s
domain.
o Useful for real-valued or integer representations to introduce substantial variation.
These mutation operations help maintain genetic diversity within the population, preventing
premature convergence and enhancing the algorithm's ability to explore the solution space
effectively.
Que 2:
Sussman Anomaly
The Sussman anomaly is a classic example in AI planning, specifically in the context of the
blocks world problem. It illustrates a situation where a naive planning algorithm can get stuck in
a cycle of undoing and redoing steps because of dependencies between goals.
Blocks World Problem Context
In the blocks world problem, you have a set of blocks that can be moved around, with the goal of
achieving a specific configuration. For example, you might need to stack block A on block B and
block B on block C.
Anomaly Description
Consider a situation where you want to achieve the following goals:
1. A on B
2. B on C
If the initial state is:
• A on the table
• B on the table
• C on the table
A naive planner might face the following issues:
1. To put A on B, you might need to move B first to make space for A.
2. But moving B can interfere with the goal of having B on C.
3. Similarly, achieving B on C might require moving A, interfering with A on B.
This creates a cycle where steps to achieve one goal undo the steps for another goal.
Overcoming Sussman Anomaly
One way to overcome the Sussman anomaly is to use Partial Order Planning (POP). POP
constructs plans where actions are partially ordered, allowing flexibility in the order of execution
and ensuring dependencies are managed correctly.
Partially Ordered Plan for "Wearing Socks and Shoes"
Given:
• Actions:
1. left-sock (pre: CleanLeftSock; add: LeftSockOn)
2. right-sock (pre: CleanRightSock; add: RightSockOn)
3. left-shoe (pre: LeftSockOn; add: LeftShoeOn)
4. right-shoe (pre: RightSockOn; add: RightShoeOn)
• Initial state: (CleanLeftSock, CleanRightSock)
• Goal state: (LeftShoeOn, RightShoeOn)
Step-by-Step Plan Generation
1. Initial State: (CleanLeftSock, CleanRightSock)
2. Goal Decomposition:
o Goal 1: LeftShoeOn
o Goal 2: RightShoeOn
3. Action Selection for Goals:
o To achieve LeftShoeOn, the action left-shoe is needed (precondition:
LeftSockOn).
o To achieve RightShoeOn, the action right-shoe is needed (precondition:
RightSockOn).
4. Subgoal Establishment:
o For left-shoe: Need LeftSockOn (achieved by left-sock).
o For right-shoe: Need RightSockOn (achieved by right-sock).
5. Construct Partial Order:
o Add left-sock before left-shoe (left-sock → left-shoe).
o Add right-sock before right-shoe (right-sock → right-shoe).
6. Initial Partial Plan:
o left-sock → left-shoe
o right-sock → right-shoe
Causal Link Protection
Causal Link: An action's precondition or effect is protected by ensuring no other action
invalidates it.
If the right-sock action additionally removes the atom LeftSockOn, we need to protect the
causal link between left-sock and left-shoe.
Protected Causal Link:
1. From left-sock to left-shoe:
o Ensure LeftSockOn is not removed by any action that occurs between them.
2. Adjust partial order:
o Ensure right-sock occurs either before left-sock or after left-shoe.
Updated Partial Order with Causal Link Protection
1. Add an order constraint:
o left-sock → left-shoe
o right-sock → right-shoe
o right-sock before left-sock or after left-shoe
2. Two possible orderings:
o right-sock → left-sock → left-shoe → right-shoe
o left-sock → left-shoe → right-sock → right-shoe
Final Protected Plan:
• Option 1: right-sock → left-sock → left-shoe → right-shoe
• Option 2: left-sock → left-shoe → right-sock → right-shoe
This ensures that LeftSockOn is established by left-sock and used by left-shoe without
being removed by right-sock.
Que 3:
[Link]
Que 4:
Que 5:
i.
ii,iii,iv
v.