What is simulated annealing algorithm in artificial intelligence?
Answers
Answered by
0
Simulated annealing maintains a current assignment of values to variables. At each step, it picks a variable at random, then picks a value at random. If assigning that value to the variable is an improvement or does not increase the number of conflicts, the algorithm accepts the assignment and there is a new current assignment. Otherwise, it accepts the assignment with some probability, depending on the temperature and how much worse it is than the current assignment. If the change is not accepted, the current assignment is unchanged.
To control how many worsening steps are accepted, there is a positive real-valued temperature T. Suppose A is the current assignment of a value to each variable. Suppose that h(A) is the evaluation of assignment A to be minimized. For solving constraints, h is typically the number of conflicts. Simulated annealing selects a neighbor at random, which gives a new assignment A'. If h(A') ≤ h(A), it accepts the assignment and A' becomes the new assignment. Otherwise, the assignment is only accepted randomly with probability
e(h(A)-h(A'))/T.
Thus, if h(A') is close to h(A), the assignment is more likely to be accepted. If the temperature is high, the exponent will be close to zero, and so the probability will be close to 1. As the temperature approaches zero, the exponent approaches -∞, and the probability approaches zero.
TemperatureProbability of acceptance1-worse2-worse3-worse100.90.820.7410.370.140.050.250.0180.00030.0000060.10.000052×10-99×10-14
Hope it would help!
To control how many worsening steps are accepted, there is a positive real-valued temperature T. Suppose A is the current assignment of a value to each variable. Suppose that h(A) is the evaluation of assignment A to be minimized. For solving constraints, h is typically the number of conflicts. Simulated annealing selects a neighbor at random, which gives a new assignment A'. If h(A') ≤ h(A), it accepts the assignment and A' becomes the new assignment. Otherwise, the assignment is only accepted randomly with probability
e(h(A)-h(A'))/T.
Thus, if h(A') is close to h(A), the assignment is more likely to be accepted. If the temperature is high, the exponent will be close to zero, and so the probability will be close to 1. As the temperature approaches zero, the exponent approaches -∞, and the probability approaches zero.
TemperatureProbability of acceptance1-worse2-worse3-worse100.90.820.7410.370.140.050.250.0180.00030.0000060.10.000052×10-99×10-14
Hope it would help!
Similar questions