[發明專利]基于自適應小生境的遺傳聚類方法

在審

• 申請號: 201310580924.9
• 申請日: 2013-11-18
• 公開（公告）號: CN103617206A
• 公開（公告）日: 2014-03-05
• 發明（設計）人: 盛偉國;白麗葉;盛蒙蒙;單鵬霄;陳勝勇
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

1.一種基于自適應小生境的遺傳聚類方法，包括如下步驟：

第一步：產生一個具有P個解的初始種群；

第二步：計算初始種群中每一個解的適宜度值；

DB=1KΣi=1Kmaxj,j≠i{Si+Sjdij}]]>

其中，K為簇數目，d_ij為簇C_i與C_j之間的距離，S_i為簇C_i的散布度，

SI=1/|Ci|Σx∈Ci||x-zi||]]>

這里Z_i為簇C_i的中心值，|C_i|為簇C_i中數據對象的個數。

第三步：重復以下(a)-(d)操作步驟，直到滿足終止條件：

(a)應用RTS小生境方法選擇一對父本，重復該過程直到選擇P/2對父本；

(b)對每對父本進行交叉操作產生后代，并對后代執行變異操作；

(c)采用自適應RTS小生境方法為每一個后代個體選擇一個相似度最高的種群個體，并與其進行生存競爭；

(d)計算每一個后代個體的適宜度值，如果后代個體優于被選擇的競爭個體，則取代其競爭個體進入種群。

第四步：提供最終種群的最優解。

2.如權利要求1所述的一種基于自適應小生境的遺傳聚類方法，其特征在于：在第三步(c)中設計種群多樣性指標來自適應的調整RTS小生境方法的關鍵參數w的值，具體步驟如下：

(1)根據個體中簇數目的不同，將種群P分成b個子種群。對于每個子種群S_j（j=1,2,…,b），設c為子種群中的個體數量，k為子種群中個體包含的簇數目，d為數據的維數；

(2)根據每個個體的適宜度，通其與子種群在解空間平均位置的距離，計算該子種群多樣性。詳細操作如下：

(2.1)計算子種群的平均基因位置：

Am=1cΣi=1cPi,m]]>

上式中，P_i,m為個體P_i的第m個基因，P_i=(P_i,1,P_i,2,…,P_i,k×d)；

(2.2)計算每個個體對子種群多樣性的貢獻，即計算每個個體到平均基因位置的適宜度加權距離：

PDiSj=wi×1kΣm=1k×d(Pi,m-Am)2]]>

其中，w_i=f_i/f_ave，f_i和f_ave分別是個體的適宜度和子種群的平均適宜度；

(2.3)通過求和所有個體對多樣性的貢獻，計算該子種群的多樣性：

PDSj=Σi=1cPDiSj]]>

然后根據種群中存在的子種群數目，計算其多樣性貢獻：

PDb=b×PDimax]]>

上式中，為當前一代種群中個體對多樣性的最大貢獻值；

最后，種群的多樣性可以表示為：

PD=PDb+Σj=1bPDSj]]>

(3)通過步驟（2）動態計算得到的種群多樣性值并用于自動調節RTS中參數w的值；具體策略：在演化的初始階段，使用一個較大的值w_max以促進在搜索空間中具較好適宜度小生境的形成。然后，基于動態計算得到的種群多樣性值，根據以下公式自動調節參數w的值：

w=wmax-PDPDmax×(wmax-wmin)]]>

上式中，w_max和w_min分別為w的上下界值，PD_max是到目前為止演化過程中得到的PD的最大值。