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

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

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.