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

动态优化问题的进化算法：设计、分析和应用

基本信息

批准号：
EP/E060722/2
负责人：
Shengxiang Yang
金额：
--
依托单位：
Brunel University London
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2010
资助国家：
英国
起止时间：
2010 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FE060722%2F2
关键词：
Evolutionary Algorithms Dynamic Optimisation Problems

项目摘要

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.

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