[發明專利]一種基于動態規劃與遺傳算法的裝配序列規劃方法及裝置

有效

• 申請號: 201410120736.2
• 申請日: 2014-03-27
• 公開（公告）號: CN103870658B
• 公開（公告）日: 2017-06-30
• 發明（設計）人: 王鵬;湯志鵬;熊召;蘇虎;陶晶
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06N3/12
• 代理公司: 中科專利商標代理有限責任公司11021
• 代理人: 宋焰琴

1.一種基于動態規劃與遺傳算法的裝配序列規劃方法，其包括：

步驟1：對于待裝配體，根據各零件間的裝配關系將待裝配體分解成多個子模塊，其中各子模塊間的零件級干涉低于第一預定值，多個子模塊的數量不高于第二預定值；

步驟2：根據各子模塊之間的模塊級干涉關系建立第一空間干涉矩陣和第一裝配效率關系干涉矩陣；

步驟3：根據所述第一空間干涉矩陣和第一裝配效率關系干涉矩陣，使用動態規劃算法求取各個子模塊之間的相對裝配順序；

步驟4：根據各個子模塊內部各零件間的干涉關系建立第二空間干涉矩陣和第二裝配效率關系干涉矩陣；

步驟5：根據所述第二空間干涉矩陣和第二裝配效率關系干涉矩陣，使用遺傳算法求取各個子模塊中各個零件間的相對裝配順序；

步驟6：綜合各個子模塊間的相對裝配序列與各個模塊內的相對裝配序列，得到待裝配體的總體裝配序列；

其中，步驟3中所述使用動態規劃算法求取各個子模塊之間的相對裝配順序具體可以通過對下述方程進行迭代求解獲得：

其中，V為劃分得到的各個子模塊的集合，f(V,B)表示安裝了集合V中的所有子模塊，且最后安裝的子模塊為B時所需的最小代價；B表示集合V中的子模塊，r_ki為第一空間干涉矩陣中的元素，p_ji為第一裝配效率關系干涉矩陣中的元素，i，j，k取值分別為1至集合V的元素數目；

其中，第一空間干涉矩陣中的元素r_ki表示安裝了第k個零件后，對安裝第i個零件所造成的空間干涉情況；第一裝配效率關系干涉矩陣中的元素p_ji表示安裝了第j個零件后，緊接著安裝第i個零件對裝配效率造成的影響。

2.如權利要求1所述的方法，其中，步驟5具體包括以下步驟：

步驟51：隨機生成M條染色體組成種群，其中每個染色體表示具有n個零件的子模塊的裝配序列，其中染色體上的第i個基因代表在第i步被裝配的零件；

步驟52：利用第二空間干涉矩陣和第二裝配效率關系干涉矩陣計算當前種群中每條染色體的適應度函數值，所述適應度函數值用于表示所述染色體表示的裝配序列的優劣程度；

步驟53：若滿足迭代停止條件，則轉步驟58；

步驟54：選取適應度函數值最低的M條染色體組成下一代種群；

步驟55：根據交叉概率從種群中選取父代染色體進行交叉操作生成子代染色體，并將所述子代染色體加入下一代種群；

步驟56：根據變異概率從種群中選取父代染色體進行變異操作生成子代染色體，并將子代染色體加入下一代種群；

步驟57：使用下一代種群替換當前種群，迭代次數加1，并轉步驟52；

步驟58：從當前種群中選出適應度函數值最小的染色體對應的裝配序列作為對應子模塊的最優裝配序列。

3.如權利要求2所述的方法，其中，所述適應度函數值如下計算：

$f=\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\underset{j=i+1}{\overset{n}{\mathrm{\Σ}}}{r}_{ij}+\underset{i=2}{\overset{n}{\mathrm{\Σ}}}{p}_{(i-1)i}$

其中，f表示適應度函數值，n表示子模塊內的零件個數，r_ij表示第二空間干涉矩陣中的元素，p_(i-1)i為第二裝配效率關系干涉矩陣中的元素。