电子中介中的交易匹配研究

研究电子中介中的匹配问题,提出了电子中介处理多属性商品交易时双方的满意度函数.以最大化双方满意度为目标,建立了多个买家和多个卖家各交易一件同类商品的多目标匹配优化模型,提出一种求解单目标的优先贪婪算法.3种算法的仿真实验表明,优先贪婪算法比精确算法损失匹配数量约8.0%,节约时间约31.6%;比标准贪婪算法提高匹配数量约2.7%,节约时间约36.3%.     

采用加权优化的图像修复

针对目前贪婪修复算法可能存在修复效果视觉不一致以及优化修复算法中存在的算法复杂度较高或者未考虑结构信息的情况,提出一种基于加权优化的图像修复算法,通过定义出新的能量函数,把图像破损修复问题转化为加权的离散优化问题,在保证结构信息强、信任度高的区域被优先修复的前提下,利用贪婪修复思想获取初值并计算权值,然后通过类EM算法迭代求解出破损区域中每一个像素的最佳值。与其他贪婪合成和最优化方法相比,优先考虑结构信息对修复效果的影响,更好地保持了纹理和结构的整体一致性。     

基于种子候选的贪心策略影响力最大化算法

爬山贪心算法的时间复杂度较高,不易扩展至大规模社会网络.为了解决此问题,文中从理论上分析节点集影响力评估可转化为局部概率解计算,能够提高算法运行效率.将局部概率解函数拓展到贪心算法中,提出基于种子候选的贪心影响力最大化算法和基于种子候选的偷懒贪心影响力最大化算法.在4个真实数据集上实验表明,文中算法与具有成本效益的惰性前向选择算法(CELF)性能一致,但在运行时间上快于CELF.     

一种改进的Split-Merge图像分割算法

图像分割的经典算法Split-Merge算法思路简洁、运算效率高,但存在边界定位不准确和过分割等问题。针对过分割问题提出了一种改进的Split-Merge算法,在合并过程中引入全局目标函数,并在目标函数中定义了长度项,使用贪心法完成合并过程。长度项以及贪心法的使用促使相邻区域充分合并,有效地克服了过分割等问题,取得了较好的分割效果。     

基于改进快速活动轮廓模型的左心室核磁共振图像分割

提出了改进的基于贪婪优化算法的快速活动轮廓模型，原算法加快了求解最优能量曲线的速度，但初始轮廓线必须给定在图像特征的附近。通过在优化的目标函数中增加面积能量项，扩大了算法捕获图像特征的范围，在对贪婪优化算法分析的基础上，给出了局部面积能量项的构造和使用方法，进而简化了优化的目标函数．实验结果表明，该算法具有快速、能在更大的范围内捕获图像的特征、较好地处理图像中凹陷区域的能力，是一种有效的分割左心室MRI图像的算法。     

二进制混合蛙跳算法求解0-1背包问题

为利用混合蛙跳算法（SFLA）求解具有二进制编码特点的组合优化问题,基于双重编码机制,提出了一种二进制混合蛙跳算法（记为BSFLA）。基于罚函数法和贪心变换策略,探讨了利用BSFLA求解背包问题（KP）的可行性与有效性。计算结果表明BSFLA与贪心策略相结合是求解KP问题的一种有效的新方法。     

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

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

Hadoop平台中一种Reduce负载均衡贪心算法

MapReduce是目前广泛应用的并行计算框架,是Hadoop平台的重要组成部分。主要包括Map函数和Reduce函数。Map函数输出key-value键值对作为Reduce的输入,由于输入的动态性,不同主机上的Reduce处理的输入量存在不均衡性。如何解决Reduce的负载均衡是优化MapReduce的一个重要研究方向。本文首先对整体数据进行抽样,通过适量的样本分析数据,达到较小的代价获得可靠的key分布;然后,提出贪心算法代替Hadoop平台默认的hash算法来划分数据,实现Reduce负载均衡。本文所提贪心算法主要思想是根据抽样数据,求取所有key频次的和对于Reduce节点数量的平均值,然后依次为每一个Reduce分配一个接近平均值的负载,从而达到整体的负载均衡。模拟实验表明,本文所提算法与默认的hash分区算法相比,运行时间节约10.6%,达到更好的负载均衡。     

社交网络中正影响支配集问题的轮转贪心算法

社交网络中最小正影响支配集问题是一个NP难度的组合优化问题,针对该问题,目前有2种典型的贪心求解算法求解速度较快,但贪心解的质量却有待提高。轮转贪心策略是在不增加贪心算法时间复杂度的前提下提升贪心解的质量,且通过实验研究表明能有效增强一些NP难度问题效果的贪心算法。本文将轮转贪心策略求解正影响支配集的2个贪心算法进行融合来提升贪心算法解的质量,提出相应的轮转贪心算法。实验表明,在典型的真实社交网络实例上,与原有贪心算法相比,本文的轮转贪心算法所获解的质量有一定的提高。     

Kernel matching pursuit for large datasets

Kernel matching pursuit is a greedy algorithm for building an approximation of a discriminant function as a linear combination of some basis functions selected from a kernel-induced dictionary. Here we propose a modification of the kernel matching pursuit algorithm that aims at making the method practical for large datasets. Starting from an approximating algorithm, the weak greedy algorithm, we introduce a stochastic method for reducing the search space at each iteration. Then we study the implications of using an approximate algorithm and we show how one can control the trade-off between the accuracy and the need for resources. Finally, we present some experiments performed on a large dataset that support our approach and illustrate its applicability.     

传感器网络节点选择的分布式在线算法

大型传感器网络部署的关键是在能量消耗最小的前提下激活传感器节点以获取有价值信息,这要求在效用函数事先不可知的情况下通过分布式方式选择正确的传感器节点。为此,提出一种分布式在线贪心算法。以效用函数满足子模性的自然报酬递减特性为前提,在模型未知的情况下,通过在线学习方式优化目标函数。实验结果表明,该算法的收敛性近似于传统的集中式方法,且在运行中所需的通信消息量较少,适用于大型网络传感器节点的部署。     

一类控制受约束非线性系统的基于单网络贪婪迭代DHP算法的近似最优镇定

提出一种贪婪迭代DHP (Dual heuristic programming)算法, 解决了一类控制受约束非线性系统的近似最优镇定问题. 针对系统的控制约束, 首先引入一个非二次泛函把约束问题转换为无约束问题, 然后基于协状态函数提出一种贪婪迭代DHP算法以求解系统的HJB (Hamilton-Jacobi-Bellman)方程. 在算法的每个迭代步, 利用一个神经网络来近似系统的协状态函数, 而后根据协状态函数直接计算系统的最优控制策略, 从而消除了常规近似动态规划方法中的控制网络. 最后通过两个仿真例子证明了本文提出的最优控制方案的有效性和可行性.     

Greedy Algorithm for Set Cover in Context of Knowledge Discovery Problems

In the paper some problems connected with a process of knowledge discovery are considered. These problems are reduced to the set cover problem. It is known that under a plausible assumption on the class N P the greedy algorithm is close to best approximate polynomial algorithms for the set cover problem solving. Unfortunately, the performance ratio of this algorithm grows almost as natural logarithm on the cardinality of covered set. Instead of usual greedy algorithm we consider greedy algorithm with threshold. This algorithm constructs a partial cover, which covers at least a fixed part (for example, 90%) of the set. We prove that the cardinality of constructed partial cover is bounded from above by a linear function on the minimal cardinality of exact cover C_min. In the case of 90% -cover, for example, in the capacity of such function we can take the function 2.31,·,C_min+1. This bound is independent of the cardinality of covered set. Notice that the concept of partial cover in context of knowledge discovery problems is very close to the concept of approximate reduct.     

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.     

一种虚拟化深度包检测部署机制

网络功能虚拟化转变了网络架构和网络业务的部署。在网络功能虚拟化架构中,实现虚拟化深度包检测只需在传输路径上进行一次扫描,但高效部署深度包检测功能引擎成为难题。将深度包检测功能部署问题形式化为线性规划问题以满足约束条件,并提出一种基于代价最小的贪婪算法和优化的贪婪算法来解决深度包检测功能部署问题。该算法对部署代价和网络资源代价进行折衷,实现了最小化的部署代价。实验结果表明,所提算法能够实现深度包检测功能部署并取得近似最优解。     

基于弱贪婪策略的快速直觉模糊核匹配追踪方法

针对现有直觉模糊核匹配追踪算法采用贪婪算法搜索最优基函数而导致学习时间过长的局限性，基于弱贪婪策略，提出了一种随机直觉模糊核匹配追踪算法。该算法不需要保证每次迭代过程都能搜索到当前最优基函数，仅需要在原搜索空间随机抽取一个较小的核字典子集进行搜索的方式来获得近似最优基函数，从而有效地减少一次迭代过程的搜索空间，大大降低了算法的训练时间。实验结果表明，与传统方法相比，本文方法在识别率相当的情况下有效缩短一次匹配追踪时间，计算效率明显提高，且所得模型具有稀疏性好，泛化能力高等优点。     

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

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

贪婪核主元模糊神经网络在转炉炼钢终点预报中的应用

本文提出基于核思想和贪婪算法的主元模糊神经网络模型,用来进一步提高转炉终点碳含量和 温度预报模型的精度．采用核函数把输入变量向高维特征空间映射以充分挖掘变量的隐藏信息,经贪婪算法 优化选取主元,除去变量的冗余信息,降低输入维数．将提取的主元输入自适应神经模糊推理系统后,网络 以规则的形式来反映数据间蕴含的关系;以此模拟操作工经验,减少经验差异带来的影响．对转炉生产实测 数据进行了仿真,结果表明该模型是有效的．     

基于改进贪婪算法的测量节点选择优化方法

未来应用场景对名字解析系统有着确定性时延保障的需求,如何有效选择测量节点,为确定时延名字解析提供支撑是本文着力解决的问题。本文将网络测量节点部署问题映射成为最小点覆盖问题,并基于传统的贪婪算法提出一种面向网络测量节点选取的改进贪婪算法,从优化贪婪算法迭代周期和针对实际场景特点改进排序算法2个方面进行优化。实验结果表明,基于改进贪婪算法的求解方式比传统贪婪算法的求解方式,平均耗时减少了90%以上。     

基于强化学习的HP模型优化方法研究

蛋白质结构预测问题一直是生物信息学中的重要问题。基于疏水极性模型的蛋白质二维结构预测问题是一个典型的NP难问题。目前疏水极性模型优化的方法有贪心算法、粒子群算法、遗传算法、蚁群算法和蒙特卡罗模拟方法等，但这些方法成功收敛的鲁棒性不高，容易陷入局部最优。由此提出一种基于强化学习的HP模型优化方法，利用其连续马尔可夫最优决策与最大化全局累计回报的特点，在全状态空间中，构建基于能量函数的奖赏函数，引入刚性重叠检测规则，充分挖掘生物序列中的全局进化关系，从而进行有效与稳定的预测。以3条经典论文序列和5条Uniref50序列为实验对象，与贪心算法和粒子群算法分别进行了鲁棒性、收敛性与运行时间的比较。贪心算法只能在62.5%的序列上进行收敛，该文方法能在5万次训练后稳定的在所有序列上达到了收敛。与粒子群算法相比，两者都能找到最低能量结构，但该文的运行时间较粒子群算法降低了63.9%。