第七章第七章 广义邻域搜索算法广义邻域搜索算法 及其统一结构及其统一结构智能优化计算智能优化计算7.1 7.1 广义邻域搜索算法广义邻域搜索算法7.1.1 7.1.1 传统邻域算法传统邻域算法7.1.2 7.1.2 广义邻域算法广义邻域算法 7.2 7.2 广义邻域搜索算法的要素广义邻域搜索算法的要素 7.3 7.3 广义邻域搜索算法的统一结构广义邻域搜索算法的统一结构 7.3.1 7.3.1 算法混合的方式算法混合的方式7.3.2 7.3.2 统一优化结构统一优化结构 7.4 7.4 优化算法的性能评价指标优化算法的性能评价指标 7.5 7.5 广义邻域搜索算法研究进展广义邻域搜索算法研究进展 7.5.1 7.5.1 理论研究概述理论研究概述 7.5.2 7.5.2 应用研究概述应用研究概述7.5.3 7.5.3 发展性研究发展性研究智能优化计算智能优化计算7.1 7.1 广义邻域搜索算法广义邻域搜索算法智能优化计算智能优化计算n传统邻域算法的优化流程从一个初始解 x 出发，利用状态发生器持续地 在解 x 的邻域中搜索比它好的解，若能找到如此的 解，就以之替代解 x 成为新的当前解，然后重复上述过程；否则结束搜索过程，以当前解作为最终解 。7 7.1.1 .1.1 传统邻域算法传统邻域算法7.1 7.1 广义邻域搜索算法广义邻域搜索算法智能优化计算智能优化计算n特点（1）通用易实现，只要设计好状态发生器（邻域函数），就能求解组合或函数优化；（2）算法性能对邻域函数和初始值具有依赖性，邻域函数和初始值选取不同，算法最终的性能将会有 差异；（3）算法的局部优化特性，没有跳出局部极值的能力。7 7.1.1 .1.1 传统邻域算法传统邻域算法7.1 7.1 广义邻域搜索算法广义邻域搜索算法智能优化计算智能优化计算n定义模拟退火、禁忌搜索、遗传算法、模糊优化、基于规则的启发式算法，以及基于它们的各种混合 算法，都是对传统邻域搜索算法的改进和变型。将上述通过不同途径而构成的改进算法统称为广义邻域搜索算法。这些算法在优化流程上呈现出很大的共性。7 7.1.2 .1.2 广义邻域算法广义邻域算法7.1 7.1 广义邻域搜索算法广义邻域搜索算法智能优化计算智能优化计算n广义邻域算法的工作流程算法从若干初始解出发，在算法参数控制下由当前状态的邻域中产生出若干个候选解，并以某种 策略在当前解和候选解中确定新的当前状态。伴随 控制参数的调节，重复执行上述搜索过程，直至满 足算法的终止准则，结束搜索过程并输出优化结果 。7 7.1.2 .1.2 广义邻域算法广义邻域算法7.1 7.1 广义邻域搜索算法广义邻域搜索算法智能优化计算智能优化计算7 7.1.2 .1.2 广义邻域算法广义邻域算法Genetic Algorithm (GA,1975)Hopfield Neural Network (HNN,1982)Tabu Search (TS,1986)Simulated Annealing (SA,1983)Ant Colony Optimization (ACO,1992)Particle Swarm Optimization (PSO,1995)7.2 7.2 广义邻域搜索算法的要素广义邻域搜索算法的要素智能优化计算智能优化计算n搜索机制的选择是构造算法框架和实现优化的关键；局部优化算法基于局部优化的贪婪机制，如梯度下降法、爬山法等；全局优化算法基于概率分布的优化机制，如GA 、SA等；自学习算法基于系统动态演化的优化机制，如混沌搜索、神经网络优化等。7.2 7.2 广义邻域搜索算法的要素广义邻域搜索算法的要素智能优化计算智能优化计算n搜索方式的选择决定优化的结构，即每代有多少解参与优化；并行搜索：以多点同时或交叉优化，计算和储存量 较大，如GA、ACO、PSO等；串行搜索：始终只有一个当前状态，处理简单，效 率较差，如SA、TS等。7.2 7.2 广义邻域搜索算法的要素广义邻域搜索算法的要素智能优化计算智能优化计算n邻域函数的设计决定了邻域结构和邻域解的产生方式；算法对问题解的不同描述方式，使解空间的优化曲面形状和解的分布有所差异，会直接影响邻域函数 的设计，进而影响算法的搜索行为。在确定邻域结构后，当前状态邻域中候选解的产生方式既可以是确定性的，也可以是随机性的。7.2 7.2 广义邻域搜索算法的要素广义邻域搜索算法的要素智能优化计算智能优化计算n状态更新方式的设计指以何种策略在新旧状态中确定新的当前状态，是决定算法整体优化性能的关键步骤之一。基于确定性的状态更新方式难以穿越大的能量障碍，容易陷入局部极小；基于随机性的状态更新方式能够取得较好地全局优化性能。7.2 7.2 广义邻域搜索算法的要素广义邻域搜索算法的要素智能优化计算智能优化计算n控制参数的修改准则和方式的设计须以一定的准则和方式进行修改以适应算法性能的动态变化；参数的修改幅度必须使算法性能的动态变化具有一定的平衡性，以实现算法行为在不同参数下的良好 过渡。7.2 7.2 广义邻域搜索算法的要素广义邻域搜索算法的要素智能优化计算智能优化计算n算法终止准则的设计决定算法最终的优化性能；应兼顾算法的优化质量和搜索效率等多方面性能，或根据问题需要着重强调算法的某方面性能，采用 与算法性能指标相关的近似收敛准则。7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n单一算法与混合算法依赖于单一邻域结构的搜索算法一般难以实现高效的优化，基于混合邻域结构的搜索算法日益受到重 视。混合算法已经成为一些学术会议专门的研讨方向。 7 7.3.1 .3.1 算法混合的方式算法混合的方式7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n主要结构类型串行镶嵌并行混合7 7.3.1 .3.1 算法混合的方式算法混合的方式7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n串行最简单；利用一种算法的搜索结果作为另一种算法的起点依次对问题进行优化；关键：确定算法的转换时机。 7 7.3.1 .3.1 算法混合的方式算法混合的方式7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n镶嵌一种算法作为另一种算法的一个优化操作或用作搜索性能的评价器；鉴于各种算法优化机制的差异，进而克服单一算法早熟和陷入局部极值；关键：子算法与嵌入点的选择。7 7.3.1 .3.1 算法混合的方式算法混合的方式7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n并行同步式并行：主过程（算法A）和子过程（其它算法）为主仆关系，各子算法的搜索过程相互独立，可 以采纳不同的搜索策略，但与主过程的通信必须保持同步；7 7.3.1 .3.1 算法混合的方式算法混合的方式7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n并行异步式并行：各子过程通过共享存储器彼此无关地进行优化，与主过程的通信不受其他子过程的限制 ，其可靠性有所提高；7 7.3.1 .3.1 算法混合的方式算法混合的方式7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n并行网络结构：各算法分别在独立的存储器上执行独立的搜索，算法间的通信是通过网络相互传递的；关键：问题分解与综合以及进程间的通信问题。7 7.3.1 .3.1 算法混合的方式算法混合的方式7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n单一邻域搜索流程将各种单一广义邻域搜索算法进行统一模块化描述，包括构成广义邻域搜索流程的所有关键步骤；n进程层次串行组合邻域搜索（SNSA）体现了优化过程在进程层次上的分解，是在进程层次上对各种混合算法的统一描述；7 7.3.2 .3.2 统一优化结构统一优化结构7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n问题分解和预处理以及子问题的综合过程体现了优化过程在空间层次上的分解，通过问题分解，可降低求解复杂性，有利于提高优化效率；n整体解的进一步NS优化这是对从“问题分解”到“综合处理”的手段所造成的全局优化质量降低的一个补充。7 7.3.2 .3.2 统一优化结构统一优化结构7.3 7.3 广义邻域搜索算法的一般结构广义邻域搜索算法的一般结构智能优化计算智能优化计算n整体流程7 7.3.2 .3.2 统一优化结构统一优化结构7.4 7.4 优化算法的性能评价体系优化算法的性能评价体系智能优化计算智能优化计算n优化性能指标离线最优性能指标：其中，cb为算法多次运行所得的最佳优化值，c*为问题的最优解，若最优解未知，可用已知最佳优化值 代替。值越小意味着优化性能越好。 7.4 7.4 优化算法的性能评价体系优化算法的性能评价体系智能优化计算智能优化计算n优化性能指标在线最优性能指标：其中，cb(k)为算法运行第k代的最佳优化值。值越小意味着算法的优化性能越好。 7.4 7.4 优化算法的性能评价体系优化算法的性能评价体系智能优化计算智能优化计算n时间性能指标其中，Ia为算法多次运行所得的满足终止条件时的迭 代步数平均值， Imax为给定的最大迭代步数阈值， T0为算法一步迭代的平均计算时间。搜索率Es用以衡量算法对问题解的搜索快慢程度，在 Imax固定情况下， Es越小说明算法收敛速度越快。 7.4 7.4 优化算法的性能评价体系优化算法的性能评价体系智能优化计算智能优化计算n鲁棒性指标离线初值鲁棒性指标（波动率）：其中，ca为算法多次运行所得的平均值，ci*为算法第 i次运行得到的最优值，STDEV()为均方差。波动率越小说明鲁棒性越强。7.4 7.4 优化算法的性能评价体系优化算法的性能评价体系智能优化计算智能优化计算n鲁棒性指标在线初值鲁棒性指标：其中，ca (k)为算法运行第k代所得的平均值， ci*(k) 为算法第i次运行在第k代得到的最优值。用来衡量算法对随机初值和操作的动态依赖程度。7.4 7.4 优化算法的性能评价体系优化算法的性能评价体系智能优化计算智能优化计算n综合指标基于上述三个性能指标，加权组合：综合性能指标越小表明算法的综合性能越好，以此作为实际应用时选择算法的一个标准。离线优化在线优化7.5 7.5 广义邻域搜索算法研究进展广义邻域搜索算法研究进展 智能优化计算智能优化计算n收敛性与鲁棒性研究模式定理（遗传算法）马尔科夫链（模拟退火、禁忌搜索、遗传算法等）目前对算法严格的理论研究均基于简单的理想模型，研究成果与实际算法实施仍有距离。7 7.5.1 .5.1 理论研究概述理论研究概述7.5 7.5 广义邻域搜索算法研究进展广义邻域搜索算法研究进展 智能优化计算智能优化计算n算法参数的选择研究目前尚无确定最优参数的一般方法，在求解实际问题时主要凭经验选取算法参数。n算法操作的研究随着人们对算法机制与功能和自然更深入的理解与研究，模拟自然科学思想来实现优化的算法操作研 究会得到进一步的发展。7 7.5.1 .5.1 理论研究概述理论研究概述7.5 7.5 广义邻域搜索算法研究进展广义邻域搜索算法研究进展 智能优化计算智能优化计算n函数优化n生产调度n控制工程n机器学习和模式识别n工艺设计n组合优化n神经网络设计n工业设备设计7 7.5.2 .5.2 应用研究概述应用研究概述7.5 7.5 广义邻域搜索算法研究进展广