[發明專利]一種可變長染色體編碼的混合并行遺傳聚類算法

在審

• 申請號: 201710315280.9
• 申請日: 2017-05-08
• 公開（公告）號: CN107038479A
• 公開（公告）日: 2017-08-11
• 發明（設計）人: 戴文華;焦翠珍;錢濤;趙君喆;聞彬;江偉;厲陽春;范平
• 申請（專利權）人: 湖北科技學院
• 主分類號: G06N3/08
• 分類號: G06N3/08;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種可變長染色體編碼的混合并行遺傳聚類算法，包括如下步驟：

A、可變長染色體編碼

染色體的基因由初始聚類中心對應的樣本點在樣本集中的編號表示，其編碼形式為：C＝{c₁,c₂,…,c_t}。

其中t為某條染色體的編碼長度，對不同的染色體，t的值是在變化的，c_i(i＝1,2,…,t)為第i個聚類中心對應的樣本在樣本集中的編號，為一個[1,N]之間的自然數(N為樣本個數)。

B、插入刪除交叉算子

染色體插入刪除交叉算子的具體步驟如下：

①以父個體CH₁作為被刪除染色體，以父個體CH₂作為被插入染色體，計算兩個染色體CH₁和CH₂的長度t₁和t₂；

②如果則重新選擇染色體CH₂，直到

其中N為樣本個數，為聚類個數的經驗值，設置該值的目的只是為了加快算法速度，如果對算法精度要求較高，則可適當放寬該值的尺度。要求是為了防止插入操作后染色體CH₂的基因由于超長截斷而無變化。

③隨機生成插入點位置Ins、刪除點位置Del和插入或刪除的長度DLen；

其中插入長度與刪除長度相等均為DLen。要求滿足如下條件：

0≤Del＜t₁，0≤Ins≤t₂且DLen＜t₁

④將染色體CH₁從刪除點開始，將長度DLen的基因段刪除，得到子個體CH₁′，并將刪除的基因段插入染色體CH₂中，得到轉換體CH₂*；

⑤將轉換體CH₂*中的重復基因去除，得到子個體CH₂′

⑥如果子個體CH₂′的長度超長，則對其進行截尾操作。

C、變異算子的處理

染色體的變異操作步驟如下：

①計算染色體長度Len；

②隨機產生一個[1，Len]之間的自然數C，作為變異點個數；

③c＝1；

④隨機產生一個與上一輪不重復的[1，Len]之間的自然數，作為變異點；

⑤隨機產生一個[0,1]之間的數r，如果r≤P_m，則轉⑥，否則直接轉⑦；其中P_m為變異概率。

⑥隨機產生一個[1,N]之間的在染色體中不存在的自然數，將父個體在變異點處的基因用這個自然數取代；

⑦c＝c+1；

⑧如果c>C，退出變異，否則轉④。

D、種群初始化

染色體的種群初始化具體步驟如下：

①設置種群規模Gsize；

②I＝1；

③如果I≤Gsize，則轉④，否則結束初始化；

④隨機設置染色體長度

⑤隨機產生Len個[1,N]之間的不重復的自然數，形成一條染色體Ind；

⑥判斷染色體Ind是否已經在種群中存在，如果存在則轉④，否則轉⑦；

⑦I＝I+1；

⑧轉③。

2.根據權利要求1所述一種可變長染色體編碼的混合并行遺傳聚類算法，其特征在于，所示可變長染色體的適應度函數如下：

3.根據權利要求1所述一種可變長染色體編碼的混合并行遺傳聚類算法，其特征在于，本算法的停止標準為：進化代數超過最大遺傳代數GNUM或群體平均適應度值連續多代遺傳后仍無變化時，本遺傳算法停止。