动态环境下自适应多种群算法及其在供水管网污染源追踪中的应用

The multi-population method is able to track multiple optima in parallel and it is an effective technique for solving dynamic optimization problems. To develop an efficient multi-population based algorithm, three challenging issues should be addressed: When to response to changes; how to adapt the number of populations; and how to adapt the search area of a population . To address these issues, we will develop a feedback learning method based on a database and a fuzzy learning mechanism. Environmental changes will result in behavior changes of an algorithm, which are recorded in the database. By analyzing the changes in the algorithm’s behavior stored in the database, we can predict the future changes of the problem. Therefore, we can use the analysis to further guide the evolution of the algorithm. Contamination source tracking problems in water distribution networks are dynamic optimization problems. Due to data limitations collected from sensors, it is likely to yield that the number of global optima is larger than the true number. In addition, the number will change as the input data change. This will make it difficult for an algorithm to track the global optima. Because it requires the algorithm to adapt the number of populations to the changes. The project will solve the problem with the proposed method. Therefore, the research in this project would have significant impact on both academic research and real-world applications.

多种群方法能并行追踪多个最优解，是一种求解动态优化问题的有效方法，然而设计高效的多种群算法需要解决三个科学难题：何时响应问题的变化、如何调整种群的数量以及如何调整每个种群的搜索范围。为了解决这些难题，本项目将设计一个基于数据库和模糊逻辑的反馈学习机制。问题的变化会导致算法行为的变化，数据库记录算法行为的变化过程，通过分析算法行为的变化过程来预测问题变化的趋势，从而为算法行为的演化提供重要依据，进而实现一种自适应多种群进化算法。供水管网污染源追踪问题的求解难点在于监测数据的局限性会导致优化模型中污染源数目多于实际数目的情况，并且随监测数据的改变而不断变化，这就要求算法具有种群数目自适应的能力，从而形成一种追踪模型中所有污染源的机制。本项目将利用所设计的自适应算法求解此问题，因此，本项目的研究具有重要的学术意义和现实应用价值。

实际优化问题中大多数的场景具有动态变化的特性如供水管网污染源追踪问题，设计一个能够及时找到并跟踪变化的最优解的算法具有重要的指导意义，但是也给算法设计带来了极大的挑战，尤其是一些变化难以检测到的环境。因此，本项目主要研究了动态环境下多种群并行搜索的协同管理策略，其设计关键在于确定响应变化的时刻，种群数量的控制，种群搜索范围的确定以及种群计算资源的分配。为了解决以上问题，本项目设计了一个基于数据库和模糊逻辑的反馈学习机制，通过数据库记录算法行为的过程，分析算法行为的变化过程来预测问题变化的趋势，从而针对性地控制种群的数量和搜索范围；设计了一个基于贡献度的计算资源分配方法为不同的子种群分配计算资源；针对约束优化问题，提出了一种动态多目标约束转换机制和可行比例控制方法，实现了约束边界的动态收缩和可行与非可行域的两侧同时搜索；将所设计的多种群算法用于求解实际供水管网污染源追踪问题时，相比于其他算法，其性能更加突出。通过上述方法和问题的研究，可以为不同环境下多种群算法的设计提供一个通用的解决方案；可以减小理论方法求解实际优化问题的缺口，为实际应用提供了一种有效的解决途径，具有广泛的科学意义与应用价值。