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