导读:本文包含了启发式组合算法论文开题报告文献综述及选题提纲参考文献，主要关键词:启发式算法,组合优化问题,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]（2018）在《基于货物组合的叁维装箱启发式算法》一文中研究指出以叁维多层货物装载布局问题为研究对象,结合货物装载的实际需要,综合考虑集装箱的重心约束、独占性约束、总体积约束、载重量约束等,将最大化集装箱的空间利用率作为首要优化目标、最大化载重率为次要目标,建立了集装箱叁维装载模型,并采用启发式算法,引入货物块的概念将具有相同特征的货物组合成为新的长方体货物快,以达到更高的空间利用率。实例证明该算法与模型能够快速制定合理的货物装载布局方案,有效求解叁维装箱问题。(本文来源于《物流工程与管理》期刊2018年12期）
丁俊文[3]（2017）在《启发式算法中疏散性机制在求解组合优化问题中的应用》一文中研究指出启发式算法是求解大规模组合优化问题最常用的方法之一。集中性和疏散性是启发式优化算法的两个关键特征,它们之间紧密相关。集中性是指算法在一定的解空间区域进行高强度的搜索来获得优质的解,而疏散性则侧重于在必要的时候引导算法探索未访问的、更有意义的解空间区域,使算法跳出局部最优陷阱。它们之间的动态平衡是启发式算法获得高性能的重要保证。为了实现这种平衡,文献中提出了许多疏散性机制,例如迭代局部搜索算法中的扰动算符、贪心随机自适应搜索算法中的构造算符、跳坑局部搜索算法中的动态自适应的疏散性机制等。这些疏散性机制大多通过扰动和重建来实现。由这些疏散性机制产生的解可能与之前的解有足够的距离,但却没有很好的考虑产生的解的质量。本文对启发式算法中的集中性和疏散性做了深入的研究:首先,在已有文献的基础上,采用跳坑局部搜索算法中的动态自适应的疏散性机制,设计新算法求解了单机加权总延迟调度问题。其次,基于使用已有的疏散性机制求解实际问题的经验,提出了基于局部搜索算法的疏散性机制(QD-LS)。QD-LS的目标函数同时考虑了解的质量和距离,并可以通过相关参数来调节它们之间的比重。为了验证QD-LS作为疏散性机制的有效性,本文设计了两个不同的启发式算法分别求解了顶点分割问题和图划分问题,并通过实验测试和对比评估了算法的性能。具体来讲,本文的主要贡献如下:(1)通过对现有疏散性机制的研究,提出了一种基于局部搜索算法的疏散性机制QD-LS,并阐述了QD-LS的基本理论和关键技术。与传统的局部搜索算法不同的是,QD-LS是由质量和距离引导的局部搜索算法,它的目标函数中添加了当前解与历史最优解的距离分量。在同时考虑解的质量和距离后,QD-LS可以获得既有很高优度,且与历史最优解保持合适距离的解。(2)对于单机加权总延迟调度问题,提出了一种跳坑动态局部搜索算法BDS。在迭代局部搜索算法框架的基础上,BDS算法使用动态局部搜索算法进行集中性搜索,并运用跳坑局部搜索中的动态自适应的扰动机制来跳出局部最优陷阱。此外,通过实验对比发现,BDS算法在0.1秒的平均时间内,以100%的命中率求出所有100个工件以内的算例的最优解,并在252秒的平均时间内,以87.66%的命中率求出所有300个工件以内的算例的最优解,从解的优度和时间效率上证明了BDS算法的优越性。此外,还分析了重要参数对BDS算法性能的影响。(3)对于顶点分割问题,提出了一种以质量和距离引导的禁忌搜索作为疏散性机制的混合进化算法QD-HA。在混合进化算法框架的基础上,QD-HA算法结合了基本的禁忌搜索算法、贪心随机的交叉算法以及由质量和距离引导的禁忌搜索算法。在包含348个算例的标准算例集上通过实验与文献中最优秀的算法对比发现,QD-HA算法无论是在解的优度和时间效率上都具有很大的优势和很强的竞争力。特别是对于244个大规模的算例,QD-HA算法能够改进其中63个算例的已知最优解,其他算例的结果与文献中最好的算法的结果持平。此外,还分析了基于质量和距离引导的疏散性机制对QD-HA算法性能的影响。(4)对于图划分问题,提出了一种基于质量和距离引导的迭代局部搜索算法QDILS。在迭代局部搜索算法框架的基础上,QD-ILS算法结合了一个基本的局部搜索算法和QD-LS的疏散性机制。基本的局部搜索算法用于集中性搜索,QD-LS使用新的目标函数引导算法搜索更有意义的解空间区域。新目标函数同时考虑了解的优度和当前解与历史最优解的距离。在162个标准算例上进行实验发现,QD-ILS算法与文献中最优秀的算法相比具有很强的竞争力。具体来讲,它改进了其中33个算例的已知最好解。剩下的算例中,除4个算例外,QD-ILS均能与已知的最好解持平。此外,还分析了基于质量和距离引导的疏散性机制对QD-ILS算法性能的影响。以上的研究结果表明,本文提出的跳坑动态局部搜索算法、以质量和距离引导的混合进化算法QD-HA和以质量和距离引导的迭代局部搜索算法QD-ILS均是求解对应问题的有效的启发式算法。此外,从理论和实践的角度来看,本文提出的由质量和距离引导的局部搜索策略QD-LS是一个新颖的高效的疏散性机制。最后,由设计和应用QD-LS的相关经验可知,集中性和疏散性的平衡在启发式算法的疏散性机制的设计中是至关重要的。(本文来源于《华中科技大学》期刊2017-11-01）
邹子靖[4]（2016）在《基于图规划的启发式Web服务组合算法研究》一文中研究指出随着计算机技术的发展,Web服务作为一种分布式业务提供解决方案,得到业界的广泛认可。但是,往往Web服务的功能单一,难以满足日益复杂的用户需求,因此,如何重用已有的细粒度服务,利用Web服务组合方法,构建出符合用户功能需求及性能需求的复合服务成为服务组合问题的研究热点。随着语义网与Web服务的结合,语义Web服务应运而生。语义Web服务使得发布机器可理解的服务成为可能,为服务的自动组合技术提供了良好的支持。本文以语义服务为研究对象,提出了基于图规划的启发式Web服务组合方法。服务组合问题本质上是智能规划问题,因此智能规划算法被广泛应用于该问题,但是基于智能规划理论的服务组合方法需要对服务和任务进行预处理和形式化转化,方法复杂度较高,如果应用于海量服务集合时,服务组合的搜索过程和推理过程将变得非常困难。本文以基于图规划的服务组合方法为研究对象,在规划效率与求解质量方面分别提出算法进行改进,研究内容如下:(1)通过对基于图规划的服务组合算法的研究,发现其在规划图的扩展过程中添加了许多与目标不相关的服务。本文提出图规划框架下基于状态距离的Web服务组合算法,通过状态距离评估服务与目标状态的可达性,对规划图剪枝从而提高规划效率。并且,通过实验验证了该方法在不影响求解成功率的基础上,拥有更低的空间消耗和更高的求解效率。(2)通过对基于图规划的服务组合算法的研究,发现算法在解提取阶段存在盲目性,规划解质量较低。本文提出图规划框架下基于QoS的服务组合算法,提出基于状态质量的评估函数,指导规划图的解提取过程,从而得到更高质量的复合服务。最后通过实验验证了,该方法具有更高的求解质量和求解效率。(本文来源于《哈尔滨工程大学》期刊2016-01-01）
李国成,肖庆宪[5]（2014）在《CVaR投资组合问题求解的一种混合元启发式搜索算法》一文中研究指出本文针对均值-CVaR投资组合优化问题,基于混沌搜索、粒子群优化和引力搜索算法提出了一种新的混合元启发式搜索算法,而后基于多维布朗运动,借助Monte Carlo模拟情景生成得到价格路径,进而近似求解均值-CVaR投资组合选择问题,并与线性规划和非参数估计两种求解算法进行比较。模拟和实证算例结果表明,新算法在求解有效性和实用性方面表现更好,取得更为满意的结果。(本文来源于《运筹与管理》期刊2014年06期）
李文启,郭为民,杨明,魏强,程凤璐[6]（2014）在《求解计及失负荷概率约束机组组合问题的快速启发式算法》一文中研究指出为了解决电力系统机组组合中的备用配置问题,提出了一种求解计及失负荷概率约束机组组合问题的快速启发式算法。该算法通过对计及备用约束机组组合问题与运行可靠性评估问题的迭代求解,将机组组合计划对应的失负荷概率指标控制在给定水平;通过对迭代中备用更新步长的直接估计,提高了备用更新效率,达到了减少迭代次数、提高整体计算速度的目的。相较于已有算法,该算法提高了计算的快速性及计算结果的鲁棒性。通过对单区域及多区域RTS-96系统的测试计算,验证了算法的有效性。(本文来源于《电力与能源》期刊2014年03期）
傅丽芳,冯玉强,吴秋峰[7]（2014）在《基于权值编码的组合拍卖竞胜标确定启发式算法研究》一文中研究指出针对较大规模组合拍卖竞胜标确定问题(WDP),提出了基于权值编码的竞胜标确定启发式算法.改进了算法编码机制并嵌入基于WDP本质特点的启发式搜索规则,极大地提高了算法进化能力和求解效率.模拟实验结果表明该算法能够在较短时间内求出WDP最优解或满意近似解,为较大规模网上组合拍卖竞胜标确定问题提供了切实可行的求解算法.(本文来源于《数学的实践与认识》期刊2014年09期）
倪禾[8]（2013）在《基于启发式遗传算法的指数追踪组合构建策略》一文中研究指出消极组合管理方法已由国内外众多基金的表现证明是一种有效的资产组合投资方式.指数基金作为采取消极管理策略的典型代表,其业绩超越多数采取积极管理模式的基金.指数基金管理者的主要目标是使其基金的收益尽可能接近其标的股指,如我国的沪深300,美国的标普500的收益.本文提出了一种基于启发式遗传算法的寻优方案,通过最大化效用函数来寻找一个最为经济的指数复制组合.该组合同时应该满足拥有最少的资产数量、尽可能少的权重调整次数、最小的收益波动性等限制条件以减少基金开销,并使其收益尽量接近或者超越标的指数的收益.为使该策略具有更强的实用性,文章考虑了股票具有最小交易规模、投资权重分布不平均等实际限制.实验所得策略通过构造追踪组合来匹配沪深300指数,其综合效果超过了使用二次规划、等权或者是先验经验构筑的投资组合.(本文来源于《系统工程理论与实践》期刊2013年10期）
赖宇阳,范莹,白焰[9]（2013）在《应用于机组组合问题的启发式蚁群算法》一文中研究指出针对机组组合(UC)的整数-实数混合规划问题,先用二次规划计算各时段不同机组组合最优负荷分配,并选取各时段煤耗最小组合构造启发式初始解,根据解提供的信息设计一种删除不合理候选运行组合的方法,大幅缩小解空间。利用最大最小蚁群算法(MMAS)在解空间中搜索机组启停策略。针对MMAS效率低搜索慢的问题,算法在迭代完成后引入局部搜索。为降低启动煤耗,在蚂蚁转移概率公式以及信息素更新表达式中加入运行机组数因子及启动煤耗惩罚项,降低启动煤耗高的组合被选中概率,进而优化各时段同时运行机组数量。仿真结果表明以上改进能够大幅提高算法求解速度,具有较强的全局寻优能力。(本文来源于《现代电力》期刊2013年04期）
李国成,肖庆宪[10]（2013）在《基数约束投资组合问题的一种混合元启发式算法求解》一文中研究指出针对资产数目和投资资金比例受约束的投资组合选择这一NP难问题,基于混沌搜索、粒子群优化和引力搜索算法提出了一种新的混合元启发式搜索算法。该算法能很好地平衡开发能力和勘探能力,有效抑制了算法早熟收敛现象。标准测试函数的测试结果表明混合算法与标准的粒子群优化和引力搜索算法相比具有更好的寻优效率;实证分析进一步对混合算法与遗传算法及粒子群优化算法在求解这类投资组合选择问题的性能进行了比较。数值结果表明,混合算法在搜索具有高预期回报的非支配投资组合方面表现更好,取得了更为满意的结果。(本文来源于《计算机应用研究》期刊2013年08期）
启发式组合算法论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
以叁维多层货物装载布局问题为研究对象,结合货物装载的实际需要,综合考虑集装箱的重心约束、独占性约束、总体积约束、载重量约束等,将最大化集装箱的空间利用率作为首要优化目标、最大化载重率为次要目标,建立了集装箱叁维装载模型,并采用启发式算法,引入货物块的概念将具有相同特征的货物组合成为新的长方体货物快,以达到更高的空间利用率。实例证明该算法与模型能够快速制定合理的货物装载布局方案,有效求解叁维装箱问题。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
启发式组合算法论文参考文献
[1].石磊（Dalaijargal,Purevsuren）.组合优化问题的混合启发式算法中的路径重链接[D].哈尔滨工业大学.2019
[2].王祎楼.基于货物组合的叁维装箱启发式算法[J].物流工程与管理.2018
[3].丁俊文.启发式算法中疏散性机制在求解组合优化问题中的应用[D].华中科技大学.2017
[4].邹子靖.基于图规划的启发式Web服务组合算法研究[D].哈尔滨工程大学.2016
[5].李国成,肖庆宪.CVaR投资组合问题求解的一种混合元启发式搜索算法[J].运筹与管理.2014
[6].李文启,郭为民,杨明,魏强,程凤璐.求解计及失负荷概率约束机组组合问题的快速启发式算法[J].电力与能源.2014
[7].傅丽芳,冯玉强,吴秋峰.基于权值编码的组合拍卖竞胜标确定启发式算法研究[J].数学的实践与认识.2014
[8].倪禾.基于启发式遗传算法的指数追踪组合构建策略[J].系统工程理论与实践.2013
[9].赖宇阳,范莹,白焰.应用于机组组合问题的启发式蚁群算法[J].现代电力.2013
[10].李国成,肖庆宪.基数约束投资组合问题的一种混合元启发式算法求解[J].计算机应用研究.2013