启发式算法.ppt

文档介绍：启发式算法一、组合优化问题二、启发式算法三、模拟退火算法四、遗传算法?解决离散的优化问题?运筹学分支。通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等,可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等诸多领域。 组合优化问题的基本概念?一般模型目标函数约束函数min ( )f x. . ( ) 0,.??s t g xx DD是有限个点构成的集合?0-1背包问题(Knapsack Problem)?加工调度问题(Scheduling Problem)?旅行商问题(Travelling Salesman Problem--TSP)?装箱问题(Bin Packing Problem)?图着色问题(Graph Coloring Problem)经典的组合优化问题:?0-1背包问题设有一个容积为b的背包,n件体积分别为,价值分别为的物品,如何以最大的价值装包?11max. . ,0 i1??????????ni iini iiiz c xs t a x bx若第种物品没选上,,?旅行商问题给定n个城市和每两个城市间的距离。一个货郎自某一城市出发巡回售货,问这个货郎应该如何选择路线,使每个城市经过一次且仅一次,并且路径长度最短。基于图论的0- 计算复杂性的概念例:TSP枚举法的基本计算量是n!,随着n的增加,计算量急剧增加。算法复杂性分析NP问题?这些问题描述非常简单,并且有很强的工程代表性,但最优化求解很困难;?其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间,以致根本不可能在现有计算机上实现,即所谓的“组合爆炸”。组合优化问题的特点:兼顾解的质量以及运行时间的较好算法:(1)设计平均形态良好的概率算法(2) 邻域结构与局部最优如何求解全局最优解?