导读:本文包含了启发式排序论文开题报告文献综述及选题提纲参考文献，主要关键词:自由作业排序问题,复杂性,单服务器,启发式算法
启发式排序论文文献综述
时凌,张琼,时义梅,魏代俊[1]（2019）在《带单服务器的自由作业排序问题的启发式算法》一文中研究指出研究带单服务器的自由作业排序问题,证明在只有两台机器且加工时间相同的情况下该问题是强NP-困难的,引入了求解该问题的启发式算法,证明该算法的紧界为5/4.在具有m台机器的情况下,给出相应的启发式算法,其紧界为2-3/(m+2).(本文来源于《数学的实践与认识》期刊2019年09期）
徐海霞[2]（2018）在《基于元启发式算法的测试用例生成与排序研究》一文中研究指出软件测试用例生成技术和优先级排序技术是软件测试自动化的两个关键技术,元启发式搜索算法被广泛应用于解决测试用例自动生成与优先级排序问题。本文系统学习并总结了目前国内外已有的在相关技术方面的研究成果,发现元启发式搜索算法在测试用例生成技术和优先级排序技术中的应用尚未成熟,普遍存在算法收敛速度慢、考虑影响因素单一、难以收敛至全局最优等问题。为此,本文主要对元启发式搜索算法用于解决测试用例生成和优先级排序的问题进行了研究,分别提出了一种基于遗传优化算法的动态引导测试用例生成策略,以及一种基于蚁群优化算法的动态约简的多目标优先级排序方法。本文主要研究内容以及具体贡献主要为以下叁个方面:(1)在基于路径覆盖的测试用例生成技术方面,本文使用被应用较广泛的遗传算法进行求解。考虑到初始测试数据对路径节点的覆盖情况,先是区分出难易覆盖路径,然后设计了一种路径相似度的计算公式,分析出难易覆盖路径间的启发信息并用于替代遗传算法的部分初始种群。(2)在遗传算法的改进方面,增加考虑了分支权重对种群适应度的影响,分别根据不同程序的特征为各影响因子赋予权重,构造了一种带有权重影响因子的适应度评价函数,并以此设计自适应遗传概率,定向引导个体交叉变异,以快速得到满足路径覆盖的高质量测试数据。(3)在测试用例优先级排序技术方面,本文使用鲁棒性较强的蚁群算法求解这一问题,在排序过程中结合一种动态约简的思想,根据需求覆盖情况对测试用例进行初始约简,然后考虑到测试用例实际执行过程中是否能检测出的错误以及错误的等级,设计测试用例失效度的判别方法对迭代过程中的测试用例进行二次约简,通过两次约简大幅度减少蚁群迭代的时间消耗。在蚁群算法的信息素更新策略上,本文综合考虑了测试用例重要度、失效度以及有效执行时间叁个因素对信息素的影响,在线指导蚁群信息素的更新,提升蚁群算法的求解精度和收敛速度。为了验证本课题在测试用例生成与优先级排序这两个方面提出的改进方法的有效性,选取多个基准和工业程序进行编程实验,将本文提出的基于元启发式搜索算法的测试用例生成和多目标优先级排序方法分别与其他方法进行对比,仿真实验结果表明,本选题研究的基于遗传算法的测试用例生成方法在收敛速度、路径覆盖率、已有测试数据的利用率上有明显优势,提出的基于蚁群优化算法的多目标优先级排序方法在语句覆盖率、缺陷检测效率和有效执行时间等方面均优于其他方法。(本文来源于《浙江理工大学》期刊2018-12-10）
付玉书,莫毓昌,潘竹生[3]（2015）在《网络可靠性BDD分析中选择最优启发式边排序策略》一文中研究指出网络可靠性二元决策图(BDD)分析方法的计算复杂度与BDD的尺度大小密切相关,而BDD的尺度大小取决于边排序策略。由于边排序问题是一个NP-完全问题,没有形式化的准则可为工程网络选择一个较好的启发式策略。文章中,使用基于边界集概念的启发式策略选择方法,为网络可靠性BDD分析做出了新的贡献。实验研究表明,所使用的选择方法可以使大部分的研究案例生成高性能的边排序,进而可以高效地实现基于BDD的大型网络可靠性分析。(本文来源于《信息通信》期刊2015年09期）
彭关伟,乔立红,胡权威[4]（2016）在《基于约束矩阵的启发式工序排序方法》一文中研究指出针对零件工艺设计过程中的工序排序问题,提出一种基于约束矩阵的启发式工序排序方法。在该方法中,工序排序被转化为以加工活动为对象的组合排序问题,并构建其数学模型。该模型将工序排序中需要满足的工艺规则分为聚类规则和顺序规则两类,建立了工艺规则与加工活动信息之间的量化关联关系,通过工艺规则的作用确定加工活动间的约束关系;定义聚类约束关系和顺序约束关系向矩阵转化的机制,生成加工活动间的聚类约束矩阵和顺序约束矩阵,在此基础上建立启发式算法对其进行聚类分组,并对聚类的加工活动进行排序,得到加工活动的组合和次序。最后通过工序排序算例验证了该方法的可行性。(本文来源于《计算机集成制造系统》期刊2016年04期）
王海燕,管莹,李闯,杨明明[5]（2015）在《两种智能值排序启发式研究》一文中研究指出为提升约束满足问题求解效率,对最受推崇的智能值排序启发式Look-ahead和Survivors-first进行深入研究。比较两种值排序启发式在常规和自适应两种环境下的效率表现。结果显示,在多数问题类上,常规情况下Survivors-first效果更好,而在自适应环境下效率有所下降;在不同环境下使用不同启发式可提升约束满足问题求解效率。(本文来源于《吉林大学学报(信息科学版)》期刊2015年04期）
朴惠淑,贾春玉,常留贤[6]（2015）在《基于最优解下限的单工序平行机排序启发式算法》一文中研究指出针对单工序平行机排序LPT方法计算步骤多等问题,提出了一种适用于中小企业现场排序的最优解下限截取启发式算法。传统平行机排序最优解下限表达式存在因偏离最优解过大而难以引导排序走向最优的缺陷,改进后的下限表达式更加接近于最优解。从计算步骤多少和偏离最优解下限的最大偏差率两个角度,比较分析了最优解下限截取法与LPT法的特点。经实验数据验证,得出零件数与平行机数之比非整除且满足一定条件时,简单易行的截取法更优于LPT法的结论。(本文来源于《工业工程与管理》期刊2015年02期）
潘竹生,莫毓昌,钟发荣,刘轩,伍欢[7]（2014）在《一种新的启发式边排序策略及其性能分析》一文中研究指出网络可靠度BDD分析方法的计算复杂度与BDD尺度线性相关,而BDD尺度严重依赖边排序质量。由于求解最优边排序是一个NP问题,在实际应用中,通常采用启发式边排序策略如BFS(Breadth-First-Search)和DFS(Depth-First-Search)。针对边排序问题,从分析基于边界集(Boundary Set)的BDD构建方法 BDD-BS出发,将边界集思想应用于边排序过程,提出了一种新的启发式边排序策略。性能分析和大量实验表明,新设计的边排序策略性能优于经典的DFS和BFS策略,该结果为网络可靠度BDD分析方法在大规模网络中的应用拓展了新的空间。(本文来源于《计算机工程与科学》期刊2014年11期）
井彩霞,张磊,刘烨[8]（2014）在《需要安装时间的平行多功能机排序问题的启发式算法》一文中研究指出考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。(本文来源于《运筹与管理》期刊2014年04期）
李哲,王志海,何颖婧,付彬[9]（2013）在《一种启发式多标记分类器选择与排序策略》一文中研究指出在多标记分类问题当中,多标记分类器的目的是为实例预测一个与其关联的标记集合。典型方法之一是将多标记分类问题转化为多个二类分类问题,这些二类分类器之间可以存在一定的关系。简单地考虑标记间依赖关系可以在一定程度上改善分类性能,但同时计算复杂度也是必须考虑的问题。该文提出了一种利用多标记间依赖关系的有序分类器集合算法,该算法通过启发式的搜索策略寻找分类器之间的某种次序,这种次序可以更好地反映标记间的依赖关系。在实验中,该文选取了来自不同领域的数据集和多个评价指标,实验结果表明该文所提出的算法比一般多标记分类算法具有更好的分类性能。(本文来源于《中文信息学报》期刊2013年04期）
刘华[10]（2012）在《基于BDD故障树分析的启发式变量排序研究》一文中研究指出故障树分析(Fault Tree Analysis, FTA)方法[2]是当今安全系统工程的主要分析方法之一,广泛应用于航天运载、武器装备、工业生产、交通控制、医疗器械等领域。在现有的FTA方法中,基于二元决策图(Binary Decision Diagram, BDD)分析方法是其中最有效的方法之一[44]。故障树BDD分析方法[4]包括BDD转换和BDD评价两个步骤,而这两者的计算复杂度都与BDD的规模呈线性相关[5]。因此,其关键的问题就在于如何快速的生成规模尽可能小的等价BDD。而BDD规模的大小取决于对故障树中布尔变量的排序,一个好的变量排序能够把一个大规模的布尔表达式转换成一个小规模的等价BDD。生成最小规模BDD的变量排序称为最优变量排序。已有的研究证明,获得布尔表达式最优变量排序是一个NP-Complete问题[5],在实际故障树分析过程中往往采用启发式变量排序方法寻找近似最优变量排序,以期降低BDD分析的复杂度。因此,设计高性能的启发式变量排序方法并进行性能分析是当前研究的热点,本文对此问题展开了细致深入的研究,具体的工作包括以下几个方面：1)故障树样本是启发式变量排序方法性能分析研究的基础。故障树样本不仅要具有规模与结构分布的可控性,又必须具备随机性,因此传统的人工建树和现行的计算机辅助建树方法都不能满足实验的要求。基于此,本文设计出自顶向下的随机故障树建树算法,通过设置门节点所占比例、或门所占比例、重复节点所占比例、门扇出节点的分布规律等参数,生成规模与结构可控、分布随机的故障树样本。2)深度优先最左(Deep-First-Left-Most, DFLM)排序是当前应用最广泛的启发式变量排序方法。由于已有研究工作对该方法的性能缺乏细致深入的分析,本文抓住启发式变量排序中故障树结构特征的核心要素“重复变量”,从无重复变量故障树(Fault Tree without Repeated variables, NRFT)和带重复变量故障树(Fault Tree with Repeated variables, RFT)两个不同的角度出发进行研究。对于NRFT,证明了DFLM排序是最优变量排序。对于RFT,根据重复事件的多寡与分布情况,故障树规模与结构(基本事件与门事件的比率),顶事件的逻辑类型等因素全面分析了DFLM排序性能与故障树结构特征的相关性。3)通过改进DFLM排序获得更高性能的排序策略是一个重要的研究方向。本文针对两种已有的改进策略：基于子树权重(Weighting-DFLM, WDFLM)策略和基于事件重复度权重(Repeated-event-priority-DFLM, RDFLM)策略,利用随机生成的故障树样本进行了性能比较研究,并总结其结构特征依赖的策略选择方法。在此基础上,提出了结合子树权重和重复度权重的新DFLM改进策略,实验数据表明该改进策略具有更优异的平均性能。4)在大规模故障树变量排序过程中进行模块化和变量化简是必要的。本文提出最简故障树的定义和基本性质,并对布尔代数运算律(分配律,结合律,幂等律等)进行扩展,总结出一套适用与故障树结构特征的冗余重复变量消减规则,将其结合模块化思想实现了故障树简化算法。针对所提出模块化排序策略,通过一个反例得出模块化策略并非是无条件最优排序策略,并给出生成最优排序的一个充分条件,即对于每一个模块Mi存在bddi*∈MinBDD(Mi),在bddi*中每一个模块变量都只出现一次。综上所述,本文围绕基于BDD故障树分析方法中的变量排序问题,针对DFLM这一基本变量排序策略展开研究,证明了DFLM策略在NRFT上的最优性；在随机生成故障树样本的基础上,通过大量实验比较分析了DFLM策略及其改进策略分析性能和故障树结构特征的依赖关系,并设计了更加高效的DFLM改进策略；在利用扩展简化规则和模块化获得最简故障树的基础上,提出了模块化排序策略并给出了生成最优排序的充分条件。(本文来源于《浙江师范大学》期刊2012-06-05）
启发式排序论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
软件测试用例生成技术和优先级排序技术是软件测试自动化的两个关键技术,元启发式搜索算法被广泛应用于解决测试用例自动生成与优先级排序问题。本文系统学习并总结了目前国内外已有的在相关技术方面的研究成果,发现元启发式搜索算法在测试用例生成技术和优先级排序技术中的应用尚未成熟,普遍存在算法收敛速度慢、考虑影响因素单一、难以收敛至全局最优等问题。为此,本文主要对元启发式搜索算法用于解决测试用例生成和优先级排序的问题进行了研究,分别提出了一种基于遗传优化算法的动态引导测试用例生成策略,以及一种基于蚁群优化算法的动态约简的多目标优先级排序方法。本文主要研究内容以及具体贡献主要为以下叁个方面:(1)在基于路径覆盖的测试用例生成技术方面,本文使用被应用较广泛的遗传算法进行求解。考虑到初始测试数据对路径节点的覆盖情况,先是区分出难易覆盖路径,然后设计了一种路径相似度的计算公式,分析出难易覆盖路径间的启发信息并用于替代遗传算法的部分初始种群。(2)在遗传算法的改进方面,增加考虑了分支权重对种群适应度的影响,分别根据不同程序的特征为各影响因子赋予权重,构造了一种带有权重影响因子的适应度评价函数,并以此设计自适应遗传概率,定向引导个体交叉变异,以快速得到满足路径覆盖的高质量测试数据。(3)在测试用例优先级排序技术方面,本文使用鲁棒性较强的蚁群算法求解这一问题,在排序过程中结合一种动态约简的思想,根据需求覆盖情况对测试用例进行初始约简,然后考虑到测试用例实际执行过程中是否能检测出的错误以及错误的等级,设计测试用例失效度的判别方法对迭代过程中的测试用例进行二次约简,通过两次约简大幅度减少蚁群迭代的时间消耗。在蚁群算法的信息素更新策略上,本文综合考虑了测试用例重要度、失效度以及有效执行时间叁个因素对信息素的影响,在线指导蚁群信息素的更新,提升蚁群算法的求解精度和收敛速度。为了验证本课题在测试用例生成与优先级排序这两个方面提出的改进方法的有效性,选取多个基准和工业程序进行编程实验,将本文提出的基于元启发式搜索算法的测试用例生成和多目标优先级排序方法分别与其他方法进行对比,仿真实验结果表明,本选题研究的基于遗传算法的测试用例生成方法在收敛速度、路径覆盖率、已有测试数据的利用率上有明显优势,提出的基于蚁群优化算法的多目标优先级排序方法在语句覆盖率、缺陷检测效率和有效执行时间等方面均优于其他方法。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
启发式排序论文参考文献
[1].时凌,张琼,时义梅,魏代俊.带单服务器的自由作业排序问题的启发式算法[J].数学的实践与认识.2019
[2].徐海霞.基于元启发式算法的测试用例生成与排序研究[D].浙江理工大学.2018
[3].付玉书,莫毓昌,潘竹生.网络可靠性BDD分析中选择最优启发式边排序策略[J].信息通信.2015
[4].彭关伟,乔立红,胡权威.基于约束矩阵的启发式工序排序方法[J].计算机集成制造系统.2016
[5].王海燕,管莹,李闯,杨明明.两种智能值排序启发式研究[J].吉林大学学报(信息科学版).2015
[6].朴惠淑,贾春玉,常留贤.基于最优解下限的单工序平行机排序启发式算法[J].工业工程与管理.2015
[7].潘竹生,莫毓昌,钟发荣,刘轩,伍欢.一种新的启发式边排序策略及其性能分析[J].计算机工程与科学.2014
[8].井彩霞,张磊,刘烨.需要安装时间的平行多功能机排序问题的启发式算法[J].运筹与管理.2014
[9].李哲,王志海,何颖婧,付彬.一种启发式多标记分类器选择与排序策略[J].中文信息学报.2013
[10].刘华.基于BDD故障树分析的启发式变量排序研究[D].浙江师范大学.2012