[發(fā)明專利]一種基于遺傳算法的并行拆卸模型構(gòu)建方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201910036487.1
• 申請(qǐng)日: 2019-01-15
• 公開（公告）號(hào): CN109886458A
• 公開（公告）日: 2019-06-14
• 發(fā)明（設(shè)計(jì)）人: 張雷;金志峰;趙希坤
• 申請(qǐng)（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/00;G06Q50/04;G06N3/12
• 代理公司: 北京青松知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 11384
• 代理人: 鄭青松

1.一種基于遺傳算法的并行拆卸模型構(gòu)建方法，其特征在于，包括以下步驟：

(1)并行拆卸模型構(gòu)建

(1.1)連接矩陣G_c和優(yōu)先矩陣G_p

在拆卸混合圖中無(wú)向邊E和有向邊DE可以用穩(wěn)定連接矩陣和優(yōu)先關(guān)系矩陣矩陣表示，即：G＝{VF,VC,E,DE}可以分解為G_c＝{VF,E}和G_p＝{VF,DE}，如果G是一個(gè)含有N個(gè)功能件的混合圖，則和G_c、G_p分別為N維的連接矩陣、N維的優(yōu)先矩陣；

連接矩陣用G_c表示，即：

其中：表示功能件i和j之間的連接關(guān)系，當(dāng)功能件i和j之間有連接關(guān)系時(shí)，當(dāng)功能件i和j不存在連接關(guān)系時(shí)由于零件i和j之間無(wú)法形成連接關(guān)系，故

優(yōu)先矩陣用G_p表示，即：

其中:表示功能件j對(duì)i的約束關(guān)系；表示第j個(gè)功能件要在第i個(gè)功能件之前拆解；若表示第i個(gè)功能件不受第j個(gè)功能件的約束；

(1.2)拆卸并行度

并行拆卸旨在通過拆卸任務(wù)的并行化減少拆卸序列串行長(zhǎng)度以提高單位時(shí)間內(nèi)的拆卸效率；由拆卸并行度定義可知，允許同時(shí)拆卸單元數(shù)量的理論最大值稱為拆卸并行度，記為D_max；在并行拆卸中，若干個(gè)單元的同步拆卸行為稱為一個(gè)步驟，第k個(gè)步驟數(shù)記為D_k(1≤D_k≤D_max)；

(1.3)并行拆卸序列規(guī)劃

采用可變序列矩陣方法，描述并行拆卸下的拆卸序列：

在串行拆卸中，假設(shè)產(chǎn)品的拆卸單位為n，由于拆卸度為1，其拆卸序列可以表示為n×1的矩陣S＝{S₁,S₂…S_i…S_n}；類似的，在并行拆卸中，假設(shè)其拆卸單位為n，拆卸步數(shù)為m，用ls表示步長(zhǎng)，則并行拆卸序列可以矩陣Q表示為:

矩陣中同一行元素所代表的拆卸單元屬于同一拆卸步驟，其中拆卸單元間為并列關(guān)系，若此步驟中拆卸單元數(shù)小于拆卸并行度，則同行中缺省元素置為0；矩陣中不同行之間為不同的拆卸步驟，且行數(shù)大小即為步驟數(shù)大小；

為了后續(xù)便于遺傳算法編碼，拆卸序列矩陣分為拆卸單元序列和拆卸步長(zhǎng)序列兩部分，分別用實(shí)數(shù)進(jìn)行編碼；

(1.4)并行拆卸模型構(gòu)建

圖模型主要有無(wú)向圖模型、有向圖模型、與或圖模型和混合圖模型，采用拆卸混合圖模型來(lái)描述產(chǎn)品的約束信息：

拆卸混合圖可以表示為G＝{VF,VC,E,DE}，其中G表示混合圖；頂點(diǎn)VF＝{VF₁,VF₂,…,VF_n}為產(chǎn)品功能件，其中n為功能件的個(gè)數(shù)；VC為連接件；E表示為無(wú)向邊，表示零件之間的有接觸的約束關(guān)系；DE為有向邊，表示零件之間的非接觸優(yōu)先關(guān)系；

(2)建立拆卸總時(shí)長(zhǎng)模型，即優(yōu)化目標(biāo)：

其中為基本拆卸時(shí)間，工序P_i的拆卸時(shí)間為BT_i；表示方位更換時(shí)間，BCTI為轉(zhuǎn)過90°所用的時(shí)間，B_iB_i+1表示前后兩個(gè)工位所轉(zhuǎn)過的角度；為拆卸工具更換時(shí)間，TCTI是拆卸工具更換一次的所花費(fèi)的時(shí)間，T_i表示第i個(gè)零件拆卸工具；

(3)基于遺傳算法進(jìn)行工序優(yōu)化

遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，是通過各代種群進(jìn)行選擇、重組和變異搜索出適應(yīng)度高的個(gè)體，增加其在種群個(gè)體中的比例，最終找到最優(yōu)解的過程；

(3.1)基因編碼

編碼是應(yīng)用遺傳算法時(shí)要首先解決的問題，也是用遺傳算法解決問題的關(guān)鍵一步，結(jié)合產(chǎn)品拆卸的實(shí)際情況，染色的編碼方式采用零件序號(hào)編碼的實(shí)數(shù)編碼；

(3.2)交叉操作

交叉運(yùn)算是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式交換其他部分基因，從而形成新的個(gè)體；在OldChrom中隨機(jī)選擇兩個(gè)順序串U₁和U₂，并生產(chǎn)一個(gè)在區(qū)間[0,1]之間的隨機(jī)數(shù)r_k，如果r_k≤P_c,則進(jìn)行交叉操作，運(yùn)用單點(diǎn)交叉法進(jìn)行交叉操作，步驟如下：

(a)在區(qū)間中取一個(gè)均勻分布的隨機(jī)數(shù)k作為交叉點(diǎn)；

(b)將交叉點(diǎn)之前的基因按照在父輩U₁串中的順序復(fù)制到子輩O₁中；

(c)在子輩O₁交叉點(diǎn)后的基因要從另一個(gè)父輩U₂中進(jìn)行以此掃描；如在此基因在父輩中，則對(duì)下一基因進(jìn)行掃描；如果不存在，將此基因按照順序存放在子輩O₁中；

(3.3)變異操作

變異是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來(lái)代替，從而形成一個(gè)新的個(gè)體，具體方法如下：

(1)根據(jù)變異概率P_m隨機(jī)在種群中選擇若干染色體；

(2)設(shè)拆卸單元序列的長(zhǎng)度為n，在[1，n]之中隨機(jī)選擇一個(gè)基因位置i，判斷i和i+1的兩個(gè)基因?qū)?yīng)的工序是否滿足約束矩陣和接觸矩陣，如果是則進(jìn)行；

(3)根據(jù)新的拆卸單元序列重新生成拆卸步長(zhǎng)序列，并組成新的拆卸序列。