导读:本文包含了混合启发式算法论文开题报告文献综述及选题提纲参考文献，主要关键词:启发式算法,组合优化问题,NP难度,混合启发式
混合启发式算法论文文献综述
石磊（Dalaijargal,Purevsuren）[1]（2019）在《组合优化问题的混合启发式算法中的路径重链接》一文中研究指出组合优化问题(Combinatorial Optimization Problems,COPs)在诸多领域具有广泛的实际应用。然而目前大多数组合优化问题(COPs)问题为NP难度问题,它还没有方法能在多项式时间内得到其最优解。实践表明,启发式算法能够在合理的时间内找到其近似解。然而随着问题规模的扩大,启发式算法的计算时间随之增加,随着可用数据的增加,问题的规模也在不断扩大。因此,开发设计高效的启发式算法来处理更大规模问题的需求显得日益迫切。而设计高效启发式算法的关键在于理解所考虑问题的本质,并以正确的方式集成优化各种有效方法。路径重链接(Path relinking)是对于难度问题的主要优化方法之一。本文的主要研究重点是通过理解问题本质以及路径重链接来提升启发式算法的性能。本文中,主要考虑两个具体的优化问题:关键节点检测问题(Critical Node Detection Problem,CNDP)和(Quality of Service,QoS)感知服务选择问题(QoS-aware Service Selection Problem,QSSP)。论文主要的工作如下:(1)在单目标优化的背景下,研究了一种成熟的元启发式方法,即贪婪随机自适应搜索过程(Greedy Randomized Adaptive Search Procedure,GRASP)与混合的外部路径链接的性能改进。外部路径重新链接是最近提出的一种元启发式方法。尽管路径链接被广泛用在贪婪随机自适应搜索过程中,但它仅限于路径连接的内部变体。因此,需要对外部路径连接与贪婪随机自适应搜索过程的混合外部路径连接进行研究。针对CNDP问题,提出了一种新的外路径连接贪婪随机自适应搜索过程混合方案。在新方案中,通过使用外部路径重新链接,将抓取迭代得到的结果与先前发现的高质量解决方案重新链接。外部路径重新链接通过探索两个解决方案之外的邻居来创建路径。计算实验表明,基于外部路径重新链接的算法在解决CNDP问题上优于其他变异的路径链接。此外,与其他方法相比,该算法找到了更高质量的解,并提高了文献中已知数据集16个实例中8个实例的最佳已知值。(2)在多目标优化的背景下,研究了路径链接与交互式进化多目标优化(Evolutionary Multi-objective Optimization,EMO)杂交路径链接的性能改进问题。由于许多组合优化问题(COPs)在本质上有多个目标,因此将用户偏好信息合并到优化过程中是找到最佳解决方案的唯一方法。我们提出了一种新的交互式EMO程序(用cdEMO表示),它在优化过程中周期性地合并用户偏好信息,并将信息建模为凸锥。该算法利用用户偏好信息将帕累托(Pareto)无与伦比的解决方法分为若干有序类。然后,我们研究了路径重新链接如何支持cdEMO算法的性能。根据用户反馈的要求,路径重新链接提高了cdEMO算法14.3%的性能。计算实验表明,cdEMO算法能够更快地收敛到所需的解。由于cdEMO是一种通用的优化算法,因此它可以用于任何组合优化问题(COPs)。(3)QSSP采用了先前提出的cdEMO的修改版本,这是一个具有高度重要性的现实问题,具有多个性质的目标。我们批判地分析了目前大多数求解QSSP的方法所采用的尺度化方法,并找出了严重的缺点,如难以定义正确的权值向量进行聚合,以及找不到帕累托前沿非凸部分的能力。cdEMO算法通过合并用户偏好信息来解决这两个缺点。实验结果表明,采用路径重链接的改进型cdEMO是一种有效的QSSP方法。(4)研究开发了有效的CNDP算法。通过对CNDP性质的理解,提出了一种适用于大型平面图CNDP的高效启发式算法。证明了CNDP在平面图上的NP难度。由于目标函数的计算代价是O(n),其中n是问题的大小,因此启发式算法的计算时间随着问题大小的增加而急剧增加。将目标函数转化为双目标函数。提出了一种利用平面图的特殊性质计算变换后的双目标函数的机制,可以通过使用特殊的平面图形的性质,在常数时间内计算被转换的双目标函数。能够用有效的方法开发一个大型图形的平面性需求。相比于最先近的一些方法,计算实验证明所提出的算法在运行时间和解法质量方面具有明显的优越性。(本文来源于《哈尔滨工业大学》期刊2019-06-01）
薛雷[2]（2019）在《最小延时问题的并行混合元启发式算法》一文中研究指出最小延时问题是旅行商问题的变体,目的是求解路线中所有客户的累计等待时间,最小延时问题相比于旅行商问题更难以解决。目前的求解方法,只能在客户数量较小时具有较高的性能,当客户数量变大时算法很难兼顾运行时间与求解质量。基于上述问题,对如何在较短时间内获得大数据量最小延时问题的优质解这一问题进行以下研究。1.对于大数据量的最小延时问题,目前主要使用元启发式算法求解,在此基础上提出一种混合元启发式算法。将遗传算法与变邻域搜索算法细粒度结合,在遗传算法的框架内实现变邻域搜索。当算法陷入局部最优解时,可以在遗传算法的交叉过程中改变子代染色体的邻域结构;并对遗传算法的变异过程进行改进,子代染色体可以在增加多样性的同时有较大概率发生优化。然后对算法进行数据预处理,通过为每个染色体构建基因节点索引列表,降低生成子代染色体的时间复杂度。2.为了进一步加快算法运行,使用GPU实现算法的并行化,并根据GPU运行特点对并行算法做出改进。将并行算法的交叉与变异过程以线程束为单位分开同步运行,每个线程具有固定的染色体选取位置与生成位置。算法整体上以线程块为单位并行运行,以保证并行算法避免产生线程发散问题并且减少线程通信开销,同时实现染色体的动态选择。此外将算法与扰动机制相结合,增强并行算法全局搜索能力,并使用多重改进方式生成最终解。通过上述方法进一步提升算法性能。为验证算法的实际运行情况,对算法进行对比实验,测试数据的节点个数从51到10150不等。实验结果表明,提出的算法在CPU环境中,相对于其它元启发式算法,可以在较短的时间内取得优质解;在CPU-GPU环境中,当数据规模较大时,并行算法可以取得明显的加速效果,数据规模越大,加速效果越明显。并且该并行算法相较于实验中其它的并行算法,具有更好的性能。因此,对于大数据量的最小延时问题,并行混合元启发式算法可以在相对较短的时间内获得优质解。(本文来源于《河北大学》期刊2019-05-01）
朱荣,徐双应[3]（2019）在《基于启发式算法的混合动力公交客车二级维护周期优化研究》一文中研究指出合理地确定城市公交客车二级维护周期,有助于提高车辆运营效率,保障车辆技术状况,节约生产运营成本。在多目标规划理论基础上,引入启发式算法,结合试验论证和数据分析,提出了一套二级维护周期优化方案。选取影响二级维护周期的若干约束变量,基于多目标规划理论,制定二级维护周期;通过维护周期里程间隔对比试验,对二级维护周期进行再优化;对比二级维护周期优化前后的车辆技术状况和经济指标,进行可行性分析;根据可行性分析结果,视情况返回第1步进行再优化。以西安市混合动力公交客车为例,二级维护周期优化后,车辆的使用可靠性得到了有效提高。此方案同样适用于其他道路运输车辆的维护周期优化。(本文来源于《小型内燃机与车辆技术》期刊2019年02期）
谢谢,周莉,郑勇跃[4]（2019）在《混合亚启发式算法求解带有热量损失的单吊机调度》一文中研究指出研究了钢铁企业物流系统中的一类单吊机调度问题.在板坯仓库中,为了最小化全部板坯的总热量损失,通过优化吊机的操作,以确定阻碍板坯的倒垛位置和目标板坯的拣选顺序.针对这个问题,建立混合整数线性规划模型求解小规模问题的最优解,对中大规模问题,提出混合亚启发式算法,该算法首先由贪婪启发式求得初始解进一步使用变深度邻域搜索策领略改进解的质量.数值计算实验结果表明,所提出的混合整数线性规划模型和混合亚启发式算法是有效的.(本文来源于《沈阳大学学报(自然科学版)》期刊2019年02期）
管卫利,龚击,薛焕堂[5]（2018）在《一维下料问题的一种混合启发式算法》一文中研究指出讨论一维下料问题,即用库存线材原料切割出若干种已知数量和长度的零件,优化目标为最大化线材利用率。提出一种混合启发式下料算法,用当前零件构造线材所有可能的切割方式,计算每种切割方式的废料长度、零件平均长度、大零件数量,按照废料最小、零件平均长度最大、大零件数量最多的原则选择一种切割方式切割相应线材,满足部分零件需求;用剩余零件继续构造线材可能的切割方式,按上述原则继续选择相应线材进行切割,重复该过程,直到所有零件的需求量得到满足为止。采用文献中基准例题验证文中下料算法,数值实验结果表明该算法与4种文献算法相比性能占优,且算法计算时间合理。(本文来源于《机械设计与制造》期刊2018年08期）
陈涛[6]（2016）在《基于大数据和混合启发式算法的公交调度方法》一文中研究指出从智能交通系统(Intelligent Transport System,ITS)在我国实施和使用以来,公交运管组织积累了大量的数据。这些数据包括公交车的行驶轨迹、乘客的刷卡记录、快速公交车站的闸机开关记录、出租车的行驶轨迹和公共自行车的借还记录等。这些数据中隐藏着非常大的价值,但是它们并没有被有效的利用起来,有些甚至因数据量过大,存储成本过高而被丢弃掉了。本文主要介绍了如何利用这些数据中的部分数据来进行分析和处理,并通过数据挖掘、自适应粒子群优化(APSO)、BP神经网络和改进的遗传-模拟退火算法等方法解决公交调度中静态调度和动态调度的相关问题,来提高现有公交系统的运营效率和服务质量。在本文中,首先对公交系统中产生数据的源头进行描述,并介绍了乘客乘车历史记录和公交车辆GPS历史记录的格式。在对这些数据进行挖掘之前,首先要对其中的异常数据实施预处理,这些异常数据包括无效的数据、重复数据、乘客上下车站点或时间缺失和GPS芯片定位不准确的数据等。预处理之后,对数值型数据进行规格化处理,并将分类型数据转换为数值。对于历史乘车记录,使用层次聚类中的Ward方法对不同日期中客流模式进行聚类分析。与以往客流时段的划分方法相比,这种方法更关注客流量在一天当中的整体规律,更符合实际情况。最后使用APSO-BP神经网络结合时间段、天气、节假日和日期等因素,对客流量进行预测。在建立预测模型是,本文创新性的提出将多变的天气数据按照对公交出行的影响划分为叁个等级,从而将它转换为数值。基于车辆的GPS数据,对与之相关的一些运营特性进行分析,然后使用APSO-BP方法对车辆的到站时间进行预测。公交调度中静态调度和动态调度是两项非常重要的活动,本文在这两个方面提出了解决方法。基于预测得到的客流量数据,使用改进的模拟退火与遗传算法进行问题的求解。本文中使用个体适应度拉伸策略来改进遗传算法前期个体多样性差和后期收敛速度慢的缺点,并以乘客等待成本最小和公交运营组织利益最大为目标建立静态调度的数学模型。在动态调度方面,基于预测得到的到站时间,结合实时车辆位置信息进行异常情况的检测;根据上车人数进行公交优先调度;结合静态调度的结果与其他出行方式和线路进行协同调度。(本文来源于《杭州电子科技大学》期刊2016-03-01）
刘畅[7]（2016）在《基于混合启发式算法的单线公交车辆调度问题研究》一文中研究指出近年来,随着城市化进程的加快,城市公共交通问题也越来越严重。为了缓解城市交通压力,就需要大力发展智能交通,提高公共交通系统的运行效率和服务质量。而公交调度问题作为智能交通的核心问题之一,对公交系统的运营水平和服务水平具有重大影响。公交调度问题是一个复杂的组合优化问题。由于问题的复杂性,当前的公交调度模型存在着一些不足,这就造成求解的问题不太适合实际情况；同时,当前的车辆调度算法也比较单一,通常使用遗传算法等智能优化算法,缺少对混合启发式算法的研究。基于此,本文建立了一个上下行发车频率不同的公交组合调度模型,该模型可以解决不同路段之间以及上行和下行之间的客流不均衡问题；进而,为了使该模型更具有普遍性,能够适应多种客流需求,又增加了区间车首站不在始发站这一因素。同时,提出了一种以粒子群算法和模式搜索算法相结合的混合启发式算法；粒子群算法在许多复杂的NP-难问题上都有很好的表现,但是也有着易早熟收敛等缺点；而模式搜索算法却有着较强的精细搜索能力,因此将两者结合起来构成混合启发式算法是合理的。最后,本文在蚌埠公交真实数据集上验证了提出的模型和算法,结果表明提出的调度模型和求解方法是有效的。(本文来源于《北京交通大学》期刊2016-03-01）
苏志雄,伊俊敏[8]（2015）在《混合流水车间调度问题的两阶段启发式算法》一文中研究指出针对以最小化makespan为目标的混合流水车间调度问题,提出了一种两阶段启发式算法。在算法设计中,借鉴求解常规流水车间调度问题的经验,定义了一种相邻交换的邻域结构。算法的第一阶段利用基于排列排序的Nawaz-Enscore-Ham(NEH)算法求得一个较好的初始解,第二阶段通过邻域搜索来提高解的质量。基于benchmark算例的仿真实验结果表明该算法的有效性,与NEH相比,77个算例的平均偏差降低了2.004%,且其运行时间不超过0.031 s。(本文来源于《厦门理工学院学报》期刊2015年04期）
刘建平,李晶,张天骄[9]（2015）在《航天测控网调度的混合构造启发式算法》一文中研究指出针对航天测控网调度问题,提出一种基于混合启发式的解构造算法。与其他构造启发式算法不同的是,本启发式算法充分利用了我国航天测控网调度需求的特点,包括优先级、任务之间时间间隔要求和一个需求包括多个相同任务要求等,综合考虑了任务局部和需求全局,融合最大可用窗口价值规则和最早可用窗口集规则。其优势在于通过动态选择构造启发式规则来提高求解质量。最后,通过仿真实验分析比较,该算法可以在不明显增加计算时间的基础上得到更高的初始解质量。(本文来源于《系统工程与电子技术》期刊2015年07期）
赵卫虎,赵静,赵尚弘,李勇军,韩磊[10]（2014）在《微波与激光混合链路中继卫星动态调度快速启发式算法》一文中研究指出针对微波与激光混合链路中继卫星系统实际应用中的动态变化,分析了混合系统动态扰动条件,依据中继卫星资源调度动态调整原则,研究了混合系统动态资源调度策略。以最大化调度任务优先级之和,以及扰动发生后对初始方案扰动变化最小为目标,建立了具有两级优化目标的混合系统动态调度模型。提出了动态插入快速启发式算法并对模型求解算法,算法包括直接插入任务操作、移动插入任务操作和删除插入任务操作。仿真结果表明与完全重调度的算法相比,动态插入算法的方案变化率平均降低了60.10%,且计算速度明显高于重新调度算法,能够有效解决混合链路中继卫星系统动态调度问题。(本文来源于《中国激光》期刊2014年09期）
混合启发式算法论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
最小延时问题是旅行商问题的变体,目的是求解路线中所有客户的累计等待时间,最小延时问题相比于旅行商问题更难以解决。目前的求解方法,只能在客户数量较小时具有较高的性能,当客户数量变大时算法很难兼顾运行时间与求解质量。基于上述问题,对如何在较短时间内获得大数据量最小延时问题的优质解这一问题进行以下研究。1.对于大数据量的最小延时问题,目前主要使用元启发式算法求解,在此基础上提出一种混合元启发式算法。将遗传算法与变邻域搜索算法细粒度结合,在遗传算法的框架内实现变邻域搜索。当算法陷入局部最优解时,可以在遗传算法的交叉过程中改变子代染色体的邻域结构;并对遗传算法的变异过程进行改进,子代染色体可以在增加多样性的同时有较大概率发生优化。然后对算法进行数据预处理,通过为每个染色体构建基因节点索引列表,降低生成子代染色体的时间复杂度。2.为了进一步加快算法运行,使用GPU实现算法的并行化,并根据GPU运行特点对并行算法做出改进。将并行算法的交叉与变异过程以线程束为单位分开同步运行,每个线程具有固定的染色体选取位置与生成位置。算法整体上以线程块为单位并行运行,以保证并行算法避免产生线程发散问题并且减少线程通信开销,同时实现染色体的动态选择。此外将算法与扰动机制相结合,增强并行算法全局搜索能力,并使用多重改进方式生成最终解。通过上述方法进一步提升算法性能。为验证算法的实际运行情况,对算法进行对比实验,测试数据的节点个数从51到10150不等。实验结果表明,提出的算法在CPU环境中,相对于其它元启发式算法,可以在较短的时间内取得优质解;在CPU-GPU环境中,当数据规模较大时,并行算法可以取得明显的加速效果,数据规模越大,加速效果越明显。并且该并行算法相较于实验中其它的并行算法,具有更好的性能。因此,对于大数据量的最小延时问题,并行混合元启发式算法可以在相对较短的时间内获得优质解。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
混合启发式算法论文参考文献
[1].石磊（Dalaijargal,Purevsuren）.组合优化问题的混合启发式算法中的路径重链接[D].哈尔滨工业大学.2019
[2].薛雷.最小延时问题的并行混合元启发式算法[D].河北大学.2019
[3].朱荣,徐双应.基于启发式算法的混合动力公交客车二级维护周期优化研究[J].小型内燃机与车辆技术.2019
[4].谢谢,周莉,郑勇跃.混合亚启发式算法求解带有热量损失的单吊机调度[J].沈阳大学学报(自然科学版).2019
[5].管卫利,龚击,薛焕堂.一维下料问题的一种混合启发式算法[J].机械设计与制造.2018
[6].陈涛.基于大数据和混合启发式算法的公交调度方法[D].杭州电子科技大学.2016
[7].刘畅.基于混合启发式算法的单线公交车辆调度问题研究[D].北京交通大学.2016
[8].苏志雄,伊俊敏.混合流水车间调度问题的两阶段启发式算法[J].厦门理工学院学报.2015
[9].刘建平,李晶,张天骄.航天测控网调度的混合构造启发式算法[J].系统工程与电子技术.2015
[10].赵卫虎,赵静,赵尚弘,李勇军,韩磊.微波与激光混合链路中继卫星动态调度快速启发式算法[J].中国激光.2014