[發明專利]粗糙集屬性約簡的方法

在審

• 申請號: 201611062288.0
• 申請日: 2016-11-25
• 公開（公告）號: CN106650936A
• 公開（公告）日: 2017-05-10
• 發明（設計）人: 趙昶宇;邢懷崗
• 申請（專利權）人: 天津津航計算技術研究所
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 中國兵器工業集團公司專利中心11011
• 代理人: 劉東升

1.一種粗糙集屬性約簡的方法，其特征在于，所述方法包括以下步驟：首先，利用屬性核本身的特征確定初始種群，建立適應度函數；然后，利用遺傳算法找到條件屬性集合中適應值最好的染色體作為遺傳的優化解集合；最后，使用所述遺傳算法生成初始信息素，利用蟻群算法的局部尋優和正反饋機制得到粗糙集屬性約簡的最優解。

2.如權利要求1所述的粗糙集屬性約簡的方法，其特征在于，所述方法具體包括以下步驟：

S₁：

S₁₁：染色體編碼

采用長度為N的二進制串來表示一個染色體，“l”表示該染色體包含對應的條件屬性，“0”表示該染色體不包含對應的條件屬性；S₁₂：確定初始種群

利用屬性核本身的特征對初始種群進行限制，在每個染色體中，將屬性核所在的位置上的基因強制取值為“1”；所述屬性核是所有屬性約簡的交集；

S₁₃：建立適應度函數

定義染色體的適應度函數為：F(v)＝|C|-L_v，其中：v表示一條染色體，即一個個體，|C|是染色體所代表的條件屬性集中屬性的個數；L_v是染色體中所包含的條件屬性的個數；

S₁₄：判斷是否滿足終止條件

終止條件：如果當連續繁殖W代的最優條件屬性的適應值沒有變化時，則算法停止，否則轉步驟S₁₅；W為整數，是預設閾值；

S₁₅：選擇算子

a1)設條件屬性集合的長度為N，每個屬性的適應度為F_i，i＝1,2,…,N，計算條件屬性集合中每個屬性在下一代條件屬性集合中的期望生存數目

$N_i=\frac{N*F_i}{\underset{i=1}{\overset{N}{\Σ}}{F}_i}---\left(1\right)$

b1)用N_i的整數部分確定各個對應條件屬性在下一代條件屬性集合中的生存數目，其中表示取不大于N_i的最大整數，從確定下一代條件屬性集合中的個屬性；

c1)以表示各個條件屬性新的適應度，選擇算子隨機確定下一代條件屬性集合中還未確定的個條件屬性；S₁₆：交叉算子

采用多點位單基因交叉的方式，用父代最優解T_max與子代染色體池T進行交叉操作：

a2)在染色體池T中選擇進行交叉操作的條件屬性集合T_i和屬性約簡的最優解T_max；

b2)隨機生成交叉片段和交叉區域；

c2)將T_i的交叉區域加到T_max前面，刪除與交叉區域相同的條件屬性，得到一個新的條件屬性集合；

d2)將T_max的交叉區域加到T_i前面，刪除與交叉區域相同的條件屬性，得到另一個新的條件屬性集合；

e2)若兩個染色體的適應度都小于它們的父代適應度，則用父代染色體替換新生子代染色體；

S₁₇：變異算子

采用基本位變異算子：對條件屬性的每一個基因，即二進制的0或1，根據變異概率指定其為變異點，對每一個指定的變異點，條件屬性核對應的基因位不發生變異，其它的則對其基因值做取反運算，從而產生出一個新的條件屬性集合；

S₁₈：復制算子

在得到新一代條件屬性集合之后，如果其中適應值最小的屬性集合的適應值小于上一代適應值最大的屬性集合的適應值，則用上一代適應值最大的屬性集合代替新一代適應值最小的屬性集合；

S₂：

選取遺傳算法終止時條件屬性集合中適應值最大的10％的染色體作為遺傳的優化解集合，以從剩余可選條件屬性中選擇屬性i的概率作為蟻群算法初始信息素的一部分，初始化所有屬性節點之間的信息素的濃度τ_初始為：

其中，x表示優化解集合中屬性j選擇屬性i的總次數，y表示優化解集合中解的個數，η_i表示屬性i對屬性j的重要性；

a3)將m個螞蟻分別置于n個屬性節點上，設定最大迭代次數；

b3)若有螞蟻成功地將屬性i添加到屬性集合中，則為屬性節點間的信息素濃度賦予增量Δτ_i＝C_e×K；否則，若屬性i未被添加到屬性集合中，則為屬性節點間的信息素濃度賦予增量Δτ_i＝C_p×K，其中K表示選擇屬性所用的時間開銷，C_e和C_p表示相應的獎懲因子；

c3)更新所有屬性節點之間的信息素濃度τ_i(t)，即τ_i(t)＝τ_i(t)+Δτ_i；

d3)在屬性約簡中，下一個屬性的選擇只能由已經選擇的屬性來決定，設R_k為已選屬性的集合，k為迭代次數，i為已選屬性，j為待選屬性，根據各個屬性之間的信息素分布情況，計算螞蟻在R_k為已選屬性的集合情況下，從剩余可選條件屬性中選擇屬性j的概率P(j|R_k)：

$P\left(j\right|R_k)=\left\{\begin{array}{cc}\frac{{\mathrm{\Σ}}_{i\∈R_k}{{\mathrm{\τ}}_{ij}}^{\mathrm{\α}}{{\mathrm{\η}}_{ij}}^{\mathrm{\β}}}{{\mathrm{\Σ}}_{m\∈U}{\mathrm{\Σ}}_{i\∈R_k}{{\mathrm{\τ}}_{im}}^{\mathrm{\α}}{{\mathrm{\η}}_{im}}^{\mathrm{\β}}},& j\∈U\\ 0,& j\∉U\end{array}\right.---\left(3\right)$

其中：集合U表示第k次迭代后剩余可選條件屬性；τ_ij表示屬性節點i到屬性節點j的路徑信息素濃度值；η_ij表示屬性j對屬性i的重要性；α表示兩個屬性節點(i,j)之間的信息素濃度值的權重；β表示屬性j對屬性i的重要性的權重，τ_ij^αη_ij^β表示屬性i對屬性j的期望，表示集合R_k對屬性j的期望，表示集合R_k從U中選擇任何一個可選條件屬性的期望值和；

基于得到的最大概率值為每只螞蟻分別選取下一個屬性；

e3)根據所有螞蟻選取的屬性，計算對應的適應度函數F(v)，輸出F(v)的最大值及其所對應的屬性集合，即最小約簡；

f3)若達到最大迭代次數，或者迭代出現退化現象，則當前得到的最優解即為所要求得的屬性集合的最小約簡；否則，清空所有螞蟻的蟻集，跳轉到步驟b3)。