238
A. Riccardi et al.
The larger group of stochastic optimisation techniques are heuristic. They are most
widely applied in practice, but in general no mathematical proof of convergence
exists. However, some results on convergence for evolutionary methods, provided
that the method satisfies some very general conditions, have been published for
single- [20] and multi-objective [21] problems.
• Two-phase methods [22]: they are the stochastic counterpart of the deterministic
grid search technique. They combine two phases of search: a global one and
a local one. The process starts with a random sampling of the feasible space
followed by the application of a local refinement. Multistart [22], clustering
methods [23] and multilevel single linkage [24] are the examples. The range
of applications for the technique is constrained to the local search used. The
greedy global strategy is suitable for both continuous and discrete variables with
no assumptions on the model structure.
• Simulated annealing [25]: the technique is based on the analogy between
minimising a cost function and the cooling process of a material till it reaches
its state of low energy equilibrium. The algorithm iteratively brings the actual
state (optimisation variables) to a lower level of the internal energy of the system
(objective function). The changes between the states are done probabilistically.
The new configuration is constructed by imposing a random displacement at each
step. If the energy of the new state is lower than the previous one, the change
is accepted. If the energy is greater, the new configuration is accepted with a
probabilistic value. The probabilistic acceptance of upward moves is aiming to
avoid the convergence to the local minima. It is able to tackle global optimisation
problems with discrete and continuous variables under mild assumptions on the
model regularity.
• Genetic algorithms (GAs) [26]: are stochastic search methods that take their
inspiration from natural selection and survival of the fittest in the biological
world. Each iteration of a GA involves a competitive selection that eliminates
poor solutions. The solutions with high fitness are recombined with other solutions by swapping parts of a solution with another. The solutions are also mutated
by making a small change to a single element, or a small number of elements,
of the solution. Recombination and mutation are used to generate new solutions
that are biased towards the regions of the space for which good solutions have
already been seen. GAs were born and are well suited, to solve discrete problems,
and they have been successfully applied to continuous problems as well. Most of
their efficacy is due to a powerful recombination operator, which, for this reason,
becomes the main operator. The recombination operation used by GAs requires
that the problem can be represented in a manner that makes combinations of the
two solutions likely to generate interesting solutions. Selecting an appropriate
representation is a challenging aspect to properly apply these methods. Usually
a binary coding is used, and many applications have demonstrated the validity of
this approach.
• Estimation of distribution algorithms (EDA): with the idea that probabilistic
modelling may offer a more efficient/effective way to treat real problems,
A. Riccardi et al.
The larger group of stochastic optimisation techniques are heuristic. They are most
widely applied in practice, but in general no mathematical proof of convergence
exists. However, some results on convergence for evolutionary methods, provided
that the method satisfies some very general conditions, have been published for
single- [20] and multi-objective [21] problems.
• Two-phase methods [22]: they are the stochastic counterpart of the deterministic
grid search technique. They combine two phases of search: a global one and
a local one. The process starts with a random sampling of the feasible space
followed by the application of a local refinement. Multistart [22], clustering
methods [23] and multilevel single linkage [24] are the examples. The range
of applications for the technique is constrained to the local search used. The
greedy global strategy is suitable for both continuous and discrete variables with
no assumptions on the model structure.
• Simulated annealing [25]: the technique is based on the analogy between
minimising a cost function and the cooling process of a material till it reaches
its state of low energy equilibrium. The algorithm iteratively brings the actual
state (optimisation variables) to a lower level of the internal energy of the system
(objective function). The changes between the states are done probabilistically.
The new configuration is constructed by imposing a random displacement at each
step. If the energy of the new state is lower than the previous one, the change
is accepted. If the energy is greater, the new configuration is accepted with a
probabilistic value. The probabilistic acceptance of upward moves is aiming to
avoid the convergence to the local minima. It is able to tackle global optimisation
problems with discrete and continuous variables under mild assumptions on the
model regularity.
• Genetic algorithms (GAs) [26]: are stochastic search methods that take their
inspiration from natural selection and survival of the fittest in the biological
world. Each iteration of a GA involves a competitive selection that eliminates
poor solutions. The solutions with high fitness are recombined with other solutions by swapping parts of a solution with another. The solutions are also mutated
by making a small change to a single element, or a small number of elements,
of the solution. Recombination and mutation are used to generate new solutions
that are biased towards the regions of the space for which good solutions have
already been seen. GAs were born and are well suited, to solve discrete problems,
and they have been successfully applied to continuous problems as well. Most of
their efficacy is due to a powerful recombination operator, which, for this reason,
becomes the main operator. The recombination operation used by GAs requires
that the problem can be represented in a manner that makes combinations of the
two solutions likely to generate interesting solutions. Selecting an appropriate
representation is a challenging aspect to properly apply these methods. Usually
a binary coding is used, and many applications have demonstrated the validity of
this approach.
• Estimation of distribution algorithms (EDA): with the idea that probabilistic
modelling may offer a more efficient/effective way to treat real problems,