基于自適應遺傳算法的船舶分段裝配序列優化研究

黃曉雪 程相茹

（渤海船舶職業學院 船舶工程系 葫蘆島125105 ）

引 言

船舶設計建造過程是一個復雜而龐大的系統工程，純依靠工程人員知識經驗安排和編制生產計劃的方式已不能滿足現代造船模式的生產要求，更不能達到未來“模塊化建造”的造船模式提出的高標準。因此，分段裝配序列優化的研究對于指導實際生產裝配具有現實意義。

裝配序列規劃主要是解決零部件裝配順序的問題，作為一個復雜的組合優化問題，已有許多學者進行了相關的研究。陳國華［1］、王春雷［2］在其各自的文獻中，提出了利用裝配體在給定方向上的干涉矩陣生成其裝配序列的方式，是最典型的基于優先關系的推理方式之一。西北工業大學白芳妮從圖分解的角度研究了裝配序列生成算法；方建新［3］運用蟻群算法求解裝配序列，林喜波［4］將遺傳算法運用于海爾洗衣機生產線的工序優化，王孝義［5］將模擬退火算法運用于裝配序列生成等，都是對運用啟發式算法求解裝配序列規劃問題的研究和探索。

通過分析我們發現：基于優先關系和圖論的方法，其可行解的搜索空間和評價規模巨大，搜索效率低，對于結構復雜的大型裝配體，求解效果差強人意；基于啟發式算法的求解方法，由于其不要求問題模型的精確數學描述，并且全局搜索能力強，能有效縮小搜索和評價空間；因此得到越來越多的裝配規劃研究工作者的青睞。

本文根據船舶分段裝配序列優化問題的特點，將裝配序列的評價標準融入到目標函數中，采用自適應遺傳算法進行裝配序列優化并進行計算。并在此基礎上進行裝配序列優化系統的總體設計，將優化后的裝配序列進行裝配流程可視化，驗證了算法的有效性。

1 數學模型及目標函數的建立

裝配序列的優劣有著許多不同的評價標準，對于裝配成本存在影響的因素也多種多樣。在分段建造過程中，建造場地的成本、使用材料的費用、焊接形式的效率、吊裝工具的利用率等因素都對船舶的建造成本產生很大影響。在當今現代化造船“殼舾涂”一體化理念的引導下，船舶建造周期的縮短顯得尤為重要。由于“殼舾涂”一體化對于船舶建造周期的影響難以進行量化，本文主要考慮零件裝配對整個建造流程的影響。根據影響裝配進行的工藝因素以及所研究問題具備的特點，總結了在裝配序列評價過程相對比較容易量化的評價準則，建立了包括連接關系約束條件、干涉關系評價函數、重定向評價函數、吊裝工具評價函數、裝配效率評價函數的裝配序列優化目標函數體系。

1.1 船舶分段裝配幾何約束分析

對于一個船舶分段裝配序列在對其進行優化之前，首先需要考慮其裝配序列的幾何可行性，所以首先需要建立分段的連接矩陣以及干涉矩陣。

1.1.1 分段裝配組立連接關系

每一個組立必須與其他組立相連接，才能夠成裝配關系，所以每一個待裝配組立進行裝配之前都要進行連接關系判斷，得出組立的連接關系矩陣。式（1）為分段裝配連接關系矩陣，其中Cij表示第i個組立與第j個組立之間是否存在接觸關系，若存在接觸關系，Cij值為1；反之，Cij的取值為0。

1.1.2 裝配干涉矩陣分析

僅僅得到待裝配組立之間的連接關系是不夠的，還要對其進行干涉分析。對于一個可行的裝配序列，不僅僅是在裝配完成時裝配組立之間不存在干涉現象，而且裝配組立在向既定位置運動時，也不可以與已裝配好或待裝配的其他組立以及裝配工具之間發生干涉現象［6］。

所謂干涉矩陣是指任意兩個裝配零件之間是否存在干涉關系的判斷矩陣，假設整個裝配體共存在n個零件，則在判斷待裝配零件與這n個零件間是否存在干涉關系后可形成一個1×n的干涉矩陣，當每個零件都進行干涉判斷后則可構成一個n×n的干涉矩陣。這個干涉矩陣需要包含（+X，+Y，+Z，-X，-Y，-Z）六個方向的干涉關系，而在實際裝配過程中，組立i與組立j沿+X方向的干涉關系與組立j相對于組立i沿-X方向的干涉關系是相同的，如果判斷（+X，+Y，+Z，-X，-Y，-Z）六個方向的干涉關系，會造成干涉關系的冗余，會降低裝配序列優化的效率，所以只需判斷沿+X方向上的干涉關系即可得到所有零件在±X方向上的干涉關系，±Y，±Z同理。則干涉矩陣可以用式（3）表示：

1.1.3 裝配序列可行性分析

已知一裝配序列為A=｛A1，A2，L，An｝，設待裝配組立為Ai，并且在Ai之前已經有m個組立裝配完成，當組立之間存在連接關系且組立在裝配過程中不存在干涉關系，則裝配序列可行。

（1）連接關系可行性分析

每個待裝配組立在裝配之前都需要判斷，如果存在與其相連接的組立，裝配序列才是可行的；否則不可行。第一個裝配的組立不需要判斷其連接關系，因為它是整個分段裝配的基準組立。待裝配組立 的裝配連接關系可以用式（4）來表達：

（2）干涉關系可行性分析

對于一個既存的裝配序列，可以根據其干涉矩陣判斷其可裝配性。在此，我們定義一個數組如下：

對于待裝配組立Ai可以判斷它與在它之前裝配的組立之間是否存在干涉關系，若存在干涉關系則相應的的值為1，則的值為1，那么Ai不可以沿+dk方向裝配。對于待裝配組立而言，的值或者-的值必須有一個為0，否則待裝配組立的裝配不可行。

1.2 分段裝配工藝約束分析

裝配序列的評價標準雖然有很多，但是評價準則難以進行量化。以下為根據研究問題所具備的特點概括出來的相對比較容易量化的關于工藝約束方面的評價準則。

1.2.1 重定向次數

對于已知的裝配序列A=｛A1，A2，L，An｝，將零件的裝配方向表示為則判斷相鄰的零件的裝配方向是否相同，若裝配方向相同，即則裝配方向沒有發生改變；若零件裝配方向不同，即則裝配方向發生了改變，需要進行重定向。

1.2.2 吊裝工具改變次數

組立裝配時需要使用起重機進行吊裝，對于不同重量的組立需要不同起重能力的起重機，設有四種起重能力的起重機ma，mb，mc，md，且ma＜mb＜mc＜md，存在某一組立重量為mi，則此組立所使用的吊裝工具Ti根據式（7）來判斷：

對于已知裝配序列A=｛A1，A2，L，An｝，根據組立的質量進行選擇起重機，判斷相鄰近的兩個零件在裝配過程中的吊裝工具是否相同，若吊裝工具相同，即，則吊裝工具沒發生改變；若吊裝工具不同，即則吊裝工具發生了改變，需要更換吊裝工具，則增加了裝配成本。

1.2.3 裝配效率

在船舶實際分段建造中，根據零件所處的空間位置的不同裝配效率各不相同。相比較而言由于其所處空間位置不同，由上而下的裝配比水平的裝配效率高，自下至上的裝配效率會更低，所以更多采用由上而下的裝配方式就會大大提高分段的裝配效率。對于已知的裝配序列A=｛A1，A2，L，An｝，設nd為由上而下進行的裝配次數，nh為水平進行的裝配次數，nu為自下至上進行的裝配次數，λd、λh、λu分別為沿其方向的效率且有λd＞λh＞λu，則有nd越大越好。

1.3 分段裝配序列優化目標體系

根據影響分段裝配的各種因素，對船舶分段裝配的幾何約束和工藝約束分別進行分析，可以建立分段裝配序列優化的目標體系，為實現船舶分段裝配序列優化提供基礎。

1.3.1 連接關系約束條件

1.3.2 干涉關系評價函數

根據上文所建立的裝配干涉矩陣可以判斷一個已知的裝配序列A=｛A1，A2，L，An｝在裝配過程中存在的干涉次數In。第一個組立不需要考慮其干涉性，從第二個組立開始判斷與前面的組立干涉性，若沿dk方向裝配，k表示組立i之前進行裝配的任意一個組立，表示第i個進行裝配的組立與之前任意一個裝配組立的干涉關系。

式中：Iikx，Iiky，Iikz分別表示在裝配序列中第i個進行裝配的組立與在它之前進行裝配的組立在x，y，z三個方向上的干涉值。則第i個進行裝配的組立的干涉關系如式（10）所示：

那么，整個裝配序列的干涉次數In可作如下表示：

1.3.3 重定向評價函數

重定向次數作為裝配序列評價的一項重要指標，直接影響著裝配序列的優劣。對于一個已知的裝配序列A=｛A1，A2，L，An｝可以根據式（12）判斷其重定向次數。

式中：δ代表裝配序列中重定向的次數，式（13）中δi代表每一個待裝配的組立與在它之前裝配組立是否發生重定向，若發生重定向則計數1，若不發生重定向則計數0。

1.3.4 吊裝工具評價函數

在船舶建造過程中，恰當使用和更換吊裝工具能很大程度上的提分段的裝配效率。對于一個已知的裝配序列A=｛A1，A2，L，An｝，可以根據式（14）判斷其吊裝工具改變的次數。

式中：e代表裝配序列中吊裝工具改變的次數，式（15）中ei代表每一個待裝配的組立與在它之前裝配組立的吊裝工具是否改變，若吊裝工具改變則計數1，若不發生改變則計數0。

1.3.5 裝配效率評價函數

不同的裝配方式下分段的裝配效率不同，盡量采用由上而下的裝配方式可以提高裝配效率。對于一已知的裝配序列A=｛A1，A2，L，An｝，可以根據式（16）得到該序列的裝配效率評價函數。式中λd、λh、λu及nd、nh、nu所代表的意義上文已經交代，λd、λh、λu分別取值為90%、60%、30%，使用n代表各種裝配方式的次數之和，其中n=nd+nh+nu，則效率P的最大值為n×λd，P的表達式如式（16）所示：

2 問題模型求解

2.1 分段裝配序列優化數學模型的建立

問題模型是一個多目標優化問題，處理這類問題通常是用加權法［7］將多目標轉化為單目標優化進行處理。然而各評價函數的重要性并不相同，針對一個評價函數比較優秀的裝配序列，對于其他的評價函數可能很差，而且僅依靠主觀的判斷也難以說明其合理性，所以必須綜合考慮各個指標對于整個系統的重要性來科學地確定權重。層次分析法自問世以來，以其思想清晰、能處理定性信息和適用于多指標分析問題等優點，獲得多個領域的廣泛應用，并在實踐應用中證實了其有效性和先進性。層次分析法的具體步驟包括確定所要解決的問題、建立問題的遞階層次結構、建立問題的判斷矩陣、層次關系單排序和層次關系總排序五個步驟。

為了確定目標函數體系中各個評價函數的權重首先建立層次結構，設定研究問題的目標層為權重的確定，根據重定向次數、裝配工具改變次數以及裝配效率對于目標評價系統的重要性不同來確定其所占的權重。

首先將準則層的三個評價因素按照表1的重要性分級進行對比，根據某船廠實際情況，并對現場施工人員以及專家進行調查，據此建立判斷矩陣A如式（17）所示，并將矩陣A列向量歸一化，并依此求出特征向量λ=3.109。則該特征值對應的歸一化特征向量為w=（0.156，0.224，0.62）T，λmax=3.109。

進行一致性檢測時，若通過了檢測，即為權向量；若一致性檢測沒有通過，則需要再一次構造對比矩陣，并再次進行一致性檢測直至檢測通過。根據表2隨機一致性指標得出RI= 0.58，根據式（18）求得CI的值為0.054，又根據式（19）得出一致性指標CR= 0.094 2 ，小于0.1，表明通過了一致性檢測。

表1 重要性比較分級

表2 隨機一致性指標

重定向次數、吊裝工具改變次數、裝配效率的權重依次為0.156，0.224，0.62。對于一個裝配序列，如果待裝配零件與已裝配零件之間存在干涉關系，則裝配序列不可行；那么，即使其他三個評價函數再優異裝配序列評價也失去了進行優化的意義，對于不滿足干涉條件的裝配序列可以采取兩種方法進行改善：

（1）將不可行的裝配序列進行修復或者丟棄；

（2）將干涉條件作為懲罰項加入到目標函數中。其中第一種方法進行丟棄不可行基因時可能會使可行基因缺乏從而導致算法收斂速度變慢，所以本文將干涉條件作為目標函數的懲罰項來進行優化。

根據上文所提出的幾何約束條件和工藝約束條件可以得出船舶分段裝配序列優化的數學模型如式（20）所示：

其中

該問題模型是一個最小化問題，f1、f2、f3、f4分別代表重定向次數、吊裝工具改變次數、裝配效率、干涉次數，它們都屬于越小越好的子目標項。與其它三個子目標不同，f4是對于裝配序列干涉情況的一種衡量，而可行的裝配序列是不允許存在干涉情況的。因此，本文在處理干涉項f4時，對其賦予一個較大的權重以產生懲罰效果，使得整個優化搜索過程受干涉情況影響較大，引導搜索過程向著干涉量迅速減小的方向進行。基于以上分析，對式（20）中權重項α1、α2、α3、α4取值依次為 0.163 8、0.297 3、0.539 0、5。

2.2 基于改進的自適應遺傳算法的分段裝配序列算法設計

2.2.1 算法參數及操作設計

（1）基因型編碼方案及種群初始化

要解決船舶分段裝配序列優化問題需要有以下幾個基礎信息，即待裝配組立編號，裝配所需的吊裝工具，待裝配組立的裝配方向，所以染色體需要包含以上三種基礎信息，則組立基因型可通過下面的編碼方式來表達：

采用十進制編碼方案，用A1、A2、A3…An來表示所有組立的編號；用1、2、3分別表示組立沿x，y，z三個方向上的正方向平動；用1、2、3、4分別來表示不同組立的吊裝工具T1、T2、T3、T4。

根據編碼方案可隨機產生初始種群，但是所產生的初始種群未必存在連接關系，所以本文采用串行進度方案生成初始種群，采用這種方法可以生成滿足連接關系約束條件的裝配序列。

本文將所研究問題設置為三個數組，分別為已裝配完成的組立數組Di，裝配雖未完成中但可以作為下一個裝配組立的數組Yi，裝配既未完成又不可以作為下一個裝配組立的數組Ni。由于船體組立重量大，吊裝翻身代價高，小組立裝配過程中不便于頻繁將中組立翻身，所以一般選取重量大、接觸組立多的構件為裝配基準件，本文選擇編號為1的組立為基準件進行裝配。則組立1進入已裝配完成的組立數組Di，根據連接關系矩陣將與組立1存在連接關系的組立進入到裝配雖未完成中但可以作為下一個裝配組立的數組Yi，其它組立進入到裝配既未完成又不可以作為下一個裝配組立的數組Ni中。采用隨機函數random選取數組Yi中任意一個組立進入到已裝配完成的組立數組Di中，接著重復上述過程，直至數組Yi和數組Ni中的組立為空，則隨機生成了即完整又滿足連接關系約束條件的初始種群。

（2）適應度函數的選取

由于采用輪盤賭的選擇方式，所以需要滿足適應度函數非負數的要求，且適應度值越大的個體對于目標函數的搜索能力越強，并且本文所解決問題為目標函數最小化的問題，所以將裝配序列優化問題的適應度函數設計如 （22）所示：

（3）選擇操作

對于一個已知種群，適應度函數值較大的個體被選為父代遺傳給后代的概率比較大，本文采用輪盤賭方法這種常用的選擇方法來進行選擇操作。首先根據蒙特卡羅法計算出個體被選擇的概率，即對于某一個體的適應度值為fi，則其被選作父代遺傳給后代的概率為Pi，然后分別計算出每個個體的累計概率，隨機產生一個0到1 區間的數，如果此數介于之間時，則此個體被選擇為父代，否則，未被選中。其中概率為Pi的表達式如下：

（4）交叉操作

采用單點交叉法進行算法的交叉操作，已知兩個即將進行交叉的個體Pi和Pj，生成一個范圍為［1，n-1］的隨機數，選擇此點作為發生交叉操作的臨界點，將Pi中此隨機數之前的基因保留，將Pj中此隨機數之后的基因補齊至Pi中，得到子代個體Ci，同理可求得子代個體Cj。

（5）變異操作

船舶分段裝配序列優化問題模型的變量主要是指組立裝配的順序、裝配方向、裝配工具，那么變異也主要是發生在這幾個方面，下面具體介紹變異的實現方式：

首先，裝配順序的變異方式。隨機產生兩個不同的在［1，n］之間的數字，將編號為這兩個數字的組立的裝配順序互換。

其次，裝配方向的變異方式。隨機產生不同于原始裝配方向的數字，然后將這個數字替換原始數字。

最后，吊裝工具的變異方式。吊裝工具必須滿足組立對于吊裝能力的要求，所以吊裝工具不可發生變異，即根據組立重量來確定吊裝工具。

（6）交叉概率和變異概率的自適應調整

交叉概率和變異概率決定了遺傳算法的搜索能力，所以選擇適宜的Pc和Pm尤為重要。本文借鑒自適應算法的思想，當某一個體適應度處于種群最大適應度值時使其交叉概率和變異概率不為0，提升到Pc2、Pm2，這種方法不但有效的避免了最大適應度個體一直處于停滯狀態，而且有效地跳出了局部最優解。交叉概率和變異概率的自適應變化方式如下：

式中：Pc1＞Pc2，Pm1＞Pm2其他字母代表含義與上文基本相同，其中f1表示要交叉的兩個個體中較大的適應度值；f′表示要變異個體的適應度值。

式（24）、式（25）中，各個交叉概率和變異概率為Pc1= 0.9，Pc2= 0.6，Pm1= 0.1，Pm2= 0.001。圖1可以形象地表達出交叉概率和變異概率的公式：

圖1 自適應交叉概率及變異概率

（7）終止準則

終止條件即為當種群進化滿足一定條件時，算法結果收斂，種群進化停止，得到結果。根據不同終止條件的分析對比，采用如下終止準則：

① 迭代次數達到預先設定的計算次數；

② 子父代個體多次迭代適應度函數值；

③ 變化不明顯終止進化，得出優化結果。

2.2.2 算法求解步驟及流程圖

（1）求解步驟

① 初始化n個個體的初始種群并編碼，設定包含種群規模、交叉和變異概率、算法最大計算次數等參數，初始化計數器t=0。

③ 根據自適應交叉概率Pc對 進行交叉，得到交叉后的子一代個體

④ 根據自適應變異概率Pm對子一代進行變異，得到變異后的子二代個體

⑤ 終止準則設定。若不滿足終止準則，轉到第③步；若滿足，則輸出計算結果，進化終止，得出問題解。

（2）流程圖

根據求解問題的步驟，可得到如圖2所示具體流程圖。

3 實例驗證

建立一個完整的裝配序列優化體系對于提高裝配質量，節約裝配成本，縮短裝配工時有重要的意義。采用本文算法對某平行中體分段的裝配進行研究，以平行中體分段的裝配問題為例可以簡化分析工作，但本系統同樣適用于裝配更為復雜的首尾分段，只是首尾分段的干涉矩陣更為復雜，使系統運行的時間增加。用編程工具對船舶分段裝配序列優化系統進行實現，驗證算法有效性，最后將經優化后的裝配序列進行裝配流程檢驗。

3.1 某平行中體分段裝配序列的優化

根據在CATIA軟件中所建立的平行中體模型確定出所包含的組立總數X，并通過點擊導入組立信息按鈕可以打開所存儲的包含組立重量和組立吊裝工具的txt文件。干涉矩陣以及連接矩陣相關信息的導入和添加與其相似。設置算法的相關參數，設定種群大小為100，最大遺傳數為100，交叉概率1為0.9，交叉概率2為0.6，變異概率1為0.1，變異概率2為0.001，具體如圖3所示。

圖2 自適應遺傳算法流程圖

圖3 算法輸入界面

利用改進的自適應遺傳算法進行編程設計，點擊開始計算，程序開始運行，得到如圖4的界面，表明已經完成了計算。

圖4 完成計算界面

點擊查看結果按鈕，彈出如圖5計算結果。根據圖5中適應度進化曲線可以看出目標函數值呈現下降趨勢，并最終趨于穩定，并且算法在進化過程中收斂速度較快，在很短的時間內即獲得問題的最優解，表明算法性能優越。

圖5 裝配序列輸出界面

3.2 裝配流程可視化驗證

隨著船舶制造業的發展，產品設計過程中的三維仿真技術的地位越來越重要。運用CATIA軟件的電子樣機裝配仿真模塊對船舶分段裝配過程進行模擬，并進行干涉檢查，可以進一步驗證經自適應遺傳算法優化后的裝配序列的合理性和正確性。

3.2.1 裝配過程可視化

根據優化出來的分段裝配序列進行裝配過程的三維動態仿真，利用CATIA軟件將整個分段的裝配流程進行演示，并記錄存儲為影片，實現裝配流程可視化，具體效果如圖6所示。在CATIA軟件電子樣機裝配仿真模塊下按照既有的裝配序列建立一個裝配樹結構，將待裝配組立插入到既定位置，給出裝配過程中的引導路徑，設置動作進行的速度和時間并將整個過程記錄成Replay的動態記錄。

圖6 裝配過程仿真

3.2.2 裝配干涉檢查

干涉檢查可以實現產品在實際裝配進行之前驗證裝配的可行性、路徑的可達性以及設計的合理性，利于用戶在實際的生產之前的分析和決策。它具體包括靜態干涉檢查和動態干涉檢查。

（1）靜態干涉檢查

所謂靜態干涉檢查是指在裝配體靜止的情況下，檢查零件間是否存在干涉關系，設計是否合理。從靜態干涉檢查中可以得到裝配體的干涉信息，具體包括零件之間的碰撞關系及接觸關系。干涉信息可以存儲為干涉報告，利于對于裝配體信息的分析、修改以及管理。從下頁圖7可知模型只存在接觸干涉這種正常的干涉現象，即模型設計合理。

圖7 平行中體靜態干涉信息

（2）動態干涉檢查

動態干涉檢查是指在裝配過程中，裝配體是否與已經裝配好的或者待裝配的零件間存在運動干涉。動態干涉檢查具體包括產品機構分解、產品布局協調以及干涉檢測。通過圖8中平行中體分段的裝配過程，可以看到本文所生成的裝配序列不存在動態干涉。

圖8 裝配過程中的動態干涉檢查

4 結 論

為了解決某典型的平行中體分段裝配序列優化問題，本文提出基于自適應遺傳算法的船舶分段裝配序列優化求解方法。根據其幾何模型得出包含干涉關系和連接關系的分段幾何約束信息，并據此建立包含干涉關系、重定向次數、吊裝工具改變次數、裝配效率等評價函數的目標優化體系。隨即，分析了遺傳算法的基本原理和不足，采用改進的自適應遺傳算法進行裝配序列優化，并將評價標準作為目標函數來進行優化計算，既降低了問題的繁瑣程度，又提高了系統的工作效率。設計并實現了船舶分段裝配序列優化問題的總體系統框架及界面功能，得出經優化后的裝配序列，并在此基礎上進行優化輸出結果分析及船舶分段裝配流程的可視化仿真，驗證了經算法優化后的裝配序列的合理性和正確性。

［1］ 陳國華，程本松，楊敏.基于CATIA的機械零件虛擬裝配方法［J］.機械研究與應用，2006（3）： 43-45.

［2］ 王春雷，許建新，朱斌.基于三維產品模型的裝配順序規劃實現技術研究［J］.機械設計，2009（5）：21-25.

［3］ 方建新.基于蟻群算法的裝配序列規劃研究［D］.武漢：華中科技大學碩士學位論文，2007：10-15.

［4］ 林喜波.基于遺傳算法的裝配序列優化［D］.南京：南京理工大學碩士學位論文，2004：7-18.

［5］ 王孝義，張友良，張帆.基于模擬退火算法的裝配序列生成與優化［J］.機械科學與技術，2005（5）： 624-627.

［6］ 曾賢虎.虛擬裝配理論與方法研究［D］.蘭州：蘭州理工大學碩士學位論文，2006：9-14.

［7］ 李俊華，陳賓康，應文樺，等.基于功能要求的艦艇指揮艙室優化布置設計數學模型［J］.武漢交通科技大學學報，2000（5）：551-555.