基于量子蚁群算法的粗糙集属性约简方法

针对蚁群算法求取属性约简中存在的迭代次数多、收敛较慢甚至得不到最小约简的问题,提出了基于量子蚁群算法的粗糙集属性约简的方法。每只蚂蚁携带一组表示蚂蚁当前位置信息的量子比特;采用量子旋转门完成蚂蚁的移动;采用量子非门实现蚂蚁所在位置的变异。实验证明,该算法能快速有效地求解属性约简,同时又能找到许多次最小约简。可以很好地解决这一难题,它不仅能得到最小约简属性集,而且可以得到很多的约简属性集。     

粗糙集多目标并行属性约简算法

粗糙集理论(RST)中,求解最小属性约简MAR (minimal attribute reduction)是一种NP-难(non-deterministic polynomialhard)组合优化问题.蚁群优化算法ACO(antcolonyoptimization)是进化算法中的一种启发式全局优化算法,粗糙集理论与ACO相结合,是求解属性约简的一种有效、可行的方式.针对蚁群优化算法易于陷入局部最优解、收敛速度慢等问题,首先以一种改进的信息增益率作为启发信息,提出了冗余检测机制,对每个被选属性和每代最优约简集合进行冗余检测,并提出了概率提前计算机制,可避免每只蚂蚁在搜索过程中相同路径上的信息反复计算;针对大数据集的属性约简问题,考虑到蚁群优化算法具有并行能力以及粗糙集中“等价类”计算的可并行性,提出一种将ACO与云计算相结合用于求解大数据集的属性约简算法,在此基础上,进一步提出一种多目标并行求解方案.该方案可以同时计算出其余属性相对于当前属性或约简集合的重要度.实验结果表明,该算法在处理大数据的情况下能够得到最小属性约简,计算属性重要度的时间复杂度由O(n2)降至O(|n|).     

基于自适应蚁群算法的粗糙集属性约简

定义粗糙集理论的近似精度,引入信息索交流机制和交流概率,通过自适应调节每组蚂蚁间的信息素浓度改进传统蚁群算法,并将其应用于粗糙集属性约简算法中.实验结果表明,相比其他属性约简算法,该算法提高了获得最小属性约简的可能性,具有较好的收敛速度且不易陷入局部最优解.     

基于快速蚁群的银行客户信息属性约简算法

银行客户群体细分对于业务营销具有深远的意义, 客户信息具有数据量大、维度高、变化需求频繁的特点, 为此需要引入一种快速的属性约简算法, 以满足关键属性快速提取进而构建决策的要求. 本文通过改进传统的基于蚁群的属性约简算法, 优化每次迭代过程中的蚂蚁搜索的集合转移策略, 提出了一种基于快速蚁群算法的属性约简算法. 多个UCI数据集实验计算表明提出的新算法求解速度优于传统的基于蚁群算法的属性约简算法, 并且求解质量较优; 最后通过银行客户数据进行实践, 验证了该算法的可行性.     

求解决策表最小属性约简的SAGA

首先给出求解决策表核属性集的算法,然后采用动态调节近邻子集的方法改进模拟退火遗传算法,应用于求解决策表的最小属性约简。该约简算法利用核属性集优化初始种群,并采用自适应方式动态选取交叉和变异概率,有效地抑制了早熟收敛现象,提高了算法在解空间中的探索能力和效率。实验结果显示该算法能有效求解决策表最小属性约简问题。     

信息熵最小约简问题的若干随机优化算法

现有的启发式属性约简算法一般无法得到信息熵意义下的最小属性约简。为此,文中探讨应用随机优化算法计算信息熵意义下最小属性约简的问题。首先通过定义适当的适应值函数,将信息熵意义下的最小属性约简问题转化为不含约束的适应值优化问题,证明问题转化的等价性。研究基于遗传算法、粒子群优化算法、禁忌搜索以及蚁群算法等若干随机优化算法的求解效率和求解质量,并用一批UCI数据集来加以测试。实验结果表明,文中设计的带增强策略的基于全息粒子群的属性约简算法,具有较高的获得信息熵意义下最小属性约简的概率和较优的算法性能。关键词随机优化算法,粗糙集,信息熵,最小属性约简,全息粒子群中图法分类号TP181ResearchonComputingMinimumEntropyBasedAttributeReductionviaStochasticOptimizationAlgorithmsMASheng-Lan,YEDong-Yi(CollegeofMathematicsandComputerScience,FuzhouUniversity,Fuzhou350108)ABSTRACTExistingheuristicattributereductionalgorithmsgenerallyfailtogetaminimumentropy-basedattributereductionofadecisiontable。Somestochasticoptimizationalgorithmsarediscussedtosolvetheproblemofentropy-basedattributereduction。Firstly,aproperfitnessfunctionisdefinedtotransformtheminimumattributereductionproblemintoafitnessoptimizationproblemwithoutadditionalconstraintsandtheequivalenceoftransformationisproved。Then,thesolvingefficiencyandthesolutionqualityofsomestochasticoptimizationalgorithmsarestudiedsuchasGeneticAlgorithm,ParticleSwarmOptimization,TabusearchandAntColonyOptimization。SomeUCIdatasetsareappliedtotestthoseperformances。TheexperimentalresultsshowthatthefullyinformedPSObasedattributereductionalgorithmwithrefineschemehasahigherprobabilitytofindaminimumentropy-basedattributereductionandgoodperformance。     

基于蚁群优化的多个属性约简的求解方法

属性约简是粗糙集理论研究的一个核心问题,很多情况下多个最小属性约简被期望能帮助用户做出更好的决策。文中提出一种基于蚁群优化的获取多个属性约简的方法。首先,结合蚁群优化方法将属性约简问题转化为受限制满足问题,并提出新的模型R-Graph,进而最小属性约简问题转化为在R-Graph中寻找最低成本路径问题。然后,定义吸收算子删除可辨识矩阵中冗余数据的方法以达到简化搜索空间的目的,并提出一个求解多个属性约简的算法(R-ACO)。最后,对比实验说明该方法在大多数情况下能得到更多的最小属性约简结果,并且算法效率较高。     

基于改进蚁群算法的物流配送路径问题研究

针对蚁群算法求解物流配送路径问题易陷入早熟、停滞、局部最优的缺点,提出了混沌、变异与最大最小蚂蚁算法相融合的改进蚁群算法。在仿真实验中,分别采用最大最小蚂蚁算法、加入混沌的最大最小蚂蚁算法、加入变异的最大最小蚂蚁算法、加入混沌和变异的最大最小蚂蚁算法对物流配送路径问题进行求解。实验结果表明,加入混沌和变异的最大最小蚂蚁算法能够有效提高蚁群算法的全局寻优能力,对物流配送路径问题的求解能够得出比较好的结果。     

基于信息熵与蚁群优化的属性约简算法

信息熵是粗糙集理论中度量不确定信息的重要工具之一。蚁群优化算法是一种新型的智能计算的方法,具有分布式、正反馈及启发性搜索等优良的性质,并且在优化计算中已得到了很多应用.最小属性约简问题也是一类优化问题,已有的属性约简算法主要采用Pawlak正域度量属性的重要度,而且求最小约简是NP-hard问题.为此,在分析信息熵度量不确定性数据的基础上,定义信息熵属性重要度概念,引入蚁群优化算法,提出基于信息熵与蚁群优化的最小属性约简算法.该算法发挥蚁群优化算法良好的寻优能力,大多数情况下能够找到最小约简.理论分析与实验结果表明该算法是有效可行的.     

蚁群算法在面向属性的数据约简中的应用

粗糙集作为一种新的数学工具可用于数据挖掘中的面向属性的数据约简,但随着信息系统中信息量的不断膨胀,属性组合的不断增长,单独使用粗糙集寻找最小属性集已证明是个NP难的问题.蚁群算法是一种新型的模拟进化算法,在求解复杂的组合优化问题中获得成功并表现出良好的性能.文中将属性约简的过程视为一个特殊的"寻优"过程:把属性视为节点,而要寻找的是这些节点的"最少"组合,使得其能代替原来的属性节点而不改变原有属性的分类粗糙度.在此基础上,提出一种新的组合算法,利用蚁群算法在寻优方面的优势,结合粗糙集算法,用于最小属性集的寻找.最后通过一个具体的例子,证明了此算法的有效性和可行性.