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

现代优化技术 第4讲：算法设计与算法评价 主要内容 算法 算法特征 算法分类 算法设计 算法分析与评价 近似算法的应用 算法实践之一：求解最短路问题的 Dijkstra Algorithm 算法的概念 算法（Algorithm）是一组明确的、可以执行步骤的有序集合。 一个有穷的规则序列；解决某一问题的一系列运算；程序设计的 第一步。 一系列解决问题的清晰指令，即能够对符合一定规范的输入，在 有限时间内获得所要求的输出 分析问题 算法设计 程序设计 解决方案 算法的特征 算法反映了求解问题的方法和步骤，不同的问题需要用不 同的算法来解决，同一个问题也可能有多种不同的算法。 一个算法必须具有以下特性： u1. 有穷性(可终止性) 一个算法必须在有限的操作步骤内以及合理的时间内执行 完成。 u2. 确定性 算法中的每一个操作步骤都必须有明确的含义，不允许存 在二义性。 算法的特征 u3. 有效性(可行性) 算法中每一个步骤必须能够实现，如在算法中不允许 出现分母为0的情况。 算法执行的结果要能够达到预期的目的，实现预定的 功能。 u4. 输入数据与输出数据的要求 一个算法应该有0个或多个输入数据、有1个或多个输 出数据。 算法的特征示例 配送配送 中心中心 配送问题的扫描算法 算法的特征示例 配送问题的扫描算法 第一步：(输入)在地图或方格中确定所有站点（仓库）的 位置，输入其坐标。 第二步：（线路指派）自仓库开始沿任意方向划一条直线 、沿顺时针（逆时针）方向旋转该直线直到与某站点相交 。考虑：如果在该线路上增加该站点，是否会超过车辆的 载货能力？如果没有，继续旋转直线，直到与下一个站点 相交，再次计算是否超载；如果超过，就剔除最后那个站 点。直到所有站点都被安排在某一线路中。 第三步：（线路内排序）确定同一线路内各站点巡回顺序 。 第四步：（输出）输出各线路与配送顺序，计算近似最优 解（配送距离、成本等）。 算法的类型 传统启发式算法 构筑法；改善法 传统启发式算法的改进型 反复局部探索法；可变邻域探索法；随机局部探索法 现代启发式算法 模拟退火法；进化算法；禁忌探索；蚁群算法； 神经网络算法； 混合算法 精确算法与近似算法的融合：解空间松弛算法；解 空间分解算法； 限制解空间算法；基于数学规划的探索进程调整法 ； 启发式算法间的融合：如 GA+SA；GA+LS； 算法设计 算法是要通过程序才能加以实现的。常用的算法描述方式 : u1. 自然语言 自然语言就是人们日常使用的语言，可以是中文、英文等。 例如，求3个数中最大者的问题，可以描述为： 比较前两个数。 将中较大的数与第三个数进行比较。 步骤中较大的数即为所求。 算法的描述工具 算法设计 u2. 流程图 流程图是用规定的一组图形符号、流程线和文字说明 来描述算法的一种表示方法。 (1) 顺序结构。程序执行完A语句后接着执行B语句，如 图所示。 (2) 选择结构。当条件P成立时，则执行A语句，否则执 行B语句，如图所示。 P 成立 AB 不成立 算法的描述工具 算法设计 (3) 当型循环结构。当条件P成立时，则 循环执行A语句，如图所示 (4) 直到型循环结构。循环执行A语句， 直到条件P1成立为止，如图所示。 算法的描述工具 算法设计 u3. 伪代码 伪代码是用一种介于自然语言与计算机语言之间的文字和符 号来描述算法，它比计算机语言形式灵活、格式紧凑，没有 严格的语法。 例如，求两个数的较大者，用伪代码描述算法如下： Find the bigger Input: two number s:a,b 1. if (the first number a is greater than or equal to the second number b) then 1.1 return a else 1.2 return b end if end 算法的描述工具 算法的基本结构 循环结构分支结构顺序结构 算法设计 算法设计 循环结构 分支结构顺序结构 算法的描述工具 算法设计 结构化编程（子程序） 算法分析与评价 算法分析与评价指标 优化性能指标 (approximation) 时间性能指标 （time complexity） 鲁棒性能指标 (robustness) 算法分析与评价 优化性能指标 (approximation) 离线评价：强调优化性能 在线评价：强调时间性能与鲁棒性能 算法分析与评价 时间性能指标 (time complexity) 算法分析与评价 鲁棒性指标（robustness） 离线评价：强调优化性能 在线评价：强调时间性能与鲁棒性能 算法分析与评价 算法评价的方法 解析的方法 极端场合计算复杂性解析（worst-case complexity ） 平均计算复杂性解析（average-case complexity） 与上（下）界值对比分析（upper or lower bounds ） 実験的方法 应用实验 (application） 与基准问题的对照实验 (benchmark problems) 随机生成实验 (randomly generated experiment) 比较实验（comparison experiment ） 算法分析与评价 解析评价（1）-计算量评价 算法的実行時間 O(n) O(n log n ) 多項式時間算法 O(n2) polynomial time algorithm O(n3) : : O(2n) 指数時間算法 O(n!) exponential time algorithm 算法分析与评价 解析评价（2）-下界值评价 比2回还能少吗？ 使用1次天秤, 可以分3种情形； 使用2次天秤，可以分9种情形； 性質: 金貨 49個：天秤2回以上 金貨1027個：天秤3回以上 ： ： 下界值：9个金币的鉴别需要使用2回以上天秤 算法分析与评价 解析评价（3）-平均情形与极端情形 （average-case Flowshop: Jobshop; 等各种SLOVER 理论 应用 实务 近似算法的应用 算法的应用（2） 定型化问题的变种 近似算法 仓库仓库 可归结为