一种改进的贪婪式覆盖算法

文中对覆盖算法进行了介绍和分析,提出了一种基于贪婪算法思想的改进的覆盖算法,称之为贪婪覆盖算法。通过对覆盖初始中心选择方式的改进,减少覆盖数量。通过实验,对比目前已有的几种实现方法,覆盖数量有了较大的下降,明显提高了分类识别的速度。     

一种改进的贪婪式覆盖算法

文中对覆盖算法进行了介绍和分析，提出了一种基于贪婪算法思想的改进的覆盖算法，称之为贪婪覆盖算法。通过对覆盖初始中心选择方式的改进，减少覆盖数量。通过实验，对比目前已有的几种实现方法，覆盖数量有了较大的下降，明显提高了分类识别的速度。     

基于特征选择和SVMs的图像分类

重点论述了基于MI图像特征选择方法[1],简要地讲述了支持向量机的SVMs分类器原理和设计[2]。提出了MI贪婪最优算法,将高维数据处理转化为一维数据处理,简化了运算难度,同时提高了分类速度和准确性。实验结果表明,通过对8个分类、上千张图片进行分类处理,效果好于传统的分类算法。     

基于Rollout算法的测试不可靠条件下的诊断策略*

实际复杂装备系统测试时存在虚警和漏检,其导致的误诊费用往往超过了测试成本。针对复杂系统故障诊断中诊断精度低、虚警率高的问题,进行了不可靠测试条件下,基于Rollout算法的诊断策略优化方法研究。首先建立综合考虑测试点的故障检测能力、信息量、测试费用以及测试结果信任度的启发函数,然后利用Rollout算法生成诊断策略,最后用阿波罗检测系统实例验证了该算法的优越性。理论和实验表明,Rollout算法的平均测试费用低于贪婪算法,而且计算时间在可接受范围内,因此可用于测试不可靠条件下的诊断策略设计。     

应用于癌症基因表达数据的OMB双向聚类算法

癌症基因表达数据的聚类分析可以为癌症的早期诊断和精确的癌症亚型分型提供依据。针对癌症基因表达数据的特点,提出一种称为OMB（Override Matrix Bicluster）的双向聚类算法。OMB算法分别在基因表达数据矩阵的行和列上搜索低于阈值的行和列,用删除添加算法产生一个子矩阵;构建与基因表达矩阵大小相同的覆盖矩阵,标识矩阵中上一次迭代产生的子矩阵的位置;在标识出来的矩阵中,重复贪婪迭代搜索找到K个聚类结果。Matlab实验结果表明OMB算法对具有重叠结构的癌症基因表达数据具有更好的聚类效果。     

求解舰船电力系统网络重构的贪婪DPSO 算法

针对舰船电力系统的网络重构,建立了故障恢复的离散模型.提出基于简单贪婪法、概率贪婪法两种离散微粒群优化算法,分析了参数对离散化过程的影响.舰船电力系统网络故障恢复算例显示:该方法能获得更好的故障恢复方案;参数选取合适的概率贪婪法能有效地克服微粒群算法易于陷入局部极值的缺点,具有优良的收敛性能.     

一种属性约简的探测性贪婪算法

贪婪算法一旦做出贪婪选择就不能反悔,因此设计简单、执行速度快,但其搜索空间过于狭小,从而降低了贪婪解的精度.针对该问题,提出一种属性约简的探索性贪婪算法,采用前景探测策略提高贪婪解的精度.实验结果表明,该算法在时间略有增加的情况下能提高解的精度.     

基于改进迭代贪婪算法的预制构件调度研究

迭代贪婪算法是一种具有较强局部搜索能力的元启发式算法,但由于传统迭代贪婪算法搜索范围过大,搜索效率有限,为了进一步提升传统迭代贪婪算法的搜索能力,考虑到阈值接受算法具有能缩小搜索范围的特点,提出了一种改进的迭代贪婪算法解决流水车间预制生产的订单接受与调度问题。该改进算法是在破坏原调度序列后加入一种基于构造启发式规则的重建策略,并结合阈值接受算法的自适应接受准则用以跳出局部最优。经大量仿真实验结果显示,与传统迭代贪婪算法、禁忌搜索算法以及遗传算法对比,改进的迭代贪婪算法具有更好的求解质量和鲁棒性。     

就背包和部件加工问题浅论贪婪算法的运用及优化方案

贪婪算法作为一种求最优解问题的方法,具有简便、迅捷的特点,然而贪婪算法因其基于局部求最优解的特点,决定了其在很大程度上无法得到问题的最优解。本文通过对[0-1背包问题]以及部件加工问题的分析,阐述了贪婪算法的应用以及贪婪算法存在的局限性,进而引出贪婪算法的优化方案——k阶优化方法,进一步对求最优解问题进行完善和归纳。     

基于Householder变换的贪婪正交最小二乘辨识算法

针对含有未知时滞的多输入受控自回归系统模型的时滞与参数辨识问题,基于Householder变换探讨一种贪婪正交最小二乘辨识算法.首先,由于各输入通道的时滞未知,通过设置输入数据回归长度对系统模型进行过参数化,得到一个含有稀疏参数向量的高维辨识模型;其次,为了避免最小二乘算法中对高维协方差矩阵的求逆运算,利用Householder变换对信息矩阵进行正交分解,推导基于Householder变换的正交最小二乘算法;然后,为了提高辨识效率,降低辨识成本,推导基于Householder变换的贪婪准则,进而得到基于Householder变换的贪婪正交最小二乘辨识算法,该算法能够在少量采样数据的条件下获得稀疏参数向量的估计值;最后,根据估计的稀疏参数向量的结构得到系统时滞估计.仿真结果表明了所提出算法的有效性.     

一种新的贪婪回溯子空间追踪算法研究

针对目前的贪婪类算法在实际应用中出现的重构遮挡和虚假等问题,本文在分析该问题产生的原因基础上,提出了一种新的贪婪回溯子空间追踪(greedy backtracking subspace pursuit, GBSP)算法。该算法基本思想是在每次的迭代过程中,采用回溯反馈和贪婪精选的思路进行支撑集选择。具体而言,在原子识别阶段,从残差投影中挑选出绝对值最大的 ( 是信号稀疏度)个投影值位置,添加到候选支撑集中,为降低在此步骤中产生的错误概率,每次只将候选支撑集中的前s（ ）个最大值对应的位置添加到真实支撑集中进行更新;此后再进行投影计算和残差更新,直到完成支撑集的选择。由于新算法结合了正交匹配追踪算法和子空间追踪算法二者的优势,因此可较好的解决重构遮挡与虚假问题,使得压缩感知重构算法更具实用性。     

电路原理图中两边网格通道布线的类贪婪算法

贪婪算法是VLSI设计中通道布线的常用算法，在电路原理图的自动布图中，也会遇到通道布线的问题。但传统的贪婪算法着重于使通道面积最小化，不能满足原理图中对布线结果有序化的要求。提出类贪婪算法，在原贪婪算法的基础上，通过修改处理规则，使得布线结果更加整齐有序，便于阅读，同时也保留了原算法简洁的优点。     

基于微博网络的影响力最大化算法

由于影响范围的重叠效应,单纯的影响力度量算法并不能解决微博网络中的影响力最大化问题,针对这一研究现状,提出一种用于微博网络中Top-K节点挖掘的算法GABE。通过归纳决定微博用户影响力的关键因素,提出了节点间影响率的概念,进而建立了用于用户影响力度量的WIR算法;根据得到的WIR值提出了符合微博特性的影响力传播模型,运用贪婪算法挖掘出微博网络中的Top-K节点。以爬取到的新浪微博数据进行了模拟验证,结果发现GABE在影响范围上与传统的最大化算法和影响力度量算法相比分别提高了7.7%和20%。这表明通过引入微博特性和贪婪思想,GABE较好地解决了微博网络中的影响力最大化问题。     

A hybrid algorithmic model for the minimum weight dominating set problem

Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches.     

一种改进的小矩阵连乘算法

首先引入了矩阵的连乘优先因子,接着采用连乘优先因子最小的贪心选择策略,提出了最小连乘因子优先算法。它确定125的连乘次序不一定是最优次序,但在确定连乘次序方面比动态规划法花费的时间和空间少。最后通过实例对比测试,表明该算法在计算小矩阵连乘时,总体效率优于动态规划法。     

An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem

This paper proposes a Tabu-mechanism improved iterated greedy (TMIIG) algorithm to solve the no-wait flowshop scheduling problem with a makespan criterion. The idea of seeking further improvement in the iterated greedy (IG) algorithm framework is based on the observation that the construction phase of the original IG algorithm may not achieve good performance in escaping from local minima when incorporating the insertion neighborhood search. To overcome this limitation, we have modified the IG algorithm by utilizing a Tabu-based reconstruction strategy to enhance its exploration ability. A powerful neighborhood search method that involves insert, swap, and double-insert moves is then applied to obtain better solutions from the reconstructed solution in the previous step. Empirical results on several benchmark problem instances and those generated randomly confirm the advantages of utilizing the new reconstruction scheme. In addition, our results also show that the proposed TMIIG algorithm is relatively more effective in minimizing the makespan than other existing well-performing heuristic algorithms.     

基于Hessian矩阵的线形结构搜索路面裂缝提取方法

针对目前三维路面裂缝提取方法效果不佳的问题,提出一种基于Hessian矩阵的线形结构搜索路面裂缝提取方法。首先针对路面深度图像对比度弱、多干扰等问题,根据裂缝的几何特性和灰度特征,给出基于分段函数的路面深度图像预处理方法;然后针对基于Hessian矩阵的多尺度路面裂缝粗提取方法,存在的裂缝提取不连续和对噪声敏感的问题,根据裂缝局部方向的一致性和噪声的离散性特点,给出基于线形结构约束的路面裂缝精提取方法。实验结果对比表明,本文方法适应于不同尺度和程度的路面裂缝提取,较文献［5］的方法完整度提高了10%以上,正确率提高了2%以上,而耗时几乎相同;较文献［15］的方法完整度提高了6%以上,正确率提高了1%以上,但耗时约为该方法的1/3。     

覆盖表生成的可配置贪心算法优化

覆盖表生成是组合测试研究的关键问题之一,其中,贪心算法因为速度快、生成的覆盖表规模小而得到人们的青睐.人们提出了很多基于不同策略的贪心算法,其中,多数算法可以归结到一个统一的算法框架,即形成一个可配置贪心算法,从该框架又可以衍生出很多新的算法.如何科学地配置优化受多个因素影响的算法框架、有效生成覆盖表是一个新的挑战.针对具有6个决策点的贪心算法框架,设计了3条不同的实验路线,系统地探索各个决策点以及它们之间相互作用对生成覆盖表规模的不同影响,寻找最佳配置,从而可以有效地生成规模更小的覆盖表,为覆盖表生成的贪心算法的设计和优化提供理论和实践基础.     

低约束密度分布式约束优化问题的求解算法

多Agent协作过程中的许多挑战都可以建模为分布式约束优化问题.针对低约束密度的分布式约束优化问题,提出了一种基于贪婪和回跳思想的求解算法.在该算法中,各Agent基于贪婪原则进行决策,能够利用低约束密度问题中大量赋值组合代价为0这一特点来加快求解速度.同时,Agent间的回跳机制可以在贪婪原则陷入局部最优时保证算法的完全性.相对于已有主流算法,该算法可以在保持多项式级别的消息长度/空间复杂度的前提下,以较少的消息数目求解低约束密度的分布式约束优化问题.给出了算法关键机制的正确性证明,并通过实验验证了算法的上述性能优势.     

一种基于近邻策略求TSP问题的改进演化算法

针对贪心演化算法(GEA)在旅行商问题中存在的求解规模小、成功率低的缺点,引入Inver-over倒异算子、贪心算子,改进近邻优化、映射算子、变异算子等策略,提出一种新的改进演化算法来求解中等规模旅行商问题(TSP)。通过仿真实验,验证了该进化算法收敛速度快、求解成功率高的优点,稳定性也更好。