Online optimization algorithms 187
E ≤ E 0 . When kT is large, there is a large probability for the system energy to
increase. This allows the system to jump out of local minima. However, when
temperature is cooled down, the system energy will more likely decrease.
When simulated annealing is applied to function minimization, the function value is analogous to the system energy. The temperature is a controlled
parameter which dictates the probability distribution of function value increase, p(f, f 0 , T ). In each step, a new temperature T is chosen. A trial solution around the present solution is evaluated. The new solution is accepted if
its function value is lower (i.e., f < f 0 ). If the function value is higher, the
new solution is accepted if p(f, f 0 , T ) is larger than a random number drawn
from the uniform distribution of [0, 1]. The variation of temperature with the
steps, the way to choose the trial solution, and the choice of the probability
function have a large impact to the performance of the algorithm.
Genetic algorithms (GA) [28, 27]: Genetic algorithms became popular in accelerator design optimization in recent years. A genetic algorithm
manipulates a population of solutions over many generations. In each generation, a portion of the population is replaced with good solutions selected
from new solutions that are generated through cross-over or mutation operations. In the cross-over operation two “children” solutions are spawned by
combining the parameter values of two “parent” solutions. The mutation operation generates a new solution by randomly modifying the parameter values
of an existing solution. The new solutions are first mixed with the existing
population of solutions, from which the fittest solutions (i.e., the ones with
the lowest objective function values) are selected to enter the next generation.
The solutions that survive the selection operation are generally better and
they tend to produce better new solutions. Therefore, the fitness (i.e., the
objective function) of the solutions will improve over time and the population
gradually converges to the minimum. The NSGA-II algorithm is a popular
multi-objective genetic algorithm (MOGA) [27].
The parameter vector for a solution is called a chromosome, which can be
represented by a bit string or an array of floating numbers. For a bit string,
the cross-over can be done by swapping bits between the two chromosomes.
In the case of an array of floating numbers, cross-over of two solutions can be
performed with simulated binary cross-over (SBX) [29],
x
1,k =
1
2
[(1 − β k )x 1,k + (1 + β k )x 2,k ],
(7.18a)
x
2,k =
1
2
[(1 + β k )x 1,k + (1 − β k )x 2,k ],
(7.18b)
where x 1 and x 2 are the parent solutions, x
1 and x
2 are the children solutions,
subscript k indicates the k’th parameter, and β k is a random number given
by
β(u ≤
1
2
) = (2u)
1
µc +1 , or β(u >
1
2
) = (2(1 − u))
−
1
µc +1 ,
(7.19)
E ≤ E 0 . When kT is large, there is a large probability for the system energy to
increase. This allows the system to jump out of local minima. However, when
temperature is cooled down, the system energy will more likely decrease.
When simulated annealing is applied to function minimization, the function value is analogous to the system energy. The temperature is a controlled
parameter which dictates the probability distribution of function value increase, p(f, f 0 , T ). In each step, a new temperature T is chosen. A trial solution around the present solution is evaluated. The new solution is accepted if
its function value is lower (i.e., f < f 0 ). If the function value is higher, the
new solution is accepted if p(f, f 0 , T ) is larger than a random number drawn
from the uniform distribution of [0, 1]. The variation of temperature with the
steps, the way to choose the trial solution, and the choice of the probability
function have a large impact to the performance of the algorithm.
Genetic algorithms (GA) [28, 27]: Genetic algorithms became popular in accelerator design optimization in recent years. A genetic algorithm
manipulates a population of solutions over many generations. In each generation, a portion of the population is replaced with good solutions selected
from new solutions that are generated through cross-over or mutation operations. In the cross-over operation two “children” solutions are spawned by
combining the parameter values of two “parent” solutions. The mutation operation generates a new solution by randomly modifying the parameter values
of an existing solution. The new solutions are first mixed with the existing
population of solutions, from which the fittest solutions (i.e., the ones with
the lowest objective function values) are selected to enter the next generation.
The solutions that survive the selection operation are generally better and
they tend to produce better new solutions. Therefore, the fitness (i.e., the
objective function) of the solutions will improve over time and the population
gradually converges to the minimum. The NSGA-II algorithm is a popular
multi-objective genetic algorithm (MOGA) [27].
The parameter vector for a solution is called a chromosome, which can be
represented by a bit string or an array of floating numbers. For a bit string,
the cross-over can be done by swapping bits between the two chromosomes.
In the case of an array of floating numbers, cross-over of two solutions can be
performed with simulated binary cross-over (SBX) [29],
x
1,k =
1
2
[(1 − β k )x 1,k + (1 + β k )x 2,k ],
(7.18a)
x
2,k =
1
2
[(1 + β k )x 1,k + (1 − β k )x 2,k ],
(7.18b)
where x 1 and x 2 are the parent solutions, x
1 and x
2 are the children solutions,
subscript k indicates the k’th parameter, and β k is a random number given
by
β(u ≤
1
2
) = (2u)
1
µc +1 , or β(u >
1
2
) = (2(1 − u))
−
1
µc +1 ,
(7.19)