Evolutionary Algorithms (EAs) have been applied
successfully to a wide range of stationary optimisation problems. Many
real-world problems, however, possess numerous time-variant attributes
that require a continuous adaptation of the proposed solution. These
dynamic attributes pose many new challenges and in this project, we
will concentrate on the design and analysis of novel EAs for such
dynamic optimisation problems (DOPs). In particular, we will design,
evaluate and analyse theoretically new EAs for DOPs in collaboration
with researchers from Honda Research Institute Europe and adapt these
algorithms to deal explicitly with dynamic telecommunication
optimisation problems as supplied by BT plc.
The proposed research has three main aspects:
- Designing and evaluating new EAs for DOPs in collaboration with
researchers from Honda Research Institute Europe,
- Theoretically
analysing EAs for DOPs,
- Adapting developed EA approaches to
solve dynamic telecommunication optimisation problems.
In this project,
we will first construct standardised (discrete and continuous)
dynamic test environments based on the concept of problem difficulty,
scalability, cyclicity and noise of environments, and standardised
performance measures for evaluating EAs for DOPs. Based on the
standardised dynamic test and evaluation environment, we will then
design and evaluate novel EAs and their hybridisation, e.g., Estimation
of Distribution Algorithms (EDAs), Genetic Algorithms, Swarm
Intelligence and Adaptive Evolutionary Algorithms, for DOPs based on
our previous research. A guiding idea here is to improve EA's
adaptability to different degrees of environmental change in the
genotypic space, be it binary or not. Systematically and adaptively
combining dualism-like schemes for significant changes, random
immigration-like schemes for medium changes, and general mutation or
variation schemes for small changes, is expected to greatly improve
EA's performance in different dynamic environments. And memory schemes
can be used when the environment involves cyclic changes.
In order to
better understand the fundamental issues, theoretical analysis of EAs
for DOPs will be pursued in this project. We will apply drift analysis
and martingale theory as the starting point to analyse the
computational time complexity of EAs for DOPs and the dynamic behaviour
of EAs for DOPs regarding such properties as tracking error, tracking
velocity, and reliability of arriving at optima. Based on the above EA
design, experimental evaluation, and formal analysis, we will then
develop a generic framework of EAs for DOPs by extracting key
techniques/properties of efficient EAs for DOPs and studying the
relationship between them and the characteristics of DOPs being solved
with respect to the environmental dynamics in the genotypic space.
Another key aspect of this project is to apply and adapt developed EAs
for general DOPs to solve core dynamic telecommunications problems,
e.g., dynamic frequency assignment problems and dynamic call routing
problems, in the real world. We will closely collaborate with
researchers from BT to extract
domain-specific knowledge and model dynamic telecommunication problems
using proper mathematical and graph representations. The obtained
domain knowledge will be integrated into our EAs for increased
efficiency and effectiveness. All algorithms and software developed in
this project will be made available publicly to benefit as many users
as possible, whether they are from academia or industry.
