离散微粒群改进算法及在属性约简中的应用

摘要

微粒群优化(Particle Swarm Optimization,简称PSO)是Kennedy和Eberhart于1995年提出的一种群体智能优化方法。具有概念简单、运算方便、需要调节的参数少以及较强的全局收敛能力的优势,迅速得到了学术界的认可,目前在函数优化、模式识别训练、工业生产优化领域等得到了成功的应用。但其多用于解决连续优化问题,很少被用来解决离散问题,而现实生活中的许多工程实例只能抽象出离散模型,离散微粒群算法(Discrete Particle Swarm Optimization,简称DPSO)就是为解决离散问题而提出的。
　　 另一方面,随着信息时代的到来,数据库中存储的数据量以惊人的速度增加,庞大的数据量渗透到社会生活和生产的各个领域,传统的统计技术及数据管理工具不再适合分析这些巨量的数据集,人们非常需要一种高效的数据处理方法。粗糙集属性约简理论是数据预处理的一项重要内容,此方法能够减小数据规模从而减少存储空间和处理时间,而且能够尽量保留原数据的有用信息从而使数据挖掘的结果更可信,准确性更高。
　　 本论文主要做了以下两方面工作:
　　 (1)传统离散微粒群算法存在局部搜索能力差的缺点,本论文将对传统离散微粒群算法进行改进。为了算法能够逃出局部最优解,本论文引入多尺度概率变异算子,变异概率算子随着微粒适应值的提升而逐渐减少,进化初期大尺度变异算子有益于快速定位到最优解区域,进化后期小尺度变异算子局部搜索能力增强,这样就可以在保证算法局部开采能力的同时提高勘探能力,使算法能有效逃出局部最优解区域。将该算法应用到不同的优化函数中并与其他DPSO算法进行比较,证明算法的优越性。
　　 (2)近年来,微粒群算法在最小属性约简方面有了广泛的应用,受自然界病毒进化理论的启发,本论文提出一种基于病毒协同离散微粒群的粗糙集最小属性约简算法。在算法中,进化在宿主与病毒种群之间协同进行,通过满足约简分辨力不变条件的最优病毒种子复制操作产生病毒库,病毒通过感染操作在宿主种群完成横向局部搜索,以提高算法局部精确解搜索能力,同时通过删减操作完成自我更新,实现增加局部搜索范围的目的。最后对UCI数据集进行属性约简实验,结果证明本文算法在搜索最小属性约简解方面优于其他进化算法,同时收敛速度及寻优效率也有较大提高。