基于改進(jìn)遺傳算法的裝配序列優(yōu)化

閻樹田, 賈曉鋒、, 賀成柱, 陶燚

(1.蘭州理工大學(xué) 機(jī)電工程學(xué)院,甘肅 蘭州730050;2.甘肅省機(jī)械科學(xué)研究院,甘肅蘭州730030)

0 前言

裝配序列規(guī)劃在產(chǎn)品裝配設(shè)計(jì)中扮演著重要的角色,裝配序列的選擇直接關(guān)系到產(chǎn)品的裝配效率和品質(zhì)[1]。序列規(guī)劃[2]就是在給定產(chǎn)品設(shè)計(jì)方案的情況下,探索合理可行的裝配序列,并從中選出最優(yōu)的序列,用以指導(dǎo)產(chǎn)品的裝配,達(dá)到預(yù)期的目標(biāo)。在裝配序列規(guī)劃研究中,最新的研究成果主要表現(xiàn)為:基于現(xiàn)代優(yōu)化算法進(jìn)化生成可行的裝配序列等;基于人機(jī)交互方法,通過將人的主動(dòng)決策和裝配知識導(dǎo)航相結(jié)合求解裝配序列;基于知識求解裝配序列等[3－7]。這些方法的主要目的是生成結(jié)果接近或達(dá)到最優(yōu)的裝配序列。裝配序列規(guī)劃通過對裝配信息的分析、提取、總結(jié)生成可行的序列規(guī)劃,可以提高裝配能力,縮短裝配時(shí)間,降低裝配成本,提高裝配精度,增加裝配的可靠性,減少產(chǎn)品的上市時(shí)間。

1 改進(jìn)遺傳算法

1.1 裝配序列規(guī)劃問題

裝配序列規(guī)劃的目標(biāo)是求解滿足各種裝配約束條件,得出具有最優(yōu)的可行裝配序列[8]。在產(chǎn)品裝配過程中,一旦出現(xiàn)違反零件之間的裝配幾何約束關(guān)系,必將出現(xiàn)裝配零件的相互干涉,影響裝配效率。操作換向、裝配工具及裝配類型等都是影響裝配效率的主要因素。在企業(yè)追求快速反應(yīng)的時(shí)代,產(chǎn)品在裝配過程中,裝配方向的改變,裝配工具的更換以及裝配類型的改變都直接影響裝配輔助時(shí)間,也增加產(chǎn)品的生產(chǎn)成本,使產(chǎn)品在競爭中處在不利的地位。

1.2 染色體的定義

復(fù)合基因稱為基因組片的編碼技術(shù),每個(gè)基因組片包括多個(gè)位碼,主要考慮4個(gè)特征元素:零件個(gè)數(shù)N,裝配工具T,裝配方向D,及裝配類型L。

Ni代表零件,Ti代表裝配工具,Di代表裝配的可行性方向,裝配方向只考慮與坐標(biāo)軸平行的＋x,－x,＋y,－y,＋z,－z6個(gè)方向(本文中出現(xiàn)兩個(gè)零件的裝配方向與x,y,z有一定夾角,特進(jìn)行簡化處理,以與夾角小的方向?yàn)闇?zhǔn)),Li代表零件的裝配類型,主要是面貼合,插入,軸對齊,焊接和鉚接等。

單個(gè)基因組的構(gòu)成,包括四個(gè)子段,Ni,Ti,Di,Li,例如(3123)這個(gè)基因組,代表的意義就是編號為3的零件,選用工具1,在＋y方向上,按第3種裝配類型進(jìn)行裝配。圖1表示每條染色體由n個(gè)基因組構(gòu)成。染色體的變異主要是各個(gè)基因組之間的變異。在進(jìn)行進(jìn)化時(shí),主要是零件的裝配方向,裝配工具,裝配類型參與變異計(jì)算,進(jìn)而實(shí)現(xiàn)整個(gè)裝配過程的進(jìn)化,計(jì)算結(jié)果直接是整個(gè)裝配過程的信息完備,算法收斂較快,效率較高。同時(shí)在計(jì)算時(shí),又充分利用遺傳算法的魯棒性強(qiáng)的特點(diǎn),即不需要過多外部信息,通過適應(yīng)度函數(shù)進(jìn)行評價(jià),得出最優(yōu)序列。

圖1 基因組片組成的染色體

1.3 算法步驟

1)確定實(shí)際問題參數(shù):裝配零件數(shù)目n,染色體長度,并對基因進(jìn)行編碼。

2)設(shè)定初始種群大小,交叉概率Pc,基因組變異概率Pm。

3)產(chǎn)生初始種群,并作為父代的種群。

4)輸入裝配體的干涉矩陣,匹配特征信息,從幾何約束和工藝約束判定初始種群的可行性,并計(jì)算適應(yīng)度值。

5)進(jìn)行遺傳操作,交叉和變異。

6)產(chǎn)生新一代種群,進(jìn)行適應(yīng)度函數(shù)的計(jì)算。

7)設(shè)定適應(yīng)度條件,判斷是否滿足條件。

8)不滿足終止條件時(shí),從種群中兩兩選擇不同的個(gè)體作為父代轉(zhuǎn)入步驟3。

9)滿足條件時(shí),輸出序列。

適應(yīng)度函數(shù)主要進(jìn)行評價(jià)的要素有幾何約束和工藝約束,幾何約束可以排除發(fā)生幾何干涉的序列,減小解的空間;工藝約束主要包括裝配方向,裝配工具,裝配類型等工藝信息,在實(shí)際生產(chǎn)裝配過程中這些都對裝配成本具有重要的影響。適應(yīng)度函數(shù):

nt裝配時(shí)更換工具的次數(shù),nd裝配時(shí)零件的換向次數(shù),nl零件裝配類型的變化次數(shù)。ωt是更換工具次數(shù)的加權(quán)系數(shù),ωd更換裝配方向次數(shù)的加權(quán)系數(shù),ωl裝配類型變化次數(shù)的加權(quán)系數(shù)。初始種群的產(chǎn)生可以通過多種方式,如專家給出,隨機(jī)設(shè)定,虛擬環(huán)境下的人工拆卸,或由以上基本方式綜合得到。

1.4 遺傳算子

遺傳計(jì)算中包括選擇算子、交叉算子、部分匹配交叉算子、次序交叉算子和變異算子。交叉和變異既相互配合又相互競爭使算法的搜索能力得到了提高,交叉算子的實(shí)質(zhì)就是父代與母代的基因組片進(jìn)行重組產(chǎn)生后代,使后代具有雙親的遺傳特征,本算法采取輪盤賭選擇,改進(jìn)部分匹配交叉算子和變異算子,圖2所示為改進(jìn)算法部分匹配交叉算子示意圖。

圖2 部分匹配交叉算子示意圖

1.5 建立干涉矩陣

在裝配過程中,為了使遺傳算法快速收斂,減少不必要的變異計(jì)算,在遺傳算法中加入了干涉矩陣,其主要是確定各個(gè)零件的裝配序列幾何可行性及可裝配方向,干涉矩陣I:

假設(shè)有n個(gè)零件參與裝配,那么干涉矩陣就是一個(gè)n行,3n列的矩陣,其元素Iijz表示零件j沿＋z方向裝配與零件i的干涉情況,具體取值判定規(guī)則:如果零件j沿＋z方向裝配到位時(shí)與零件i發(fā)生干涉,則Iijz＝1;反之,則Iijz＝0。零件j沿－z方向裝配與零件i干涉的情況,與零件i沿＋z方向裝配與零件j干涉的情況相同,由元素Ijiz表示。按照這種方法,可以確定Iijx和Iijy的值。每個(gè)零件在空間坐標(biāo)系中考慮＋x,＋y,＋z,－x,－y,－z這六個(gè)方向的裝配干涉情況,對圖3中馬鈴薯種植覆膜機(jī)減速器中標(biāo)注的序號1~12的零件的干涉矩陣進(jìn)行列舉如下矩陣所示,由于受篇幅限制其余13個(gè)零件的干涉矩陣按照上述判斷方法可以得出:

1.6 裝配方向的確定

對一個(gè)零件i的裝配方向進(jìn)行分析時(shí),主要是根據(jù)已經(jīng)裝配好的上一個(gè)零件決定,根據(jù)下面布爾或運(yùn)算公式進(jìn)行判斷:

Iij對應(yīng)干涉矩陣中各個(gè)元素,U表示矩陣元素的求或運(yùn)算,在三維坐標(biāo),根據(jù)式(3)~式(8)對圖3中的馬鈴薯種植覆膜機(jī)的減速器裝置進(jìn)行分析得到的可裝配零件方向如表1所示。

表1 裝配體中零件的可行方向

2 實(shí)例分析

結(jié)合馬鈴薯種植覆膜機(jī)的減速器裝置進(jìn)行分析,在對裝置進(jìn)行分析時(shí)對裝置進(jìn)行了適當(dāng)?shù)暮喕?把部分零件進(jìn)行了刪減,并對過于重復(fù)的零件進(jìn)行了整合,具體如圖3所示,共整合標(biāo)注成25個(gè)零件。

圖3 馬鈴薯種植覆膜機(jī)減速器

疊加代數(shù)取100,初始化選擇率,交叉率和變異率分別設(shè)置為0.7,0.8和0.3。從運(yùn)行過程中得到如表2兩種算法對比表,并得出改進(jìn)算法優(yōu)化后的最優(yōu)裝配序列如表3所示。

表2 遺傳算法與改進(jìn)遺傳算法的結(jié)果對比

由表2遺傳算法與改進(jìn)遺傳算法的結(jié)果對比可以看出,加入干涉矩陣和添加裝配零件的裝配方向,裝配工具和裝配類型等約束信息,通過幾何約束和工藝約束,排除不可行的裝配序列,縮小解空間,使算法快速收斂,能在較短的時(shí)間內(nèi)實(shí)現(xiàn)最優(yōu)序列,達(dá)到預(yù)期的改進(jìn)效果。實(shí)驗(yàn)結(jié)果表明改進(jìn)算法具有收斂快,效率高,實(shí)用性強(qiáng)的優(yōu)點(diǎn)。

表3 裝配序列優(yōu)化結(jié)果

3 結(jié)語

如何有效綜合利用幾何知識,算法和實(shí)際裝配常識等,使序列求解的功能和效率達(dá)到滿意的結(jié)果是改進(jìn)算法目的。改進(jìn)算法主要加入了干涉矩陣和裝配匹配特征,在運(yùn)算中直接排除了許多不合理的裝配序列,由表2遺傳算法與改進(jìn)遺傳算法的結(jié)果對比可以看出,改進(jìn)遺傳算法具有較好的收斂性能,能在較短的時(shí)間內(nèi)搜索到最優(yōu)裝配序列解。改進(jìn)算法是裝配序列規(guī)劃問題高效求解的一個(gè)方向,如果能在算法中自動(dòng)識別各零件的裝配穩(wěn)定性,同時(shí)突破有關(guān)機(jī)械裝配的傳統(tǒng)觀點(diǎn),從系統(tǒng)化、自動(dòng)化和智能化的新角度進(jìn)行研究,對裝配序列規(guī)劃有很大的現(xiàn)實(shí)意義,這也將是今后研究的重點(diǎn)內(nèi)容。

[1]寧黎華,古天龍.裝配序列規(guī)劃問題求解的一種混合算法[J].計(jì)算機(jī)集成制造系統(tǒng),2007,13(4):762-767.

[2]楊鵬,劉繼紅,管強(qiáng).面向裝配序列優(yōu)化的一種改進(jìn)基因算法[J].計(jì)算機(jī)集成制造系統(tǒng),2002,8(6):467-471.

[3]鄧明星,唐秋華,雷喆.基于蟻群算法的改進(jìn)裝配序列規(guī)劃方法[J].武漢大學(xué)學(xué)報(bào)(工學(xué)版),2013,46(2):246-251.

[4]敬石開,李連升,曾森,等.面向產(chǎn)品裝配序列規(guī)劃的智能優(yōu)化算法庫[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2010,22(9):1593-1599.

[5]彭濤,李世其,王峻峰,等.基于增強(qiáng)人機(jī)交互技術(shù)的虛擬裝配[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2009,21(3):354-361.

[6]邢彥鋒,來新民,金隼,等.改進(jìn)遺傳算法在裝配操作優(yōu)化中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2007,19(10):1298-1302.

[7]寧汝新,鄭軼.虛擬裝配技術(shù)的研究進(jìn)展及發(fā)展趨勢分析[J].中國機(jī)械工程,2005,16(15):1398-1403.

[8]張燁,寧汝新,劉檢華.面向虛擬裝配的裝配序列規(guī)劃技術(shù)研究[J].計(jì)算機(jī)集成制造系統(tǒng),2006,12(1):90-9.