论文部分内容阅读
在工程设计、科学计算、宏观经济、自动控制和人工智能等诸多领域中存在种类繁多的优化计算问题。然而,根据NFL定理可知,并不存在能够完美的解决所有优化问题的“超级算法”。因此,只有研究优化问题与启发式算法的适配关系,才能有针对性的提高优化算法的性能。此外,启发式优化算法的发展也非常迅猛,新算法和新策略层出不穷,特别是文化基因算法等分层启发式算法取得长足发展。由于文化基因算法的框架内可以储备多种启发式算法作为底层算法,故可以在文化基因算法的框架内实现算法与问题的最佳适配。若要实现这种最佳适配,则必须在了解优化问题特性的基础上设计新的知识体系。优化难度主要研究优化问题的特征如何影响启发式算法的寻优过程,因此优化难度研究是设计新知识体系的理论基础之一。本文工作对启发式算法的进一步发展和解决各领域存在的优化问题都具有特殊意义。针对蚁群算法、粒子群算法等不具备分层结构的启发式算法,优化难度研究能够使其具备针对优化问题进行自设计和自学习的能力。本文从两个方面研究优化难度:首先,本文通过分析优化问题的特征研究优化难度。针对优化问题特征的研究基于最优吸引子定理(OCT)展开,最优吸引子定理是一种描述启发式优化算法作用过程的理论,其以优化特征因子(OFF)为描述优化问题特征的工具。但是,最优吸引子定理并未提供探测或估计优化特征因子的方法。因此,本文提出一种用于估计优化特征因子的方法,通过一个采样序列估计优化特征因子中的两个指标。本文还将优化特征因子和数值函数的频率特性联系起来,通过分析优化问题的频率特性提出有效高频分量占比(EHFR)。然而,优化特征因子虽然抓住了优化难度的核心问题,却未能全面反映问题特征对优化难度的作用。针对优化特征因子无法反映的问题特征,本文通过梯度依赖集合(GDS)度量其对优化难度的影响。其次,本文研究优化难度如何影响启发式优化算法的策略或参数选择。因此需要将不同机制的启发式算法放在相同的框架下讨论,而探索与利用平衡理论是最合适的理论框架之一。在探索与利用平衡理论的基础上,本文以正交实验的方式分别测试具备不同特征的静态和动态优化问题对启发式优化算法的影响,并通过正交实验的理论最优因素组合分析问题特征对选择算法参数的影响。本文基于理论最优因素组合提出基于优化难度的文化基因算法(OHBMA),并将其应用于断口图像的多阈值分割问题。同时,本文还给出测试图像的有效高频分量占比作为分析测试结果的参考。最后,本文通过以上研究工作得出四方面主要结论:(1)有效高频分量占比是目前唯一的频域优化难度指标,并在准确性、稳定性和分辨力三方面都展示出优异的性能。(2)在优化特征因子之外的其它问题特征中,欺骗问题与启发式算法利用信息的方式相关性较强,而粗糙性等特征则较弱。(3)正交实验的结果显示问题特征对探索与利用平衡有显著影响,这种影响的表现是不同优化问题对应探索行为的强度和引入时机不相同。显然,不同的强度和引入时机也对应不同的算法策略和参数。(4)根据基于优化难度的文化基因算法的相关实验结果可知,运用基于优化难度的相关知识能够提高启发式优化算法的性能表现。