基于遺傳算法的分段裝配序列優(yōu)化研究

黃曉雪，李照輝

1.渤海船舶職業(yè)學(xué)院，遼寧 興城 125105；2.大連船舶重工集團(tuán)有限公司，遼寧 大連 116000

現(xiàn)代造船模式實(shí)現(xiàn)了由整體建造到分段建造再到分道建造的轉(zhuǎn)變過程，因此以往單純依靠工藝人員經(jīng)驗(yàn)編制的生產(chǎn)進(jìn)度方案已經(jīng)不能夠滿足“模塊化建造”的現(xiàn)代造船模式的要求[1]?；诖?，提出船舶分段裝配序列優(yōu)化研究這一問題，進(jìn)而指導(dǎo)船廠實(shí)際的生產(chǎn)裝配工作。

大多數(shù)的裝配序列優(yōu)化研究是圍繞一些零部件展開的，常用的裝配序列優(yōu)化大多采用基于優(yōu)先關(guān)系和圖論的方法和基于啟發(fā)式算法的求解方法[2]。通過大量的實(shí)驗(yàn)和數(shù)據(jù)對(duì)比不難發(fā)現(xiàn)：基于優(yōu)先關(guān)系和圖論這種方式研究空間大、評(píng)價(jià)系統(tǒng)繁瑣，導(dǎo)致搜索效率低，所以并不適合一些結(jié)構(gòu)比較復(fù)雜的大型構(gòu)件；基于啟發(fā)式算法的求解方法，不但可以有效地構(gòu)建問題模型，并且搜索能力強(qiáng)，能夠有效地避免基于優(yōu)先關(guān)系和圖論這種研究方式的缺點(diǎn)，研究空間適中、評(píng)價(jià)系統(tǒng)合理，因此對(duì)于一些結(jié)構(gòu)復(fù)雜的大型構(gòu)件普遍適用于此研究方法[3]。

由于船舶分段裝配是一個(gè)系統(tǒng)復(fù)雜、規(guī)模龐大的工作，本文根據(jù)這一特點(diǎn)，將研究問題的目標(biāo)函數(shù)設(shè)定為裝配序列優(yōu)化的評(píng)價(jià)準(zhǔn)則，并在優(yōu)化過程中引入遺傳算法來進(jìn)行目標(biāo)函數(shù)的計(jì)算和優(yōu)化，得出優(yōu)化后的裝配序列，并將其進(jìn)行可視化虛擬仿真，從而驗(yàn)證算法和目標(biāo)函數(shù)的有效性和合理性。

1 約束條件的選取

船體分段的裝配成本存在許多影響因素，裝配序列的好壞也有著各種各樣的評(píng)價(jià)準(zhǔn)則。船體分段裝配成本的影響因素主要有：現(xiàn)場的使用成本，材料的價(jià)格，焊接效率，吊裝工具的使用情況等?，F(xiàn)代造船模式采用“殼舾涂”一體化的建造方式，但是這種建造方式很難加以量化，所以本文只針對(duì)組立裝配對(duì)整個(gè)造船周期的影響[4]。在研究過程中，根據(jù)影響裝配的諸多因素進(jìn)行分析，總結(jié)組立裝配過程中的評(píng)價(jià)準(zhǔn)則，建立由連接關(guān)系、干涉關(guān)系、重定向次數(shù)、吊裝工具等組成的目標(biāo)函數(shù)優(yōu)化體系。

1.1 組立連接關(guān)系

任何一個(gè)組立在進(jìn)行裝配之前第一步要考慮的就是其裝配序列的幾何可行性，所以首先要建立組成平行中體分段中的各個(gè)組立的連接矩陣和干涉矩陣[5]。裝配關(guān)系成立的條件是既有組立與待裝配組立存在連接關(guān)系，繼而得出整個(gè)組立的連接關(guān)系矩陣。取Cij來代表組立i與組立j之間的連接關(guān)系，存在取1，不在連接關(guān)系取0，如式1-1。

根據(jù)上述連接關(guān)系矩陣判斷CiAm的值，進(jìn)而判斷組立Gi是否與其緊前裝配的組立之間存在連接關(guān)系，式中Ci代表某組立是否與在其之前裝配組立之間的連接關(guān)系，如式1-2。

1.2 組立干涉關(guān)系

干涉關(guān)系是通過兩個(gè)組立之間的干涉矩陣來進(jìn)行表示的，假設(shè)整個(gè)分段包含n個(gè)組立，則判定一個(gè)待裝配組立與既有n個(gè)組立之間的干涉關(guān)系可形成1×n的干涉矩陣，對(duì)每個(gè)組立干涉關(guān)系進(jìn)行判斷后可形成n×n的干涉矩陣，如式1-3。

取式中Iijdk來表達(dá)組立j靜止不動(dòng)，組立i從d k方向的無窮遠(yuǎn)處進(jìn)行裝配的過程中與組立j的干涉關(guān)系。若存在干涉關(guān)系則其取值為1，不存在干涉關(guān)系取值為0。

由上述分析可得平行中體分段的干涉矩陣，并可以求取一個(gè)已知裝配序列的干涉次數(shù)。第一個(gè)進(jìn)行裝配的組立不需要考慮干涉次數(shù)，之后每個(gè)進(jìn)行裝配的組立都要考慮其與之前裝配的組立之間的干涉次數(shù)。若組立沿某一方向d k進(jìn)行裝配，其中k為在組立i之前裝配的組立，取IAiakdk表示第i個(gè)進(jìn)行裝配的組立與在其之前裝配的任一組立之間干涉關(guān)系，Iikx，Iiky，Iikz表示其與在它之前裝配的組立在三個(gè)坐標(biāo)方向上的干涉關(guān)系，如式1-4。

則第個(gè)進(jìn)行裝配的組立其干涉關(guān)系如式1-5。

綜上，整個(gè)裝配序列的干涉次數(shù)In如式1-6。

1.3 組立重定向次數(shù)

船體分段裝配序列的評(píng)價(jià)標(biāo)準(zhǔn)很難加以量化，但是根據(jù)所研究問題的基本特點(diǎn)選取重定向次數(shù)為其中的一個(gè)標(biāo)準(zhǔn)對(duì)目標(biāo)函數(shù)進(jìn)行約束。假設(shè)某一已知的裝配序列為A={A1，A2，…An}，將組立的裝配方向表示為T r（Ai），則需要判斷相互連接的兩個(gè)組立裝配方向是否相同。假設(shè)某一已知的裝配序列為A={A1，A2，…An}，設(shè)δi為待裝配組立與其緊前裝配的組立之間是否發(fā)生重定向，若重定向?yàn)?，不重定向?yàn)?，則已知的裝配序列的重定向次數(shù)如式1-7。

1.4 吊裝工具改變次數(shù)

船體分段裝配過程中離不開吊裝工具，而吊裝工具的選擇很大程度上取決于起重機(jī)的吊裝能力，根據(jù)組立質(zhì)量和起重能力來選擇不同的起重設(shè)備，設(shè)起重能力分別為ma，mb，mc，md，ma＜mb＜mc＜md，則任一組立mi吊裝工具如式1-8。

假設(shè)某一已知的裝配序列為A={A1，A2，…An}，設(shè)ei為待裝配組立與其緊前裝配的組立之間是否發(fā)生吊裝工具的改變，若改變?yōu)?，不改變?yōu)?，則已知的裝配序列的吊裝工具改變次數(shù)如式1-9。

2 數(shù)學(xué)模型的建立

2.1 平行中體分段裝配序列優(yōu)化數(shù)學(xué)模型

根據(jù)上述約束條件可以建立一個(gè)包含連接關(guān)系、干涉關(guān)系、重定向次數(shù)、裝配工具改變次數(shù)的目標(biāo)函數(shù)體系，但體系中各個(gè)評(píng)價(jià)函數(shù)所占的比重需要根據(jù)層次分析法來確定。依據(jù)前述所提到的干涉關(guān)系、重定向次數(shù)、吊裝工具改變等約束條件，得到平行中體分段裝配序列優(yōu)化的數(shù)學(xué)模型如式2-1。

其中

本問題模型是一個(gè)函數(shù)最小化的問題，式中f1、f2、f3分別代表重定向函數(shù)、吊裝工具函數(shù)以及干涉函數(shù)。這些目標(biāo)函數(shù)都屬于數(shù)值越小，問題模型效果越好的子目標(biāo)，其中f3為裝配序列干涉信息的目標(biāo)函數(shù)，這個(gè)數(shù)值不是越小越好，而是不允許存在的，所以在處理f3的權(quán)重時(shí)，需要賦予其比較大的權(quán)重，而凸顯出其值的增大而產(chǎn)生的懲罰效果，使其對(duì)于整個(gè)目標(biāo)函數(shù)的影響極大，基于此將權(quán)重α1、α2、α3賦值為0.41、0.59、5。

2.2 基于遺傳算法的平行中體分段裝配序列求解步驟

步驟一：對(duì)于初始種群每個(gè)個(gè)體進(jìn)行編碼[6]，即包括n個(gè)個(gè)體，初始設(shè)置的數(shù)據(jù)包括種群的規(guī)模、所采用的交叉概率和變異概率、本算法擬采用的計(jì)算參數(shù)等，并初始化計(jì)數(shù)器t＝0。

步驟二：隨機(jī)初始化裝配序列種群P0（t）[7]，根據(jù)上述約束條件和目標(biāo)函數(shù)體系計(jì)算隨機(jī)產(chǎn)生的初代種群的適應(yīng)度值，并設(shè)置將適應(yīng)度值最高的個(gè)體將基因保存復(fù)制給下一代，得到新種群。

步驟三：設(shè)置交叉概率Pc對(duì)P0進(jìn)行交叉[7]，并以此概率進(jìn)行復(fù)制和組合得到交叉組合后的新一代的個(gè)體P1（t）=C r o ss ov er[P0（t）]。

步驟四：設(shè)置自適應(yīng)變異概率Pm進(jìn)行子一代的繁殖[8]，進(jìn)而得到經(jīng)過變異后的子二代個(gè)體P2（t）=M u t a ti o n[P1（t）]。

步驟五：終止原則的設(shè)定標(biāo)準(zhǔn)。若滿足終止原則，則輸出本算法的優(yōu)化結(jié)果，然后終止計(jì)算，得到優(yōu)化后的裝配序列；若不滿足終止原則，轉(zhuǎn)換到第三個(gè)步驟接著進(jìn)行計(jì)算[9]。

3 平行中體分段裝配序列優(yōu)化實(shí)例計(jì)算

想要確認(rèn)裝配序列優(yōu)化算法的正確性，需要以某平行中體分段為實(shí)例進(jìn)行運(yùn)算，選取平行中體分段進(jìn)行運(yùn)算的原因是由于平行中體分段的干涉矩陣相對(duì)來說比較簡單，能夠有效地減少系統(tǒng)運(yùn)算時(shí)間，提高系統(tǒng)運(yùn)算效率。本算法同樣適用于一些比較復(fù)雜的首尾分段，只是由于首尾分段的復(fù)雜性增加了系統(tǒng)的運(yùn)算時(shí)間。利用編程工具，根據(jù)算法建立一個(gè)裝配序列優(yōu)化系統(tǒng)對(duì)于提高裝配質(zhì)量、減少裝配工時(shí)耗費(fèi)有著重要意義。

利用CA TI A軟件中某平行中體分段模型確定出組立總數(shù)，點(diǎn)擊導(dǎo)入組立信息鍵將包含組立重量和吊裝工具的信息文件導(dǎo)入到裝配序列規(guī)劃輸入界面，干涉信息和連接關(guān)系矩陣的導(dǎo)入方法同上。設(shè)置本算法相關(guān)參數(shù)：種群規(guī)模為200，最大遺傳數(shù)為100，交叉概率1為0.9，交叉概率2為0.6，變異概率1為0.1，變異概率2為0.001。采用前述自適應(yīng)遺傳算法進(jìn)行編程，并按照數(shù)學(xué)模型進(jìn)行目標(biāo)函數(shù)設(shè)置，點(diǎn)擊開始計(jì)算，開始運(yùn)行程序，得到如下計(jì)算結(jié)果，如圖1所示。

圖1 裝配序列規(guī)劃輸出界面

根據(jù)進(jìn)化曲線可以分析出目標(biāo)函數(shù)的設(shè)置合理有效，目標(biāo)函數(shù)為求取最小值的過程，其整體呈現(xiàn)下降趨勢(shì)并逐漸穩(wěn)定到一個(gè)值，證明算法可以有效收斂并且運(yùn)算速度較快[10]。

4 結(jié)論

裝配序列優(yōu)化問題可以有效地降低船舶裝配成本，提高船舶裝配效率。本文根據(jù)某平行中體分段的裝配序列優(yōu)化問題提出了一個(gè)在幾何和工藝約束條件基礎(chǔ)上的包含干涉關(guān)系、重定向次數(shù)、裝配工具改變次數(shù)的目標(biāo)函數(shù)優(yōu)化體系，并利用層次分析法確定每個(gè)目標(biāo)函數(shù)在整個(gè)函數(shù)體系中的權(quán)重?；谶z傳算法進(jìn)行船體分段裝配序列優(yōu)化設(shè)計(jì)，實(shí)現(xiàn)了整體界面設(shè)計(jì)，最終輸出了優(yōu)化后的裝配序列，驗(yàn)證了經(jīng)優(yōu)化后的裝配序列的合理性和可行性。