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

無效

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

技術領域

本發明涉及機構運動鏈同構識別方法，特指一種用于機構創新設計及智能CAD中機構 運動鏈同構識別方法。

背景技術

由于運動鏈同構識別應用的廣泛性和在機構創新設計及智能CAD中的重要地位，近半 個世紀以來，專家和學者提出了很多種機構運動鏈同構識別方法，大致可分為如下幾大類：

1、基于鄰接矩陣特征多項式的同構判定方法。

2、基于編碼的同構判定方法。

3、基于哈明串的同構判定。

4、基于特征值和特征向量的同構判定方法。

上述各方法在應用中，機構運動鏈同構識別中出現誤識、漏識的概率較大，可靠性較 差，并且隨著運動鏈構件的增多，識別的時間耗費嚴重，效率很低，具體表現為：

1、基于特征多項式法的同構判別方法以特征多項式作為指標來判別同構僅僅只是同 構判別的必要條件而非充分條件，這必然導致很多失效的反例；并且這種方法的另外一個 不足是其不可以編碼。

2、基于編碼的同構判別方法從理論上來說具有編碼唯一性和可解碼性的優點，并且 可以用此來對運動鏈進行拓撲分類。但是到目前為止，大多數被提出的方法都只能有效判 別10桿以內的運動鏈。

3、基于哈明碼的同構判別方法的失效性已成為事實，而且在什么情況下一階哈明串 的判別方法失效還是未知，而二階哈明串的計算量則很大。

4、基于特征值和特征向量的同構識別方法在出現相同的特征值時，尋找兩圖特征向 量的一一對應關系是十分復雜的，并且這種方法也不是基于編碼的方法。

發明內容

本發明的目的是為克服已有的設計方法的缺陷、解決現有機構創新設計、機構同構識 別效率低的問題、一步促使機構創新設計向高效及低成本的方向發展而提供一種基于偽雜 交混合遺傳算法的機構運動鏈同構識別方法。

本發明技術方案是依次采用如下步驟：

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表示為：