Evolutionary Algorithms for Dynamic Optimisation Problems: Design, Analysis and Applications

进化算法（EAs）已被应用于求解许多平稳问题。然而，现实世界的问题通常更加复杂和动态，其中目标函数、决策变量和环境参数可能随时间而变化。在这个项目中，我们将研究新的EA方法来解决动态优化问题（DOPs），这是一个具有挑战性但非常重要的研究领域。提出的研究有三个主要方面：(1)与本田欧洲研究所的研究人员合作设计和评估DOPs的新EA，(2)理论上分析DOPs的EA，以及(3)采用已开发的EA方法来解决动态电信优化问题。在本项目中，我们将首先基于环境的问题难度、可扩展性、循环性和噪声的概念构建标准化的、离散的和连续的动态测试环境，以及用于评估DOPs的ea的标准化性能度量。基于标准化的动态测试和评估环境，我们将基于我们之前的研究，设计和评估新的ea及其混合，例如分布估计算法（EDAs），遗传算法，群体智能和自适应进化算法。这里的指导思想是提高EA对基因型空间中不同程度的环境变化的适应性，无论是二元的还是非二元的。系统地、自适应地结合针对重大变化的类二元论方案，针对中等变化的类随机迁移方案，以及针对小变化的一般突变或变异方案，有望大大提高EA在不同动态环境中的性能。当环境涉及循环变化时，可以使用记忆方案。为了更好地理解基本问题，本项目将对DOPs的ea进行理论分析。我们将应用漂移分析和鞅理论作为起点，分析用于DOPs的ea的计算时间复杂度和用于DOPs的ea的动态行为，如跟踪误差、跟踪速度和到达最优点的可靠性等特性。在上述EA设计、实验评估和形式化分析的基础上，我们将通过提取高效EA的关键技术/属性，并在基因型空间中研究它们与待解的EA特征之间的关系，建立一个通用的EA框架。该项目的另一个关键方面是应用和调整已开发的ea，以解决现实世界中的核心动态电信问题，例如动态频率分配问题和动态呼叫路由问题。我们将与英国电信（BT）的研究人员密切合作，提取特定领域的知识，并使用适当的数学和图形表示建立动态电信问题的模型。获得的领域知识将集成到我们的ea中，以提高效率和有效性。在这个项目中开发的所有算法和软件都将公开提供，以使尽可能多的用户受益，无论他们是来自学术界还是工业界。

Evolutionary algorithms (EAs) have been applied to solve many stationary problems. However, real-world problems are usually more complex and dynamic, where the objective function, decision variables, and environmental parameters may change over time. In this project, we will investigate novel EA approaches to address dynamic optimisation problems (DOPs), a challenging but very important research area. The proposed research has three main aspects: (1) designing and evaluating new EAs for DOPs in collaboration with researchers from Honda Research Institute Europe, (2) theoretically analysing EAs for DOPs, and (3) adapting developed EA approaches to solve dynamic telecommunication optimisation problems. In this project, we will first construct standardised, both 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 British Telecommunications (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 academe or industry.