大连海事大学现代优化技术第4讲算法及其设计与评价.ppt
现代优化技术,第4讲：算法设计与算法评价,胶会擂鸵匀紊备关炽闹估匣文伶羹峡埔藻佣镇如蚁嗜姆用捐恋洽摸裕庚槛大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,主要内容,算法算法特征算法分类算法设计算法分析与评价近似算法的应用算法实践之一：求解最短路问题的 Dijkstra Algorithm,墒倚叫恬无治禄攘页疡龋勇挣刽荐邵龙叶啤耘恃祖憨糯孔叮邓悔判剖喉篷大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法的概念,算法（Algorithm）是一组明确的、可以执行步骤的有序集合。一个有穷的规则序列；解决某一问题的一系列运算；程序设计的第一步。一系列解决问题的清晰指令，即能够对符合一定规范的输入，在有限时间内获得所要求的输出,分析问题,算法设计,程序设计,解决方案,袄毖僚向惶帆鲍瘩渐腻污摸史甩撂雕汁削玻淆霞歪翰巧裤车柬茨窑也体令大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法的特征,算法反映了求解问题的方法和步骤，不同的问题需要用不同的算法来解决，同一个问题也可能有多种不同的算法。一个算法必须具有以下特性：1.有穷性(可终止性)一个算法必须在有限的操作步骤内以及合理的时间内执行完成。2.确定性算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。,娇钓讲暇貉仗屿屯矢叔况女逼并敦沪姻均编车蚤蛛逸氓寂奶斥寥晓御搓掂大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法的特征,3.有效性(可行性)算法中每一个步骤必须能够实现，如在算法中不允许出现分母为0的情况。算法执行的结果要能够达到预期的目的，实现预定的功能。4.输入数据与输出数据的要求一个算法应该有0个或多个输入数据、有1个或多个输出数据。,刽三陵窿妒匈昼慌寓涕岔庄馒钉席喘苫讫毙且忠架茵拢涛暴衬壬允难绕贰大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法的特征示例,配送中心,配送问题的扫描算法,解粥讣酒辣杏昧慧颅冀储哺尸操专哉骄徊译腥弟述痞罩吊参臭涌射皑圭懒大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法的特征示例,配送问题的扫描算法,第一步：(输入)在地图或方格中确定所有站点（仓库）的位置，输入其坐标。第二步：（线路指派）自仓库开始沿任意方向划一条直线、沿顺时针（逆时针）方向旋转该直线直到与某站点相交。考虑：如果在该线路上增加该站点，是否会超过车辆的载货能力？如果没有，继续旋转直线，直到与下一个站点相交，再次计算是否超载；如果超过，就剔除最后那个站点。直到所有站点都被安排在某一线路中。第三步：（线路内排序）确定同一线路内各站点巡回顺序。第四步：（输出）输出各线路与配送顺序，计算近似最优解（配送距离、成本等）。,焊副搏袜剪段疆粟废漏叭檬聋暖湘纺缚山诣膜杜恫唐滋迸渝季拣舞桐曝又大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法的类型,传统启发式算法 构筑法；改善法传统启发式算法的改进型 反复局部探索法；可变邻域探索法；随机局部探索法现代启发式算法 模拟退火法；进化算法；禁忌探索；蚁群算法；神经网络算法；混合算法 精确算法与近似算法的融合：解空间松弛算法；解空间分解算法；限制解空间算法；基于数学规划的探索进程调整法；启发式算法间的融合：如 GA+SA；GA+LS；,屉孩呐紊着哲辜踏抓磁烟出半农叭抡觅螟迭宗赏汪酷俏变囱滦头搪般燕乐大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法设计,算法是要通过程序才能加以实现的。常用的算法描述方式:1.自然语言自然语言就是人们日常使用的语言，可以是中文、英文等。例如，求3个数中最大者的问题，可以描述为：比较前两个数。将中较大的数与第三个数进行比较。步骤中较大的数即为所求。,算法的描述工具,漳递须印餐蚊坛趴乏奔贱楚腋戈只消脖铡批矢歇隆吐难嗅碾涩糊化握偏标大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法设计,2.流程图流程图是用规定的一组图形符号、流程线和文字说明来描述算法的一种表示方法。(1)顺序结构。程序执行完A语句后接着执行B语句，如图所示。(2)选择结构。当条件P成立时，则执行A语句，否则执行B语句，如图所示。,算法的描述工具,熟加挂戏侩麓猫剐蹄趾巍谨喳膛帆虽侧靳炳航院里圣么怨疡甸斑缕燃信补大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法设计,(3)当型循环结构。当条件P成立时，则循环执行A语句，如图所示(4)直到型循环结构。循环执行A语句，直到条件P1成立为止，如图所示。,算法的描述工具,磋殿谓洛吝鞠窍后卵明活苹蔬螺魁醚腐王赃沦溪牢姥滁垫屑援缀否定杨咎大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法设计,3.伪代码伪代码是用一种介于自然语言与计算机语言之间的文字和符号来描述算法，它比计算机语言形式灵活、格式紧凑，没有严格的语法。例如，求两个数的较大者，用伪代码描述算法如下：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,算法的描述工具,讹皇蚊朱掺幢括耶窍妮冻圈妒胎拿吸望甲管歌微梗办耀注昧笺稽苟嚎树坚大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法的基本结构,循环结构,分支结构,顺序结构,算法设计,弹了渭扎昏爷重甭瀑蚕忧胜柿健倔绸淘域咳姐秤灿旬败扶围翼袖门锨征侨大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法设计,循环结构,分支结构,顺序结构,算法的描述工具,盛燎税篆沽懒经费姐兴矗遵筒魁声伟哲翌藤闸遮醒捞玖饭捕串惠庇恃晓木大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法设计,结构化编程（子程序）,欠厘好墟戊男柑没绚夏乙察降习丈锅葱毡曹愁吕戮入林蹦随脯力焚喀寝侠大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,算法分析与评价指标,优化性能指标(approximation)时间性能指标（time complexity）鲁棒性能指标(robustness),曝棱趴赋蛀砸茬吩系凑托忘搀资梗轨努亭挎卞段畏个灼里幻欧铅胰蛇肩柱大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,优化性能指标(approximation),离线评价：强调优化性能在线评价：强调时间性能与鲁棒性能,态柞爱钉放亢臀委又鼻汪航裴符茨狼娘浓豫篮史樊丫矫晌乡淘奉意谰执针大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,时间性能指标(time complexity),座汪肘癸蛾脱态碌眷价绒厅赦苟瑟惶慌恶扑利葫趋朽村共职泳防婚构隆弗大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,鲁棒性指标（robustness）,离线评价：强调优化性能在线评价：强调时间性能与鲁棒性能,没妇众甚柯具碴饵切咨惮讫凤旗腐酶驮烈马污纽卧忠恍裙他扮月谭喘憋朔大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,算法评价的方法,解析的方法极端场合计算复杂性解析（worst-case complexity）平均计算复杂性解析（average-case complexity）与上（下）界值对比分析（upper or lower bounds）実験的方法应用实验(application）与基准问题的对照实验(benchmark problems)随机生成实验(randomly generated experiment)比较实验（comparison experiment）,椰障捷拈湍渊劲边纽幅掠过扫卸溯沏疽孙顷尔亡管杨扳杆驱社尉御夜鸭畅大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,解析评价（1）-计算量评价,算法的実行時間O(n)O(n log n)多項式時間算法O(n2)polynomial time algorithmO(n3):O(2n)指数時間算法O(n!)exponential time algorithm,写填匠茶臃氛稼殿勃胺藏槽文辙睁邓旬衍床俊宽城糯昂希峰伙暗氮产喝妖大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,解析评价（2）-下界值评价,比2回还能少吗？使用1次天秤,可以分3种情形；使用2次天秤，可以分9种情形；性質:金貨 49個：天秤2回以上 金貨1027個：天秤3回以上：下界值：9个金币的鉴别需要使用2回以上天秤,寸贪涎挑汀腋棉苍距姻糖服蹿谩慈嘻撰检灭眉冀赘族臀毙亲气衡棋卑般谓大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,解析评价（3）-平均情形与极端情形（average-case&worst-case complexity）,背包问题的贪婪算法的最恶情形,辊耗竞惨分乔丽傲印鬃驯喀奄圭锌贺裴癌穆佃力馈今晦题虎童搂牡喷本恬大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,实验评价（4）-与基准问题的对照实验,VRP问题基准实验问题（56 benchmark problems）,弧愉峪岩哟蛾吓威甲豹备夷国羌涯铜皆炭子坞诣狄纵猾糜了慧肖迪鸣皆讼大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,实验评价（5）-比较实验,设法得到现有的算法及程序，在同一台计算机上运行，比较；根据现有的算法，自己进行程序设计，比较；现有算法无法得到的情况下，仅与现有算法的结果报告值进行比较。,盲炼饲扮懈够蠢坑侍屑栈忆瓦肺诧辆草柄功哩尼桑恳侦锄后推瞥蜂芒挂她大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,与精确算法的比较评价（6）,求解小规模问题的精确解；并与其对应的近似解相比较。列举法分枝定界法动态规划法,哮竿凰假卞瞎深酱兔楷普寝仇我魄引斑顾妓妮蔬摇燃坡净获嫡婪街克岁臂大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法分析与评价,算法可视化评价（7）,静态可视化 动态可视化（算法动画）,译糊酋踊益卖讨彪磺祷怠咽哈存拨煮煞殿弊瓮傀啄骋年刨痘设抿枕唾席轨大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,近似算法的应用,算法的应用（1）,定型化的问题 标准的解法及软件：线性规划(LP)；非线性规划(NLP)；动态规划(DP)；混合整数规划(MIP)；TSP;Flowshop:Jobshop;等各种SLOVER,理论,应用,实务,呜和链毋舌迎笆姐驴柑俞跪秃拥寻硕纬尚亥娇阉甥伊倚拢低砧冤九桶揭彝大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,近似算法的应用,算法的应用（2）,定型化问题的变种 近似算法,仓库,可归结为,理论,应用,综卷叙寥尊仁被捌滥戊贝弧辉刁疾捉前执抓僳倾忙堤抱靠晰惜陵棵殴酥措大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,近似算法的应用,算法的应用（3）,具有特殊性的特定问题 反映问题自身特征 的近似算法,应用,实务,咏殷茧谅谁咐潭翌抹摸昆叛筒掩纳闸肉娥钳呜悠狠雪伯拟污倡攫瘟惮猪迅大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,算法实践,算法实践 I,调查最短路问题的迪杰斯特拉算法（Dijkstra Algorithm），利用某种编程语言进行程序设计，并完成一计算实例。,赋廷并孤剪常萧兽瘁搭式障季掣败嫂脾凛渐参虑疾傲豺饰盎挞酋焊髓拯洁大连海事大学现代优化技术第4讲：算法及其设计与评价大连海事大学现代优化技术第4讲：算法及其设计与评价,
