Page 97 - Mathematical Models and Algorithms for Power System Optimization

New Algorithms Related to Power Flow 87

4.2.2 Outline of Simulated Annealing Method

The SA method is a general purpose technique for solving combinatorial optimization
problems, which is a simulation of the annealing process in the heat treatment of a physical
system. At high temperature, atoms in metal move violently, even in a melted state. Metal
gradually cools to crystal during annealing. The random atom crystal structure may be
optimized by controlling the cooling speed to obtain the desired physical properties of the
metal. The objective function in the SA method corresponds to the energy of a physical system
in the process of annealing, whereas the final crystal structure of a metal corresponds to an
optimal solution of the SA method. As the atom arrangement is completely random during
annealing, the SA method simulating this process is also a stochastic algorithm.
There are four important elements in the SA process: (A) configuration space, (B) perturbation
mechanism, (C) a cost function, and (D) a cooling scheme. The details are explained as follows:

(A) Configuration space is a set of allowed system configurations over which the optimal
solution variables are searched for. Design of configuration space is critical to the
efficiency of the SA-based solution algorithm and the quality of final solutions.
(B) The perturbation mechanism is a set of feasible moves by which variables are to be solved.
These moves allow the system to alter from one state of configuration to another. Moves
are chosen randomly.
(C) Moves that reduce the value of the system cost function (i.e., improve the configuration) are
called“downhill”moves,andmovesthatincreasethesystemcostarecalled“uphill”moves.
All downhill moves are accepted; uphill moves are accepted with a probability of exp
( ΔC/T), where ΔC is the increase in cost and T is a temperature derived from the cooling
scheme.Alluphillmovesthatdonotsatisfytheprobabilityconditionwillberejected.Oneof
theattractivefeaturesoftheSAtechniqueisthatitcanprobabilisticallyacceptuphillmoves,
based on certain criteria, without being trapped into a local solution.
(D) The cooling scheme shall determine the initial temperature and temperature drop rule at
the beginning of the annealing process. These two can be determined through
experiments. In principle, the initial temperature is usually set such that a majority of the
moves can be accepted. The temperature drop rule is a control strategy of the SA
technique. The ideal temperature drop rule is that the temperature will be lowered after
the heat balance is established at each stage. A sufficient number of moves should be
performed so the heat balance corresponds to each stage. That is, only after a certain
number of moves are performed, the temperature is lowered, and the annealing process
moves to the next stage. The temperature drop rule is as follows:

ðÞT k
T k +1 ¼ bT k
where T k —temperature at stage k during annealing; b(T k )—cooling rate.