摘要
最优化问题广泛存在于管理和工程制造中，普遍有时效性、多约束条件、超大规模等特点。已有许多研究人员针对最优化问题进行深入研究，提出了众多优化方法。经典的优化方法在面对大规模复杂最优化问题时，存在运行时间长以及消耗计算资源大等局限性。然而这类问题又广泛存在人们生活中，涉及经济，工程，科学等方面应用。于是模拟自然进化对问题迭代求解的元启发式算法成为求解大规模复杂最优化问题的重要手段。元启发式算法具有不依赖特定问题、通用性强、优化效率高等特点，现已经被应用于各行各业的优化领域中。禁忌搜索作为一种元启发式算法，通过藐视准则来接受部分被禁忌的解，提高优化能力，可以增大获得全局最优的概率。禁忌搜索在求解组合优化和连续优化问题表现出明显的优势，现已被成功用于求解多种优化问题，然而禁忌搜索的优化过程在一定程度上受到初始解、邻域结构和禁忌属性的影响。在此背景下，提出禁忌搜索元启发式的不同变体是非常必要的。因此，本文针对组合优化和连续优化两类问题，深入研究并改进禁忌搜索。本文主要工作如下： （1）提出一种基于禁忌搜索的自适应启发式算法。针对基本的禁忌搜索局部能力强全局能力弱的问题，引入分散搜索机制，对参考集策略进行改进，根据产生新解的质量自适应调整参考集大小，充分利用优质解的信息，平衡种群中多样性，并加入重复翻转变异策略，使得搜索在停滞时能经过连续多次的扰动产生新解，更高效的避免搜索陷入局部最优，使算法搜索朝着全局最优解的方向前进。此外，根据所求问题特点，对禁忌搜索的邻域动作进行创新，设计限制步长交换的邻域结构。为验证所提算法性能，使用OR-Library中的90个基准实例，与对比算法比较，所提算法在求解多维背包问题的效率和精度上更具竞争力。 （2）提出一种基于禁忌搜索的人工蜂群算法。针对人工蜂群算法重勘探弱开采和构建种群扑结构耗时的问题，设计网络重构策略，当满足种群多样性准则时才重新构建拓扑结构。其次设计了基于该拓扑结构的邻域多样本学习策略，加强了算法的开采能力。此外，将禁忌搜索作为后续搜索方法，并对禁忌搜索的禁忌属性进行创新设计，采用二重判断准则来对解的禁忌状态进行判断。将所提算法与多种知名的变体人工蜂群算法在21个基准函数上进行对比，实验结果表明本文所提算法在求解能力上令人满意。 为求解愈加复杂的最优化问题，本文对禁忌搜索进行改进，同时对分散搜索和人工蜂群进行改进，最后将禁忌搜索与后两种元启发式算法结合，提出了两种基于禁忌搜索的启发式算法，分别用于求解多维背包和函数数值优化问题。经过实验验证，所提算法相较于对比算法有着不错的表现，对于复杂大规模和实时性的优化问题，在求解性能和效率上得到了提高。
NETL