最小约简问题的一个免疫离散粒子群算法

Immune Discrete Particle Swarm Optimization Algorithm for Minimum Attribute Reduction Problems

把求决策表最小属性约简问题归结为一个不含非线性约束的0-1组合优化问题,证明了两个问题之间最优解的等价性.针对问题的特性,对原有的二进制粒子群算法进行改进,引入基于决策表差别矩阵的疫苗接种机制以及k-精英保优策略,由此提出一个免疫二进制粒子群算法并用于求解转化后的组合优化问题.仿真计算结果表明该算法有效地提高了获得最小属性约简的可能性,同时还具有较快的收敛速度.与其它类型的最小属性约简算法相比较,该算法取得明显的改进效果.

The problem of computing a minimum attribute reduct of a decision table is converted into a binary combinatorial optimization problem without extra nonlinear constraints. The equivalence on optimality between the two problems is proved. An improved binary particle swarm optimization algorithm is presented to solve the converted problem. The algorithm includes a vaccination mechanism based on the discernibility matrix of the decision table. Experimental results show that the proposed algorithm can get better results than some other existing algorithms for minimum attribute reduction in terms of both solution quality and computational effort.