面向大规模复杂优化问题的自适应合作协同进化算法研究

Evolutionary Algorithms (EAs) have been widely used to solve the optimization problems in the fields of science and engineering. However, the performance of the traditional EAs deteriorates rapidly with the scale of the optimization problems increases. Currently, Cooperative Co-evolutionary Algorithm (CCA) has been one of the effective techniques to solve the large-scale optimization problems. However, on the one hand, existing decomposition strategies are only suitable to the large-scale separable optimization problems. On the other hand, dimensionality and characteristic are two important factors of the sub-problems, but researchers have not considered the important influence of them when designing EA to solve the sub-problems. The purpose of this research project is to propose an efficient self-adaptive CCA for solving the large-scale complex optimization problems. Firstly, the structure knowledge of the large-scale complex optimization problems would be obtained. After that, an automatic decomposition strategy would be proposed. Secondly, the influence to the EA caused by different dimensionality and characteristic of the sub-problems would be researched, and a self-adaptive evolutionary algorithm which can adapt the difference would be proposed. Finally, the computing load assigning problem would be researched and a suitable cooperative co-evolutionary model would be proposed. This research project not only can expand the research scope of the large-scale complex optimization problem and the CCA, but also can provide an efficient and novel method for solving the large-scale complex optimization problems. The research achievement can be employed to many practical application problems such as the covering problem in the large-scale wireless sensor networks.

进化算法被广泛用于求解科学研究和工程应用领域中的优化问题。然而，随着问题规模的增大，传统进化算法的求解性能急剧下降。目前，合作协同进化算法成了求解大规模优化问题的有效途径之一。但是，一方面，现有分解策略大多仅仅适用于大规模可分优化问题；另一方面，现有研究在设计求解子问题的进化算法时未能注意子问题的维度和性质对进化算法性能的重要影响。本项目旨在提出高效求解大规模复杂优化问题的自适应合作协同进化算法。首先，获取大规模复杂优化问题的结构知识，在此基础上提出自动分解策略。其次，研究子问题维度和性质的差异对进化算法性能的影响，提出能够适应子问题维度和性质不同的自适应进化算法。最后，研究子问题优化计算开销分配问题并设计合适的合作协同进化模型。该研究可拓展大规模优化问题和合作协同进化算法的研究范畴，为求解大规模复杂优化问题提供有效的新方法，研究成果可用于大规模无线传感网络覆盖优化等实际应用领域。

最优化问题广泛存在于科学研究和工程应用领域。由于求解最优化问题的最速下降法、牛顿法、共轭梯度法等传统优化方法通常要求优化问题的目标函数具有连续、可微、单峰等性质，而实际优化问题常常具有非线性、多维度、多峰值、不连续、不可微、动态不确定等性质，这使传统优化方法的发展和应用受到了很大的限制。近几十年来，随着计算机容量和计算速度的不断提高、大规模并行处理技术的产生和并行分布式理论的逐步成熟，无需优化问题特殊信息的进化算法(Evolutionary Algorithms, EAs)进入了一个全新的发展时期并引起了诸多专家、学者的极大关注。.近年来，随着信息和通信技术的突飞猛进，物理信息系统、互联网、物联网和社交网络等技术迅猛发展，各行各业所面临的数据在规模上呈爆炸式增长，大数据(big data)已广泛存在。在大数据时代，网络规划、飞行器设计、 数据挖掘、分布式系统、交通运输、环境保护、生物力学等实际工程应用领域都已出现了大规模优化问题。例如，在随机部署的大规模无线传感器网络中，为了使网络覆盖最优化，需要优化每个传感器的实际发射范围；在超音速喷气式空间飞行器机翼设计中，为了使全程油耗量最小化，需要优化来自空气动力学、结构力学、气动力弹性学等多个交叉学科的大量参数。这些优化问题的求解空间规模和复杂性呈指数增长，而传统进化算法的性能随着优化问题规模和复杂性的增加而迅速降低，他们无法在线性增长的时间内 求得问题的最优解或近似最优解，即传统进化算法的可扩展性 (scalability)较差，这就是进化算法研究领域所谓的“维度灾难 (curse of dimensionality)”问题。目前，已有研究针对的往往是大规模简单优化问题，而实际中存在着大量大规模复杂优化问题。因此，需要进一步拓宽研究范畴，即需要针对大规模复杂优化问题寻求有效求解的新理论和新方法，这项研究不仅具有重要的理论意义，而且具有更广阔的应用前景。