[發明專利]基于偽雜交混合遺傳算法的機構運動鏈同構識別方法

無效

• 申請號: 200910184138.0
• 申請日: 2009-08-25
• 公開（公告）號: CN101655928A
• 公開（公告）日: 2010-02-24
• 發明（設計）人: 楊平;曾科翰
• 申請（專利權）人: 江蘇大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06F17/50
• 代理公司: 南京知識律師事務所
• 代理人: 汪旭東

1.一種基于偽雜交混合遺傳算法的機構運動鏈同構識別方法，其特征是依次采用如 下步驟：

1)根據機構運動鏈的結構形成其對應的機構拓撲圖；

2)根據機構拓撲圖設定鄰接矩陣的遺傳編碼；

3)取待判定的兩機構拓撲圖鄰接矩陣確定目標函數，計算每個個體的目標函數值 和適應度；目標函數為：C＝TAT^T，式中，d為個體長度， T＝P₁P₂……P_n，其中P_i為矩陣，A、B為兩個機構拓撲圖的鄰接矩陣，C為鄰接矩陣A 經過變換矩陣T進行行變換和列變換后得到的矩陣；

4)采用偽雜交算子，在隨機產生的父代群體中隨機選取兩個個體x、y，隨機產生兩 個雜交點k₁、k₂進行空中擴展；從擴展生成的中間種群中選擇兩個個體進行初步局部尋 優；

所述兩個個體x、y表示為：

x=(x1,···,xk1,xk1+1,···,xk2-1,xk2,···,xd);]]>

y=(y1,···,yk1,yk1+1,···,yk2-1,yk2,···,yd),]]>(0≤k₁≤k₂≤d)，d為個體長度；

令tx＝x，ty＝y，對x進行如下操作：

步驟1：令i＝k₁+1；

步驟2：令j＝0；

步驟3：如果tx_j≠ty_i，則j＝j+1，重復步驟3；

步驟4；如果(i≠j)∩(k₁+1≤j≤k₂-1)，則轉步驟5；否則轉步驟6；

步驟5：交換x_i和x_j；

步驟6：i＝i+1，如果i＝k₂，結束，否則轉步驟2；

對y進行如下操作：

步驟1：令i＝k₁+1；

步驟2：令j＝0；

步驟3：如果ty_j≠tx_i，則j＝j+1，重復步驟3；

步驟4：如果(i≠j)∩(k₁+1≤j≤k₂-1)，則轉步驟5；否則轉步驟6；

步驟5：交換y_i和y_j；

步驟6：i＝i+1；如果i＝k₂，結束；否則轉步驟2；

所述初步局部尋優的步驟為：

步驟1：令i＝1；

步驟2：如果y_i≠i，則交換x_i和得到x′=(x1,···,xi-1,xyi,xi+1,···,xyi-1,xi,xyi+1,···,xd);]]>否則轉步驟4；

步驟3：若F(x′)＞F(x)，則x＝x′；

步驟4：i＝i+1，如果i＞d，則結束；否則轉步驟2；

5)結合局部搜索算子形成偽雜交混合遺傳算法，進行機構運動鏈同構識別的運算和仿真； 局部搜索算子步驟如下：

步驟1：令i＝1；

步驟2：令j＝1；

步驟3：如果j≠i，則交換x_i和x_j的位置，得到x′；否則轉步驟5；

步驟4：比較x和x′的適應度，如果F(x′)＞F(x)，則x＝x′；

步驟5：j＝j+1；如果j≤d，則轉步驟3；

步驟6：i＝i+1；如果i≤d，轉步驟2；否則結束。