最小权顶点覆盖和线性排序问题的求解算法研究

发布时间：2020-10-16 04:37

　　 在实际生产生活和现代科学研究中存在着大量具有NP难性质的优化问题,如无线通讯信号覆盖、复杂电路设计布线、网络流量控制与疏导、航班任务调度等问题。这些具有NP难性质的众多复杂实际应用问题都是属于各自领域中的核心和关键性问题。基于计算复杂性理论的研究经验,计算机科学界普遍认为对这些具有NP难性质的复杂优化问题不存在多项式时间复杂度的完备且高效的精确求解算法。而在最近几十年的研究中,基于非完备的启发式优化算法在求解许多具有NP难性质的组合优化问题上表现出了良好的效果。也就是说,在一个相对合理的时间开销内,一个比较优秀的启发式优化算法通常能够获得所求问题的优度非常高的解。这为实际应用领域出现的大量NP难度的复杂优化问题提供了现实解决的途径。研究表明,上述实际案例中出现的大量NP难度的复杂优化问题均可在基于顶点覆盖和线性排序问题模型的基础上建模来求解。本文首先从算法研究的理论背景、经典求解算法框架方面系统梳理了启发式优化方法的特点、作用机理及其评价准则。然后选取两类经典的且具有重要实际价值的组合优化问题最小权顶点覆盖问题和线性排序问题(包括带累积成本的线性排序问题)作为参考研究对象,分别基于其各自问题的本质为它们设计了四种高效的启发式优化求解算法,并借助在公开基准算例上的计算实验对提出的算法进行了分析和评价。本文的主要贡献包括:(1)针对最小权顶点覆盖问题提出了一种高效的多启动迭代禁忌搜索算法(MS-ITS算法)。MS-ITS算法包括三个主要子算法和一个调节机制:初始解构造算法、禁忌搜索算法、扰动算法及多启动迭代机制。初始解构造算法通过引入随机和贪心两种策略来选择若干关键顶点构成合法初始解。禁忌搜索算法通过引入两种特性即基于同时多点移动的邻域结构并与之相适应的基于增量计算的快速邻域评估机制和双表禁忌策略,算法在每个当前解作邻域变换中既能探索更大的邻域空间又能快速的产生局部最优解。扰动算法引入一个基于顶点权值和关联度信息的扰动策略对局部最优解实施变换。使得算法搜索能从一个局部最优解慢慢找到优度更好的局部最优解。另外引入了多启动迭代机制扩展了算法的全局搜索能力。使用了最小权顶点覆盖问题的公开算例集(SPI、MPI和LPI)上的共126个基准算例进行了测试,多启动迭代禁忌搜索算法能够匹配约92%算例的历史最好结果并改进了44个算例的当前最好上界。(2)针对最小权顶点覆盖问题提出了一种更为高效的混合进化算法(HGA算法)。HGA算法混合了基于多启动迭代禁忌搜索算法MS-ITS和基于群体解操作的遗传算法GA。首先,通过引入一个基于GRASP思想的初始解生成策略来构造具有一定质量和分散性保证的初始种群,然后算法开始周期性迭代求解。在每次迭代周期中,通过引入基于公共基因继承机制的交叉算子对选择的两个随机父本解进化产生优质的新子代个体。再通过多启动迭代禁忌搜索算法使得当前优质的新子代个体从现有格局逐步变换到一个更优的局部最优解上,最后通过引入一个精英值打分机制来进行种群更新以使得种群中个体保持多样性的同时种群中的局部最优解的质量更好。其中多启动迭代禁忌搜索算法作为HGA算法的局部搜索算法强调算法的集中性搜索能力以找到质量更优的局部最优解,基于群体解的遗传进化算法来加强整个算法的疏散性搜索能力达到全局寻优。使用了最小权顶点覆盖问题的公开算例集(SPI、MPI、LPI)和另外的随机生成的大规模算例集RLPI上的共176个基准算例进行了测试,在同时比较MS-ITS算法的结果并引入公开的ILP求解器Gurobi的结果对比实验中,基于全部176个MWVCP测试算例上,HGA算法能够找到其中27个算例的最好上界并达到剩余所有算例的当前最好解或最优解。(3)针对带累积成本的线性排序问题提出了一个有效的混合进化算法(FBLSE算法)带累积成本的线性排序问题是线性排序问题的一种特殊演变形式。其解序列上的每个子项又包含了一个非线性的累积代价,该问题表现出了更高的计算复杂性。FBLS-E算法融合了一个Memetic框架和一个基于问题结构新提出的局部搜索算法。首先针对带累积成本的线性排序问题的内在结构提出了一个forward-backward邻域结构,该邻域结构扩展了当前解的邻域搜索空间,为每次邻域动作能够从一个当前解变换到更好的邻居解提供了更多的机会。由此,同时引入了一个基于多次SWAP动作的快速邻域评估方法以提高在较大邻域空间搜索上对解的评估效率。以此为基础,为带累积成本的线性排序问题设计了一个基于forward-backward邻域结构的高效局部搜索算法FBLS。在算法的每次迭代中,首先初始解构造算法融合随机初始解方法和局部搜索算法FBLS来产生高质量的初始种群。然后引入一个基于序列再融合的操作算子对两个随机选择的父本进化以产生优度较好的新子代解。接着通过局部搜索算法FBLS对新子代优化以产生更好的局部最优解。通过引入基于解的质量替换标准的种群更新策略来维护算法迭代中种群的多样性。使用了带累积成本的线性排序问题的118个公开基准算例进行了测试,FBLS-E算法在很短的时间内能匹配绝大部分算例的最优解,并找到了另外46个算例的最新上界。(4)针对经典线性排序问题提出了一个基于多父本再融合操作的改进的混合进化算法(MPM算法)MPM算法融合了一个Memetic进化框架和一个有效的局部搜索算法。首先,通过随机初始解生成策略和局部优化操作相融合的种群初始化构造算法来产生由局部最优解组成的初始种群。然后算法开始周期性迭代求解。在每次迭代周期中,先通过引入一个基于解距离特征的父本选择策略在考虑种群多样性的条件下进行多父本选择。在此基础上提出了一个基于多父本操作的再融合交叉算子对多个父本进化操作以产生尽可能继承更多父本优秀特征的新子代解,以此保证新产生的解的优异性。接着使用局部搜索算法对新子代进一步优化产生更好的局部最优解。最后通过引入一个基于种群解的质量和健康度的打分策略来更新种群,以维护进化过程中种群的多样性,以此进一步增强算法的全局寻优能力。使用了经典线性排序问题的8组共484个公开算例进行了测试,MPM算法能成功匹配所有最优解已知算例的最好结果,并在另外255个最优解未知的困难算例上,能成功匹配其中的163个当前最好解,并找到了其余66个算例的最新下界。以上研究成果表明,本文提出的多启动迭代禁忌搜索算法、混合进化算法及改进的混合进化算法都是求解对应顶点覆盖和线性排序类NP难优化问题的有效的启发式算法。通过本课题的研究,加深了对启发式优化算法求解NP难度的组合优化问题的理解。
【学位单位】：华中科技大学
【学位级别】：博士
【学位年份】：2019
【中图分类】：TP18;O224
【文章目录】：
摘要
Abstract
1 绪言
    1.1 选题来源与研究目的
    1.2 本文研究背景与意义
    1.3 主要研究内容及组织
2 组合优化及启发式优化方法简析
    2.1 关于组合优化问题
    2.2 组合优化问题的计算复杂性
    2.3 启发式优化经典算法简析
    2.4 启发式算法的评价准则
    2.5 本章小结
3 求解最小权顶点覆盖问题的多启动迭代禁忌搜索算法
    3.1 最小权顶点覆盖问题概述
    3.2 MWVCP问题的多启动迭代禁忌搜索优化算法
    3.3 计算结果及与其他参考算法的比较
    3.4 实验分析与讨论
    3.5 本章小结
4 求解最小权顶点覆盖问题的混合进化算法
    4.1 混合进化算法的基本原理
    4.2 MWVCP问题的混合进化优化算法
    4.3 计算结果及与其他参考算法的比较
    4.4 实验分析与讨论
    4.5 本章小结
5 求解带累积成本的线性排序问题的混合进化算法
    5.1 带累积成本的线性排序问题概述
    5.2 带累积成本的线性排序问题的研究现状
    5.3 带累积成本的线性排序问题模型
    5.4 LOPCC问题的混合进化优化算法
    5.5 计算结果及与其他参考算法的比较
    5.6 本章小结
6 求解经典线性排序问题的改进的混合进化算法
    6.1 线性排序问题的研究现状
    6.2 经典线性排序问题模型
    6.3 LOP问题的改进的混合进化优化算法
    6.4 计算结果及与其他参考算法的比较
    6.5 分析和讨论
    6.6 本章小结
7 总结及展望
    7.1 本文总结及研究成果
    7.2 主要创新点
    7.3 未来探索的着力点
参考文献
致谢
附录1 攻读学位期间发表论文目录
附录2 攻读博士学位期间参与的科研项目

【相似文献】

相关期刊论文 前10条

1 李刚刚;鲁习文;;目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J];运筹学学报;2019年04期

2 苟燕;戴秦;张新功;;具有时间与位置相关的两类平行机排序问题[J];运筹学学报;2019年04期

3 冉金玉;张新功;;总加权误工损失的两个代理单机排序问题[J];湖北民族学院学报(自然科学版);2019年01期

4 韩飞;;高中数学一道数列典型题解法的探究[J];数学学习与研究;2016年23期

5 豆俊梅;孙彩贤;;单机排序问题的研究[J];数学学习与研究;2017年24期

6 胡觉亮;杨佳雯;苏晓彤;董建明;;机器带周期性维护时段的加工与运输协同排序问题[J];浙江理工大学学报(自然科学版);2016年06期

7 仲维亚;马晓茹;;带有运输且加工具有灵活性的无等待流水作业排序问题[J];运筹学学报;2016年04期

8 隋楠;罗成新;;具有维护活动及公共工期的加工时间依赖资源的单机排序问题[J];沈阳航空航天大学学报;2016年06期

9 林浩;何程;;关于工期分配与加权误工数的双指标排序问题（英文）[J];工程数学学报;2017年01期

10 赵传立;张蕾;;带有交货期窗口和加工时间可控的排序问题[J];沈阳师范大学学报(自然科学版);2016年04期

相关博士学位论文 前10条

1 周淘晴;最小权顶点覆盖和线性排序问题的求解算法研究[D];华中科技大学;2019年

2 李融奇;在线排序和批排序问题研究[D];浙江大学;2018年

3 沈佳煜;不确定情形下若干排序问题的研究[D];南京理工大学;2017年

4 高园;新型排序问题的计算复杂性研究[D];郑州大学;2018年

5 殷娜;依赖于资源分配的排序问题研究[D];上海大学;2015年

6 李好好;若干排序问题研究[D];浙江大学;2014年

7 王吉波;工件加工时间可变的现代排序问题[D];大连理工大学;2005年

8 罗润梓;平行机半在线排序问题[D];上海大学;2005年

9 季敏;当代工业中的若干排序问题研究[D];浙江大学;2006年

10 叶德仕;通讯网络中排序问题的若干在线和高性能算法[D];浙江大学;2005年

相关硕士学位论文 前10条

1 李红;多AGV的多任务分配与路径规划研究[D];南京邮电大学;2019年

2 陈秋宏;与误工相关的双代理单机排序问题研究[D];重庆师范大学;2019年

3 马亚杰;工件具有相似加工时长的排序问题[D];湖南师范大学;2019年

4 丛稳;工件可拒绝的单机重新排序问题[D];郑州大学;2019年

5 曹移林;平行多阶段作业排序问题的研究[D];华东理工大学;2019年

6 康宇红;具有错位限制的重新排序问题研究[D];重庆师范大学;2019年

7 姜晓燕;MapReduce排序问题的若干算法研究[D];北京邮电大学;2019年

8 王亚男;具有退化维护和资源分配的单机排序问题[D];沈阳师范大学;2019年

9 李石;与资源相关加工时间可变的单机排序问题[D];沈阳师范大学;2019年

10 高焰红;平行批处理机上不相容族工件的在线排序问题[D];郑州大学;2019年

本文编号：2842772