大连海事大学现代优化技术第4讲算法及其设计与评价.ppt

《大连海事大学现代优化技术第4讲算法及其设计与评价.ppt》由会员分享，可在线阅读，更多相关《大连海事大学现代优化技术第4讲算法及其设计与评价.ppt（31页珍藏版）》请在优知文库上搜索。

1、现代优化技术现代优化技术第第4 4讲：算法设计与算法评价讲：算法设计与算法评价主要内容主要内容 算法算法 算法特征算法特征 算法分类算法分类 算法设计算法设计 算法分析与评价算法分析与评价 近似算法的应用近似算法的应用 算法实践之一：求解算法实践之一：求解最短路问题的最短路问题的 Dijkstra Dijkstra AlgorithmAlgorithm算法的概念算法的概念算法（算法（AlgorithmAlgorithm）是一组明确的、可以执行步骤的有序集合。）是一组明确的、可以执行步骤的有序集合。一个有穷的规则序列；解决某一问题的一系列运算；程序设计的一个有穷的规则序列；解决某一问题的一系列运

2、算；程序设计的第一步。第一步。一系列解决问题的清晰指令，即能够对符合一定规范的输入，在一系列解决问题的清晰指令，即能够对符合一定规范的输入，在有限时间内获得所要求的输出有限时间内获得所要求的输出分析问题分析问题算法设计算法设计程序设计程序设计解决方案解决方案算法的特征算法的特征 算法反映了求解问题的方法和步骤，不同的问题需要用不算法反映了求解问题的方法和步骤，不同的问题需要用不同的算法来解决，同一个问题也可能有多种不同的算法。同的算法来解决，同一个问题也可能有多种不同的算法。一个算法必须具有以下特性：一个算法必须具有以下特性：u1.1.有穷性有穷性(可终止性可终止性)一个算法必须在有限的操作步

3、骤内以及合理的时间内执行一个算法必须在有限的操作步骤内以及合理的时间内执行完成。完成。u2.2.确定性确定性 算法中的每一个操作步骤都必须有明确的含义，不允许存算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。在二义性。算法的特征算法的特征u3.3.有效性有效性(可行性可行性)算法中每一个步骤必须能够实现，如在算法中不允许算法中每一个步骤必须能够实现，如在算法中不允许出现分母为出现分母为0 0的情况。的情况。算法执行的结果要能够达到预期的目的，实现预定的算法执行的结果要能够达到预期的目的，实现预定的功能。功能。u4.4.输入数据与输出数据的要求输入数据与输出数据的要求 一个算法应该有

4、一个算法应该有0 0个或多个输入数据、有个或多个输入数据、有1 1个或多个输个或多个输出数据。出数据。算法的特征示例算法的特征示例配送问题的扫描算法配送问题的扫描算法算法的特征示例算法的特征示例配送问题的扫描算法配送问题的扫描算法 第一步：第一步：(输入输入)在地图或方格中确定所有站点（仓库）的在地图或方格中确定所有站点（仓库）的位置，输入其坐标。位置，输入其坐标。第二步：（第二步：（线路指派线路指派）自仓库开始沿任意方向划一条直）自仓库开始沿任意方向划一条直线、沿顺时针（逆时针）方向旋转该直线直到与某站点线、沿顺时针（逆时针）方向旋转该直线直到与某站点相交。考虑：如果在该线路上增加该站点，是

5、否会超过相交。考虑：如果在该线路上增加该站点，是否会超过车辆的载货能力？如果没有，继续旋转直线，直到与下车辆的载货能力？如果没有，继续旋转直线，直到与下一个站点相交，再次计算是否超载；如果超过，就剔除一个站点相交，再次计算是否超载；如果超过，就剔除最后那个站点。直到所有站点都被安排在某一线路中。最后那个站点。直到所有站点都被安排在某一线路中。第三步：第三步：（线路内排序线路内排序）确定同一线路内各站点巡回顺）确定同一线路内各站点巡回顺序。序。第四步：（第四步：（输出输出）输出各线路与配送顺序，计算近似最）输出各线路与配送顺序，计算近似最优解（配送距离、成本等）。优解（配送距离、成本等）。算法的

6、类型算法的类型传统启发式算法传统启发式算法 构筑法；改善法构筑法；改善法传统启发式算法的改进型传统启发式算法的改进型 反复局部探索法；可变邻域探索法；随机局部探索法反复局部探索法；可变邻域探索法；随机局部探索法现代启发式算法现代启发式算法 模拟退火法；进化算法；禁忌探索；蚁群算法；模拟退火法；进化算法；禁忌探索；蚁群算法；神经网络算法；神经网络算法；混合算法混合算法 精确算法与近似算法的融合：解空间松弛算法；解精确算法与近似算法的融合：解空间松弛算法；解空间分解算法；空间分解算法；限制解空间算法；基于数学规划的探索进程调整限制解空间算法；基于数学规划的探索进程调整法；法；启发式算法间的融合：如

7、启发式算法间的融合：如 GA+SA GA+SA；GA+LSGA+LS；算法设计算法设计算法是要通过程序才能加以实现的。常用的算法描述方式算法是要通过程序才能加以实现的。常用的算法描述方式:u1.1.自然语言自然语言 自然语言就是人们日常使用的语言，可以是中文、英文等。自然语言就是人们日常使用的语言，可以是中文、英文等。例如，求例如，求3 3个数中最大者的问题，可以描述为：个数中最大者的问题，可以描述为：比较前两个数。比较前两个数。将中较大的数与第三个数进行比较。将中较大的数与第三个数进行比较。步骤中较大的数即为所求。步骤中较大的数即为所求。算法的描述工具算法的描述工具算法设计算法设计u2.流程

8、图流程图是用规定的一组图形符号、流程线和文字说明来描述算法的一种表示方法。(1)顺序结构。程序执行完A语句后接着执行B语句，如图所示。(2)选择结构。当条件P成立时，则执行A语句，否则执行B语句，如图所示。P成立成立AB不成立不成立算法的描述工具算法的描述工具算法设计算法设计(3)(3)当型循环结构。当条件当型循环结构。当条件P P成立时，则成立时，则循环执行循环执行A A语句，如图所示语句，如图所示(4)(4)直到型循环结构。循环执行直到型循环结构。循环执行A A语句，语句，直到条件直到条件P1P1成立为止，如图所示。成立为止，如图所示。算法的描述工具算法的描述工具算法设计算法设计u3.3.

9、伪代码伪代码 伪代码是用一种介于自然语言与计算机语言之间的文字和符伪代码是用一种介于自然语言与计算机语言之间的文字和符号来描述算法，它比计算机语言形式灵活、格式紧凑，没有号来描述算法，它比计算机语言形式灵活、格式紧凑，没有严格的语法。严格的语法。例如，求两个数的较大者，用伪代码描述算法如下：例如，求两个数的较大者，用伪代码描述算法如下：Find the biggerFind the bigger Input:two number s:a,b Input:two number s:a,b 1.if(the first number a is greater than or equal to th

10、e 1.if(the first number a is greater than or equal to the second number b)second number b)then then 1.1 return a 1.1 return a else else 1.2 return b 1.2 return b end if end if end end算法的描述工具算法的描述工具算法的基本结构算法的基本结构循环结构循环结构分支结构分支结构顺序结构顺序结构算法设计算法设计算法设计算法设计循环结构循环结构分支结构分支结构顺序结构顺序结构算法的描述工具算法的描述工具算法设计算法设计结构化

11、编程（子程序）结构化编程（子程序）算法分析与评价算法分析与评价算法分析与评价指标算法分析与评价指标 优化性能指标优化性能指标 (approximation)(approximation)时间性能指标时间性能指标（time complexitytime complexity）鲁棒性能指标鲁棒性能指标 (robustness)(robustness)算法分析与评价算法分析与评价优化性能指标优化性能指标(approximation)(approximation)离线评价：强调优化性能离线评价：强调优化性能在线评价：强调时间性能与鲁棒性能在线评价：强调时间性能与鲁棒性能算法分析与评价算法分析与评价时间

12、性能指标时间性能指标 (time complexity)(time complexity)算法分析与评价算法分析与评价鲁棒性指标（鲁棒性指标（robustnessrobustness）离线评价：强调优化性能离线评价：强调优化性能在线评价：强调时间性能与鲁棒性能在线评价：强调时间性能与鲁棒性能算法分析与评价算法分析与评价算法评价的方法算法评价的方法解析的方法解析的方法 极端场合计算复杂性解析（极端场合计算复杂性解析（worst-case complexityworst-case complexity）平均计算复杂性解析（平均计算复杂性解析（average-case complexityavera

13、ge-case complexity）与上（下）界值对比分析（与上（下）界值对比分析（upper or lower boundsupper or lower bounds）実験的方法実験的方法 应用实验应用实验(application(application）与基准问题的对照实验与基准问题的对照实验(benchmark problems)(benchmark problems)随机生成实验随机生成实验(randomly generated experiment)(randomly generated experiment)比较实验（比较实验（comparison experiment comp

14、arison experiment）算法分析与评价算法分析与评价解析评价（解析评价（1 1）-计算量评价计算量评价 算法的実行時間算法的実行時間 O(n)O(n log n)多項式時間算法多項式時間算法 O(n2)polynomial time algorithm O(n3):O(2n)指数時間算法指数時間算法 O(n!)exponential time algorithm算法分析与评价算法分析与评价解析评价（解析评价（2 2）-下界值评价下界值评价 比比2 2回还能少吗？回还能少吗？使用使用1 1次天秤次天秤,可以分可以分3 3种情形；种情形；使用使用2 2次天秤，可以分次天秤，可以分9 9

15、种情形；种情形；性質性質:金貨金貨 4 49 9個：天秤個：天秤2 2回以上回以上 金貨金貨10102727個：天秤個：天秤3 3回以上回以上 ：下界值：下界值：9 9个金币的鉴别需要使用个金币的鉴别需要使用2 2回以上天秤回以上天秤算法分析与评价算法分析与评价解析评价（解析评价（3 3）-平均情形与极端情形平均情形与极端情形（average-case&worst-case complexityaverage-case&worst-case complexity）背包问题的贪婪算法的最恶情形背包问题的贪婪算法的最恶情形算法分析与评价算法分析与评价实验评价（实验评价（4 4）-与基准问题的对照实

16、验与基准问题的对照实验 VRPVRP问题基准实验问题（问题基准实验问题（56 benchmark problems 56 benchmark problems）算法分析与评价算法分析与评价实验评价（实验评价（5 5）-比较实验比较实验1.1.设法得到现有的算法及程序，在同一台计算机上设法得到现有的算法及程序，在同一台计算机上运行，比较；运行，比较；2.2.根据现有的算法，自己进行程序设计，比较；根据现有的算法，自己进行程序设计，比较；3.3.现有算法无法得到的情况下，仅与现有算法的结现有算法无法得到的情况下，仅与现有算法的结果报告值进行比较。果报告值进行比较。算法分析与评价算法分析与评价与精确算法的比较评价（与精确算法的比较评价（6 6）求解小规模问题的精确解；求解小规模问题的精确解；并与其对应的近似解相比较。并与其对应的近似解相比较。列举法列举法 分枝定界法分枝定界法 动态规划法动态规划法 算法分析与评价算法分析与评价算法可视化评价（算法可视化评价（7 7）静态可视化静态可视化 动态可视化（算法动画）动态可视化（算法动画）近似算法的应用近似算法的应用算法的应用（算法的应用（1 1）定