海事大学现代优化技术

《海事大学现代优化技术》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.［P6］优化技术具体包括数学建模、约束处理、算法设计以及程序设计等主要环节2.【P18］优化问题包括连续的数学规划与离散的组合优化问题组合优化问题的最大特点是决策变量取值是离散的、有限的，可行解集合同样也是有限的。组合爆炸一一指数形式增加3.【P20算法与计算量】优化问题通常会存在不同的算法，而其屮最有效的算法常常用计算所需时间作为衡量标准，时间决定了算法的效率。背包问题，n个物品，2八种可行解旅行商问题，n个城市，（n・l）!种可行解算法所用时间取决于该算法的计算量与其输入长度（1）计算量：力口、减、乘、除、比较

2、5种基本运算的次数（Step数）（2）输入长度：优化问题实例所用的计算机内存的单元数（基本可以用问题的规模n来代替英输入长度L）4.【P21】任何一个优化问题的算法都可以用计算量来表示计算复杂程度。【P22计算复杂性的表示】计算复杂性的分析往往忽略常数项和增长速度较慢的想，而仅仅关注增长速度最快的关键项计算复杂性的表示：（1）上限表示法（0）；（2）下限表示法（Q）；（3）上下限表示法（0）上限0最能体现算法的最坏可能的实例所需要的时间，更常用！【P23】多项式时间算法：g（n）是关于n的多项式函数.多项式时间算法的计

3、算时间随着问题规模的扩大，时间不断增加，但基本上是在可接受的范I韦I内，且有较好的封闭性。指数时间算法：g（n）是关于n的指数函数.指数时间算法随着问题规模的扩大，计算吋问将变得不可忍受。指数吋I'可算法求解大规模问题是不实用的、非有效算法。5.【P25-27P与NP类问题】P类问题（多项式时间可解问题）：一个优化问题已经找到了多项式时间算法一一可以快速求得大规模问题的最优解NP类问题（非确定性多项式问题）：一个优化问题目前尚未找到一个多项式时间算法一—借助于能够在多项式吋问内得到近似解的近似解算法（通过强化约束或松弛

4、约束转化）6.【P28】优化算法的基本特征：有穷性、确定性、可行性、具有输入、具有输出7.优化算法分为：求解全局最优解的精确解算法、求解近似解的启发式算法8.启发式算法包括：（1）传统启发式算法：构筑法和改善法（2）改进的启发式算法：A算法、反复局部探索发、可变邻域探索法、随机局部探索法（3）现代启发式算法：模拟退火法、进化算法（遗传算法）、禁忌搜索、蚁群算法、神经网络算法（4）混合启发式算法：［1］精确解算法与近似解算法的融合（解空间松弛算法、解空问分解算法、限制解空间算法、基于数学规划的探索进程调整法等）【2】启发

5、式算法间的融合（遗传算法与局部探索算法的融合、禁忌搜索与局部探索的融合、遗传算法与模拟退火法的融合）9.［P29］优化算法的描述是基于语言的，其表现形式主要有自然语言、流程图语言以及伪代码语言。10.【P30】启发式算法的开发策略：逐步构造解策略、改进解策略、分解策略、分割策略、松弛策略1.【31优化算法的评价】时间性能评价：指其计算复杂性近似性能评价：指启发式算法求得的近似解的精确程度解析评价（理论解析）：最差情形解析和平均情形解析实验评价：上（下）界值对比分析、小规模问题精确解对比分析【包括在线评价和离线评价】通过

6、与基進问题、应用问题对比分析或与其他已公开的结果对比分析鲁棒性能评价：指算法的稳健性or普适性，可通过大量生成随机实例的办法，并采用数理统计学的方差分析得以实现综合性能评价：三种指标的凸组合2.[36传统启发式算法一一构筑算法】基于逐步构造解策略，在每一步都是做出当时的最佳移动，以获取当时的最人化“好处〃。俗称贪婪算法，每一步对目前构造的部分解做一次扩展（可行性、局部最优性和不可逆性）【37】贪婪属性简洁明了、易于实现，具有很强的实用性。但由于每一步决策的短视行为，导致每一步做出的现时点的局部最优解并不能保证可构成最终

7、的全局最优解。（1）背包问题的构筑算法（2）TSP问题的构筑算法：最近近邻算法、随机近邻法、最小增加算法（TeastAdditionAlgorithm）＞多部分巡回路法（3）配送问题（VRP）的构筑算法：节约算法（贪婪性体现在step2中）3.【43传统启发式算法一一改善算法】基于改进解策略，又称为局部探索法（LocalSearch）或爬山法。核心环节在于当前点邻域的选择问题。如果邻域的范围较小，那么就可以快速地搜索该邻域，但容易陷入局部最优；如果邻域的范围较大，就不易陷入局部最优，但探索的效率会受到影响。邻域探索策略

8、：最初改善策略和最大改善策略【47】两种基本的邻域操作：插入操作和交换操作TSP问题改善算法：Or・opt操作K-opt操作（枝的交换），k的选取直接影响邻域的范围、探索吋间以及近似解的质量，k值得确定収决于刈问题解的精度要求以及刈计算时间及计算速度的要求。【k值的选取，鱼和熊掌不可兼得】配送问题改善算法:insert-opt插入