动态环境下基于聚类的自学习多种群算法研究

Many real world optimization problems are changing overtime, and changes are difficult or impossible to be detected. Evolutionary computation has been subjected to two fundamental challenges when solving dynamic optimization problems (DOPs). They are how to maintain the social diversity and how to handle the dynamism, respectively. In order to solve the two issues, this proposal proposes a general framework of self-learning multi-population methods using clustering in dynamic environments. To maintain the population diversity in changing environments, this framework employs some feedback information obtained from the whole populations to estimate a proper number of individuals needed. A hierarchical clustering method is used for the first time to create multiple populations to solve DOPs. This framework provides an efficient way to solve some difficult issues which have never been discussed in the literature of multi-population methods for DOPs, e.g., how to define search areas of sub-populations, how to define the number of sub-populations, and how to create sub-populations. Because only feedback from populations themselves is used to maintain the population diversity, this framework can be used in dynamic environments with any change types, including the environments where changes are hard or impossible to be detected. This is quite different from the research for DOPs, much of which is based on the assumption that changes can be detected or predicted. Therefore, this research would provide a general platform for evolutionary algorithms based on multi-population methods in dynamic environments, and it would also promote theoretical research in real-world applications.

现实中很多优化问题是变化的，而且变化是很难或者不能被检测到的。如何合理地保持种群多样性和处理环境的变化是演化计算求解这类动态优化问题面临的两个挑战。为了解决以上挑战，本项目将设计一个基于聚类的自学习多种群算法框架。该算法框架利用演化过程中种群的反馈信息，推断出与环境匹配的个体数量，并用聚类的办法生成子种群，从而能在变化的环境中合理地保持种群的多样性。本项目首次利用层次聚类方法生成多个种群，可以有效地解决多种群方法中尚未深入讨论和解决的困难，比如怎样定义种群的数量及如何产生每个种群等。另外，该算法框架仅利用种群自身的反馈信息来维持种群的多样性，不依赖于环境变化的检测。它适用于变化很难或者不能被检测到的动态环境，这是目前大部分优化算法不能做到的。因此，该研究可以为基于多种群的演化算法求解动态优化问题提供一个有效的通用平台，对推动理论研究的实际应用具有重要意义。

基于演化计算方法求解动态优化问题的一个关键科学问题是如何保持群体的多样性和收敛性的平衡。多种群方法是解决这个问题的一种有效方法，然而如何设计一个高效的多种群算法依然是一个开放性难题。针对如何设计高效的多种群优化算法来有效求解动态优化问题，对以下研究内容作了重点研究：1）如何给定每个种群的搜索范围，2）如何确定种群的数量；3）如何产生每个种群。我们在整个研究的过程中，发现了多种群算法设计中又一个新的问题--何时响应环境的变化。以往的研究都认为环境发生改变的时刻是算法做出调整和影响的关键时刻，然而我们的研究发现，这种策略并非是最好的选择。除了上面列出的主要因素，我们还讨论了制约算法性能的其他因素，包括如何避免群体间的重复搜索、单个种群的大小、每个种群的搜索策略以及种群间的通讯等。针对第二点研究内容，我们设计了一个基于聚类的多种群粒子群优化算法，提出了一个自学习方法，该方法能够根据在演化过程中种群的演化状态自适应调整种群的数目，从而能够在动态环境下有效预测合理的种群数目。和其他算法进行试验对比分析的结果表明，该算法的性能都明显好于目前主流的算法。上述研究结果对利用多种群求解动态优化问题，提供了算法设计思路，对该领域的研究有着重要学术指导意义。