论文部分内容阅读
实值优化问题普遍存在于工业与工程实践中,具有广泛的应用背景。演化算法是从自然界的进化与自适应机制中获得启发而发展起来的求解问题的计算方法,具有简单、易于操作和通用性强等特性,在实值优化领域取得了广泛的成功,受到了人们越来越多的重视。数十年间,演化实值优化获得了飞速的发展,各种各样的实值演化算法不断涌现。这些算法的提出一方面促进了实值演化优化的发展,但同时也给实践人员带来了如何选择算法的问题。实际中,人们所能提供的计算时间通常是有限的。因此,怎样在有限时间内为给定问题找到尽可能好的解,具有十分重要的现实意义。对于一个给定的问题,人们常常事先并不知道选择何种算法才能有效地进行求解。由于计算时间有限,一旦所选择的算法表现不佳,则很难再有足够的时间选择下一个算法进行有效求解。因此,对算法的选择是有风险的。针对这一问题,我们提出了一个用于比较两个算法风险程度的度量标准,并讨论了该标准的合理性。在定义了风险度量标准之后,我们还面临怎样减小已有算法的风险程度这一问题。我们建议,相对于将所有计算时间都“投注”在单个算法上,将时间分配在多个算法上将能够获得更优的整体性能。基于这一思想,我们设计出一种演化算法的投资组合设计框架(population-based algorithmportfolios, PAP)。它将计算时间预先分配到多个子算法上,子算法并行进行搜索。此外,PAP通过周期性地激活迁移机制以促进子算法间的信息交流。该框架能够将任意实值演化算法组合在一起,具有简单、易实现等优点。我们通过理论与实验相结合的方式,全面分析了PAP框架在提升子算法整体性能、减小子算法风险方面的潜力。接下来,我们进一步讨论了如何在有限时间内最有效地求解一组实值优化问题。而对于实值优化问题,通常存在若干演化算法可以对其进行求解。通过第二章的研究成果可以看出,相对于简单地将计算时间平均分配到各个候选算法上,或者任意选择一个算法并将所有计算时间分配给该算法,更好的做法是在求解问题之前先进行算法选择。基于这样的考虑,我们提出了以演化算法投资组合作为基本搜索算法的解决方案。该方案能够为一个给定的问题集自动地找出最优PAP实例,具有简单易用的优点。此外,它对问题间的联系不作任何假设,并且利用了所有算法在所有问题上的性能信息。PAP作为该解决方案的基本搜索算法,具有提升其子算法在给定问题集上整体性能的潜力。然而,怎样选择一个最优的算法子集来进行投资组合设计,在此前的工作中并没有提及。我们第一次将这一选择任务形式化为一个优化问题,并提出两个选择方法,试图尽可能高效地找出最优的PAP实例。实验结果表明,该解决方案在解决一组问题时具有十分优异的性能。最后,我们将演化算法投资组合应用于非均匀间隔对称天线阵列综合问题。由于差分演化算法和粒子群算法在该问题上都已表现出良好的性能,因此,我们相应地选择了差分演化算法的一个变体,和粒子群算法的一个变体,作为子算法进行投资组合设计。为了评估该投资组合实例的整体性能,我们将其与非均匀天线阵列综合领域代表目前最新水平的算法进行全方面的比较。实验表明,该投资组合实例在所有4个优化问题上都获得了最低的优化目标值,并且算法在求解问题时具有更高的可靠性。此外,当我们对解的质量要求更高时,该投资组合实例具有更高的求解效率。