186 Beam-based Correction and Optimization for Accelerators
x 1
x 2
u 1
u 2
0
1
2
3
4
1
′
M
Figure 7.3 Illustration of iterative line minimization with or without conjugate directions. Starting from the initial solution at point 0, the algorithms try to converge
to the minimum at point M with non-conjugate directions x1 and x2, or the conjugate directions, u1 and u2.
function evaluations is not always an improvement. However, there is a benefit
at the cost of the efficiency loss – the stochastic algorithms often have a
better chance of finding the global optimum. By allowing taking steps in bad
directions and using random sampling, the stochastic algorithms are not as
easily attracted to the local minima as the deterministic algorithms are.
Random search: One of the simplest stochastic optimization algorithms
is to sample the parameter space with randomly selected solutions. This
method is not efficient, but it can be very useful in some cases. For example, it can be used to find working solutions from which a starting point for
other algorithms is chosen.
Random search [99] is a method with a little more sophistication. It
searches in the vicinity of the present solution with a random trial solution,
e.g.,
x i+1 = x i + ∆x, with ||∆x|| ≤ r,
(7.17)
where ∆x is randomly selected within the hyper-sphere with a radius r. The
algorithm moves to the new solution if it is better, otherwise tries a new one.
Simulated annealing [97]: Simulated annealing is a method that mimics
the slow cooling process through which hot materials settle to the state with
the lowest energy. The system is characterized by its energy E and temperature T . The system energy normally tends to decrease; but it can also increase
with a certain probability. The probability for the system energy to change
from E 0 to E is given by p(E, E 0 , T ) = exp(−
E−E0
kT ) for E > E 0 and p = 1 for
x 1
x 2
u 1
u 2
0
1
2
3
4
1
′
M
Figure 7.3 Illustration of iterative line minimization with or without conjugate directions. Starting from the initial solution at point 0, the algorithms try to converge
to the minimum at point M with non-conjugate directions x1 and x2, or the conjugate directions, u1 and u2.
function evaluations is not always an improvement. However, there is a benefit
at the cost of the efficiency loss – the stochastic algorithms often have a
better chance of finding the global optimum. By allowing taking steps in bad
directions and using random sampling, the stochastic algorithms are not as
easily attracted to the local minima as the deterministic algorithms are.
Random search: One of the simplest stochastic optimization algorithms
is to sample the parameter space with randomly selected solutions. This
method is not efficient, but it can be very useful in some cases. For example, it can be used to find working solutions from which a starting point for
other algorithms is chosen.
Random search [99] is a method with a little more sophistication. It
searches in the vicinity of the present solution with a random trial solution,
e.g.,
x i+1 = x i + ∆x, with ||∆x|| ≤ r,
(7.17)
where ∆x is randomly selected within the hyper-sphere with a radius r. The
algorithm moves to the new solution if it is better, otherwise tries a new one.
Simulated annealing [97]: Simulated annealing is a method that mimics
the slow cooling process through which hot materials settle to the state with
the lowest energy. The system is characterized by its energy E and temperature T . The system energy normally tends to decrease; but it can also increase
with a certain probability. The probability for the system energy to change
from E 0 to E is given by p(E, E 0 , T ) = exp(−
E−E0
kT ) for E > E 0 and p = 1 for