[發(fā)明專利]一種船舶多芯管下料的優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201310637887.0
• 申請日: 2013-11-29
• 公開（公告）號: CN103714198B
• 公開（公告）日: 2017-12-26
• 發(fā)明（設(shè)計）人: 陳映;陳波;崔峻;馬延德;季寶軍;楊光;顏麗琳;艾進(jìn);王袖鈞;高霞;鮑雨暉
• 申請（專利權(quán)）人: 大連船舶重工集團(tuán)有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 大連智慧專利事務(wù)所21215
• 代理人: 劉琦

1.一種船舶多芯管下料的優(yōu)化方法，其特征在于，對多芯管下料問題進(jìn)行數(shù)學(xué)抽象，將生產(chǎn)實際問題轉(zhuǎn)化為數(shù)學(xué)問題，建立數(shù)學(xué)模型，針對該數(shù)學(xué)模型采用遺傳算法進(jìn)行求解，通過實現(xiàn)以上算法，計算出原材料的總需求量，并詳細(xì)給出每一根原料對應(yīng)的切割模式；

包括如下步驟：

第一步，建立數(shù)學(xué)模型；

對于遺傳算法，可描述為下述數(shù)學(xué)模型：

maxf(X)1as.t.X∈Ω1bΩ⊆U1c---(1)]]>

式中，X＝[x₁,x₂,…,x_n]^T為決策變量，f(X)為目標(biāo)函數(shù)，式1b和1c為約束條件，U是基本空間，Ω是U的一個子集，滿足約束條件的解X稱為可行解，集合Ω表示由所有可行解所組成的一個集合，叫做可行解集合；

第二步，針對該數(shù)學(xué)模型采用遺傳算法進(jìn)行求解，通過實現(xiàn)以上算法，計算出原材料的總需求量，并詳細(xì)給出每一根原料對應(yīng)的切割模式；

遺傳算法求解步驟為：

S1、初始群體的確定，設(shè)初始群體的規(guī)模為Q，即產(chǎn)生問題中Q個可行解，設(shè)t為進(jìn)化代數(shù)計數(shù)器，T為最大進(jìn)化代數(shù)，設(shè)染色體P_k為初始群體中第k個染色體，在產(chǎn)生每個染色體可行解過程中，tn_i是指當(dāng)前第i種材料剩下的需求量，RL是在輸出時為總切邊損失，TL是當(dāng)前切邊損失，C是當(dāng)前訂貨材料的總根數(shù)，d是第i種訂貨材料當(dāng)前能選取的最大數(shù)量；

具體算法如下：

1.1.k＝1；

1.2.當(dāng)k>Q時，完成染色體的選取過程，輸出目前包含多種信息的染色體P_k,k＝1,2,…,Q；否則，tn_i＝l_i,i＝1,2,…,m，l₁,l₂,…,l_m排序滿足下列條件：

l₁*tn₁≥l₂*tn₂≥…≥l_m*tn_m (2)

轉(zhuǎn)1.3；

1.3.產(chǎn)生第k個染色體；

1.4.

1.5.當(dāng)C＝0時，轉(zhuǎn)1.8；否則TL＝L,num＝num+1；

1.6.i＝1；

1.6.1.如果i<m，轉(zhuǎn)1.6.2；否則，轉(zhuǎn)1.7；

1.6.2.如果l_i≤TL且tn_i>0，轉(zhuǎn)1.6.3；否則，i＝i+1轉(zhuǎn)1.6.1；

1.6.3.從1到d中隨機(jī)地選取一個整數(shù)g，tn_i＝tn_i-g,TL＝TL-g*l_i,i＝i+1，轉(zhuǎn)1.6.1；循環(huán)1.6會產(chǎn)生一根原材料的切割方式；

1.7.RL＝TL+RL，對改變需求量后的訂貨材料綜合長度重新進(jìn)行排序，使得(1)成立，轉(zhuǎn)1.5；

1.8.儲存第k個染色體P_k的信息，其中num為消耗的原材料的數(shù)量，總的切邊損失為RL，同時記錄所有的切割方式；k＝k+1，轉(zhuǎn)1.2；

S2、個體評價，即計算個體的適應(yīng)值，采用數(shù)字符號編碼方法，使用目標(biāo)函數(shù)的倒數(shù)作為其適應(yīng)度函數(shù)；假設(shè)第t代第k個染色體為P(t,k)，它是對應(yīng)問題(1)一個可行解，其中消耗根原材料，每根原材料對應(yīng)一個切割模式，它們分別記為將其排列在一起，得到P(t,k)的編碼為：

P(t,k)=Pk1tPk2t...PkNktt,k=1,2,3,...,Q---(3)]]>

其中編碼記錄了第j個切割模式的數(shù)據(jù)和其中：

ujtk=L-Σi=1maijtkli---(4)]]>

適應(yīng)度函數(shù)為：

F(P(t,k))=1/Σj=1Nktujtk---(5)]]>

S3、選擇運算，采用比例選擇算子，其基本思想為個體被選中的概率與適應(yīng)度大小成正比，設(shè)第t代第k個個體的適應(yīng)度為則它被選中的概率為：

pkt=Fkt/Σv=1QFvt,k=1,2,...,Q---(6)]]>

具體算法如下：

3.1.計算計算令csum₁＝0；

3.2.在[0,1]之間隨機(jī)產(chǎn)生一個整數(shù)d，若csum_k<d≤csum_k+1,1≤k≤Q，則染色體被選中；這一步重復(fù)Q次，便有Q個染色體被選為下一代的父本；

S4、交叉運算，對于第t代染色體，選擇單點交叉算子進(jìn)行運算；

假設(shè)交叉點取為w，則相應(yīng)產(chǎn)生兩個候選子代為：

但是在一般情況下，它們不一定是問題(1)的一個可行解；我們先計算P(t,k)和P(t,k')的對應(yīng)第i種材料的根數(shù)與需求量的差：

yi=ni-yi′-Σj=w+1Nk′taijtk′,i=1,2,...,m---(7a)]]>

zi=ni-zi′-Σj=w+1Nktaijtk,i=1,2,...,m---(7b)]]>

其中這里表示第t代第k個染色體中第j個切割模式長度為l_i的切割數(shù)量；然后分別對子代染色體P(t,k)和P(t,k')進(jìn)行修正，修正后得到問題(1)的可行解；

具體算法如下：

4.1.確定整數(shù)j₀，先令j₀＝w+1,tn_i＝n_i-y′_i,i＝1,2,…,m，計算若tn_i≥0,i＝1,2,…,m，并且則j₀＝j(luò)₀+1，轉(zhuǎn)4.2.1；若tn_i<0，且則停止；否則

4.2.補(bǔ)充訂貨材料的差額部分，

4.2.1.若C＝0，則停止；否則，TL＝L,j＝j(luò)+1,i＝1，轉(zhuǎn)4.2.2；

4.2.2.如果i<m，轉(zhuǎn)4.2.3；否則，轉(zhuǎn)4.2.5；

4.2.3.如果l_i≤TL且tn_i>0，轉(zhuǎn)4.2.4；否則，i＝i+1，轉(zhuǎn)4.2.2；

4.2.4.從0到d中隨機(jī)地選取一個整數(shù)g，tn_i＝tn_i-g,TL＝TL-g*l_i,i＝i+1，轉(zhuǎn)4.2.2；

4.2.5.RL＝TL+RL，對改變需求量后的訂貨材料按當(dāng)前綜合長度進(jìn)行排序，使得(2)成立，轉(zhuǎn)4.2.1；

S5、變異運算，采用簡單變異策略對經(jīng)過交叉后的群體中以變異概率p_m隨機(jī)選取染色體進(jìn)行變異，首先隨機(jī)選取變位的個數(shù)，即在1至等概率選一個整數(shù)為然后再隨機(jī)選擇I_α個變異，設(shè)為接著對這I_α個切割模式進(jìn)行重新選擇；

具體算法如下：

5.1.令u＝1,tn_i＝0,i＝1,2,…,m；

5.2.隨機(jī)選取在區(qū)間隨機(jī)產(chǎn)生I_α個數(shù)

5.3.tn_i＝tn_i+a_iu,i＝1,2,…,m,u＝j(luò)₁,P(t,k)中消去后記為P'(t,k)；

5.4.對重新選擇，num_k＝0；

5.4.1若tn_i＝0,i＝1,2,…,m，則停止；否則，TL＝L,num_k＝num_k+1,i＝1，轉(zhuǎn)5.4.2；

5.4.2.如果i<m，轉(zhuǎn)5.4.3；否則，轉(zhuǎn)5.4.5；

5.4.3.如果l_i≤TL且tn_i>0，轉(zhuǎn)5.4.4；否則，i＝i+1，轉(zhuǎn)5.4.1；

5.4.4.從1到d中隨機(jī)地選取一個整數(shù)g，tn_i＝tn_i-g,TL＝TL-g*l_i,i＝i+1，轉(zhuǎn)5.4.1；

5.4.5.對改變需求量后的訂貨材料按當(dāng)前綜合長度重新進(jìn)行排序，轉(zhuǎn)5.4.1；

5.5.將上一步中產(chǎn)生的num_k個切割方式加入P'(t,k)中，就完成了變異運算；

S6、終止條件判斷，若t≤T，則t＝t+1，轉(zhuǎn)到S2；若t>T，則輸出具有最大適應(yīng)度的個體最優(yōu)解，終止計算。