7 Introduction to Optimisation
235
electronic computers into the research community. They are mostly based on the
idea of trying to construct a sequence of approximate solutions which converge to
the exact one by dividing the problem into smaller subproblems or approximations
of the original one. With the evolution of the computational power at the beginning
of the 1990s, different probabilistic global optimisation approaches were affirmed
as new strategies. Among them it is worth to mention simulated and nested
annealing [6, 7] and the large family of evolutionary strategies [8]. They are in
general computationally less efficient than deterministic techniques, but due to their
structure, they are able to tackle a wider range of problems, and no assumptions
on the model regularity and smoothness is required. For these reasons they are
considered as one of the most promising techniques for solving also global discrete
non-linear optimisation problems.
There are several classifications of global optimisation strategies. One is the
already mentioned division between deterministic and stochastic algorithms. In
the first category, the model and the optimisation variables are completely known,
and the algorithm performs through predefined steps. The stochastic component
of the latter group instead lies either on the random sampling of the trial points,
random parameters of the algorithm itself that made the single step not predictable,
or on the use of a stochastic model for the objective function. Another division can
be made between exact methods and heuristic methods. Exact methods provide a
mathematical proof that the optimal solution can be found, while heuristic methods
are not based on convergence theories. In most of the cases, no guarantee of finding
the optimal solution can be provided and used to stop the search process: the
optimisation process is constituted of iterative steps that improve the candidate
solutions based on a measure of the quality of their fitness, a function that combines
indexes of optimality and feasibility.
An overview of the relevant methods is given below according to the first
classification deterministic or stochastic with an internal differentiation between
exact and heuristic methods. The objective of the section is to give a comprehensive
overview of the available methodologies. For details about a specific algorithm,
please refer to the corresponding bibliography. The extension of the methodologies
to the multi-objective case is discussed in the next section.
7.2.2.1 Deterministic Strategies
The first group are deterministic and exact global optimisation strategies [9]. It
means that no randomness is involved in the optimisation process and the algorithm
will always produce the same solutions for the same starting condition or initial
state. The optimisation steps are predictable and a proof of convergence exists.
• Uniform grid search [4]: it is a trivial search strategy that makes use of a grid
over the search domain to evaluate cost and constraints functions. Local search
from a point in each element of the grid can be performed, and the feasible
local minimum with lowest objective function is the approximation of the global
235
electronic computers into the research community. They are mostly based on the
idea of trying to construct a sequence of approximate solutions which converge to
the exact one by dividing the problem into smaller subproblems or approximations
of the original one. With the evolution of the computational power at the beginning
of the 1990s, different probabilistic global optimisation approaches were affirmed
as new strategies. Among them it is worth to mention simulated and nested
annealing [6, 7] and the large family of evolutionary strategies [8]. They are in
general computationally less efficient than deterministic techniques, but due to their
structure, they are able to tackle a wider range of problems, and no assumptions
on the model regularity and smoothness is required. For these reasons they are
considered as one of the most promising techniques for solving also global discrete
non-linear optimisation problems.
There are several classifications of global optimisation strategies. One is the
already mentioned division between deterministic and stochastic algorithms. In
the first category, the model and the optimisation variables are completely known,
and the algorithm performs through predefined steps. The stochastic component
of the latter group instead lies either on the random sampling of the trial points,
random parameters of the algorithm itself that made the single step not predictable,
or on the use of a stochastic model for the objective function. Another division can
be made between exact methods and heuristic methods. Exact methods provide a
mathematical proof that the optimal solution can be found, while heuristic methods
are not based on convergence theories. In most of the cases, no guarantee of finding
the optimal solution can be provided and used to stop the search process: the
optimisation process is constituted of iterative steps that improve the candidate
solutions based on a measure of the quality of their fitness, a function that combines
indexes of optimality and feasibility.
An overview of the relevant methods is given below according to the first
classification deterministic or stochastic with an internal differentiation between
exact and heuristic methods. The objective of the section is to give a comprehensive
overview of the available methodologies. For details about a specific algorithm,
please refer to the corresponding bibliography. The extension of the methodologies
to the multi-objective case is discussed in the next section.
7.2.2.1 Deterministic Strategies
The first group are deterministic and exact global optimisation strategies [9]. It
means that no randomness is involved in the optimisation process and the algorithm
will always produce the same solutions for the same starting condition or initial
state. The optimisation steps are predictable and a proof of convergence exists.
• Uniform grid search [4]: it is a trivial search strategy that makes use of a grid
over the search domain to evaluate cost and constraints functions. Local search
from a point in each element of the grid can be performed, and the feasible
local minimum with lowest objective function is the approximation of the global