基于自適應(yīng)遺傳算法的船舶分段裝配序列優(yōu)化研究

黃曉雪 程相茹

（渤海船舶職業(yè)學(xué)院 船舶工程系 葫蘆島125105 ）

引 言

船舶設(shè)計(jì)建造過(guò)程是一個(gè)復(fù)雜而龐大的系統(tǒng)工程，純依靠工程人員知識(shí)經(jīng)驗(yàn)安排和編制生產(chǎn)計(jì)劃的方式已不能滿足現(xiàn)代造船模式的生產(chǎn)要求，更不能達(dá)到未來(lái)“模塊化建造”的造船模式提出的高標(biāo)準(zhǔn)。因此，分段裝配序列優(yōu)化的研究對(duì)于指導(dǎo)實(shí)際生產(chǎn)裝配具有現(xiàn)實(shí)意義。

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

通過(guò)分析我們發(fā)現(xiàn)：基于優(yōu)先關(guān)系和圖論的方法，其可行解的搜索空間和評(píng)價(jià)規(guī)模巨大，搜索效率低，對(duì)于結(jié)構(gòu)復(fù)雜的大型裝配體，求解效果差強(qiáng)人意；基于啟發(fā)式算法的求解方法，由于其不要求問(wèn)題模型的精確數(shù)學(xué)描述，并且全局搜索能力強(qiáng)，能有效縮小搜索和評(píng)價(jià)空間；因此得到越來(lái)越多的裝配規(guī)劃研究工作者的青睞。

本文根據(jù)船舶分段裝配序列優(yōu)化問(wèn)題的特點(diǎn)，將裝配序列的評(píng)價(jià)標(biāo)準(zhǔn)融入到目標(biāo)函數(shù)中，采用自適應(yīng)遺傳算法進(jìn)行裝配序列優(yōu)化并進(jìn)行計(jì)算。并在此基礎(chǔ)上進(jìn)行裝配序列優(yōu)化系統(tǒng)的總體設(shè)計(jì)，將優(yōu)化后的裝配序列進(jìn)行裝配流程可視化，驗(yàn)證了算法的有效性。

1 數(shù)學(xué)模型及目標(biāo)函數(shù)的建立

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

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

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

1.1.1 分段裝配組立連接關(guān)系

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

1.1.2 裝配干涉矩陣分析

僅僅得到待裝配組立之間的連接關(guān)系是不夠的，還要對(duì)其進(jìn)行干涉分析。對(duì)于一個(gè)可行的裝配序列，不僅僅是在裝配完成時(shí)裝配組立之間不存在干涉現(xiàn)象，而且裝配組立在向既定位置運(yùn)動(dòng)時(shí)，也不可以與已裝配好或待裝配的其他組立以及裝配工具之間發(fā)生干涉現(xiàn)象［6］。

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

1.1.3 裝配序列可行性分析

已知一裝配序列為A=｛A1，A2，L，An｝，設(shè)待裝配組立為Ai，并且在Ai之前已經(jīng)有m個(gè)組立裝配完成，當(dāng)組立之間存在連接關(guān)系且組立在裝配過(guò)程中不存在干涉關(guān)系，則裝配序列可行。

（1）連接關(guān)系可行性分析

每個(gè)待裝配組立在裝配之前都需要判斷，如果存在與其相連接的組立，裝配序列才是可行的；否則不可行。第一個(gè)裝配的組立不需要判斷其連接關(guān)系，因?yàn)樗钦麄€(gè)分段裝配的基準(zhǔn)組立。待裝配組立 的裝配連接關(guān)系可以用式（4）來(lái)表達(dá)：

（2）干涉關(guān)系可行性分析

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

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

1.2 分段裝配工藝約束分析

裝配序列的評(píng)價(jià)標(biāo)準(zhǔn)雖然有很多，但是評(píng)價(jià)準(zhǔn)則難以進(jìn)行量化。以下為根據(jù)研究問(wèn)題所具備的特點(diǎn)概括出來(lái)的相對(duì)比較容易量化的關(guān)于工藝約束方面的評(píng)價(jià)準(zhǔn)則。

1.2.1 重定向次數(shù)

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

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

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

對(duì)于已知裝配序列A=｛A1，A2，L，An｝，根據(jù)組立的質(zhì)量進(jìn)行選擇起重機(jī)，判斷相鄰近的兩個(gè)零件在裝配過(guò)程中的吊裝工具是否相同，若吊裝工具相同，即，則吊裝工具沒(méi)發(fā)生改變；若吊裝工具不同，即則吊裝工具發(fā)生了改變，需要更換吊裝工具，則增加了裝配成本。

1.2.3 裝配效率

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

1.3 分段裝配序列優(yōu)化目標(biāo)體系

根據(jù)影響分段裝配的各種因素，對(duì)船舶分段裝配的幾何約束和工藝約束分別進(jìn)行分析，可以建立分段裝配序列優(yōu)化的目標(biāo)體系，為實(shí)現(xiàn)船舶分段裝配序列優(yōu)化提供基礎(chǔ)。

1.3.1 連接關(guān)系約束條件

1.3.2 干涉關(guān)系評(píng)價(jià)函數(shù)

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

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

那么，整個(gè)裝配序列的干涉次數(shù)In可作如下表示：

1.3.3 重定向評(píng)價(jià)函數(shù)

重定向次數(shù)作為裝配序列評(píng)價(jià)的一項(xiàng)重要指標(biāo)，直接影響著裝配序列的優(yōu)劣。對(duì)于一個(gè)已知的裝配序列A=｛A1，A2，L，An｝可以根據(jù)式（12）判斷其重定向次數(shù)。

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

1.3.4 吊裝工具評(píng)價(jià)函數(shù)

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

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

1.3.5 裝配效率評(píng)價(jià)函數(shù)

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

2 問(wèn)題模型求解

2.1 分段裝配序列優(yōu)化數(shù)學(xué)模型的建立

問(wèn)題模型是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，處理這類問(wèn)題通常是用加權(quán)法［7］將多目標(biāo)轉(zhuǎn)化為單目標(biāo)優(yōu)化進(jìn)行處理。然而各評(píng)價(jià)函數(shù)的重要性并不相同，針對(duì)一個(gè)評(píng)價(jià)函數(shù)比較優(yōu)秀的裝配序列，對(duì)于其他的評(píng)價(jià)函數(shù)可能很差，而且僅依靠主觀的判斷也難以說(shuō)明其合理性，所以必須綜合考慮各個(gè)指標(biāo)對(duì)于整個(gè)系統(tǒng)的重要性來(lái)科學(xué)地確定權(quán)重。層次分析法自問(wèn)世以來(lái)，以其思想清晰、能處理定性信息和適用于多指標(biāo)分析問(wèn)題等優(yōu)點(diǎn)，獲得多個(gè)領(lǐng)域的廣泛應(yīng)用，并在實(shí)踐應(yīng)用中證實(shí)了其有效性和先進(jìn)性。層次分析法的具體步驟包括確定所要解決的問(wèn)題、建立問(wèn)題的遞階層次結(jié)構(gòu)、建立問(wèn)題的判斷矩陣、層次關(guān)系單排序和層次關(guān)系總排序五個(gè)步驟。

為了確定目標(biāo)函數(shù)體系中各個(gè)評(píng)價(jià)函數(shù)的權(quán)重首先建立層次結(jié)構(gòu)，設(shè)定研究問(wèn)題的目標(biāo)層為權(quán)重的確定，根據(jù)重定向次數(shù)、裝配工具改變次數(shù)以及裝配效率對(duì)于目標(biāo)評(píng)價(jià)系統(tǒng)的重要性不同來(lái)確定其所占的權(quán)重。

首先將準(zhǔn)則層的三個(gè)評(píng)價(jià)因素按照表1的重要性分級(jí)進(jìn)行對(duì)比，根據(jù)某船廠實(shí)際情況，并對(duì)現(xiàn)場(chǎng)施工人員以及專家進(jìn)行調(diào)查，據(jù)此建立判斷矩陣A如式（17）所示，并將矩陣A列向量歸一化，并依此求出特征向量λ=3.109。則該特征值對(duì)應(yīng)的歸一化特征向量為w=（0.156，0.224，0.62）T，λmax=3.109。

進(jìn)行一致性檢測(cè)時(shí)，若通過(guò)了檢測(cè)，即為權(quán)向量；若一致性檢測(cè)沒(méi)有通過(guò)，則需要再一次構(gòu)造對(duì)比矩陣，并再次進(jìn)行一致性檢測(cè)直至檢測(cè)通過(guò)。根據(jù)表2隨機(jī)一致性指標(biāo)得出RI= 0.58，根據(jù)式（18）求得CI的值為0.054，又根據(jù)式（19）得出一致性指標(biāo)CR= 0.094 2 ，小于0.1，表明通過(guò)了一致性檢測(cè)。

表1 重要性比較分級(jí)

表2 隨機(jī)一致性指標(biāo)

重定向次數(shù)、吊裝工具改變次數(shù)、裝配效率的權(quán)重依次為0.156，0.224，0.62。對(duì)于一個(gè)裝配序列，如果待裝配零件與已裝配零件之間存在干涉關(guān)系，則裝配序列不可行；那么，即使其他三個(gè)評(píng)價(jià)函數(shù)再優(yōu)異裝配序列評(píng)價(jià)也失去了進(jìn)行優(yōu)化的意義，對(duì)于不滿足干涉條件的裝配序列可以采取兩種方法進(jìn)行改善：

（1）將不可行的裝配序列進(jìn)行修復(fù)或者丟棄；

（2）將干涉條件作為懲罰項(xiàng)加入到目標(biāo)函數(shù)中。其中第一種方法進(jìn)行丟棄不可行基因時(shí)可能會(huì)使可行基因缺乏從而導(dǎo)致算法收斂速度變慢，所以本文將干涉條件作為目標(biāo)函數(shù)的懲罰項(xiàng)來(lái)進(jìn)行優(yōu)化。

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

其中

該問(wèn)題模型是一個(gè)最小化問(wèn)題，f1、f2、f3、f4分別代表重定向次數(shù)、吊裝工具改變次數(shù)、裝配效率、干涉次數(shù)，它們都屬于越小越好的子目標(biāo)項(xiàng)。與其它三個(gè)子目標(biāo)不同，f4是對(duì)于裝配序列干涉情況的一種衡量，而可行的裝配序列是不允許存在干涉情況的。因此，本文在處理干涉項(xiàng)f4時(shí)，對(duì)其賦予一個(gè)較大的權(quán)重以產(chǎn)生懲罰效果，使得整個(gè)優(yōu)化搜索過(guò)程受干涉情況影響較大，引導(dǎo)搜索過(guò)程向著干涉量迅速減小的方向進(jìn)行?；谝陨戏治觯瑢?duì)式（20）中權(quán)重項(xiàng)α1、α2、α3、α4取值依次為 0.163 8、0.297 3、0.539 0、5。

2.2 基于改進(jìn)的自適應(yīng)遺傳算法的分段裝配序列算法設(shè)計(jì)

2.2.1 算法參數(shù)及操作設(shè)計(jì)

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

要解決船舶分段裝配序列優(yōu)化問(wèn)題需要有以下幾個(gè)基礎(chǔ)信息，即待裝配組立編號(hào)，裝配所需的吊裝工具，待裝配組立的裝配方向，所以染色體需要包含以上三種基礎(chǔ)信息，則組立基因型可通過(guò)下面的編碼方式來(lái)表達(dá)：

采用十進(jìn)制編碼方案，用A1、A2、A3…An來(lái)表示所有組立的編號(hào)；用1、2、3分別表示組立沿x，y，z三個(gè)方向上的正方向平動(dòng)；用1、2、3、4分別來(lái)表示不同組立的吊裝工具T1、T2、T3、T4。

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

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

（2）適應(yīng)度函數(shù)的選取

由于采用輪盤賭的選擇方式，所以需要滿足適應(yīng)度函數(shù)非負(fù)數(shù)的要求，且適應(yīng)度值越大的個(gè)體對(duì)于目標(biāo)函數(shù)的搜索能力越強(qiáng)，并且本文所解決問(wèn)題為目標(biāo)函數(shù)最小化的問(wèn)題，所以將裝配序列優(yōu)化問(wèn)題的適應(yīng)度函數(shù)設(shè)計(jì)如 （22）所示：

（3）選擇操作

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

（4）交叉操作

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

（5）變異操作

船舶分段裝配序列優(yōu)化問(wèn)題模型的變量主要是指組立裝配的順序、裝配方向、裝配工具，那么變異也主要是發(fā)生在這幾個(gè)方面，下面具體介紹變異的實(shí)現(xiàn)方式：

首先，裝配順序的變異方式。隨機(jī)產(chǎn)生兩個(gè)不同的在［1，n］之間的數(shù)字，將編號(hào)為這兩個(gè)數(shù)字的組立的裝配順序互換。

其次，裝配方向的變異方式。隨機(jī)產(chǎn)生不同于原始裝配方向的數(shù)字，然后將這個(gè)數(shù)字替換原始數(shù)字。

最后，吊裝工具的變異方式。吊裝工具必須滿足組立對(duì)于吊裝能力的要求，所以吊裝工具不可發(fā)生變異，即根據(jù)組立重量來(lái)確定吊裝工具。

（6）交叉概率和變異概率的自適應(yīng)調(diào)整

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

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

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

圖1 自適應(yīng)交叉概率及變異概率

（7）終止準(zhǔn)則

終止條件即為當(dāng)種群進(jìn)化滿足一定條件時(shí)，算法結(jié)果收斂，種群進(jìn)化停止，得到結(jié)果。根據(jù)不同終止條件的分析對(duì)比，采用如下終止準(zhǔn)則：

① 迭代次數(shù)達(dá)到預(yù)先設(shè)定的計(jì)算次數(shù)；

② 子父代個(gè)體多次迭代適應(yīng)度函數(shù)值；

③ 變化不明顯終止進(jìn)化，得出優(yōu)化結(jié)果。

2.2.2 算法求解步驟及流程圖

（1）求解步驟

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

③ 根據(jù)自適應(yīng)交叉概率Pc對(duì) 進(jìn)行交叉，得到交叉后的子一代個(gè)體

④ 根據(jù)自適應(yīng)變異概率Pm對(duì)子一代進(jìn)行變異，得到變異后的子二代個(gè)體

⑤ 終止準(zhǔn)則設(shè)定。若不滿足終止準(zhǔn)則，轉(zhuǎn)到第③步；若滿足，則輸出計(jì)算結(jié)果，進(jìn)化終止，得出問(wèn)題解。

（2）流程圖

根據(jù)求解問(wèn)題的步驟，可得到如圖2所示具體流程圖。

3 實(shí)例驗(yàn)證

建立一個(gè)完整的裝配序列優(yōu)化體系對(duì)于提高裝配質(zhì)量，節(jié)約裝配成本，縮短裝配工時(shí)有重要的意義。采用本文算法對(duì)某平行中體分段的裝配進(jìn)行研究，以平行中體分段的裝配問(wèn)題為例可以簡(jiǎn)化分析工作，但本系統(tǒng)同樣適用于裝配更為復(fù)雜的首尾分段，只是首尾分段的干涉矩陣更為復(fù)雜，使系統(tǒng)運(yùn)行的時(shí)間增加。用編程工具對(duì)船舶分段裝配序列優(yōu)化系統(tǒng)進(jìn)行實(shí)現(xiàn)，驗(yàn)證算法有效性，最后將經(jīng)優(yōu)化后的裝配序列進(jìn)行裝配流程檢驗(yàn)。

3.1 某平行中體分段裝配序列的優(yōu)化

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

圖2 自適應(yīng)遺傳算法流程圖

圖3 算法輸入界面

利用改進(jìn)的自適應(yīng)遺傳算法進(jìn)行編程設(shè)計(jì)，點(diǎn)擊開始計(jì)算，程序開始運(yùn)行，得到如圖4的界面，表明已經(jīng)完成了計(jì)算。

圖4 完成計(jì)算界面

點(diǎn)擊查看結(jié)果按鈕，彈出如圖5計(jì)算結(jié)果。根據(jù)圖5中適應(yīng)度進(jìn)化曲線可以看出目標(biāo)函數(shù)值呈現(xiàn)下降趨勢(shì)，并最終趨于穩(wěn)定，并且算法在進(jìn)化過(guò)程中收斂速度較快，在很短的時(shí)間內(nèi)即獲得問(wèn)題的最優(yōu)解，表明算法性能優(yōu)越。

圖5 裝配序列輸出界面

3.2 裝配流程可視化驗(yàn)證

隨著船舶制造業(yè)的發(fā)展，產(chǎn)品設(shè)計(jì)過(guò)程中的三維仿真技術(shù)的地位越來(lái)越重要。運(yùn)用CATIA軟件的電子樣機(jī)裝配仿真模塊對(duì)船舶分段裝配過(guò)程進(jìn)行模擬，并進(jìn)行干涉檢查，可以進(jìn)一步驗(yàn)證經(jīng)自適應(yīng)遺傳算法優(yōu)化后的裝配序列的合理性和正確性。

3.2.1 裝配過(guò)程可視化

根據(jù)優(yōu)化出來(lái)的分段裝配序列進(jìn)行裝配過(guò)程的三維動(dòng)態(tài)仿真，利用CATIA軟件將整個(gè)分段的裝配流程進(jìn)行演示，并記錄存儲(chǔ)為影片，實(shí)現(xiàn)裝配流程可視化，具體效果如圖6所示。在CATIA軟件電子樣機(jī)裝配仿真模塊下按照既有的裝配序列建立一個(gè)裝配樹結(jié)構(gòu)，將待裝配組立插入到既定位置，給出裝配過(guò)程中的引導(dǎo)路徑，設(shè)置動(dòng)作進(jìn)行的速度和時(shí)間并將整個(gè)過(guò)程記錄成Replay的動(dòng)態(tài)記錄。

圖6 裝配過(guò)程仿真

3.2.2 裝配干涉檢查

干涉檢查可以實(shí)現(xiàn)產(chǎn)品在實(shí)際裝配進(jìn)行之前驗(yàn)證裝配的可行性、路徑的可達(dá)性以及設(shè)計(jì)的合理性，利于用戶在實(shí)際的生產(chǎn)之前的分析和決策。它具體包括靜態(tài)干涉檢查和動(dòng)態(tài)干涉檢查。

（1）靜態(tài)干涉檢查

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

圖7 平行中體靜態(tài)干涉信息

（2）動(dòng)態(tài)干涉檢查

動(dòng)態(tài)干涉檢查是指在裝配過(guò)程中，裝配體是否與已經(jīng)裝配好的或者待裝配的零件間存在運(yùn)動(dòng)干涉。動(dòng)態(tài)干涉檢查具體包括產(chǎn)品機(jī)構(gòu)分解、產(chǎn)品布局協(xié)調(diào)以及干涉檢測(cè)。通過(guò)圖8中平行中體分段的裝配過(guò)程，可以看到本文所生成的裝配序列不存在動(dòng)態(tài)干涉。

圖8 裝配過(guò)程中的動(dòng)態(tài)干涉檢查

4 結(jié) 論

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

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

［2］ 王春雷，許建新，朱斌.基于三維產(chǎn)品模型的裝配順序規(guī)劃實(shí)現(xiàn)技術(shù)研究［J］.機(jī)械設(shè)計(jì)，2009（5）：21-25.

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

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

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

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

［7］ 李俊華，陳賓康，應(yīng)文樺，等.基于功能要求的艦艇指揮艙室優(yōu)化布置設(shè)計(jì)數(shù)學(xué)模型［J］.武漢交通科技大學(xué)學(xué)報(bào)，2000（5）：551-555.