Evolutionary Dynamic Optimisation for Network Problems

由于大多数网络优化问题都是np困难的，传统的精确算法计算成本高，不能有效地处理大型问题。因此，启发式或元启发式算法，如进化算法（EAs），在实践中经常用于求解nop。到目前为止，大多数nop的研究和应用都假设了静态或准静态条件，其中网络环境和优化问题都是事先已知的，并且在解决问题的过程中保持不变。然而，现实世界中的大多数nop都受到动态环境的影响，其中网络拓扑、资源可用性、用户需求等都随着时间而变化，并且不是先验的。为了令人满意地处理现实世界的nop，我们不能忽视内在的动态。我们需要考虑不断变化的网络环境下的nop，即对动态nop （dnop）进行建模。DNOP比静态版本要困难得多，因为网络环境的动态性和问题本身带来了许多额外的困难。为了成功地解决DNOP，应该随着时间的推移提供一系列高质量的解决方案，而不是像在静态环境中那样提供一次性的解决方案。近年来，研究动态优化问题（DOPs）的ea的兴趣迅速增长，其中目标函数、决策变量和环境参数可能随时间而变化。然而，目前还没有对不同网络环境下dnop的EC方法进行系统的研究。无论是从理论上还是从计算上，我们都不知道是什么让EA对哪种类型的动力学有效。目前尚不清楚如何对不同的动力学进行建模和表征，以便更深入地了解DNOPs。与人为基准函数相反，dnop在实践中的独特功能尚未完全揭示。本课题旨在通过计算、理论和应用研究，填补上述空白，为DNOPs开发先进的EC方法，并进一步了解EC方法为什么以及如何有效和高效地解决DNOPs。在本提案中，我们将主要以物流网络作为dnop的例子，尽管所提出的研究更为通用，并且有可能对不同网络环境中的广泛应用产生深远的影响。

Since most of the network optimisation problems (NOPs) are NP-hard, classical exact algorithms suffer from high computational costs and cannot deal with large problems efficiently. As a result, heuristic or metaheuristic algorithms, such as evolutionary algorithms (EAs), are often used to solve NOPs in practice. Most research and applications in NOPs so far have assumed static or quasi-static conditions, where both the network environments and the optimisation problems are known in advance and remain unchanged in the problem-solving process. However, most NOPs in the real world are subject to dynamic environments, where the network topologies, availability of resources, user requirements, etc. change with time and are not known a priori. To satisfactorily address real-world NOPs, we cannot ignore the inherent dynamics. We need to consider NOPs under continuously changing network environments, i.e., to model dynamic NOPs (DNOPs). A DNOP is much harder than its static version since the dynamics in the network environment and the problem itself bring in many additional difficulties. To successfully solve a DNOP, a series of high-quality solutions should be provided over time instead of a one-off solution as in the static environment. In recent years, there has been a rapidly growing interest in studying EAs for dynamic optimisation problems (DOPs), where the objective function, decision variables, and environmental parameters may change over time. However, there is no systematic research on EC methods for DNOPs in different network environments. It is still unknown, either theoretically or computationally, what makes an EA effective and efficient for what types of dynamics. It is still unclear how different dynamics can be modelled and characterised in order to gain a deeper understanding of DNOPs. The unique features of DNOPs in practice, as opposed to the artificial benchmark functions, are yet to be fully revealed. This proposal aims to fill in the gaps mentioned above, develop advanced EC methods for DNOPs, and further our understanding of why and how EC methods can solve DNOPs effectively and efficiently, through computational, theoretical and applied studies. In this proposal, we will mainly take logistics networks as examples of DNOPs, although the proposed research is more generic and has the potential to have a far-reaching impact on a wide range of applications in different network environments.