基于蚁群优化算法的属性约简方法

《基于蚁群优化算法的属性约简方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于蚁群优化算法的属性约简方法刘业政姜元春(合肥工业大学管理学院电子商务研究所合肥230009)摘要：为了获得信息系统中条件属性的最小约简，本文将基于信息论的属性重要度作为启发信息引入蚁群算法，提出了一种基于蚁群算法的属性约简方法。首先分析了属性约简与TSP问题的差异，提出了属性约简的数学模型，在此基础上对蚁群优化算法中的启发信息和信息素更新函数进行重新定义，最后研究了属性约简中解的构造过程。实验表明，本文方法能有效地对信息系统进行最大程度的约简。关键字：粗糙集；属性约简；蚁群优化算法；信息论蚂蚁k(k1,2,,m)在运

2、动过程中，根据各条路径k1引言上的信息量和启发信息决定转移方向，pij表示第t属性约简是粗糙集理论的核心内容之一。由于代时蚂蚁k由城市Ti转移到城市Tj的概率属性约简可以删除冗余信息，形成简洁的规则库，(t)*(t)ijij对人们的决策提供快速、准确的支持，因此，属性Tjallowedkpkis(t)*is(t)（1）约简成为粗糙集理论研究的热点，并提出了许多有ijTsallowedk效的方法。其中，文献[3]提出了一种基于互信息0else的知识相对约简算法，文献[4]提出了基于遗传算

3、其中，tabuk用来记录蚂蚁k已路过的城市，并随法的属性约简的方法，文献[5,6]也在属性约简方面着进化过程作动态调整。allowedk＝做了许多工作。然而，作为一类NP组合优化难题，属性约简至今尚未找到高效、完备的解决方法。{T1,T2,,Tn}tabuk表示蚂蚁k当前可以选择的蚁群优化算法（ACO）是一种非常有效的全局城市集合。ij是基于具体问题的启发信息。在TSP寻优的随机搜索算法,具有并行性、鲁棒性和全局问题中，d(T,T)1。,是信息素和启发信ijij搜索等特点。近几年来，蚁群优化算法已经被用来息对

4、蚂蚁决策的影响权重。随着时间的推移，以前求解二次分配问题等复杂组合优化问题[7-9],取留下的信息素会慢慢地挥发，如果参数1表示得了很好的结果，显示出蚁群优化算法在求解组合信息素的挥发程度，则t1代各路径上的信息素按优化问题方面的优越性。式（2）进行调整：受蚁群优化算法成功解决众多组合优化难题ij(t1)ij(t)ij（2）的启发，本文将从信息论角度定义的属性重要度作m为启发信息引入蚁群优化算法，提出了一种基于蚁k群优化算法的属性约简新方法，实验表明该方法适ijij（3）k1合于求解大规

5、模数据集的属性约简问题。k其中，ij表示路径(Ti,Tj)上的信息素增量，ij2蚁群优化算法表示蚂蚁k在周游过程中释放在路径(Ti,Tj)上的蚁群优化算法是由意大利学者MDorigo等人信息素Q若第k只蚂蚁经过路径(T,T)提出的一种新型启发式随机优化搜索模型[1,2]，其kLij（4）ijK思想是模拟蚁群的正反馈机制，通过个体之间的信0else息交流与相互协作达到优化的目的。本文以求解其中，Q为常数，Lk表示蚂蚁k在本次周游中所TSP问题为例说明蚁群优化算法的基本原理。走回路的长度。已知n个城市T

6、(T1,T2,,Tn)以及城市之间蚁群优化算法进化的过程为：m只蚂蚁同时从的距离，TSP问题就是要寻找一条经过每个城市仅m个不同城市出发，根据(1)选择下一个旅行的城一次且最后回到出发点的最短路径。设m为蚂蚁的市，已去过的城市放入tabuk中，一次循环完成后，数量，ij(t)表示第t代时路径(Ti,Tj)上的信息量，由公式(2)，(3)，(4)更新每条路径上的信息素，重初始时刻各条路径上的信息量相等，ij(0)为常数。复上述过程，直到终止条件成立。3基于蚁群优化算法的属性约简基金项目：国家自然科学基金(7047104

7、6)和教育部博士点基由于蚁群优化算法在求解复杂组合优化问题金(20040359004)所表现出的优越性，本文将蚁群优化算法应用于属相对决策属性的重要度可以通过添加某个条件属性约简。但是，与TSP等组合优化问题不同，属性所引起的互信息的变化大小来衡量[3]：性约简有其自身的特点，主要体现在三个方面。第SGF(a,R,D)I(R{a};D)I(R;D)(7)一，在解的构造过程中，每只蚂蚁无需搜索所有的这一结果度量了属性a的重要性，也就是说在已知属性，只要搜索到的属性子集构成了一个约简，蚂R的情况下，SGF(a,R,D)的值

8、越大，属性a对于蚁就可以结束本次搜索；第二，在属性约简问题的决策D就越重要。可行解中，属性排列的顺序并不重要。而在TSP本文将此结果引入蚁群优化算法中，将向集合中，城市的排列顺序对路径的质量是非常关键的；kSP中添加属性ci所引起的互信息的变化第三，由于信息系统的约简不唯一，因此蚁群算法j