一种高效的最小连通支配集贪心算法

连通支配集（CDS）在无线网络设计中有着广泛应用,现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法（GCDS）,依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点,当删除处理节点后剩余点不连通时减少处理的节点数,进而把节点分为支配点和受支配点;最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明,GCDS算法具有较低的时间复杂度,所得到的连通支配集大小优于已有算法。     

改进的分布式互斥请求集生成算法

在分布式系统中,各节点必须互斥地访问临界区.节点的请求集的长度决定了系统的效率、性能.虽然最优请求集的节点数最少(大约n),但已有的解决方案该类问题算法类似于穷举法,随着节点的增加,该方法变得不可计算.提出了一种快速的请求集生成算法,该算法以循环差集请求集生成算法的理论和贪心算法的基本思想为基础,在每次迭代的过程中,选出一个当前条件下最优的节点加入请求集.与其他的方法相比较,该方法能对任意给定的整数快速、有效地生成对称的请求集.本算法时间复杂度为O(n2),生成的请求集长度为n～2n.     

一种贪心策略的更高效的请求集生成算法

在折半循环编码算法的基础上,依据贪心策略对可纳入节点进行局部求最优的方式来生成请求集的算法,从而使算法的请求集长度下降了一个数量级,接近姨N。     

基于混合遗传算法的回归测试用例集最小化研究

为缩减测试用例规模,降低回归测试成本,将遗传算法和贪心算法相结合,提出了一种混合遗传算法用于解决测试用例最小化问题.算法对标准遗传算法中的选择、交叉和变异操作进行改善,提高了算法的全局寻优能力.同时,利用贪心算法处理可行解和不可行解,提高了算法的局部寻优能力.实验结果表明:与标准遗传算法相比,在保证测试完备性的前提下,混合遗传算法能够得到更优的缩减效果和更快的收敛速度.     

一种求解TSP问题的单亲遗传算法

1 前言 TSP问题可描述为:给定一个城市的集合,寻找一条从集合中的某个城市出发,访问每个城市一次且仅一次,最后回到出发点的最短路径。这已被证明是一个NP难解问题。求解TSP问题,遗传算法通常采用序号编码和非序号编码两种解表达方式。其中序号编码相对简单直接,其代表性的有“邻接表达”、“普通表达”和“路径表达”等几种编码方式,后者是最自然的表达方式。序号编码方式的杂交算子难于设计,杂交后解的合法性是需着重考虑的问题。虽然目前已提出了一些基于路径表达的杂交算子,如PMX、OX和CX,但普遍计算额外开销很大,而且杂交算子的使用对群体的多样性存在很大影响,容易使算法过早收敛。     

一种新的自适应水平集融合算法

在处理不均匀图像时,自适应距离保持水平集演化(ADPLS)算法速度快、不受初始轮廓影响,但精度较低;LBF算法精度高,但速度较慢同时易受初始轮廓影响。针对上述2种算法的优缺点,提出一种新的自适应融合算法。该算法根据图像信息自动调整ADPLS与局部二值拟合算法在融合算法中所占比重,实现不同算法的优势互补。实验结果证明,该融合算法在分割精度、速度及稳定性等方面有明显提高。     

一种基于矩阵的求最小覆盖集算法

本文提出了一种利用矩阵的方法表示函数依赖集。通过有效迭加和对相应矩阵的化简得出了基于矩阵的求最小覆盖集的新算法。     

一种基于单亲遗传算法的基因芯片的筛选方法

本文提出了一种通过pearson相关系数建立的邻接矩阵中,利用基于单亲遗传算法寻找最大团的基因芯片的筛选方法。通过对实际数据的模拟证明该算法具有良好的应用价值。     

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

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

粗集结合决策树的一种数据挖掘算法

决策树是一种重要的数据挖掘方法,本文将决策树的基本建树思想ID3算法与对象决策属性化简的粗集理论相结合,得到一种新型的决策树建树方法。通过实例证明了该方法的效率有所提高,使挖掘的效果更简单、更容易理解。     

测试集问题的集合覆盖贪心算法的深入近似

测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).     

一种基于改进遗传算法的粗糙集属性约简算法磁

为解决传统遗传算法在属性约简时会出现迭代次数多,收敛较慢的问题,论文提出了一种改进的遗传算法。该方法在适应函数上加入属性重要度因子,同时在交叉操作中有选择地保留子代个体,确保算法能够快速收敛。实验结果证明,改进之后的算法在保证属性约简的基础上,能够实现比传统遗传算法更快的迭代和收敛。     

基于优化的邻域粗糙集的混合基因选择算法

DNA微阵列技术可以同时检测细胞内成千上万的基因的活性,被广泛应用于重大基因疾病的临床诊断。然而微阵列数据通常具有高维小样本特点,且存在大量噪声和冗余基因。为了进一步提高微阵列数据分类性能,提出一种特征基因混合选择算法。首先采用ReliefF算法剔除大量无关基因,获得特征基因候选子集;然后采用基于差分进化算法优化的邻域粗糙集模型实现特征基因选择;最后利用支持向量机进行分类,以验证算法的有效性。仿真实验结果表明,该算法能用尽可能少的特征基因来获得更高的分类精度,既增强了算法的泛化性能,又提高了时间效率,而且对致病基因的临床诊断有着重要的参考意义。     

改进工作集选择策略的序贯最小优化算法

针对标准序贯最小优化(sequential minimal optimization, SMO)算法采用可行方向工作集选择策略所带来的缓存命中率低下问题,给出了SMO类型算法每次迭代所带来的目标函数下降量的二阶表达式,并据此提出了一种改进的工作集选择策略.新策略综合考虑算法收敛所需的迭代次数及缓存效率,从总体上减少了核函数计算次数,因此极大提高了训练效率,并且,它在理论上具有严格的收敛保障.实验结果表明,核函数越复杂,样本维度越高,缓存容量相对训练样本的规模越小,改进工作集选择策略的SMO算法相较于标准SMO算法的性能提高就越显著.     

一种基于组合变换的粗糙集属性约简算法

粗糙集的核心问题是知识的约简和获取。该文提出一种基于组合变换的粗糙集属性约简算法,此算法基于数理逻辑的组合推理,采用核属性和单属性进行过滤,并用超集关系对候选约简进行消减。分析表明,算法具有较好的时间复杂度和空间复杂度。     

物化视图选择的一种两阶段优化算法

物化视图是数据仓库中提高查询效率的有效方法,物化视图选择问题是数据仓库设计时期最重要的决定之一。通过研究和实验,提出了一种结合迭代改进算法和模拟退火算法的两阶段优化算法,用于解决物化视图的选择。理论分析和实验结果表明,该算法有效地解决了传统模拟退火算法收敛过慢的缺点,并且其解的质量逼近经典贪婪算法。     

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

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

寡核苷酸芯片的逐步探针选取算法

探针集的挑选是寡核苷酸芯片设计过程中最重要的部分。基于合成探针成本的考虑,探针的个数成为评价探针集优劣的一个最重要的指标。一个好的探针挑选算法应该挑选出尽可能少的探针。为此,对探针选取的贪心算法作了改进,提出一个类似于逐步向前回归算法的探针选取算法。该算法在每次向探针集加入边际效用最大的探针的同时,把边际效用没有或者很小的探针从探针集中剔除出去。对HLA等位基因数据的实验结果表明,逐步选取算法得到的探针集优于贪心算法挑选出的探针集。