求解基约束下上模函数最小值的局部搜索算法及其性能保证

论文摘要

组合优化是通过数学方法的研究去寻找离散问题的最优筛选、分组、排序等,是运筹学中的一个重要分支,所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通讯网络等诸多领域。然而,不幸的是绝大多数的组合优化问题为NP-难问题,即一般情况下没有有效的多项式时间求解算法。故人们只能退而求其次,寻找可以求得近似解的多项式时间近似算法。局部搜索算法就是其中较为简单、灵活且有效的一种。局部搜索算法在求解组合优化问题时,是将搜索限制在解空间的某一局部范围内的一类算法。20世纪60-70年代,Lin和Kemighan两人在求解旅行商问题和图划分问题时发展了经典局部搜索算法的各种技术。局部搜索算法诞生以后,在运筹学界求解优化问题的应用中一直很活跃,在算法的复杂性理论研究中也有许多成果。上模函数是一类定义在格上或有限集的幂集上的特殊实值函数。与一般实值函数的最大区别是上模函数的变量是离散的。正是这一区别使得上模函数在组合优化中起到了非常重要的作用。一方面体现在对上模函数性质的应用,另一方面是许多组合优化问题都可视为求解上模函数的最值问题,如设备选址问题、k-中心问题、一般运输问题、集合覆盖问题等。因此,对于上模函数的性质和最值问题的研究是非常具有理论意义和实用价值的。然而,求解上模函数的最值问题为NP-难问题。故人们致力于寻找有效的多项式时间近似算法。有时甚至致力于解决特殊的上模函数的最值问题。本文首先简要介绍了局部搜索算法的基本原理及发展状况,随后给出了上模函数的若干性质及研究现状。最后利用局部搜索算法求解基约束下上模函数的最小值问题。全文共分四章,第一章首先简述了组合优化的基本概念及问题分类,然后给出了求解组合优化问题的两种不同方法,即精确算法与近似算法,最后介绍了本文内容安排。第二章综述了局部搜索算法的研究现状,以及其在组合优化中的广泛应用。介绍了局部搜索算法基本原理,在此基础上给出了若干基本概念。之后,给出了局部搜索算法的一般描述以及改进方法。最后,从理论上证明了改进后的局部搜索算法为多项式时间近似算法。第三章介绍了上模函数的基本概念和基本性质,给出了两个具体实例,为其后展开的研究工作做了必要的准备。在查阅相关文献资料的基础上,简要综述了目前上模函数的研究现状以及其在运筹学、应用数学、计算机科学中的重要应用。第四章给出求解基约束下上模函数最小值问题的局部搜索算法,并从理论上分析了所给算法的性能保证,说明了算法的有效性与实用性。本文主要考虑如下两种情况:（1）给出求解基约束下非负非增上模函数最小值的局部搜索算法及其性能保证,并与已有结果进行比较,说明了本文所给结果的优点及不足之处。（2）在考虑问题（1）的基础上,进而给出求解基约束下非负非减上模函数最小值的局部搜索算法及其性能保证。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 组合优化问题
• 1.2 计算复杂性理论与NP-完全理论
• 1.2.1 计算复杂性理论
• 1.2.2 NP-完全理论
• 1.3 算法及其分类
• 1.3.1 精确算法
• 1.3.2 近似算法
• 1.4 研究背景
• 1.5 本文任务
• 2 局部搜索算法
• 2.1 基本概念、原理及算法分类
• 2.2 计算复杂性分析
• 2.3 结束语
• 3 上模函数及其基本性质
• 3.1 上模函数的基本概念
• 3.2 两个例子
• 3.3 上模函数的基本性质
• 3.4 结束语
• 4 求解基约束下上模函数最小值的局部搜索算法及其性能保证
• 4.1 基约束下非负非增上模函数最小值问题
• 4.1.1 主要引理及证明
• 4.1.2 局部搜索算法及其性能分析
• 4.2 基约束下非负非减上模函数最小值问题
• 4.2.1 主要引理及证明
• 4.2.2 局部搜索算法及其性能分析
• 4.3 结束语
• 4.3.1 总结
• 4.3.2 展望
• 结论
• 致谢
• 附录
• 参考文献
• 攻读学位期间的研究成果