学位论文 > 优秀研究生学位论文题录展示

变邻域搜索算法研究及在组合优化中的应用

作　者: 董伟
导　师: 高雷阜
学　校: 辽宁工程技术大学
专　业: 应用数学
关键词: 变邻域搜索算法 组合优化 SQP 粒子群算法 罚函数法
分类号: TP301.6
类　型: 硕士论文
年　份: 2011年
下　载: 56次
引　用: 0次
阅　读: 论文下载
 

内容摘要


对变邻域搜索算法做出改进,提出了一种解决连续优化问题的变邻域搜索算法和一种结合粒子群算法的变邻域搜索混合算法。并将改进的算法应用于旅行商问题和0-1非线性混合整数规划问题中。主要的研究成果和创新点包括:首先,针对因连续优化问题的可行解空间特点而无法直接应用变邻域搜索算法的问题,将SQP算法与变邻域搜索算法结合,用SQP问题求解局部最优解,用变邻域搜索算法跳出局部最优解,进而求得全局最优解。通过数据仿真,证明变邻域搜索算法比其他启发式算法在全局收敛性等方面更好。其次,针对一般变邻域搜索算法计算时间长的问题,借鉴粒子群优化算法的思想,提出一种结合粒子群算法的变邻域搜索混合算法。通过调整变邻域搜索算法中的扰动过程和邻域变换过程,减少变邻域搜索算法中的局部搜索数量,提高扰动过程的效果。通过数据仿真,证明混合算法的有效性。最后,将改进的变邻域搜索算法应用于旅行商问题和0-1非线性混合整数规划两个组合优化问题中。其中,对于旅行商问题,引入新的粒子群算法运算法则,得到适合旅行商问题的变邻域搜索混合算法,通过数据仿真证明混合算法比一般变邻域搜索算法和其他启发法效果更好;对于0-1非线性混合整数规划,把它转化为一般约束优化问题,利用罚函数法和变邻域搜索算法在连续空间中求解,通过实例证明方法是可行的。

全文目录


致谢  5-6
摘要  6-7
Abstract  7-12
1 绪论  12-17
  1.1 引言  12-13
  1.2 问题的描述  13-15
    1.2.1 最优化问题  13-14
    1.2.2 组合最优化问题  14-15
  1.3 变邻域搜索算法研究现状  15-16
  1.4 本文的主要内容  16-17
2 变邻域搜索算法  17-24
  2.1 引言  17
  2.2 局部搜索  17-18
  2.3 变邻域搜索算法的基本构架  18-21
    2.3.1 变邻域深度搜索算法  18-19
    2.3.2 简化变邻域搜索算法  19-20
    2.3.3 基本变邻域搜索算法  20-21
  2.4 变邻域搜索算法的扩展  21-22
    2.4.1 偏态变邻域搜索算法  21
    2.4.2 变邻域分解搜索算法  21
    2.4.3 并行变邻域搜索算法  21-22
  2.5 算法分析与改进策略  22-23
  2.6 本章小结  23-24
3 变邻域搜索算法求解连续优化问题  24-34
  3.1 引言  24
  3.2 连续优化问题的邻域结构  24-25
  3.3 结合SQP 的一种变邻域搜索算法  25-27
  3.4 数值仿真  27-33
    3.4.1 仿真函数  27-30
    3.4.2 VNS 与纯SQP 的比较  30-32
    3.4.3 VNS 算法与其他启发法的比较  32-33
  3.5 本章小结  33-34
4 结合粒子群算法的变邻域搜索混合算法  34-40
  4.1 引言  34
  4.2 粒子群优化算法简介  34-37
    4.2.1 粒子群算法的起源  34-35
    4.2.2 粒子群算法的基本原理  35-36
    4.2.3 粒子群算法的算法流程  36-37
  4.3 结合粒子群算法的变邻域搜索混合算法  37-38
  4.4 数据仿真  38-39
  4.5 本章小结  39-40
5 变邻域搜索混合算法在旅行商问题中的应用  40-46
  5.1 引言  40
  5.2 旅行商问题简介  40-41
  5.3 求解旅行商问题的改进变邻域搜索算法  41-44
    5.3.1 旅行商问题的邻域结构  41-42
    5.3.2 求解TSP 问题的改进变邻域搜索算法  42-44
  5.4 数据仿真  44-45
  5.5 本章小结  45-46
6 变邻域搜索算法求解0-1 非线性混合整数规划  46-54
  6.1 引言  46
  6.2 0-1 非线性混合整数规划简介  46-47
  6.3 变邻域搜索算法求解0-1 混合整数规划问题  47-51
    6.3.1 0-1 混合整数规划问题转化为非线性整数规划问题  47
    6.3.2 外点罚函数算法  47-50
    6.3.3 外点VNS 算法求解MIP 问题  50-51
  6.4 数值实例  51-53
  6.5 本章小结  53-54
结论  54-55
参考文献  55-59
作者简历  59-60
学位论文数据集  60-61

相似论文

  1. 有源电力滤波器及其在配电网中的应用,TN713.8
  2. 基于粒子群的分子对接算法,R91
  3. 基于粒子群算法的露天矿道路路径优化研究,TP301.6
  4. 移动机器人路径规划研究及仿真实现,TP242
  5. 量子粒子群算法研究及其在图像矢量量化码书设计中的应用,TP301.6
  6. 电力系统无功优化的混合算法研究,TM714.3
  7. 基于QoS的无线传感器网络路由算法研究,TP212.9
  8. 参数协进化的改进和声搜索算法及其应用,TP391.3
  9. 非汛期水库群协同优化调度与应用研究,TV697.11
  10. 不确定环境下供应链多时段生产采购计划问题研究,F224
  11. 改进二进制粒子群算法在梯级水电站AGC中的应用研究,TV737
  12. 基于参数辨识的电力系统动态等值方法研究,TM712
  13. 粒子群算法在水库防洪优化调度中的应用研究,TP301.6
  14. 智能电网中蓄电池储能的价值评估研究,TM76
  15. 柔性路径下基于混合粒子群算法的跨单元调度方法,TH165
  16. 基于Copula风险控制的贷款组合优化模型研究,F224
  17. 连续竞争反应装置的效益优化方法与应用研究,TQ015
  18. 多自主车传感网络信息传输的优化配置研究,TN929.5
  19. 基于下偏度最小化贷款组合优化模型,F224
  20. 基于违约相关性的集中度风险控制方法研究,F830.5

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com