基于量子精英蛙的最小属性自适应合作型协同约简算法  

A Minimum Attribute Self-Adaptive Cooperative Co-Evolutionary Reduction Algorithm Based on Quantum Elitist Frogs

作　　者：丁卫平[1,2,3] 王建东[2] 管致锦[1] 

机构地区：[1]南通大学计算机科学与技术学院,江苏南通226019 [2]南京航空航天大学计算机科学与技术学院,南京210016 [3]计算机软件新技术国家重点实验室(南京大学),南京210093

出　　处：《计算机研究与发展》2014年第4期743-753,共11页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61139002;61300167);计算机软件新技术国家重点实验室(南京大学)开放课题(KFKT2012B28);江苏省高校自然科学研究资助项目(12KJB520013);江苏省普通高校研究生科研创新计划资助项目(CXZZ11_0219);南通市科技计划应用研究项目(BK2011062);南通大学自然科学类科研基金前期预研项目(12ZY016)

摘　　要：属性约简是粗糙集理论研究的重要内容之一,现已证明求决策表的最小属性约简是一个典型NP-Hard问题.提出一种基于量子精英蛙的最小属性自适应合作型协同约简算法.该算法首先将进化蛙群编码为多状态量子染色体形式,利用量子精英蛙快速引导进化蛙群进入最优化区域寻优,有效增强进化蛙群的收敛速度和全局搜索能力.然后构建一种自适应合作型协同进化的最小属性约简模型,融合蛙群最优执行经验和分配信任度自适应分割属性约简集,并以模因组内最优精英蛙优化各自选择的属性子集,提高属性约简的协同性和高效性,快速找到全局最小属性约简集.实验研究表明提出的算法在搜索最小属性约简解时具有较高的执行效率和精度.Attribute reduction is a key point in studying rough sets theory.It has been proven that computing minimum attribute reduction of the decision table is an NP-hard problem.However,the conventional evolutionary algorithms are not efficient in accomplishing minimum attribute reduction.A novel minimum attribute self-adaptive cooperative co-evolutionary reduction algorithm （QEFASCR） based on quantum elitist frogs is proposed.Firstly,evolutionary frogs are represented by multi-state quantum chromosomes,and quantum elitist frogs can fast guide the evolutionary frogs into the optimal area,which can strengthen the convergence velocity and global search efficiency.Secondly,a self-adaptive cooperative co-evolutionary model for minimum attribute reduction is designed to decompose evolutionary attribute sets into reasonable subsets according to both the best historical performance experience records and assignment credits,and some optimal elitists in different subpopulations are selected out to evolve their respective attribute subsets,which can increase the cooperation and efficiency of attribute reduction.Therefore the global minimum attribute reduction set can be obtained quickly.Experiments results indicate that the proposed algorithm can achieve the higher performance on the efficiency and accuracy of minimum attribute reduction,compared with the existing algorithms.

关 键 词：最小属性约简 量子精英蛙 合作型协同进化 自适应分割 最优执行经验 分配信任度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.6[自动化与计算机技术—控制科学与工程]