汪雪蓮 黃 君

中國(guó)艦船研究設(shè)計(jì)中心，湖北武漢430064

遺傳算法在船舶電纜布局優(yōu)化設(shè)計(jì)中的應(yīng)用研究

汪雪蓮 黃 君

中國(guó)艦船研究設(shè)計(jì)中心，湖北武漢430064

船舶電纜布局優(yōu)化是實(shí)現(xiàn)船舶布線自動(dòng)化的一項(xiàng)技術(shù)難題，這一問(wèn)題的解決可節(jié)省大量電纜布局設(shè)計(jì)的時(shí)間和費(fèi)用。建立優(yōu)化模型，并對(duì)傳統(tǒng)遺傳算法中初始種群的產(chǎn)生方法、選擇算子及變異算子進(jìn)行改進(jìn)，增加檢測(cè)操作，從而構(gòu)造求解該模型的改進(jìn)遺傳算法。仿真結(jié)果表明，該算法是一種具有全局尋優(yōu)能力的布局優(yōu)化方法，具有高效性、實(shí)用性，并可擴(kuò)展于解決船舶設(shè)計(jì)中的其它優(yōu)化問(wèn)題。

遺傳算法；優(yōu)化；電纜敷設(shè)；船舶

1 引言

船舶設(shè)計(jì)中存在復(fù)雜的電、氣、液纜線或管路布局設(shè)計(jì)（簡(jiǎn)稱“布線設(shè)計(jì)”）問(wèn)題。布線設(shè)計(jì)不僅直接影響布局空間的結(jié)構(gòu)設(shè)計(jì)、線路總長(zhǎng)度和總費(fèi)用，而且還關(guān)系到整個(gè)系統(tǒng)的可靠性、可維修性和電子設(shè)備間電磁兼容性等。由于船舶線路數(shù)量龐大、約束復(fù)雜，因而布線設(shè)計(jì)非常困難與耗時(shí)?？梢钥闯觯瑢?shí)現(xiàn)布線設(shè)計(jì)的自動(dòng)化和優(yōu)化對(duì)提高船舶設(shè)計(jì)質(zhì)量、縮短造船周期有著重要的意義。本文所要解決的問(wèn)題就是在大型CAD系統(tǒng)CADDS5中，實(shí)現(xiàn)自動(dòng)布放電纜功能時(shí)所遇到的路徑分配的全局優(yōu)化問(wèn)題（簡(jiǎn)稱“電纜布局優(yōu)化問(wèn)題”）。這里的全局優(yōu)化是指，在已鋪設(shè)好的電纜通道網(wǎng)絡(luò)中，給定電纜的起止結(jié)點(diǎn) （即終端電子設(shè)備），如何分配各根電纜的路徑以使布放電纜的總費(fèi)用最低，并保證不超過(guò)各通道段的容量限制。

近年來(lái)，以遺傳算法、模擬退火、禁忌搜索以及人工神經(jīng)網(wǎng)絡(luò)為代表的智能優(yōu)化技術(shù)發(fā)展迅速，受到人們普遍關(guān)注。其中，遺傳算法是基于進(jìn)化理論發(fā)展起來(lái)的一種廣為應(yīng)用的、高效的優(yōu)化算法，它以其優(yōu)良的計(jì)算性能和顯著的應(yīng)用效果而特別引人注目［1］。本文給出了電纜布局優(yōu)化問(wèn)題的數(shù)學(xué)模型，并選用遺傳算法進(jìn)行求解，同時(shí)對(duì)傳統(tǒng)遺傳算法中的諸多方面進(jìn)行改進(jìn)，仿真結(jié)果證明了該算法的有效性。

2 遺傳算法的基本原理

遺傳算法（Genetic Algorithm，GA）是由美國(guó)科學(xué)家John Holland［2，3］提出來(lái)的，它是以自然選擇和遺傳理論為基礎(chǔ)，將生物進(jìn)化過(guò)程中適者生存規(guī)則與群體內(nèi)部染色體的隨機(jī)信息交換機(jī)制相結(jié)合的一種概率搜索算法。

用遺傳算法求解問(wèn)題的一般步驟如下：

1）確定染色體（即個(gè)體）的編碼方案，將解空間的解數(shù)據(jù)通過(guò)編碼表示成遺傳空間的基因型數(shù)據(jù)串；

2）隨機(jī)產(chǎn)生一個(gè)初始群體，群體中每個(gè)染色體都滿足約束條件；

3）計(jì)算每個(gè)染色體的適應(yīng)值；

4）選擇進(jìn)行交叉和變異的父代染色體，即把當(dāng)前群體中的個(gè)體按與適應(yīng)值成比例的概率復(fù)制到新的群體中，用于提高群體的平均適應(yīng)值；

5）對(duì)選出的染色體進(jìn)行交叉操作，即從交配池中隨機(jī)選取兩個(gè)個(gè)體作為父代串，交換父代串中的若干基因位，得到兩個(gè)新的子串，用于產(chǎn)生新的個(gè)體，保持群體的多樣性；

6）對(duì)選出的染色體進(jìn)行變異操作，即以很小的概率隨機(jī)地改變個(gè)體上的某些基因位，用于進(jìn)一步增加和恢復(fù)群體的多樣性；

7）重復(fù)3）～6）條直至滿足終止條件。

3 問(wèn)題描述及數(shù)學(xué)建模

本文要解決的船舶電纜布局優(yōu)化問(wèn)題，就是在已鋪設(shè)好的電纜通道網(wǎng)絡(luò)中，在考慮通道容量約束的條件下，實(shí)現(xiàn)電纜路徑的最佳分配從而使布放電纜的總費(fèi)用最低。

這里，電纜通道網(wǎng)絡(luò)可表示成一個(gè)加權(quán)無(wú)向圖G（N，E），其中N表示結(jié)點(diǎn)數(shù)，E表示連接結(jié)點(diǎn)的通道數(shù)。假設(shè)在該圖中共需布放S根電纜，則上述布線問(wèn)題就可轉(zhuǎn)化為具有S個(gè)變量，E個(gè)約束條件的組合優(yōu)化問(wèn)題，具體數(shù)學(xué)模型如下：

式中，i為電纜編號(hào)（i＝0，1，…S－1）；qi為電纜i所需容量，這里指電纜的橫截面積 （即截面大小）；pi為電纜i每單位長(zhǎng)度所需費(fèi)用，這里假設(shè)電纜每單位長(zhǎng)度的費(fèi)用與電纜截面大小成正比，為簡(jiǎn)單起見(jiàn)，取電纜所需容量值為電纜單位長(zhǎng)度費(fèi)用，即pi＝qi；Xi為電纜i所選定的路徑矩陣，即Xi∈｛Xi1，Xi2，…，Xin｝，n為電纜i的候選路徑數(shù)目，其中Xij（j＝1，2，…，n）為電纜i的第j條候選路徑矩陣，Xij＝［I1，I2，…IE］T，Ik∈｛0，1｝，0表示電纜i不經(jīng)過(guò)第k段通道，1表示電纜i經(jīng)過(guò)第k段通道（k＝1，2，…，E）；L為通道段長(zhǎng)度矩陣，即L＝［L1，L2，…LE］；Q為通道段容量矩陣，即Q＝［Q1，Q2，…，QE］T；C為布放電纜的總費(fèi)用。

4 改進(jìn)遺傳算法的構(gòu)造

針對(duì)傳統(tǒng)遺傳算法的不足，本文構(gòu)造改進(jìn)遺傳算法來(lái)求解上述數(shù)學(xué)模型。

1）確定染色體編碼方案

首先對(duì)每根待布放電纜的所有候選路徑按長(zhǎng)度從小到大進(jìn)行編號(hào)，然后將每根電纜的每條候選路徑的編號(hào)視為一個(gè)基因，這樣由所有電纜的某條候選路徑編號(hào)所組成的序列，就可以作為一個(gè)染色體，即一種電纜布放方案。例如表1，染色體（0，0，0）表示3根待布放的電纜（AB、AC、AD），均取編號(hào)為0的路徑 （A→B、A→E→C、A→E→C→D），即全部選取最短路徑。為簡(jiǎn)單起見(jiàn)，本文所有表中的數(shù)據(jù)均不帶單位。

表1 電纜布放方案編碼

2）產(chǎn)生初始種群

理論上，初始種群可以隨機(jī)選取，這也是最常用的辦法。但就本文布線問(wèn)題的特點(diǎn)而言，在最終的解決方案中，即在全局最優(yōu)路徑中必然包括了某些單根電纜的最短路徑。所以本文先對(duì)每根電纜的所有候選路徑按長(zhǎng)度從小到大排序，然后按概率為每根電纜指定初始路徑：

式中，n為當(dāng)前電纜的候選路徑數(shù)目；i為候選路徑編號(hào)，i＝0，1，…，n－1。

這樣編號(hào)越小的路徑，即長(zhǎng)度越短的路徑被選中的概率就越大，從而有利于更快速地找到合適的解。本文設(shè)種群規(guī)模（即群體中個(gè)體數(shù)目）為100。

3）計(jì)算每個(gè)染色體的適應(yīng)值

對(duì)于每個(gè)染色體所對(duì)應(yīng)的路徑方案，要判定其優(yōu)劣，一是要看其是否滿足問(wèn)題的約束條件，即判斷每種電纜布放方案的每段通道實(shí)際占用容量是否不超過(guò)最大容量的限制；二是要計(jì)算其目標(biāo)函數(shù)值，即計(jì)算每種電纜布放方案的總費(fèi)用。

4）選擇操作

在應(yīng)用遺傳算法解決實(shí)際問(wèn)題時(shí)，有時(shí)會(huì)出現(xiàn)早熟收斂現(xiàn)象，即種群中的大部分個(gè)體都在某一個(gè)局部極值附近［4］。過(guò)早收斂的主要原因是超級(jí)個(gè)體的存在，這些超級(jí)個(gè)體的適應(yīng)值要比種群的平均適應(yīng)值大得多，以至于它們擁有大量的后代。由于種群規(guī)模是固定的，它們就會(huì)阻止其他個(gè)體的子代在下一代中出現(xiàn)。經(jīng)過(guò)不多的代數(shù)，一個(gè)超級(jí)個(gè)體可能會(huì)排除其他有希望的染色體，并造成快速收斂到可能是局部的最優(yōu)解。因此，必須設(shè)計(jì)可調(diào)節(jié)選擇壓力的算法。本文根據(jù)Baker［5］和Whitley［6］等人提出來(lái)的基于“排名”的選擇方法，設(shè)計(jì)了一個(gè)符合本文布線問(wèn)題特點(diǎn)的選擇機(jī)制，其步驟如下：

（1）排除完全重復(fù)的個(gè)體；

（2）對(duì)剩下的互不相同的個(gè)體按照目標(biāo)值從小到大排序 （假設(shè)ni為第i個(gè)個(gè)體的序號(hào)，i＝1，2，…，h；h為互不相同的個(gè)體總數(shù)）；

（3）找到滿足約束條件并且目標(biāo)值最小的個(gè)體即當(dāng)前最優(yōu)解（假設(shè)其序號(hào)為nk）；

（4）對(duì)于序號(hào)小于nk的個(gè)體，執(zhí)行ni＝nk－ni；對(duì)于序號(hào)大于或等于nk的個(gè)體，執(zhí)行ni＝ni－nk；

（5）按概率選擇用于繁殖下一代的個(gè)體：

式中，m為經(jīng)過(guò)第（4）步序號(hào)變換后最大的序號(hào)值。

上述步驟（1）是為了避免已經(jīng)擁有大量后代的個(gè)體繁殖出更多的后代，從而保證種群中個(gè)體的多樣性。步驟（4）是基于當(dāng)前最優(yōu)解調(diào)整所有個(gè)體的序號(hào)，使目標(biāo)值越接近于當(dāng)前最優(yōu)解的個(gè)體其排序就越靠前。步驟（5）中的個(gè)體選擇概率可以使目標(biāo)值越接近于當(dāng)前最優(yōu)解的個(gè)體其繁殖機(jī)會(huì)越大。

5）交叉操作

本文采用了一般的簡(jiǎn)單交叉算子，而交叉概率則根據(jù)不同情況是可變的。當(dāng)種群中符合約束條件的個(gè)體數(shù)目很少時(shí)，使用較大的交叉概率使個(gè)體更新更快從而產(chǎn)生更多的新個(gè)體；當(dāng)種群中符合約束條件的個(gè)體數(shù)目較多時(shí)，則使用較小的交叉概率，以免較好的個(gè)體被很快地破壞掉。

6）變異操作

通常，變異操作是以較小的概率將某些個(gè)體的某些位簡(jiǎn)單、隨機(jī)地變成其他值［7］。本文結(jié)合布線問(wèn)題的特點(diǎn)，借鑒了免疫遺傳算法［8］中接種疫苗的思想，使變異操作不是對(duì)某些基因位進(jìn)行隨機(jī)盲目地修改，而是使這些基因位的修改更有可能產(chǎn)生出適配度更高的個(gè)體。其具體實(shí)現(xiàn)與產(chǎn)生初始種群時(shí)的改進(jìn)方法相似，將隨機(jī)選定的發(fā)生變異的基因位的值（對(duì)應(yīng)于某根電纜的布放方案）按概率修改為值i，即：

式中，n為當(dāng)前電纜的候選路徑數(shù)目；i為候選路徑編號(hào)，i＝0，1，…，n－1。

也就是說(shuō)，通過(guò)變異使某根電纜的布放方案以較大的概率變?yōu)檫x擇長(zhǎng)度更短的路徑，而不是完全隨機(jī)地?fù)Q成其他路徑。通過(guò)這種改進(jìn)的變異方法，不僅可以達(dá)到通常通過(guò)變異加大種群多樣性的目的，而且可以達(dá)到接種疫苗、提高后代個(gè)體適應(yīng)度的效果。另外，將變異概率設(shè)計(jì)成隨種群中符合約束條件的個(gè)體數(shù)目的多少而變化。

7）檢測(cè)操作

傳統(tǒng)的遺傳算法并沒(méi)有這一操作，這是本文的另一項(xiàng)改進(jìn)，目的是防止在交叉、變異的過(guò)程中出現(xiàn)退化現(xiàn)象。該操作借鑒了De Jong的“杰出人才模型”［9］及免疫遺傳算法中免疫檢測(cè)的思想。具體方法是對(duì)經(jīng)過(guò)交叉、變異后的新一代個(gè)體進(jìn)行檢測(cè)，如果其最佳個(gè)體反不如上一代最佳個(gè)體的適應(yīng)度高，那么就復(fù)制上一代的最佳個(gè)體取代新一代個(gè)體中適應(yīng)度較低的某一個(gè)體。

8）確定算法終止條件

由于最大進(jìn)化代數(shù)很難進(jìn)行合適的設(shè)置，為適應(yīng)算法性能的動(dòng)態(tài)變化，較好地兼顧算法的優(yōu)化性能和時(shí)間性能，可采用佱閾值法設(shè)計(jì)算法的終止條件［10］，即若最優(yōu)解經(jīng)過(guò)連續(xù)若干代（本文設(shè)為100）進(jìn)化仍保持不變，則終止搜索過(guò)程。

5 仿真結(jié)果

5.1 實(shí)例計(jì)算

圖2表示一個(gè)6結(jié)點(diǎn)8通道的簡(jiǎn)單電纜通道網(wǎng)絡(luò)，其中括號(hào)內(nèi)的數(shù)字為各段通道的編號(hào)，括號(hào)外的數(shù)字為各段通道的長(zhǎng)度，即通道段長(zhǎng)度矩陣L＝［3，3，1，2，5，5，2，3］。

假設(shè)要在圖2中每?jī)蓚€(gè)結(jié)點(diǎn)間都布1根電纜，電纜可走任意路徑，但要符合各段通道的容量約束要求。由于該圖是無(wú)向圖，全連接時(shí)最多存在N·（N－1）／2（N為結(jié)點(diǎn)數(shù)）條鏈路，故共需布放15根電纜。已知每段通道的最大容量均為20，即通道段容量矩陣：

Q＝［20，20，20，20，20，20，20，20］T

圖2 電纜通道網(wǎng)絡(luò)圖

所有電纜的基礎(chǔ)信息如表2所示。

表2 電纜基礎(chǔ)信息

在實(shí)際操作時(shí)，通常要首先搜索出每根電纜的全部可行路徑，但在進(jìn)行全局優(yōu)化時(shí)，并不一定要把所有的可達(dá)路徑都列為候選路徑，因?yàn)橛行┞窂皆趯?shí)際中根本不可能被選中，例如連接結(jié)點(diǎn)A和B的電纜，雖然存在路徑A→E→C→D→F→B，但這種路徑并沒(méi)有多大實(shí)際意義。另外，在有些情況下，用戶可能需要為某些電纜指定特殊的布線規(guī)則，例如要求連接結(jié)點(diǎn)A和D的電纜必須經(jīng)過(guò)（或禁止經(jīng)過(guò)）結(jié)點(diǎn)B。所以在選擇候選路徑時(shí)，可以指定一個(gè)候選路徑數(shù)目，例如每根電纜都只自動(dòng)搜索長(zhǎng)度最短的兩條路徑作為該電纜的候選路徑，或者先給出某根電纜的所有可達(dá)路徑，然后由用戶指定幾條路徑作為候選路徑。在本文中，為了測(cè)試算法的最終性能，將所有可達(dá)路徑都作為候選路徑以增加搜索難度。

采用上述構(gòu)造的改進(jìn)遺傳算法對(duì)該例求解，計(jì)算結(jié)果如下（詳見(jiàn)表3、表4）：

優(yōu)化變量：

X∈｛（0，0，0，0，0，0，0，0，0，0，0，0，0，0，0），（0，0，0，0，0，0，0，0，0，0，0，0，0，1，0）｝；

最小費(fèi)用：

C＝216

實(shí)例計(jì)算結(jié)果表明本算法能夠快速、準(zhǔn)確地找到全局最優(yōu)的電纜布放方案，證明了該算法對(duì)求解電纜布局優(yōu)化問(wèn)題是可行、有效的。

5.2 性能分析

針對(duì)上述實(shí)例，應(yīng)用傳統(tǒng)遺傳算法和改進(jìn)遺傳算法分別求解。兩種算法都基于C語(yǔ)言編程并在同一臺(tái)計(jì)算機(jī)上運(yùn)行，其中種群規(guī)模和終止代數(shù)（即最優(yōu)解連續(xù)出現(xiàn)代數(shù)）均設(shè)為100。兩種算法各隨機(jī)運(yùn)行20次，其測(cè)試結(jié)果如表5所示。

表3 電纜最優(yōu)布放方案所需費(fèi)用

表4 電纜最優(yōu)布放方案所需容量

表5 兩種算法性能測(cè)試結(jié)果

從表5可以看出，與傳統(tǒng)遺傳算法相比，應(yīng)用改進(jìn)遺傳算法能夠在獲得相同最優(yōu)解 （即最小目標(biāo)值）的同時(shí)大大減少迭代次數(shù)，計(jì)算時(shí)間也相應(yīng)減少。若將某些關(guān)鍵通道的最大容量減小，如：

Q＝［15，20，20，20，10，20，20，15］T

則這種收斂速度的差距還將更大，而且傳統(tǒng)算法還常會(huì)出現(xiàn)收斂于某些局部最優(yōu)解的情況。另外，隨著電纜通道網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)量的增加，本算法的優(yōu)勢(shì)還將更加明顯。

6 結(jié)束語(yǔ)

本文采用遺傳算法進(jìn)行船舶電纜布局優(yōu)化設(shè)計(jì)，具有很高的實(shí)用性，使得船舶設(shè)計(jì)中復(fù)雜的布線工作實(shí)現(xiàn)自動(dòng)化和最優(yōu)化，以達(dá)到提高效率與降低成本的目的。與傳統(tǒng)遺傳方法不同的是，本文對(duì)產(chǎn)生初始種群的方法、選擇算子及變異算子進(jìn)行了改進(jìn)，并增加了檢測(cè)操作，大大提高了算法的收斂速度和準(zhǔn)確性，而且避免了傳統(tǒng)算法容易陷入局部最優(yōu)的不足。當(dāng)然，該方法還有許多值得進(jìn)一步研究的地方，例如在數(shù)學(xué)建模時(shí)可以考慮更多的實(shí)際因素，使其具有更強(qiáng)的適用性，另外仍需不斷提高算法自身的尋優(yōu)能力，以更好地發(fā)揮其優(yōu)越性。

［1］楊新敏，孫靜怡，錢育渝.城市交通流配流問(wèn)題的遺傳算法求解［J］.昆明理工大學(xué)學(xué)報(bào)（理工版），2002，27（5）：144－146.

［2］HOLLAND J H.Genetic algorithms and the optimal allocations of trials［J］.SIAM Journal of Computing，1973（2）：88－105.

［3］HOLLAND J H.Adaptation in natural and artificial systems［M］.Ann Arbor，MI：The University of Michigan Press，1975.

［4］錢志勤，滕弘飛，孫治國(guó).人機(jī)交互的遺傳算法及其在約束布局優(yōu)化中的應(yīng)用［J］.計(jì)算機(jī)學(xué)報(bào)，2001，24（5）：553－559.

［5］BAKER J E.Adaptive selection methods for genetic algorithms ［C］／／Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Hillsdale：New Jersey，1985.

［6］WHITLEY D，et al.The GENITOR algorithm and selection pressure：why rank base allocation reproduction trials is best［C］／／Proceedings of the 3rd International Conference on Genetic Algorithms.LosAltos：Morgan Kaufmann Publishers，1989.

［7］姚文俊.遺傳算法及其研究進(jìn)展［J］.計(jì)算機(jī)與數(shù)字工程，2004，32（4）：41－43.

［8］王小平，曹立明.遺傳算法——理淪、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，2004.

［9］李敏強(qiáng)，寇紀(jì)凇，林丹，等.遺傳算法的基本理論與應(yīng)用［M］.北京：科學(xué)出版社，2002.

［10］王凌.智能優(yōu)化算法及其應(yīng)用［M］.北京：清華大學(xué)出版社，2001.

The Application of Genetic Algorithm in Optimal Design for Ship Cable Routing

Wang Xue-lian Huang Jun
China Ship Development and Design Center，Wuhan 430064，China

Local optimization on cable layout is a technical obstacle to achieve automatic cabling in ships.The solution to this problem can save both time and cost dramatically so that the technology is significant.This paper establishes the optimizing model on cable routing problem.On the basis of analyzing the weakness of traditional genetic algorithm，the paper builds an improved genetic algorithm which improves population initialization，selection and mutation operator，and adds detection operator.The simulation results show that this genetic algorithm is a method of routing optimization which has the global optimum seeking ability.At the same time，the method has high efficiency and practicability，and can be extended to solve other optimization problems concerning ship design.

genetic algorithm；optimum design；cable laying；ship

U665

A

1673－3185（2009）04－72－04

2008－11－12

汪雪蓮（1978－），女，工程師，碩士。研究方向：船舶優(yōu)化設(shè)計(jì)。E-mail：lily1128＠126.com

黃 君（1980-），男，工程師，碩士。研究方向：船舶系統(tǒng)設(shè)計(jì)