EADOP@Bham

Overview

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.