基于遺傳算法的分段裝配序列優化研究

黃曉雪，李照輝

1.渤海船舶職業學院，遼寧 興城 125105；2.大連船舶重工集團有限公司，遼寧 大連 116000

現代造船模式實現了由整體建造到分段建造再到分道建造的轉變過程，因此以往單純依靠工藝人員經驗編制的生產進度方案已經不能夠滿足“模塊化建造”的現代造船模式的要求[1]。基于此，提出船舶分段裝配序列優化研究這一問題，進而指導船廠實際的生產裝配工作。

大多數的裝配序列優化研究是圍繞一些零部件展開的，常用的裝配序列優化大多采用基于優先關系和圖論的方法和基于啟發式算法的求解方法[2]。通過大量的實驗和數據對比不難發現：基于優先關系和圖論這種方式研究空間大、評價系統繁瑣，導致搜索效率低，所以并不適合一些結構比較復雜的大型構件；基于啟發式算法的求解方法，不但可以有效地構建問題模型，并且搜索能力強，能夠有效地避免基于優先關系和圖論這種研究方式的缺點，研究空間適中、評價系統合理，因此對于一些結構復雜的大型構件普遍適用于此研究方法[3]。

由于船舶分段裝配是一個系統復雜、規模龐大的工作，本文根據這一特點，將研究問題的目標函數設定為裝配序列優化的評價準則，并在優化過程中引入遺傳算法來進行目標函數的計算和優化，得出優化后的裝配序列，并將其進行可視化虛擬仿真，從而驗證算法和目標函數的有效性和合理性。

1 約束條件的選取

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

1.1 組立連接關系

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

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

1.2 組立干涉關系

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

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

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

則第個進行裝配的組立其干涉關系如式1-5。

綜上，整個裝配序列的干涉次數In如式1-6。

1.3 組立重定向次數

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

1.4 吊裝工具改變次數

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

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

2 數學模型的建立

2.1 平行中體分段裝配序列優化數學模型

根據上述約束條件可以建立一個包含連接關系、干涉關系、重定向次數、裝配工具改變次數的目標函數體系，但體系中各個評價函數所占的比重需要根據層次分析法來確定。依據前述所提到的干涉關系、重定向次數、吊裝工具改變等約束條件，得到平行中體分段裝配序列優化的數學模型如式2-1。

其中

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

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

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

步驟二：隨機初始化裝配序列種群P0（t）[7]，根據上述約束條件和目標函數體系計算隨機產生的初代種群的適應度值，并設置將適應度值最高的個體將基因保存復制給下一代，得到新種群。

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

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

步驟五：終止原則的設定標準。若滿足終止原則，則輸出本算法的優化結果，然后終止計算，得到優化后的裝配序列；若不滿足終止原則，轉換到第三個步驟接著進行計算[9]。

3 平行中體分段裝配序列優化實例計算

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

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

圖1 裝配序列規劃輸出界面

根據進化曲線可以分析出目標函數的設置合理有效，目標函數為求取最小值的過程，其整體呈現下降趨勢并逐漸穩定到一個值，證明算法可以有效收斂并且運算速度較快[10]。

4 結論

裝配序列優化問題可以有效地降低船舶裝配成本，提高船舶裝配效率。本文根據某平行中體分段的裝配序列優化問題提出了一個在幾何和工藝約束條件基礎上的包含干涉關系、重定向次數、裝配工具改變次數的目標函數優化體系，并利用層次分析法確定每個目標函數在整個函數體系中的權重。基于遺傳算法進行船體分段裝配序列優化設計，實現了整體界面設計，最終輸出了優化后的裝配序列，驗證了經優化后的裝配序列的合理性和可行性。