基于二进制粒子群优化的一个最小属性约简算法

研究基于二进制粒子群优化算法思想求解决策表最小属性约简问题的方法.定义适当的适应值函数,将决策表最小属性约简问题转化为一个适合二进制粒子群优化算法求解的0-1组合优化问题,证明问题解的等价性.在此基础上,引入种子粒子概念及其自适应保护策略,提出一个改进的二进制粒子群算法,取得良好的效果.实验结果说明该算法的有效性.     

基于免疫粒子群优化的最小属性约简算法

把求决策表最小属性约简问题归结为一个0 1组合优化问题，为该问题定义了合理的粒子适应度函数，提出了一种把免疫接种、免疫测试机制与二进制粒子群算法相结合的混合算法用于求解该问题。对UCI数据表的实验结果表明该算法在获得更优解的同时,仍具有较快的运算速度。多种算法的比较结果表明了该算法的有效性和可行性。     

基于免疫量子粒子群优化的测试代价敏感属性约简算法

为了解决测试代价敏感属性约简的高效性和准确性问题,提出一种基于免疫量子粒子群优化的最小测试代价属性约简算法。依据条件信息熵和测试代价因素定义适当的适应值函数,将最小测试代价属性约简问题转化为0-1组合优化问题,提出最小属性的属性约简问题是一种具有特殊测试代价的最小测试代价属性约简问题。最后结合量子粒子群和人工免疫方法给出约简算法。实验对比已有的最小属性约简算法和测试代价敏感属性约简算法,实验结果表明本算法是有效的。     

基于粒子群的不完备决策表属性约简PSOIDTAR法

属性约简是粗糙集理论的一个核心部分。由于经典的粗糙集模型对不完备信息系统不适应,通过把属性约简问题归结为0-1组合优化问题,提出了一种应用二进制粒子群算法来求解属性约简的方法。通过引入近似分类精度和近似分类质量,为获得最小约简确定了有效合理的粒子适应度函数。仿真实验结果表明该算法能得到最小相对约简,且具有较高的运算效率。     

基于量子粒子群优化的属性约简

量子粒子群优化(QPSO)算法改进了粒子进化策略,使粒子具有更大搜索空间,可更好地避免陷入局部最优。该文将普通QPSO算法转化为二进制QPSO算法,提出基于QPSO优化的属性约简算法。实验结果表明,二进制QPSO算法的约简结果优于Hu算法和粒子群优化约简算法。     

基于混沌离散粒子群的粗糙集属性约简算法

针对粒子群属性约简算法容易早熟、易陷入局部最优解的问题,提出一种融合混沌离散粒子群与粗糙集的属性约简算法(CBPSORS).在该算法中,首先利用混沌序列初始化粒子的位置和速度,得到一个无序的粒子种群.其次改进最优粒子进行混沌变异过程,改进惯性因子和加速因子来提高算法性能.再次用粗糙集理论对生成的属性子集相关性进行评估.最后用K-近邻(KNN)算法生成分类模型在UCI数据集上对该算法进行验证.理论分析与实验结果表明,与基于粗糙集的属性约简算法(RS)、基于粒子群的粗糙集属性约简算法(PSORS)以及基于遗传算法的粗糙集属性约简算法(GARS)相比,文中算法可以在保持决策表知识信息的前提下,约减掉更多的条件属性,提高分类精度.     

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

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

一种粗糙集属性约简的伪粒子群算法

针对高维数据集的属性约简问题,通过改变经典粒子群算法的运动方程,并用属性依赖性和属性子集特征数构造适应度函数,提出以决策表核属性为基础的最小属性子集搜寻策略。实验结果表明,与其他类型的最小属性约简算法相比,该算法不仅能有效提高获得最小属性约简的机率,同时还大大降低了计算时间。     

基于遗传粒子群和粗糙集的最小属性约简算法

阐述了粗糙集理论、遗传约简算法和粒子群约简算法。属性约简是知识发现的关键问题之一。传统的属性约简算法都是串行搜索的,算法效率低且收敛速度慢。将计算智能和粗糙集相结合,提出了一种基于遗传粒子群和粗糙集的最小属性约简算法。该算法利用属性依赖度计算属性核,并在种群初始化时引入属性核作为限制条件,动态调整适应度函数,以达到求得最小属性约简的目的。实验表明,对于数据量大、属性维度高的属性约简问题,该算法具有高效的处理能力。     

基于多种群量子粒子群优化的属性约简

现代工业发展要求迅速、可靠地实现故障诊断。针对粒子群约简算法易陷入局部最优等问题,提出了一种多种群量子粒子群优化算法（MIQPSO）。该算法对量子粒子群算法进行分群,并通过接种疫苗,指导粒子朝更优化方向进化,提高了量子粒子群的收敛速度和寻优能力。利用UCI相关数据集,通过对Hu算法、粒子群算法、量子粒子群算法、多种群量子粒子群算法的粗糙集属性约简验证,结果表明,基于多种群量子粒子群优化的约简算法具有良好的约简效果。     

基于二进制的决策表求核算法

决策表属性约简是粗糙集理论中的核心内容之一,其中求核运算是决策表属性约简的基础,提出了基于二进制的新的决策表求核算法,将求核运算转化为数值的比较运算,并给出了属性绝对必要性和相对必要性的新的判定规则,与传统算法相比,其速度更快,效率更高,易于计算机实现,为扩展粗糙集的应用提供了理论基础。     

一种基于不完备决策表的求核方法

求核是粗糙集理论的重要研究内容之一,现有的求核算法大部分都是基于完备决策表的,对基于不完备决策表的求核研究很少。提出了不完备决策表二进制差别矩阵的构造方法,在此基础上,利用二进制差别矩阵设计了一种不完备决策表的求核算法。从理论上证明了基于二进制差别矩阵的求核与基于正区域的求核是相等的。新算法的时间复杂度是[O(|C||U|2)],用实例分析说明了新算法的正确性。     

一种基于决策表的属性约简增量式快速更新算法

针对实际的决策表中的对象通常是动态变化的情况,首先引入了简化的决策袁,然后在动态更新核的基础上,结合简化二进制差别矩阵和位图运算的设计思想,提出了一种快速的属性约简增量式更新算法.当有新对象加入决策表时,新算法只需验证新增的对象和原决策表中的对象是否一致性,然后采用在计算二进制差别矩阵的同时对原属性约简进行动态更新,从而有效地降低算法的时空复杂度,最后用实例说明了新算法的可行性和高效性.     

The continuous artificial bee colony algorithm for binary optimization

Artificial bee colony (ABC) algorithm, one of the swarm intelligence algorithms, has been proposed for continuous optimization, inspired intelligent behaviors of real honey bee colony. For the optimization problems having binary structured solution space, the basic ABC algorithm should be modified because its basic version is proposed for solving continuous optimization problems. In this study, an adapted version of ABC, ABC_bin for short, is proposed for binary optimization. In the proposed model for solving binary optimization problems, despite the fact that artificial agents in the algorithm works on the continuous solution space, the food source position obtained by the artificial agents is converted to binary values, before the objective function specific for the problem is evaluated. The accuracy and performance of the proposed approach have been examined on well-known 15 benchmark instances of uncapacitated facility location problem, and the results obtained by ABC_bin are compared with the results of continuous particle swarm optimization (CPSO), binary particle swarm optimization (BPSO), improved binary particle swarm optimization (IBPSO), binary artificial bee colony algorithm (binABC) and discrete artificial bee colony algorithm (DisABC). The performance of ABC_bin is also analyzed under the change of control parameter values. The experimental results and comparisons show that proposed ABC_bin is an alternative and simple binary optimization tool in terms of solution quality and robustness.     

基于幂图的属性约简

针对粗糙集理论中基于差别矩阵的属性约简方法存在的不足,提出一种基于幂图的属性约简算法.首先通过修改样本决策属性值将不相容决策表转化为简化的相容决策表;然后将样本对概念与幂图概念相结合,将基于修正差别矩阵的不相容决策表的属性约简转化为幂图的搜索问题;最后通过实例和实验验证了所提出算法的有效性.     

粒子群算法在贷款组合优化决策中的应用

针对贷款组合优化决策模型的求解问题,论文提出了用于求解该问题的二进制粒子群算法,并阐明了算法的具体实现过程。为了加快粒子群算法的收敛速度,论文在传统粒子群算法中引入了记忆机制。通过对论文中两个仿真实例的计算和结果比较,表明了该算法不论在寻优能力方面,还是在求解速度和稳定性方面都取得了很好的效果。     

一种基于新的模型的多目标存档遗传算法

在多目标优化中,如何在最优解集中获得一组分布均匀且质量较好的代表解是十分重要的。文中给出了种群个体的序和解的均匀性分布定义,在此基础上又给出了解的序值方差和U-度量方差,然后把对任意多个目标函数的优化问题转化成对两个目标函数的优化问题,并对转化后的优化问题提出了一种新的多目标存档遗传算法,并证明了其全局收敛性。数据实验比较表明该算法能找到问题的数量更多、分布更广、更均匀的Pareto最优解。     

一种新的完全决策表属性约简的高效算法

属性约简是粗糙集理论的核心问题之一,也是粗糙集有效算法研究的焦点。为获得最简明的规则集,通常希望能找出最小的属性约简集,但得到最优解是NP-hard的问题,通常采取启发式的算法得到近似最优解。文中研究了不完全决策表的属性约简,提出一种衡量不完全决策表属性重要性的标准,依此给出了一种新的进行属性约简启发式算法。对寻找对象的相似类的步骤则在排序和二分查找的基础上提出了一种新的高效的算法,这样就相应地使得属性约简的效率得到提高。此算法较好地解决了不完全决策表的属性约简问题。     

一种改进的新二分查找算法的研究与实现

基于传统的二分查找算法,给出了有序表中任意两元素之间距离的最优表示方法,改进了low和high的取值,得到一种基于距离的新二分查找算法。该算法与传统的二分查找算法相比,判定树高度得到有效降低;随着有序表元素的增加,平均查找长度ASL显著减少,查找速度明显提升。