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

论文摘要

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

论文目录

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