358
M. Antoniou et al.
11.1 Evolutionary Optimisation
Finding the exact solution of an optimisation problem with a deterministic method
guarantees the optimality of this solution. For example, running an exhaustive search
of all the combinations of the variables of a function, until the best solution is
obtained, is one of these approaches. As one can understand, this is prohibitive
to problem instances above a number of variables, since the runtime complexity
grows exponentially, the search space becomes huge and the needed computational
resources are not yet available. Moreover, one should consider that usually what is
being optimised (especially in real-world applications) is actually a model of the
problem, a representation of reality, which already is an approximation. Therefore,
trying to find an exact solution is not always useful, since finding a solution near
to optimal or a better than known so far can be sufficient enough. Stochastic
algorithms that use random sampling for directing the search process [1] cannot
prove the convergence to a global optimum, but can provide a sufficiently good
solution and alternative for this kind of complex problems within a reasonable
time [2]. Moreover, metaheuristic algorithms make few or no assumptions about
a problem and may apply a deterministic method to explore the search space.
A metaheuristic algorithm may implement single solution or population-based
searches. In a single solution approach, one single candidate solution is being
improved, whilst in population-based methods a number of candidate solutions are
taken into consideration to guide the search [3]. One of the most popular branches
of population-based metaheuristics is evolutionary algorithm (EA).
11.1.1 Evolutionary Algorithms
Evolutionary algorithms (EAs) are nature-inspired approaches, imitating the Darwinian evolution of species or other similar phenomena. They occupy an important
position amongst optimisation techniques when solving difficult optimisation problems, being non-linear, non-convex, multimodal or non-differentiable in the variable
search space, or might even require considering multiple contradictory objectives.
They are typically used to provide good solutions to problems that cannot be solved
easily using other techniques. When it may be too computationally intensive to find
an exact solution, a near-optimal solution might be sufficient. EAs do not guarantee
to find an optimal solution, but they often find a good and acceptable solution if it
exists [4].
EAs apply principles of evolution found in nature, such as reproduction, mutation, recombination and selection. In an EA a number of artificial individuals
(candidate solutions to the optimisation problem) search simultaneously over the
problem search space [5]. The shared environment dictates the fitness or performance of each individual in the population. The individuals compete continually
with each other to discover optimal areas of the search space. It is expected that
M. Antoniou et al.
11.1 Evolutionary Optimisation
Finding the exact solution of an optimisation problem with a deterministic method
guarantees the optimality of this solution. For example, running an exhaustive search
of all the combinations of the variables of a function, until the best solution is
obtained, is one of these approaches. As one can understand, this is prohibitive
to problem instances above a number of variables, since the runtime complexity
grows exponentially, the search space becomes huge and the needed computational
resources are not yet available. Moreover, one should consider that usually what is
being optimised (especially in real-world applications) is actually a model of the
problem, a representation of reality, which already is an approximation. Therefore,
trying to find an exact solution is not always useful, since finding a solution near
to optimal or a better than known so far can be sufficient enough. Stochastic
algorithms that use random sampling for directing the search process [1] cannot
prove the convergence to a global optimum, but can provide a sufficiently good
solution and alternative for this kind of complex problems within a reasonable
time [2]. Moreover, metaheuristic algorithms make few or no assumptions about
a problem and may apply a deterministic method to explore the search space.
A metaheuristic algorithm may implement single solution or population-based
searches. In a single solution approach, one single candidate solution is being
improved, whilst in population-based methods a number of candidate solutions are
taken into consideration to guide the search [3]. One of the most popular branches
of population-based metaheuristics is evolutionary algorithm (EA).
11.1.1 Evolutionary Algorithms
Evolutionary algorithms (EAs) are nature-inspired approaches, imitating the Darwinian evolution of species or other similar phenomena. They occupy an important
position amongst optimisation techniques when solving difficult optimisation problems, being non-linear, non-convex, multimodal or non-differentiable in the variable
search space, or might even require considering multiple contradictory objectives.
They are typically used to provide good solutions to problems that cannot be solved
easily using other techniques. When it may be too computationally intensive to find
an exact solution, a near-optimal solution might be sufficient. EAs do not guarantee
to find an optimal solution, but they often find a good and acceptable solution if it
exists [4].
EAs apply principles of evolution found in nature, such as reproduction, mutation, recombination and selection. In an EA a number of artificial individuals
(candidate solutions to the optimisation problem) search simultaneously over the
problem search space [5]. The shared environment dictates the fitness or performance of each individual in the population. The individuals compete continually
with each other to discover optimal areas of the search space. It is expected that