《现代优化计算方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《现代优化计算方法ppt课件.ppt（79页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、授课：张授课：张 彩彩 霞霞 #四教四教204# 3690caixiazhanggmail变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分教教 材材n邢文训，谢金星邢文训，谢金星现代优化计算方法现代优化计算方法（第二版）（第二版） 清华大学出版社清华大学出版社变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分主要内容主要内容n概论（概论（49页）页）n禁忌搜索算法（禁忌搜索算法（26页）页）（tabu search）n模拟
2、退火算法（模拟退火算法（35页）页） （simulated annealing）n遗传算法（遗传算法（35页）页） （genetic algorithms）n蚁群算法（蚁群算法（23页）页） （群体（群集）智能，Swarm Intelligence） n人工神经网络（人工神经网络（38页）页） （artificial neural networks）n拉格朗日松弛算法（拉格朗日松弛算法（35页）页） （lagrangean relaxation）变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分第一章第一章
3、概论概论n组合最优化问题组合最优化问题n计算复杂性计算复杂性n邻域邻域n启发式算法启发式算法变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分背背 景景n传统实际问题的特点传统实际问题的特点 连续性问题连续性问题主要以微积分为基础，且问题规模较小主要以微积分为基础，且问题规模较小n传统的传统的优化方法优化方法 追求准确追求准确精确解精确解 理论的完美理论的完美结果漂亮结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策
4、论、决策论等。数规划等；排队论、库存论、对策论、决策论等。n传统的传统的评价方法评价方法 算法收敛性（从极限角度考虑）算法收敛性（从极限角度考虑） 收敛速度（线性、超线性、二次收敛等）收敛速度（线性、超线性、二次收敛等）变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分传统运筹学面临新挑战传统运筹学面临新挑战n现代问题的特点现代问题的特点 离散性问题离散性问题主要以组合优化（针对离散问题，定义见主要以组合优化（针对离散问题，定义见后）理论为基础后）理论为基础 不确定性问题不确定性问题随机性数学模型随机性数学模
5、型 半结构或非结构化的问题半结构或非结构化的问题计算机模拟、决策支持系统计算机模拟、决策支持系统 大规模问题大规模问题并行计算、大型分解理论、近似理论并行计算、大型分解理论、近似理论n现代现代优化方法优化方法 追求满意追求满意近似解近似解 实用性强实用性强解决实际问题解决实际问题n现代优化算法的现代优化算法的评价方法评价方法 算法复杂性算法复杂性变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.1 组合优化问题组合优化问题 组合优化组合优化（combinatorial optimization）:解决解决
6、离散问题的优化问题离散问题的优化问题运筹学分支。通过数学方运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。程、交通运输和通信网络等许多方面。 数学模型：数学模型：决策变量有限点集约束函数目标函数, . , 0)(. . )( minDxxgtsxf变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.1 组合优化问题组合优化问题
7、组合优化问题的组合优化问题的三参数三参数表示：表示： .| )(min)(,:,0)(,|:),(FxxfxfFxxFxfxgDxxFDfFD最优解，如果可行解（点）目标函数有限点集可行域决策变量定义域变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.1 组合优化问题组合优化问题n例例1 0-1背包问题（背包问题（0-1 knapsack problem）装包？问题：如何以最大价值件物品单位价值，第件物品单位体积，第背包容积., 1:., 1:niicniiabii变电站电气主接线是指变电站的变压器、输电
8、线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.1 组合优化问题组合优化问题 .1 , 0i0i 1(1.3) ., 1,1 , 0 (1.2) ,as.t.(1.1) maxn1ii1iniiiniiDxnixbxxc物品，不装第物品装第，其中决策变量包容量限制总价值数学模型：变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.1 组合优化问题组合优化问题n例例2 旅行商问题旅行商问题（TSP,traveling salesman problem） 管梅
9、谷教授管梅谷教授1960年首先提出，国际上称年首先提出，国际上称之为中国邮递员问题。之为中国邮递员问题。 问题描述：一商人去问题描述：一商人去n个城市销货，所有个城市销货，所有城市走一遍再回到起点，使所走路程最城市走一遍再回到起点，使所走路程最短。短。变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.1 组合优化问题组合优化问题ij1ij1min (1.4) s.t.1.1,2, , (1.5) i 1.1,2, , ijijijnjnid xxinxjn数学模型：总路长只从城市 出来一次, (1.6)
10、1,21,1,2, (1.7) 0,1 , ,1,2, ,. (1.8) :ij , s :s 1, iji jsijijijjxssnsnxi jn ijdijx只走入城市 一次在任意城市子集中不形成回路决策变量其中城市 与城市 之间的距离集合 中元素的个数，走城市 和城市0.:,:,ijjiijjiijTSPddi jTSPddi j之间的路径，不走城市 和城市 之间的路径对称距离非对称距离)1(1 , 0nnD变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.1 组合优化问题组合优化问题例例4 装箱
11、问题（装箱问题（bin packing） 尺寸为尺寸为1的箱子有若干个，怎样用最少的的箱子有若干个，怎样用最少的箱子装下箱子装下n个尺寸不超过个尺寸不超过1 的物品，物品的物品，物品集合为：集合为： 。 12 ,.na aa变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.1 组合优化问题组合优化问题11min. .1,1, 2, 1,1, 2, 0,1 ,1, 2,;1, 2, B :1, 0 .BibbniibiibibBs txina xbBxin bBibxib数 学 模 型 ：其 中装 下 全
12、部 物 品 需 要 的 箱 子 ，第 物 品 装 在 第个 箱 子 ， 第 物 品 不 装 在 第个 箱 子每个物品都被装箱每个物品都被装箱装在每个箱子的物品装在每个箱子的物品总尺寸不能超过箱子总尺寸不能超过箱子的容量的容量变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分例3 整数线性规划(integer linear programming)nTZxxbAxtsxc, 0. .minmnmnRbRARc,的元素都是整数。cbA,变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配
13、电任务。变电站的主接线是电力系统接线组成中一个重要组成部分特特 点点n决策变量的定义域和可行解集合都是决策变量的定义域和可行解集合都是有有限的限的n在问题的规模较小时，用在问题的规模较小时，用枚举法枚举法容易得容易得最优解最优解n组合优化问题常用组合优化问题常用整数规划模型整数规划模型表示表示n由于组合最优化问题的复杂性，很多快由于组合最优化问题的复杂性，很多快速的算法只给出可行解速的算法只给出可行解变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.2 计算复杂性的概念计算复杂性的概念n评价算法的好坏评价
14、算法的好坏计算时间计算时间的多少、解的的多少、解的偏离偏离程程度度n以二进制计算机中的存储和计算为基础以二进制计算机中的存储和计算为基础n理论产生于理论产生于20世纪世纪70年代年代n例例 非对称距离非对称距离TSP问题的算法实现：所有路径问题的算法实现：所有路径枚枚举举。n计算时间计算时间：n个城市，固定个城市，固定1个为起终点需要个为起终点需要(n-1)!个枚举个枚举 设计算机设计算机1秒能完成秒能完成24个城市的枚举，则城市数与个城市的枚举，则城市数与计算时间的关系如下表：计算时间的关系如下表：变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的
15、主接线是电力系统接线组成中一个重要组成部分1.2 计算复杂性的概念计算复杂性的概念城市数城市数2425262728293031计算时计算时间间1sec24sec10min4.3hour4.9day136.5day10.8year325year随城市增多，计算时间增加很快。随城市增多，计算时间增加很快。到到31个城市时，要计算个城市时，要计算325年。年。描述算法的好坏描述算法的好坏计算复杂性计算复杂性讨论讨论计算时间与问题规模计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。以理
16、论的形式系统描述，是评估算法性能的基础。变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.2 计算复杂性的概念计算复杂性的概念n问题（问题（problem）：）：要回答的一般性提问，通常含有要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从若干个满足一定条件的参数（或自由变量）。可以从两方面描述：两方面描述： （1）对所有参数的一般性描述；）对所有参数的一般性描述； （2）答案（或解）必须满足的性质。）答案（或解）必须满足的性质。n实例（实例（instance）:给问题的所有参数指
17、定具体值，得给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为到问题的一个实例。这些具体值称为数据数据.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.2 计算复杂性的概念计算复杂性的概念数的数的规模规模（编码长度）（编码长度） ：一个数在计算机中存储时占据的一个数在计算机中存储时占据的位数位数实例的实例的规模规模：)(xl一个实例所有参数数值的规模之和一个实例所有参数数值的规模之和)(Il算法的算法的计算量计算量：算法求解中的加、减、乘、除、比较、算法求解中的加、减、乘、除、比较、读、写等
18、基本运算的总次数读、写等基本运算的总次数)(ICA变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分数的数的规模规模n正整数正整数x的二进制位数是的二进制位数是:(整数到二进制的转换整数到二进制的转换)2 ,21ssx) 1 , 0, 1(2.220111isssssaaaaaax)(01aaaxss1)( sxl112212log2sssxxxsx) 1(log)(2xxlxxx222log1) 1(loglog2变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的
19、主接线是电力系统接线组成中一个重要组成部分实例实例）和距离实例的规模（城市数例ijdnTSP 1 . 2 . 1ninjijijdnIl11222log2) 1(log)(jidijijdnPPnnIlPnn, 022log3) 1(3)(log2) 1(2变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分课课 堂堂 练练 习习）的规模（例cbAnm,IP 2 . 2 . 1变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分
20、1.2 计算复杂性的概念计算复杂性的概念n算法计算量的度量之例算法计算量的度量之例TSP枚举枚举法法21, , (1)!(1)!;(1)! (1)!nniinnnnnnnn城市数第一城市为始终点，计算一条路径（,1） 长度的基本运算为两两城市间距离的 个数求和,共有条路径,求和运算次数为：枚举所有路径进行次比较可得最优路径,基本计算总次数为总计算量:计算量的统计：计算量的统计：变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.2 计算复杂性的概念计算复杂性的概念n实例的输入长度：实例的输入长度：22,(1
21、)( log12)log12ijijdKLn nKn设 对有则（）（）n实例的输入长度是实例的输入长度是n的的多项式函数多项式函数n枚举法的基本计算量是枚举法的基本计算量是n的的阶乘函数阶乘函数， 随随n的增加，比的增加，比指数函数指数函数增加得还快增加得还快.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.2 计算复杂性的概念计算复杂性的概念AAA, ( )AC (I)( ) ( ( ) ( )( ( ( )( )Il Ig xC (I)g l ICIO g l Ig x 实例实例规模：，算法基本计算
22、总次数：存在函数和一个常数 ，使得对于该问题的任意实例都满足 （）则二者关系表示为：的性质决定了算法的性能。控制的函数，且被是)()()(IlgIlICA算法复杂性分析：由最坏实例的输入规模与算法的计算量之算法复杂性分析：由最坏实例的输入规模与算法的计算量之间的关系来衡量算法的好坏。间的关系来衡量算法的好坏。问题复杂性分析问题复杂性分析变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.2 计算复杂性的概念计算复杂性的概念定义定义 多项式算法多项式算法给定问题给定问题P，算法，算法A，对，对一个一个实例实例
23、I，存在存在多项式多项式函数函数g(x)，使（，使（XX ）成立，称）成立，称算法算法A对实例对实例I是是多项式算法多项式算法；若存在多项式函数若存在多项式函数g(x)，使（，使（XX）对问题）对问题P的的任任意意实例实例I都成立，称都成立，称算法算法A为解决该问题为解决该问题P的多项的多项式算法式算法.当当g(x)为指数函数时，称为指数函数时，称A为为P的指数时间算法。的指数时间算法。随着变量的增加，多项式函数增长的速度比指数随着变量的增加，多项式函数增长的速度比指数函数增长的速度慢得多函数增长的速度慢得多nCnC2222101变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接
24、，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.2 计算复杂性的概念计算复杂性的概念n利用复杂性分析对组合优化问题归类。利用复杂性分析对组合优化问题归类。n定义定义多项式问题多项式问题 给定一个组合优化问题，若给定一个组合优化问题，若存在存在一个多项一个多项式算法，称该问题为多项式时间可解问题，式算法，称该问题为多项式时间可解问题，或简称或简称多项式问题多项式问题(或或P问题问题). 所有多项式所有多项式问题的集合记为问题的集合记为P.n例：线性规划是否为多项式问题？例：线性规划是否为多项式问题？ 是是变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接
25、，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分n通常将存在多项式时间算法的问题看作通常将存在多项式时间算法的问题看作是是易解问题易解问题（Easy Problem），将需），将需要指数时间算法解决的问题看作是要指数时间算法解决的问题看作是难解难解问题问题（Hard Problem）。）。变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分 为什么把多项式时间复杂性作为易解问题和为什么把多项式时间复杂性作为易解问题和难解问题的分界线？难解问题的分界线？多项式函数与指数函数的增长率有本质的
26、差别多项式函数与指数函数的增长率有本质的差别问 题规 模n多项式函数指数函数log2nnnlog2nn2n32nn!10101121103.32 1033.21001000 1024 36288001006.64 100 664.4 100001.0E61.3E309.3E157变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.3 邻域的概念邻域的概念n距离空间中，邻域是以一点为中心的一距离空间中，邻域是以一点为中心的一个球体个球体n目的：寻找下一个迭代点目的：寻找下一个迭代点的邻域。称为。的所有子集组成
27、的集合表示中称为一个邻域映射，其且的子集的一个映射上的一点到），对于组合最优化问题（定义：xxNDxNxxNDxNDDfFDDD)(2),(,2)(: , 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分示例,|)(TSP 1 . 3 . 1,DykxyxyyxNjiijij，定义邻域对例化个位置的值可以发生变最多有kx。中的两个元素进行对换，即定义它的邻域映射为的排列是为问题解的另一种表示法例SoptniiiiiiSDnn2.,1,2,.,| ),.,(TSP 1.3.22121变电站电气主接线是指变电站
28、的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分n局部最优n全局最优FxNxxfxf*)(),()(*)(Fxxfxf),()(*)(1 2 3 4 5 6 7 8 9 101|)(xyZyxN变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分n传统的优化算法传统的优化算法可能陷入局部最优点。可能陷入局部最优点。n现代优化算法就是解决现代优化算法就是解决如何跳出如何跳出局部最局部最优点以达到全局最优点。优点以达到全局最优点。变电站电气主接线是指变电
29、站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.4 启发式算法启发式算法_定义定义n启发式算法（启发式算法（heuristic algorithm）n定义定义1. 基于基于直观或经验直观或经验构造的算法，在可接受的花构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每费（时间、空间）下，给出待解组合优化问题的每个实例的一个个实例的一个可行解可行解，该可行解与最优解偏差事先，该可行解与最优解偏差事先不一定可以预计不一定可以预计.n定义定义2. 启发式算法是一种技术，在可接受的计算费启发式算法是一种技术，在可接受的
30、计算费用内寻找最好解，但不保证该解的可行性与最优性，用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。无法描述该解与最优解的近似程度。n特点（与传统优化方法不同）：特点（与传统优化方法不同）：凭凭直观和经验直观和经验给出给出算法；算法；不考虑不考虑所得解与最优解的所得解与最优解的偏离程度偏离程度.变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.4 启发式算法启发式算法_优点优点 优点：优点：（1）有可能比简化数学模型解的误差小；）有可能比简化数学模型解的误差小；（2）对有些难
31、题，计算时间可接受；）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算）可用于某些最优化算法（如分支定界算 法）之中的估界；法）之中的估界；（4）直观易行；）直观易行；（5）速度较快；）速度较快；（6）程序简单，易修改。）程序简单，易修改。变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.4 启发式算法启发式算法_不足不足不足：不足：（1）不能保证求得全局最优解；）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经
32、验、技）算法设计与问题、设计者经验、技术术 有关，缺乏规律性；有关，缺乏规律性；（4）不同算法之间难以比较。）不同算法之间难以比较。变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.4 启发式算法启发式算法_分类分类 (1) 一步算法：不在两个可行解之间比较一步算法：不在两个可行解之间比较 (2) 改进算法（迭代算法）：从一个可行解到另一个可行改进算法（迭代算法）：从一个可行解到另一个可行解变换解变换 (3) 数学规划算法：主要用连续优化的方法数学规划算法：主要用连续优化的方法 如解空间松弛法如解空间松弛
33、法 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.4 启发式算法启发式算法_分类分类（4）现代优化算法：）现代优化算法： 80年代初兴起年代初兴起n禁忌搜索（禁忌搜索（tabu search）n模拟退火（模拟退火（simulated annealing）n遗传算法（遗传算法（genetic algorithms）n神经网络（神经网络（neural networks）n蚂蚁算法（蚂蚁算法（Ant Algorithm，群体（群集）群体（群集）智能，智能，Swarm Intelligence）（5 5）其他
34、算法：）其他算法： 多种启发式算法的集成多种启发式算法的集成. . 理论上难以理论上难以区分目标值区分目标值的优劣的优劣变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分1.4启发式算法启发式算法_性能分析性能分析n评价指标：评价指标：n算法的复杂性（计算效率）算法的复杂性（计算效率）n解的偏离程度（计算效果）解的偏离程度（计算效果）1.算法的鲁棒性算法的鲁棒性变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分n评价手段：评
35、价手段：n最坏情形分析最坏情形分析n概率分析概率分析1.计算模拟分析计算模拟分析1.4启发式算法启发式算法_性能分析性能分析变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分全局优化启发式算法的特点全局优化启发式算法的特点n在一些限定条件下，理论上可以收敛到在一些限定条件下，理论上可以收敛到全局最优。全局最优。n但付出的计算时间可能无法接受。但付出的计算时间可能无法接受。n在限定计算时间后，无法保证收敛到全在限定计算时间后，无法保证收敛到全局最优。局最优。n随着计算时间的增加，算法的解越来越随着计算时间的增加
36、，算法的解越来越好。好。变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分n策略策略1：集中集中 集中搜索，求得局部最优解集中搜索，求得局部最优解n策略策略2：扩散扩散 扩大搜索区域，达到全局最优解扩大搜索区域，达到全局最优解变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分第二章第二章 禁忌搜索算法（禁忌搜索算法（ Tabu Search）Glover 1986禁忌禁忌：禁止重复前面的工作：禁止重复前面的工作禁忌表禁忌表：
37、记录已经到达过的局部最优解：记录已经到达过的局部最优解或或达到局部最优的过程。达到局部最优的过程。变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分2.1 局部搜索局部搜索)x(N:T ,x:x;xbest0best0或其他停止准则x Tbest是是停止停止否否nowx,TS得最好解选 )x(f)x(fbestnow)x(NT,x:xbestnowbest是是否否ST:T 变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分例
38、例2.1.1 五个城市的对称五个城市的对称TSP05159250201361520081591380102615100 全邻域搜索全邻域搜索 随机搜索随机搜索.opt2),ABCDE(x0序对换的邻域映射为两个城市顺初始解变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分陷入局部最优解！陷入局部最优解！例例2.1.2四城市非对称四城市非对称TSP01111055 . 1110115 . 010D.opt2),ABCD(x0序对换的邻域映射为两个城市顺初始解变电站电气主接线是指变电站的变压器、输电线路怎样与电力
39、系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分特特 点点n依赖于依赖于初始点初始点的选取和的选取和邻域邻域的结构的结构选取选取足够多足够多的初始点的初始点变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分2.2 禁忌搜索禁忌搜索n基本思想基本思想： 标记标记已得到的局部最优解或求解的过程，已得到的局部最优解或求解的过程，并在进一步的迭代中并在进一步的迭代中避开避开这些局部最优这些局部最优解或过程。解或过程。变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从
40、而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分禁忌搜索算法禁忌搜索算法nowx,H 初始解初始禁忌表停止准则停止准则结果结果是是否否);x(fmin()x(fHx ,x)x(N)x(N_Canx ,xnextnextnownownext 候选集Hx:xnextnow更新变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分n禁忌对象禁忌对象：被禁的变化元素：被禁的变化元素n禁忌长度禁忌长度：被禁对象不允许选取的：被禁对象不允许选取的迭代次数迭代次数n候选集合候选集合的构成：的构成：邻域邻域中
41、的邻居组成中的邻居组成n评价函数评价函数的构造：赋予候选集合中每个元素一个的构造：赋予候选集合中每个元素一个实数值实数值，通常是目标，通常是目标函数。函数。n特赦规则特赦规则n记忆频率信息记忆频率信息n终止规则终止规则 禁禁忌忌表表变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分技术问题技术问题变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分例例2.2.1 四城市非对称四城市非对称TSP的的距离矩阵距离矩阵0111105
42、5 . 1110115 . 010D.opt2),ABCD(x0序对换的邻域映射为两个城市顺初始解变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分例例2.2.2 禁忌长度从禁忌长度从3变到变到201111055 . 1110115 . 010D.opt2),ABCD(x0序对换的邻域映射为两个城市顺初始解变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分禁忌对象禁忌对象：被禁的：被禁的变化元素变化元素n解的简单变化解的简单
43、变化n向量分量的变化向量分量的变化n目标值变化目标值变化变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分解的简单变化解的简单变化n从一个解变化到另一个解从一个解变化到另一个解)x(Nyx)ACBDE()ABCDE(变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分例例2.3.4(例例2.1.1) 五个城市的对称五个城市的对称TSP05159250201361520081591380102615100.opt2),ABCDE
44、(x0序对换的邻域映射为两个城市顺初始解)45;ABCDE(H)x(N)x(N_Can0nownow个最佳的解的包含禁忌对象：解自身禁忌长度：5 4变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分向量分量的变化向量分量的变化n对解向量的每个分量进行变化对解向量的每个分量进行变化)x,.,x ,y,x,.,x()x,.,x ,x ,x,.,x(n1ii1i1n1ii1i1例例2.3.1 0-1背包问题背包问题例例2.3.2 TSP问题问题变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完
45、成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分例例2.3.5(例例2.1.1) 五个城市的对称五个城市的对称TSP05159250201361520081591380102615100.opt2),ABCDE(x0序对换的邻域映射为两个城市顺初始解0nownownowHx)x(N)x(N_Can个最佳的解的包含换禁忌对象：城市顺序对禁忌长度：5 3变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分目标值变化目标值变化a)x(f|Dx)a(Hba )b(Hy)a(Hx等值线等值线例例2.3.3
46、4b , 1ax)x(f2变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分例例2.3.6(例例2.1.1) 五个城市的对称五个城市的对称TSP05159250201361520081591380102615100.opt2),ABCDE(x0序对换的邻域映射为两个城市顺初始解45H)x(N)x(N_Can0nownow个最佳的解的包含禁忌对象：目标值禁忌长度：5 3变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分n解的简
47、单变化解的简单变化比比解的分量变化解的分量变化和和目标值目标值变化变化的受禁忌范围要小的受禁忌范围要小变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分禁忌长度禁忌长度n被禁对象被禁对象x不允许选取的不允许选取的迭代次数迭代次数t tabu(x)=ttabu(x)=t-1tabu(x)=0变化maxminmaxmint ,t. 3t ,tt. 2ct. 1为邻居的个数其中n,nt ;10t是邻居的个数是问题的规模，其中nT,n,n;T,T变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完
48、成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分特赦规则特赦规则n让一些禁忌对象重新可选：让一些禁忌对象重新可选： 候选集中的全部对象都被禁忌候选集中的全部对象都被禁忌 一对象被禁，但若解禁后其当前最优值将下降一对象被禁，但若解禁后其当前最优值将下降变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分例例2.3.7 五个城市的非对称五个城市的非对称TSP0110102201101010201101010201110102024)x(f),AEDBC(x当前解,.BC禁忌对象：)AEDCB(5)y
49、(fy变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分n基于评价值的规则基于评价值的规则n基于最小错误的规则基于最小错误的规则n基于影响力的规则基于影响力的规则选评价值最小的解禁选评价值最小的解禁关注影响大的变化关注影响大的变化变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分候选集合的确定候选集合的确定n由邻域中的邻居组成由邻域中的邻居组成 从邻域中从邻域中所有邻居所有邻居中选择若干个目标值中选择若干个目标值或评价值最佳
50、的邻居或评价值最佳的邻居 从邻域中的从邻域中的一部分邻居一部分邻居中选择若干个目中选择若干个目标值或评价值最佳的邻居标值或评价值最佳的邻居 随机选取随机选取变电站电气主接线是指变电站的变压器、输电线路怎样与电力系统相连接，从而完成输配电任务。变电站的主接线是电力系统接线组成中一个重要组成部分评价函数评价函数n赋予候选集合中每个元素一个赋予候选集合中每个元素一个实数值实数值，以此选取下一步的以此选取下一步的替代点替代点目标函数目标函数 直接直接评价函数：含目标函数评价函数：含目标函数 间接间接评价函数：尽量反映目标函数的特性评价函数：尽量反映目标函数的特性)x(f)x(f)x(f)x(f)x(f