一种求解集合覆盖问题的启发式算法

集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小.集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域.对这一问题,国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法.本文以贪心算法为基础,利用人类的智慧和经验,提出了一种求解集合覆盖问题的启发式算法.算法的主要思想为:从某个解出发,随机移除一定比例的列,再用贪心策略加入若干列.用本文提出的算法,对Beasley提出的45个测试实例进行了实算测试,所得结果和最优解的平均相对差值为0.44%,并且得到了其中33个实例的最优解,实算结果表明,本文提出的算法对求解集合覆盖问题是行之有效的.     

集合覆盖问题的数据约简研究*

针对当前解决大规模集合覆盖问题的算法普遍存在着效率不高的问题,提出了一套削减数据规模的约简方法,并给出了一个能够与其他所有解决集合覆盖问题算法相结合的约简算法。用Beasley提出的45个测试用例进行试验,结果显示贪心算法和遗传算法在结合了约简算法后能够在更少的时间内得到更优的解,表明该约简方法和约简算法可以有效提高传统算法和智能算法解决大规模集合覆盖问题的效率。     

基因学习算法及其在集合覆盖问题中的应用

在用传统方法解决一些复杂而规模较大的组合优化问题,尤其是NP难题,出现困难时,一些近似算法相继推出。启发式搜索法、模拟退火算法及进化算法等的出现,为解决这些优化问题提供了非常好的手段。近年来,出现了一种概率学习的进化计算模型,如Baluja的PBIL算法与Corno的自私基因算法。概率学习的进化计算模型通过不断地学习每一代的最优个体,最终收敛于最优或较优的解的等位基因概率,其过程描述如下:     

基于动态集合进化算法的弱变异测试用例集生成

为解决基于集合进化算法（SEA）的弱变异测试用例集生成过程中个体规模固定和执行开销大的问题,提出一种基于动态集合进化算法（DSEA）的弱变异测试用例集生成方法。以测试用例集为个体,生成覆盖所有变异分支的弱变异测试用例集。在进化过程中,集合精简算子根据最优个体的最小子集及其未覆盖变异分支数量计算所需测试用例集的最小规模,并基于该最小规模调整种群中所有个体的规模,以生成最小规模的弱变异测试用例集,同时设计了适用于评估以测试用例集为个体的适应度函数。实验结果表明,动态集合进化算法指导弱变异测试用例集生成,获得的测试用例集规模比个体初始规模平均约简了50.15%,执行时间比集合进化的弱变异测试用例集生成最多降低了74.58%。因此,动态集合进化算法为最小规模的弱变异测试用例集生成和提升算法速度提供了一种解决方案。     

基于蚁群算法的集合覆盖问题

蚁群算法是一种基于群体智能原理的优化模型,用于解决组合优化问题。集合覆盖问题是NP完全问题中应用面最广的问题之一,它在模式识别、机器学习等领域中具有重要的应用。以SCHF[1]启发函数作为启发信息,用蚁群算法求得集合覆盖问题的优化解。通过几种算法的仿真结果对照表明,用蚁群算法求解集合覆盖问题是有效的,蚁群算法得到的解是比较理想的。     

基于最小集合覆盖的网络连通性自动化测试

网络规模的增长加大了分布式网络管理与测试的难度。为此,提出一种优化的全连通自动化测试用例集生成算法。在最小集合覆盖理论的基础上,引入空间因子参数,优先选取搜索空间中起点或终点被选取次数最多的测试路径进入解集,以减少测试点数。实验结果表明,该算法在空间因子为4的情况下,比贪心搜索算法减少约20%的测试点数,比GRASP算法缩短约99.9%的测试时间,具有较高的测试效率。     

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

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

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

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

关于最小测试集的线性规划松弛近似

目前最小测试集的最佳近似比是贪心算法的2 ln n＋o（1）.这个近似比能否改进是一个公开的问题.本文讨论了最小测试集的基于线性规划松弛的近似比证明方法的能力问题.我们证明最小测试集的整性间隙至少为0.72 ln n,而且最小测试集整性间隙的系数可以与最小集合覆盖的整性间隙的系数一样大.另外,我们说明加权最小测试集的贪心算法的近似比不能通过对偶拟合方法改进超过一个常数.     

集合多覆盖问题的乘性权重更新分析

集合多覆盖问题的简单贪心算法的近似比是lnn＋1。本文提出简单贪心算法的一个变形,宽度优先贪心算法,并且证明其有近似比（lnn）／r＋lnlnn＋O（1）,其中r是覆盖要求。这个结果比由随机取整方法得到的近似比O（（lnn）/r＋√（lnn）＋1为优。宽度优先贪心算法的设计可以归入Arora等最近提出的乘性权重更新方法的框架。关键词集合多覆盖,宽度优先贪心算法,乘性权重更新方法     

无线传感器网络最小覆盖集的贪婪近似算法

网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一个NP难问题,目前,其近似算法的性能较低.提出了一种基于贪婪法的最小覆盖集近似算法,在构造覆盖集的过程中,优先选择扩展面积最大的有效节点加入覆盖集.理论分析表明,该算法能够构造出较好的覆盖集,时间复杂度为O(n),其中,n为初始节点总数.实验数据表明,该算法的性能要优于现有算法,得到的覆盖集的平均大小比现有算法减小了14.2%左右,且执行时间要短于现有算法.当初始节点分布较密时,该算法得到的平均覆盖度小于1.75,近似比小于1.45.     

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.     

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

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

一种求解最小连通支配集的高效近似算法

寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果.     

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

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

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

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