k-median问题反向贪心随机算法

k-median问题的近似算法研究一直是计算机科学工作者关注的焦点。基于均衡限制条件,利用反向贪心策略,给出求解该问题的随机近似算法。证明该算法以较大的概率满足其近似性能比的期望值为(3+O(ln(ln(k)/α))。该算法的时间复杂度为O([kαln(k)]2(n+m)),其中n和m分别代表设施集合以及客户点集的大小。最后,通过计算机实验验证了k-median问题的反向贪心算法的实际计算效果。     

求解矩形packing问题的贪心算法

在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试,所得结果的平均面积未利用率为0.28%,平均计算时间为17.86s,并且还得到了其中8个实例的最优解。测试结果表明,该算法对求解矩形packing问题相当有效。     

求解广义背包问题的贪心DS_BPSO算法

首先针对演化算法求解背包问题定义了贪心变换的概念,并给出了该变换的一种有效实现算法;然后将此算法与文献[5]中提出的具有双重结构编码的二进制粒子群优化算法(DS_BPSO)相结合,提出了一种解决广义背包问题GKP(General Knapsack Problem)的快速算法:基于贪心变换的DS_BPSO算法(GDS_BPSO).利用该算法求解文献[3,6]中的著名背包实例,给出了该背包实例的目前最好结果.此外,对于随机生成的大规模背包实例,通过与文献[3]中的HGA算法对比计算表明:GDS_BPSO算法是求解广义背包问题的一种高效方法.     

贪心二进制狮群优化算法求解多维背包问题

针对经典的多约束组合优化问题——多维背包问题(MKP),提出了一种贪心二进制狮群优化(GBLSO)算法。首先,采用二进制代码转换公式将狮群个体位置离散化,得到二进制的狮群算法;其次,引入反置移动算子对狮王位置进行更新,同时对母狮和幼狮位置重新定义;然后,充分利用贪心算法进行解的可行化处理,增强搜索能力并进一步提高收敛速度;最后,对10个MKP典型算例进行仿真实验,并把GBLSO算法与离散二进制粒子群(DPSO)算法和二进制蝙蝠算法(BBA)进行对比。实验结果表明,GBLSO算法是一种有效的求解MKP的新方法,在求解MKP时具有相对良好的收敛效率、较高的寻优精度和很好的鲁棒性。     

求解背包问题的更贪心粒子群算法

将粒子群算法与贪心思想相融合,提出一种用于求解0/1背包问题的更贪心混合粒子群算法。对超过背包重量约束的粒子的处理措施是去掉已经装进去且性价比最差的物品,直至满足重量约束为止,这种思想在改善粒子质量的同时避免了通常罚函数方法中敏感的参数选择问题;对当前可行粒子的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止。通过与文献中基于经典算例的计算结果比较表明,更贪心粒子群算法无论在寻优能力、计算速度和稳定性方面都超过了文献中提到的混合遗传算法（HGA）、贪心遗传算法（GGA）和混合粒子群算法（GBPSOA）。     

求解多维背包问题的贪心粒子群算法

将多维背包问题的贪心变换和两种求解算法,用于求解具有重量和体积两个约束的背包问题,分别将物品按价值/重量、价值/体积比的凸组合和无穷范数的定义获得两组混合"性价比"权值向量,再以该混合"性价比"权值为依据构造两种贪心粒子群算法(wPSO,infPSO)。数值试验表明,算法wPSO、infPSO不仅大大优于现有粒子群算法,而且表现出优秀、稳定的搜索能力和快速定位最优解的搜索能力。     

求解背包问题的贪心遗传算法及其应用

分析了文献[2]中求解背包问题(KP)的混合遗传算法(HGA)所采用的贪心变换方法缺陷;重新定义了贪心变换的概念,并给出了一种新的且更高效的贪心变换方法,将此方法与遗传算法相结合得到一种新的混合遗传算法,称之贪心遗传算法(简记GGA).利用GGA得出了文献[2,4]中一个著名KP问题实例的目前最好结果;同时,对于文献[7]中的KP问题实例和一个随机生成的KP问题实例,将GGA算法与求解KP问题的最有效算法HGA算法进行对比计算,结果表明GGA算法远远优于HGA算法.     

求解TSP问题的贪心遗传算法

提出贪心遗传算法。通过构建“基因库”形成好的“基因片断”,从而生成高性能的初始种群;依据贪心选择的原则指导遗传操作,实施贪心交叉操作和贪心变异操作;移民操作向种群引进新的遗传物质,克服了封闭竞争缺点,并且可以避免早熟收敛。贪心遗传算法可以大大加快搜索的速度,仿真结果表明算法是十分有效和实用的。     

带权重的贪心萤火虫算法求解0-1背包问题

根据萤火虫算法的自身特点，将自适应权重、改进贪心算法、变异算子与基本萤火虫算法相结合，提出一种带权重的贪心萤火虫算法。通过加入自适应权重与变异算子，可以提高算法全局搜索能力，加入贪心算法在一定程度上可提高算法收敛速度，整体看，改进萤火虫算法提高了算法性能。通过仿真实验将改进后的算法与一些基本算法进行比较，实验结果表明，该算法在求解0-1背包问题时，无论在运算速度还是求解精度上都有明显改进。     

用贪心算法解决多机调度问题

给定n个独立的作业和m个相同的机器,给出了一个找到比较理想的分配方法使得n个独立的作业在m个相同机器上完成的时间最短.     

K-median问题贪心近似算法的分析与实验

讨论K-median问题的贪心近似算法及其在实际计算中的表现。提出一个解K-median问题的贪心算法,证明该算法的近似度为O(ln(n/k)),通过实验证明该贪心算法在实际应用当中可以取得较好的效果,大约有90%的客户能被距离其最近、次近和第三近的设备服务。     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

贪婪算法与压缩感知理论

贪婪算法以其重建速度快、重建方法实现简便的特点在压缩感知(Compressed sensing, CS)理论中获得了广泛的应用. 本文首先介绍压缩感知的基本理论;然后,着重介绍现有几种重要的贪 婪重建算法,包括MP, OMP, IBOOMP, StOMP, SP, ROMP和CoSaMP等, 详细给出每种算法的数学框架和本质思想,着重从最优匹配原子的选择策略和残差信号的更新 方式这两个方面对各种算法进行对比分析,以限制等容常数为条件讨论各种算法在实现重建时的性能,包括重建时间、 重建的稳定性等;最后,通过模拟实验进一步验证了 各种算法的重建效果,同时模拟实验结果还进一步得出各种算法的重建效果与待重建信号 本身的稀疏度及测量次数这三者之间的关系,这也为新的更优算法的提出打下理论基础.     

核矩阵逼近的贪心算法

在综合考虑数据之间的相关性与残差范数最小的基础上,本文分别提出向前贪心算法、向后贪心算法和混合贪心算法寻踪最佳低秩逼近.为此提出一种稀疏回归算法(SRA).SRA能有效减少"训练样本",并具备良好的推广能力.将SRA应用于2个实际的模式识别问题,并与支持向量机(SVM)、核主元回归(KPCR)和关键算法(KA)进行比较,验证SRA的有效性.     

Regularized Greedy Algorithms for Network Training with Data Noise

The aim of this paper is to construct a modified greedy algorithm applicable for an ill-posed function approximation problem in presence of data noise. We provide a detailed convergence analysis of the algorithm in presence of noise, and discuss the choice of the iteration parameters. This yields a stopping rule for which the corresponding algorithm is a regularization method with convergence rates in L₂ and under weak additional assumptions also in Sobolev-spaces of positive order.Finally, we discuss the application of the modified greedy algorithm to sigmoidal neural networks and radial basis functions, and supplement the theoretical results by numerical experiments.     

贪心算法优化云数据中心的虚拟机分配策略

如何将云客户端的大量虚拟机均匀的分配到云数据中心的物理主机上执行是一个关键问题.提出了贪心算法优化云数据中心的虚拟机分配策略,首先设计一个用于企业的云数据中心的工作场景,该场景包括三层云计算系统结构,包括用户层、云服务提供者层和云数据中心集合层.用户层用来生成虚拟机的请求集;云服务提供者层通过经典的装箱问题算法完成用户...     

Greedy Algorithms for the Shortest Common Superstring That Are Asymptotically Optimal

There has recently been a resurgence of interest in the shortest common superstring problem due to its important applications in molecular biology (e.g., recombination of DNA) and data compression. The problem is NP-hard, but it has been known for some time that greedy algorithms work well for this problem. More precisely, it was proved in a recent sequence of papers that in the worst case a greedy algorithm produces a superstring that is at most β times (2≤β≤ 4 ) worse than optimal. We analyze the problem in a probabilistic framework, and consider the optimal total overlap O _n ^opt and the overlap O _n ^rg produced by various greedy algorithms. These turn out to be asymptotically equivalent. We show that with high probability , where n is the number of original strings and H is the entropy of the underlying alphabet. Our results hold under a condition that the lengths of all strings are not too short. Received November 1996; revised March 1997.     

压缩感知中贪婪重构算法研究

压缩感知理论是利用信号的稀疏性,通过少量的观测值就可以实现对该信号的精确重构。贪婪类算法是压缩感知重构步骤中广泛应用的一类算法。该文主要对该类算法中典型的三种算法在存在噪声环境中进行了综合分析比较。首先从理论方面分析了三种算法,给出了实现过程;然后在不同稀疏度情况下,对三种贪婪算法重构性能进行综合比较。根据理论分析结果和仿真结果,得出相应的结论。