文档介绍：现代优化算法
许志军
xuzhijun1998@
2010-8-1
目录
Part 1 概论
Part 2 模拟退火算法
Part 3 遗传算法
Part 1 概论
主要是说明现代优化算法的重要性。
现代优化算法
现代优化算法
禁忌搜索算法
模拟退火算法
遗传算法
人工神经网络
蚁群算法
粒子群算法
混合算法
特点:
基于客观世界中的一些自然现象;
建立在计算机迭代计算的基础上;
具有普适性,可解决实际应用问题。
如何解决问题?
经典数学理论的解法:
Viete 定理:
由公理、定理形成的演绎逻辑体系
优点:准确、快速、有明确数学意义
不足:只能解决有限问题、解法是特定
的无法解决高次问题及更复杂问题。
考虑一个一元方程:
数值解法:
通过引入一些假设来获得问题的近似解
取初始值为1,代入得:
1
优点:可求解问题的范围比较广泛
不足:解法的特殊性,要求迭代收敛
如何解决问题?
(1)
传统算法的局限
解法是特定的
---- 不同的问题需要使用不同的解法
所能解决的问题是有限的
---- 和数学工具直接相关,若没有解
决问题的数学方法,则难以解决
数学建模竞赛中的算法(1)
93A 非线性交调的频率设计: 拟合、规划
93B 足球队排名次: 矩阵论、图论、层次分析法、整数规划
94A 逢山开路: 图论、插值、动态规划
94B 锁具装箱问题: 图论、组合数学
95A 飞行管理问题: 非线性规划、线性规划
95B 天车与冶炼炉的作业调度: 非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法
96A 最优捕鱼策略:微分方程、积分、非线性规划
96B 节水洗衣机:非线性规划
97A 零件参数设计:微积分、非线性规划、随机模拟
97B 截断切割:组合优化、几何变换、枚举、蒙特卡罗、递归、最短路
98A 投资收益与风险:线性规划、非线性规划
98B 灾情巡视:最小生成树、Hamilton圈、旅行商问题
99A 自动化车床:积分、概率分布、随机模拟、分布拟合度检验
数学建模竞赛中的算法(2)
99B 钻井布局:几何变换、枚举、最大完全子图、混合整数规划
00A DNA分类:神经网络、最小二乘拟合、统计分类
00B 管道订购:最短路、二次规划
01A 血管的三维重建:数据挖掘、曲面重建与拟合
01B 公交车调度:非线性规划
02A 车灯光源优化设计:最优化
02B 彩票中的数学:概率与优化
数学建模竞赛中的算法(3)