共查询到19条相似文献,搜索用时 187 毫秒
1.
2.
启发式算法是求解组合优化问题求解的重要手段,其主要特征是能够以可接受的计算代价找到足够好的可行解.然而,设计良好的用于求解组合优化问题的启发式算法需要大量的专业领域知识以及大量的试错工作,且人工设计的启发式算法不能够保证在不同问题集上均具有一致性表现.另一方面,深度学习方法能够通过学习自动设计启发式规则,然而深度学习方法通常缺少在解空间内搜索的能力.为克服以上问题,提出了一种基于蚁群优化和深度强化学习的混合启发式算法框架.在该框架中,蚁群算法能够利用深度强化学习提取的启发式信息,而深度强化学习方法的解空间搜索性能也由于蚁群算法的加入而获得提高.采用经典的TSPLIB中的算例对该算法求解旅行商问题的效能进行了计算验证,结果表明采用深度学习方法能够极大地提升蚁群算法的计算表现,并降低其计算代价. 相似文献
3.
浮动车数据主要是由车辆的轨迹点数据组成,是一种重要的原始数据,可以广泛地用于各种交通应用,如交通管理和控制、路况计算等.但是原始的车辆GPS数据存在定位误差,必须经过路径推测的修正处理才可以应用.传统的路径推测算法主要采用两种方法:渐增式和全局式.两种方法各有优缺点,渐增式方法计算速度快但准确性差,全局式方法准确性好但计算速度慢.通过综合考虑两种传统算法,文中提出了一种基于向量识别的启发式路径推测算法,该算法采用了启发式图搜索方式,导入几何运算的约束条件,根据车辆轨迹点所形成的向量与路网模型比较来进行启发式搜索,并选择车辆所有可能行驶的候选路径.根据全局择优的方式从整体进行比较,确定车辆最有可能的行驶路径.实验结果表明,这种算法能够在复杂路网下,比较准确地推测距离间隔较大的车辆轨迹点,并且能够实时高效地处理大规模数据. 相似文献
4.
课程表问题是经典的组合优化问题,属于NP-hard问题.长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法.在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法.在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法.与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排.旅行商问题、背包问题等应用领域.实验表明,该算法是可行有效的,且无一例时间、空间冲突. 相似文献
5.
服务器集群中的负载均衡和作业调度是影响系统性能的重要因素.本文描述服务器集群批量任务的作业调度问题,对该问题建立了基于图的模型.由于使用一般的启发式算法或动态规划算法解决该问题具有局限性,本文引入蚁群算法进行求解,并针对该问题具体求解提出了启发式距离合适的计算方法.最后在仿真的基础上,讨论了算法的优化效果和收敛性,结果表明蚁群算法解决该问题具有优异的性能. 相似文献
6.
7.
目前提高求解SAT问题完全算法的计算效率问题已成为挑战性研究问题。提出了一种基于启发式分组的SAT完备算法。启发式分组策略将一个全局搜索问题,转为局部搜索问题。并将该策略引入到结合BDD与SAT算法的形式验证中,与一般的启发式SAT算法相比,该算法在求解速度和求解问题的规模等方面都明显地改进了,实验结果表明了该算法的可行性和有效性。 相似文献
8.
最小化总完工时间无等待流水调度是典型的NP-完全问题,广泛存在于实际生产系统.改变传统求解调度序列目标函数的模式,提出目标增量法,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间;通过证明启发式算法基本操作的目标增量性质,设计两种基本目标增量法以快速评估新产生解的质量.提出快速迭代贪婪算法FIG(Fast Iterative Greedy algorithm)求解该问题,构造初始解生成算法,提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量.基于110个经典Benchmark实例,将提出的FIG算法与目前求解该问题较好的启发式算法PHlp和元启发式算法SRTS、DPSOvnd进行比较,实验结果表明FIG在性能上优于SRTS和PHlp,略逊于DPSOvnd;在效率上优于SRTS和DPSOvnd,略逊于PHlp. 相似文献
9.
本文提出一种求解最大独立集问题(MIS)的启发式神经网络算法.该算法基于MIS问题的特点,有效地限制神经网络初始点的选择范围,并利用神经网络快速收敛能力获得问题的解.与标准神经网络算法相比,该算法显示了较高的全局优化性态与计算效率.模拟计算实例表明了该算法的有效性. 相似文献
10.
11.
12.
一种新的启发式Web服务组合算法 总被引:1,自引:0,他引:1
作为推动SoA和Web服务向纵深化发展的重要支撑技术,Web服务组合一直在领域研究中占据着重要地位。提出了一种新的启发式Web服务组合算法—HASC算法,该算法分为遍历搜索和回溯组合两个过程。前者以Web服务输出集合基数为启发函数,确定到达每个目标本体所需调用的Web服务;在此基础上,后者采用输出集合与目标集合交集的基数为启发函数,逐步建立输出集合到输入集合的回溯路径,进而获取最优组合方案。最后,以公共测试集EEE05和ICEBE05为测试对象,对该算法的性能进行深入分析。实验结果表明,该算法在组合效率和寻求最短组合路径方面较同类算法有较大提升。 相似文献
13.
针对当前方法进行大型建筑表层墙体裂痕监测时,普遍存在着监测响应时间过长,准确率较低,能源消耗较大等问题。提出基于人工智能视觉的墙体裂痕监测方法。利用k-means算法将含有裂痕的表层墙体进行分类,引入概率松弛算法求出含有裂痕表层墙体像素点之间的空间结构特点,对含有裂痕信息的墙体进行特征提取,采用MeanShift序列算法,对墙体裂痕目标进行判别,引入核函数采集墙体裂痕图像集合间差异,以此完成监测。实验结果表明,所提出方法在进行大型建筑表层墙体裂痕监测时,监测响应时间较短、准确率较高、能源消耗较小。 相似文献
14.
Jingli Wu Jianxin Wang Jian’er Chen 《Engineering Applications of Artificial Intelligence》2009,22(3):401-406
The minimum error correction (MEC) model is one of the important computational models for single individual single nucleotide polymorphism (SNP) haplotyping. Due to the NP-hardness of the model, Qian et al. presented a particle swarm optimization (PSO) algorithm to solve it, and the particle code length is equal to the number of SNP fragments. However, there are hundreds and thousands of SNP fragments in practical applications. The PSO algorithm based on this kind of long particle code cannot obtain high reconstruction rate efficiently. In this paper, a practical heuristic algorithm PGA-MEC based on parthenogenetic algorithm (PGA) is presented to solve the model. A kind of short chromosome code and an effective recombination operator are designed for the algorithm. The reconstruction rate of PGA-MEC algorithm is higher than that of PSO algorithm and the running time of PGA-MEC algorithm is shorter than that of PSO algorithm, which are proved by a number of experiments. 相似文献
15.
16.
17.
Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance
Ju-Yong LeeYeong-Dae Kim 《Computers & Operations Research》2012,39(9):2196-2205
This research focuses on the problem of scheduling jobs on a single machine that requires periodic maintenance with the objective of minimizing the number of tardy jobs. We present a two-phase heuristic algorithm in which an initial solution is obtained first with a method modified from Moore's algorithm for the problem without maintenance and then the solution is improved in the second phase. Performance of the proposed heuristic algorithm is evaluated through computational experiments on randomly generated problem instances and results show that the heuristic gives solutions close to those obtained from a commercial integer programming solver in much shorter time and works better than an existing heuristic algorithm in terms of the solution quality. 相似文献
18.
提出了一种基于可信基点的结构化签名比较算法,对现有的结构化签名比较算法在基点初始化和传播过程中的不足进行了改进,并证明了改进的算法更可信.同时,通过增加循环属性、相同参数信息等方法作为新的划分属性来更细致地刻画函数信息,提高了可信基点在初始化和传播过程中的正确性和匹配率.还提出了一种启发式策略对比较结果是否存在错误匹配进行校验. 相似文献
19.
Mustafa Mısır Katja Verbeeck Patrick De Causmaecker Greet Vanden Berghe 《Journal of Scheduling》2013,16(3):291-311
This study provides a new hyper-heuristic design using a learning-based heuristic selection mechanism together with an adaptive move acceptance criterion. The selection process was supported by an online heuristic subset selection strategy. In addition, a pairwise heuristic hybridization method was designed. The motivation behind building an intelligent selection hyper-heuristic using these adaptive hyper-heuristic sub-mechanisms is to facilitate generality. Therefore, the designed hyper-heuristic was tested on a number of problem domains defined in a high-level framework, i.e., HyFlex. The framework provides a set of problems with a number of instances as well as a group of low-level heuristics. Thus, it can be considered a good environment to measure the generality level of selection hyper-heuristics. The computational results demonstrated the generic performance of the proposed strategy in comparison with other tested hyper-heuristics composed of the sub-mechanisms from the literature. Moreover, the performance and behavior analysis conducted for the hyper-heuristic clearly showed its adaptive characteristics under different search conditions. The principles comprising the here presented algorithm were at the heart of the algorithm that won the first international cross-domain heuristic search competition. 相似文献