Evolutionary Dynamic Optimisation for Network Problems

由于大多数网络优化问题都是NP-Hard问题，经典的精确算法计算量大，不能有效地处理大型问题。因此，在实际中经常使用启发式或元启发式算法，如进化算法(EA)来求解NOPS。到目前为止，NOPS中的大多数研究和应用都假设了静态或准静态条件，即网络环境和优化问题都是预先知道的，并且在问题求解过程中保持不变。然而，现实世界中的大多数NoP都受到动态环境的影响，其中网络拓扑、资源可用性、用户需求等随着时间而变化，并且不是先验已知的。要令人满意地解决现实世界的NOP，我们不能忽视内在的动态。我们需要考虑不断变化的网络环境下的NOPS，即对动态NOP(DNOPs)进行建模。DnOP比它的静态版本难得多，因为网络环境中的动态和问题本身带来了许多额外的困难。要成功解决DnOP，需要随着时间的推移提供一系列高质量的解决方案，而不是静态环境中的一次性解决方案。近年来，人们对动态优化问题(DOPS)中目标函数、决策变量和环境参数随时间变化的进化算法的研究兴趣与日俱增。然而，目前还没有针对不同网络环境下DNOP的EC方法进行系统的研究。无论是在理论上还是在计算上，是什么使EA对哪种类型的动力学有效和高效，仍然是未知的。目前还不清楚如何对不同的动态进行建模和表征，以便对DNOP有更深入的了解。与人工基准函数相比，DNOP在实践中的独特特性尚未完全揭示。这一建议旨在通过计算、理论和应用研究，填补上述空白，开发适用于DNOP的先进的EC方法，并加深我们对EC方法为什么以及如何有效地解决DNOP的理解。在这项建议中，我们将主要以物流网络作为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.