基于改進遺傳算法的裝配序列優化

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

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

0 前言

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

1 改進遺傳算法

1.1 裝配序列規劃問題

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

1.2 染色體的定義

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

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

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

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

1.3 算法步驟

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

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

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

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

5)進行遺傳操作,交叉和變異。

6)產生新一代種群,進行適應度函數的計算。

7)設定適應度條件,判斷是否滿足條件。

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

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

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

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

1.4 遺傳算子

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

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

1.5 建立干涉矩陣

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

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

1.6 裝配方向的確定

對一個零件i的裝配方向進行分析時,主要是根據已經裝配好的上一個零件決定,根據下面布爾或運算公式進行判斷:

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

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

2 實例分析

結合馬鈴薯種植覆膜機的減速器裝置進行分析,在對裝置進行分析時對裝置進行了適當的簡化,把部分零件進行了刪減,并對過于重復的零件進行了整合,具體如圖3所示,共整合標注成25個零件。

圖3 馬鈴薯種植覆膜機減速器

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

表2 遺傳算法與改進遺傳算法的結果對比

由表2遺傳算法與改進遺傳算法的結果對比可以看出,加入干涉矩陣和添加裝配零件的裝配方向,裝配工具和裝配類型等約束信息,通過幾何約束和工藝約束,排除不可行的裝配序列,縮小解空間,使算法快速收斂,能在較短的時間內實現最優序列,達到預期的改進效果。實驗結果表明改進算法具有收斂快,效率高,實用性強的優點。

表3 裝配序列優化結果

3 結語

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

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

[2]楊鵬,劉繼紅,管強.面向裝配序列優化的一種改進基因算法[J].計算機集成制造系統,2002,8(6):467-471.

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

[4]敬石開,李連升,曾森,等.面向產品裝配序列規劃的智能優化算法庫[J].計算機輔助設計與圖形學學報,2010,22(9):1593-1599.

[5]彭濤,李世其,王峻峰,等.基于增強人機交互技術的虛擬裝配[J].計算機輔助設計與圖形學學報,2009,21(3):354-361.

[6]邢彥鋒,來新民,金隼,等.改進遺傳算法在裝配操作優化中的應用[J].計算機輔助設計與圖形學學報,2007,19(10):1298-1302.

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

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