0 引言
產(chǎn)品裝配序列規(guī)劃作為產(chǎn)品生命周期的重要一環(huán)，在產(chǎn)品設(shè)計開發(fā)過程中占有很重要的地位，因為產(chǎn)品設(shè)計總費用40%～60%被花費在裝配勞動中，如何在給定產(chǎn)品在設(shè)計方案的條件下，尋找滿足幾何約束以及其它約束條件（工藝、裝配成本等）的合理可行的裝配序列一直是裝配工藝師所面臨的富有挑戰(zhàn)性的工作。好的裝配序列規(guī)劃已經(jīng)被視為減小裝配難度、減少裝配工具以及縮短裝配時間的實用方法。裝配序列規(guī)劃問題的本質(zhì)是一個NP組合優(yōu)化難題，傳統(tǒng)的裝配序列規(guī)劃的方式有兩種：一是基于裝配工程師的知識以及經(jīng)驗，二是圖搜索算法。方法一受設(shè)計者的知識局限性和主觀性影響較大，尤其是對于復(fù)雜零件的裝配工藝，設(shè)計出的裝配序列常常不是最優(yōu)的，甚至是不可行的。方法二的局限性在于當產(chǎn)品零件數(shù)目較多時，將會出現(xiàn)裝配序列組合爆炸的問題。20世紀90年代以來，人工智能被運用到組合優(yōu)化求解問題中，并取得了一些成就。包括模擬退火算法、人工神經(jīng)網(wǎng)絡(luò)、蟻群算法、遺傳算法及其相關(guān)混合算法。因遺傳算法具有搜索速度快、算法簡單，無需遍歷整個解空間就能找到一個最優(yōu)或次最優(yōu)解，能有效解決組合優(yōu)化中得組合爆炸問題，修改染色體的編碼方式和適應(yīng)度函數(shù)可解決不同的優(yōu)化問題等特點，遺傳算法被廣泛的運用到裝配序列規(guī)劃問題的求解。
1 零件可行裝配方向推理及裝配基準件選擇
1.1 遺傳算法的相關(guān)研究及改進
Bonnevil等首先將遺傳算法引入裝配規(guī)劃設(shè)計中，但他們的算法效果受初始迭代值的影響，而且要求初始序列都是有效的；Romeo M Marian等在建立關(guān)聯(lián)矩陣和優(yōu)先關(guān)系矩陣的基礎(chǔ)上，通過向?qū)阉魉惴ㄉ煽尚械难b配序列后，再用遺傳算法對可行的裝配序列進行優(yōu)化，該方法也要求初始序列都是有效的；楊鵬等改進了傳統(tǒng)的基因算法，通過交叉和多層次變異來實現(xiàn)基于基因組編碼表示的多信息裝配序列的并行優(yōu)化；周開俊等在楊鵬的研究基礎(chǔ)上考慮子裝配體穩(wěn)定性的目標函數(shù)，采用帶記憶的遺傳算法進行裝配序列規(guī)劃；劉誠等將遺傳學(xué)原理的基因修復(fù)技術(shù)引入用于求解裝配序列規(guī)劃問題的遺傳算法，利用基因“修復(fù)”操作，將子代個體中違反先序約束的基因“修復(fù)”為有效基因，從而保證了整個種群的基因多樣性，避免了進化過早地收斂于局部最優(yōu)解�；趲缀胃缮婢仃嚨幕A(chǔ)推導(dǎo)并優(yōu)化裝配序列，但是忽視了裝配過程中裝配基準和零件裝配優(yōu)先關(guān)系。
有鑒于此，采用改進的遺傳算法，考慮裝配基礎(chǔ)件對產(chǎn)品的裝配序列進行規(guī)劃研究。通過該算法，獲得一條滿足幾何約束、符合實際裝配過程的高效率產(chǎn)品裝配序列，用以指導(dǎo)產(chǎn)品的實際裝配。
1.2 零件裝配方向推理和可行性判斷
在笛卡兒直角坐系下，零部件的裝配方向采用該坐標系的坐標軸方向，一個裝配序列的幾何可行性是指：至少存在一個坐標軸方向使得將某一零部件裝配到位時，而不與其他已裝配好的零部件發(fā)生干涉。為評價裝配序列的幾何可行性，采用干涉矩陣I描述裝配過程中零部件間的幾何優(yōu)先關(guān)系。
假定有n個零件參與裝配，那么干涉矩陣是一個n行、3×n列的矩陣，3代表零件在+X、+Y、+Z的3個裝配方向。其元素Iijx表示了零件j沿+X方向裝配時與零件i的干涉情況，判定規(guī)則如下：如果零件j沿+X方向裝配到位與零件i發(fā)生干涉，則Iijx=1；反之則Iijx=0。零件j沿-X方向裝配與零件i干涉的情況即Iij-x，與零件i沿+X方向裝配與零件j干涉的情況相同，由元素Iijx表示，規(guī)定Ii=0。同理，可以確定Iijy和Iijz的值。
現(xiàn)設(shè){P1，P2，…Pm}為零件Pi裝配前已經(jīng)裝配完的零件序列，則零件Pi的可行裝配方向可由式(1)～式(6)判定。
其中，I[i][j]對應(yīng)干涉矩陣中的元素，U表示矩陣元素求或運算，I的維數(shù)取決于裝配的維數(shù)，二維的情況取2，三維的情況取3。對于序列{P1，P2，…，Pm，Pi}是否為幾何可行裝配序列取決于式(1)～式(6)的結(jié)果，當式(1)～式(6)中至少存在一個為零時，例如式(1)的結(jié)果為0，則說明Pi可從+X方向裝配到位而不與P1，P2，…，Pm發(fā)生干涉，反之，若式(1)～式(6)的結(jié)果全不為零，則P1，P2，…，Pm，Pi是不可裝配的。
1.3 裝配基準件的選擇
1.1節(jié)從幾何角度上推理了零件的裝配方向，其并不涉及裝配初始零部件。現(xiàn)實產(chǎn)品裝配過程中，通常會裝配一個零件固定不動，其余零部件均以該零件為裝配基準進行裝配。一個裝配體包含n個零件，所有可能的裝配序列為，n!個，當指定了基準件后可能的裝配序列為(n-1)!，搜索空間變?yōu)橐郧暗?／n。可見基準件最先裝配作為一條啟發(fā)式規(guī)則可以在很大程度上減小搜索空間，提高裝配序列生成的效率�；鶞始倪x取對裝配操作的難度、裝配夾具的設(shè)計等產(chǎn)生重大的影響，基準件的選擇一般遵循以下幾個原則：與其它零件連接數(shù)多；重量大、重心低；體積大；剛性大；一般避免選用易碎的、貴重的零件做基準件，例如傳動軸、齒輪等。
2 基于遺傳算法的裝配序列規(guī)劃方法
在考慮基礎(chǔ)件的情況下，設(shè)計了相應(yīng)的交叉算子、變異算子和適應(yīng)度函數(shù)，對產(chǎn)品的裝配序列進行規(guī)劃，用以獲得滿足相關(guān)約束條件的裝配序列。
2.1 編碼
采用實數(shù)序列的遺傳算法編碼求解產(chǎn)品裝配序列規(guī)劃問題，染色體的一個基因用以編碼一個待裝配零部件，每個基因所在染色體的位置代表了相應(yīng)待裝配零部件的在該裝配順序中的位置。群體的初始化、交叉操作及變異操作中各零件的序號僅出現(xiàn)．一次。例如染色體3-1-4-2-6-5-9-8-7，該染色體首先裝配的零部件為3，其后，裝配零部件1，依此類推。
2.2 交叉算子
采用如下的部分交叉重組方法，具體方式如下。
a.隨機在種群中選擇2條染色體A，B，隨機在染色體中選擇一個交配區(qū)域。2父染色體及交配區(qū)域選定為：
b.將B的交配區(qū)域加到A的交叉點后，將A的交配區(qū)域加到B的交叉點后得到：
c.在A＇，B＇中依次刪除與交配區(qū)相同的零部件編碼得到最終的2子染色體為：
這種交叉方法在能夠確�；鶞始奈恢迷谌旧w的最前端。
2.3 變異算子
每一代種群以機率Pm進行變異，一旦變異操作發(fā)生，隨機挑選K條染色體進行變異，且當染色體的基因個數(shù)為奇數(shù)時，從該染色體的第二位基因開始．每相鄰2個基因前后交換；當染色體的基因個數(shù)為偶數(shù)時，從該染色體的第三位基因開始，每相鄰2個基因前后交換。通過這樣的變異操作不僅最大限度地打破了裝配序列的排列順序，同時能夠確�；鶞始奈恢迷谌旧w的最前端。
2.4 適應(yīng)度函數(shù)設(shè)計
遺傳算法中適應(yīng)度函數(shù)的設(shè)計將待求解問題的目標函數(shù)與種群的每個個體聯(lián)系起來，通過將待求解問題的目標函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)，再通過適應(yīng)度函數(shù)求得個體的適應(yīng)度，適應(yīng)度值高的個體遺傳到下一代的幾率較大，反之，適應(yīng)度值低的個體遺傳到下一代的幾率較小。影響裝配效率的因素很多，僅從裝配方向的改變次數(shù)、裝配工具的更改次數(shù)、子裝配的穩(wěn)定性、基準件的位置四個方面考慮設(shè)計適應(yīng)度函數(shù)。
a.裝配換向次數(shù)C。對某一給定裝配序列，由1.1節(jié)可以推理零部件的裝配方向。當相鄰的2個零部件裝配方向改變時，序列的裝配換向次數(shù)加1。該指標反映了裝配操作的復(fù)雜性信息。
b.裝配工具的更換次數(shù)To通過判斷相鄰2個零部件裝配時所使用的裝配工具是否相同，累加計算出給定裝配序列的裝配工具改變次數(shù)，該指標量化表示了裝配序列的聚合性。T越小，裝配工具更換的次數(shù)越小，裝配效率越高。
c.裝配體的穩(wěn)定性。它是指某一裝配操作所涉及的2個子裝配體在重力和建立裝配所需力的作用下，保持各自內(nèi)部裝配關(guān)系的能力。定義穩(wěn)定聯(lián)接矩陣SN×N，其中矩陣元素Sij表示零部件i與零部件j之間的聯(lián)接關(guān)系，當i與j存在穩(wěn)定聯(lián)接關(guān)系時Sij=2，當i與j存在接觸聯(lián)接關(guān)系時Sij=1，當i與j不存在聯(lián)接關(guān)系時Sij=0。穩(wěn)定聯(lián)接指有強制約束零件之間相互移動的聯(lián)接，包括螺紋聯(lián)接、軸與孔的過盈聯(lián)接、O型圈聯(lián)接和卡簧聯(lián)接。則一個裝配序列的裝配穩(wěn)定性就可以用1×（N-1）的向量K={k2，k3，…，kn}，其值S如式(7)所示。裝配體的穩(wěn)定性直接影響到裝配操作的可靠性、夾具和工具的復(fù)雜性。
式中，n為裝配零件總數(shù)；S值越大裝配序列的穩(wěn)定性越好，0≤S≤2n-2。
d.基準件的位置。如1.3節(jié)所述，基準件的裝配應(yīng)該在第一位，在初始種群中存在滿足幾何約束的裝配序列，但是居首的零件并非裝配基準件，則需要對裝配基準件居首的可行裝配序列與裝配基準件非居首的可行裝配序列予以區(qū)分。通過區(qū)分，一方面能保持種群的多樣性；另一方面對裝配基準件居首的可行裝配序列的適應(yīng)度值予以加權(quán)，提高該序列的適應(yīng)度值，保證其在種群中的競爭性。
綜上所述，適應(yīng)度函數(shù)設(shè)計如下：
式中，S為種群的各裝配序列，當裝配序列滿足幾何約束且基礎(chǔ)件位置位于序列非首位時取式(8)第1式，當裝配序列滿足幾何約束且基礎(chǔ)件位置位于序列首位時取式(8)第2式，當裝配序列不滿足幾何約束式(8)第3式；F(S)為裝配序列的適應(yīng)度函值；ω1，ω2，ω3，ω4為權(quán)重系數(shù)；P為懲罰系數(shù)，根據(jù)經(jīng)驗，取ω4=0.8，ω1+ω2+ω3=1，取P=2。
3 遺傳算法執(zhí)行步驟
按照遺傳算法的一般思路，結(jié)合裝配序列規(guī)劃應(yīng)用的實際情況，在考慮基準件的基礎(chǔ)上，該算法步驟如下：
步驟1。設(shè)定初始種群大小pop、交叉概率Pc、基因組變異概率Pm。
步驟2。確定初始種群并將其作為最初的父代種群；先隨機生成初始種群，然后，在DELMIA軟件中通過虛擬拆卸的方式獲得一些裝配序列，最后，將通過虛擬拆卸的方式獲得的這些裝配序列隨機替換初始種群的裝配序列，將替換后的種群作為最初的父代種群。
步驟3。根據(jù)事先建立的裝配體干涉矩陣，先從幾何約束角度判斷初始種群中個體的可行性，再對幾何約束可行的個體判斷居首位置的零件判斷是否為基準件，最后根據(jù)式(8)分別計算初始種群個體的適應(yīng)度值。
步驟4。確定個體選擇算法，選擇輪賭盤選擇方法。
步驟5。當優(yōu)化結(jié)果不滿足終止條件時。
a.從群體中隨機兩兩選擇出不同個體作為親本，用交叉概率來確定染色體是否進行交叉操作。
b.用變異概率來確定染色體是否進行了交叉操作。
c.用交叉和變異產(chǎn)生與父代相同個數(shù)的子代。
d.同步驟3判斷新個體的可行性，計算新個體的適應(yīng)值。
e.通過選輪賭盤選擇方法得到pop個新的個體，并用這些新的個體更新原始種群。
步驟6。當?shù)螖?shù)達到預(yù)先設(shè)定的某值時，輸出適應(yīng)度值最高的個體，即為優(yōu)化的裝配序列。算法流程圖如圖1所示。
圖1 算法流程
4 實例驗證
為驗證算法的有效性，采用Matlab編程軟件驗證分析裝配基準件的改進遺傳裝配序列規(guī)劃算法，并以如圖2所示的某鏈輪為例進行了裝配仿真驗證，出于驗證過程的簡便化目的，對鏈輪做了以下簡化：①由于鏈輪的對稱結(jié)構(gòu)，故只考慮了鏈輪一側(cè)的裝配，如圖3所示；②規(guī)劃過程中未出現(xiàn)子裝配體的裝配過程；③螺栓一般只考慮一組。初始種群中的個體均以隨機的方式產(chǎn)生，并加入由DELMIA軟件虛擬拆卸得到的可行裝配序列，用以改善裝配序列種群的組成成份。在程序運行時，初始種群的規(guī)模pop=50，迭代條件設(shè)定為gmax=50，交叉概率和變異概率(Pc，Pm)分別取0.8，0.1。最終規(guī)劃出的鏈輪裝配序列如表1所示，圖4為pop，Pc，Pm分別取50，0.8，0.1時各代種群的平均適應(yīng)度函數(shù)值圖，該序列的適應(yīng)度函數(shù)值是0.1866。
圖2 鏈輪
圖3 鏈輪左側(cè)爆炸圖
表1 裝配序列規(guī)劃結(jié)果
圖4 種群各代平均適應(yīng)度值
5 結(jié)束語
在考慮裝配基準件的基礎(chǔ)上，設(shè)計和改進了規(guī)劃裝配序列遺傳算法，通過加入基礎(chǔ)件后的改進算法，獲得了更貼近實際裝配過程的產(chǎn)品裝配序列。該算法對初始裝配序列無特殊要求，初始種群加入由DELMIA軟件虛擬拆卸得到的可行裝配序列，由于這些裝配序列帶有經(jīng)驗知識成份，其能有效地改善裝配序列種群的組成成份，加快算法向最優(yōu)解或近優(yōu)解的收斂速度。通過實例證明，由該方法快速搜索到最優(yōu)或近優(yōu)裝配序列，能夠用于指導(dǎo)產(chǎn)品實際裝配過程。
核心關(guān)注：拓步ERP系統(tǒng)平臺是覆蓋了眾多的業(yè)務(wù)領(lǐng)域、行業(yè)應(yīng)用，蘊涵了豐富的ERP管理思想，集成了ERP軟件業(yè)務(wù)管理理念，功能涉及供應(yīng)鏈、成本、制造、CRM、HR等眾多業(yè)務(wù)領(lǐng)域的管理，全面涵蓋了企業(yè)關(guān)注ERP管理系統(tǒng)的核心領(lǐng)域，是眾多中小企業(yè)信息化建設(shè)首選的ERP管理軟件信賴品牌。
轉(zhuǎn)載請注明出處：拓步ERP資訊網(wǎng)http://www.oesoe.com/
本文標題：基于遺傳算法的產(chǎn)品裝配序列規(guī)劃研究
本文網(wǎng)址：http://www.oesoe.com/html/solutions/1401938385.html
相關(guān)文章
