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