李世春，楊世文

（中北大學(xué)機(jī)械與動力工程學(xué)院，山西 太原 030051）

基于迷宮問題遺傳算法的復(fù)合材料鋪層數(shù)量優(yōu)化

李世春，楊世文

（中北大學(xué)機(jī)械與動力工程學(xué)院，山西 太原 030051）

研究使用最少鋪層數(shù)量，使產(chǎn)品達(dá)到性能指標(biāo)的復(fù)合材料鋪層優(yōu)化問題。使用遺傳算法，參考迷宮問題的解決方法，保留普通遺傳算法的框架，改變求染色體的適應(yīng)度值的計算過程，找出滿足要求的最少鋪層數(shù)量的解。在求適應(yīng)度值過程中增加逐位解釋環(huán)節(jié)，以得不同鋪層數(shù)量的解。在求適應(yīng)度值過程中增加解碼、剔除無效項、對稱環(huán)節(jié)，以滿足復(fù)合材料鋪層角角度離散、鋪層角要少于4層連續(xù)相同、對稱這些常見要求。結(jié)合示例，指出將逐位解釋范圍分段，可以提高計算效率。該方法實(shí)現(xiàn)了對復(fù)合材料產(chǎn)品的鋪層數(shù)量和角度的同時優(yōu)化，可以實(shí)現(xiàn)產(chǎn)品的經(jīng)濟(jì)性和輕量化。

鋪層數(shù)量優(yōu)化；迷宮問題；遺傳算法

CLC NO.:TB332Document Code:AArticle ID:1671-7988(2014)02-17-06

前言

以力學(xué)性能為主要目標(biāo)的復(fù)合材料產(chǎn)品，通常使用層合結(jié)構(gòu)。其原材料通常為單向帶預(yù)浸料。預(yù)

浸料的剛度和強(qiáng)度在平行纖維方向很高，而垂直纖維方向很差。因此在層合結(jié)構(gòu)中，預(yù)浸料鋪放的角度順序，將極大地影響產(chǎn)品最終的性能。

鑒于鋪層的角度順序非常重要，目前研究者主要優(yōu)化每個角度值的取值，以得到產(chǎn)品最好的力學(xué)性能。而很多工程問題則是要求產(chǎn)品性能達(dá)到一個指標(biāo)即可，優(yōu)化目標(biāo)為產(chǎn)品的重量的優(yōu)化問題。若產(chǎn)品宏觀尺寸不變，產(chǎn)品重量將直接由所用鋪層的數(shù)量決定。因此對于這類工程問題，優(yōu)化目標(biāo)應(yīng)當(dāng)涵蓋鋪層數(shù)量。

目前針對鋪層數(shù)量的優(yōu)化，常用的有兩種方法。第一種方法[1]為，視角度數(shù)量固定，而每層鋪層的厚度可變，得到最優(yōu)解后，再將一層拆分為若干層。這種方法的缺點(diǎn)是無法滿足鋪層角要少于4層連續(xù)相同，否則將導(dǎo)致基體開裂。第二種方法[2]為，將角度序列作為染色體，使用遺傳算法。將一個角度順序表示前后兩個向量。第一個向量中，每一項為0或1，表示該層角度值不存在或存在。第二個向量中，每一項為角度值或角度值代號。由于第一個向量中0的存在，角度序列中有效角度個數(shù)是不確定的，以此實(shí)現(xiàn)了鋪層數(shù)量的變化。這種方法的缺點(diǎn)是，表示一個角度順序需要一個兩倍長度的向量，一個最優(yōu)解需要前后兩個模式（pattern)共同匹配，得到最優(yōu)解的難度較大。

觀察一個角度序列，首先可以看到各層的角度值，然后可以數(shù)出角度值的個數(shù)，即序列的長度。后者便是鋪層的數(shù)量，這個由角度序列可以得到的信息常常被忽略。去除一個原始的較長的角度序列中的一些項，會得到一個新的鋪層數(shù)量和角度順序的角度序列。本文正是基于這個基本思想，借鑒迷宮問題的遺傳算法解決方法，實(shí)現(xiàn)了對鋪層數(shù)量和角度順序同時優(yōu)化。

1、迷宮問題與復(fù)合材料鋪層優(yōu)化介紹

1.1 迷宮問題

迷宮問題[3,4]即，為小人B尋找一條，從起點(diǎn)到出口，能夠走出迷宮，且路程盡量短的路徑,見圖1。迷宮問題有三個特點(diǎn)。第一，在任意一個位置，小人的每一步有上下左右4種方向可選。第二，當(dāng)選定的方向遇到障礙物時，該方向會被認(rèn)為無效，將跳過該步進(jìn)行下一步。第三，每走一步，就需要判斷當(dāng)前位置與出口的距離，一旦到達(dá)出口，就停止。將有效的方向記錄在一個序列中?？尚薪鉃槟軌虻竭_(dá)出口的序列。解的長度作為解的評價指標(biāo)。最優(yōu)解則為長度最短的可行解。最優(yōu)解的長度未知。

1.2 復(fù)合材料鋪層優(yōu)化

由單向帶預(yù)浸料構(gòu)成的復(fù)合材料產(chǎn)品的性能，除材料本身的性能和產(chǎn)品尺寸外，主要由鋪層組合決定。

鋪層組合指鋪層的數(shù)量和每一層的角度值所構(gòu)成的角度序列。在工程實(shí)際中，角度值并不是連續(xù)變量，而是一些離散的值，通常為[-45°，0°，45°，90°]，也有以15°為間隔的角度系列。這些角度即可以認(rèn)為是小人的每一步的上下左右方向。產(chǎn)品的最終性能即由這些角度的序列決定。這一點(diǎn)與迷宮問題的第一個特點(diǎn)相同。

復(fù)合材料鋪層中，若連續(xù)4層方向均相同，則容易造成基體開裂而失效。即不能出現(xiàn)例如[45/ 45/45/45]的情況，第4個45°即被認(rèn)為是無效的方向。這個角度值的無效可以認(rèn)為是小人選定的方向有障礙物，自動跳過該角度值，讀取下一個角度值。這一點(diǎn)與迷宮問題的第二個特點(diǎn)相同。

最終得到的最優(yōu)的角度序列，其長度在優(yōu)化之初完全未知。角度序列的長度小，即鋪層數(shù)量少，則在同樣的尺寸下可以減輕產(chǎn)品質(zhì)量，優(yōu)化目標(biāo)即為鋪層的數(shù)量。這一點(diǎn)與迷宮問題的第三個特點(diǎn)相同，也是兩者本質(zhì)上的相同之處。

2、遺傳算法實(shí)現(xiàn)

2.1 算法流程

解決迷宮問題和鋪層數(shù)量優(yōu)化的遺傳算法，與一般的遺傳算法并沒有基本框架的變化，仍然是隨機(jī)生成若干染色體組成種群，計算每個染色體的適

應(yīng)度值。染色體根據(jù)適應(yīng)度值，通過復(fù)制、交叉、變異得到下一代種群，再次計算每個種群的適應(yīng)度值。如此循環(huán)迭代，直到滿足停止條件。有最好適應(yīng)度值的染色體即為最優(yōu)解。

迷宮問題遺傳算法，與普通遺傳算法的區(qū)別，僅在于對染色體的理解，和計算染色體的適應(yīng)度值的過程。迷宮問題遺傳算法，不認(rèn)為種群中的染色體可以直接作為解。染色體中的每個變量不都是有效的。真實(shí)染色體包含在染色體中，它的長度比染色體短。它的每一項才都是有效的。染色體使用真實(shí)染色體的適應(yīng)度值參與遺傳算法計算，這樣對普通遺傳算法改動較小。

普通遺傳算法得到適應(yīng)度值的流程圖，如圖2所示。

迷宮問題遺傳算法，得到染色體的適應(yīng)度值的流程圖，如圖3所示。

2.2 關(guān)鍵步驟

2.2.1 角度值的變換

遺傳算法所處理的染色體，并不是直接由角度值構(gòu)成的。因?yàn)榻嵌葹殡x散值，所以使用一些整數(shù)來代表角度。染色體由整數(shù)值構(gòu)成。在將染色體解釋完成后，才將整數(shù)還原為角度值，帶入產(chǎn)品計算函數(shù)計算該角度序列的適應(yīng)度值。

在鋪層設(shè)計中，有時要求平衡性。即+θ°與-θ°的數(shù)量相等。為解決這個問題，可將角度系列編為對應(yīng)變量向量為[1,2,3]。其中1代表0°，2代表±45°共兩層，3代表90°。這樣把問題進(jìn)一步簡化了。

2.2.2 染色體的對稱

復(fù)合材料鋪層設(shè)計中，通常要求對稱。所以將序列對稱后作為實(shí)際的鋪層順序。即變量(x1,x2…,xn)，實(shí)際代表的鋪層順序是（xn,…,x2,x1,x1,x2…,xn)。這樣的對稱，對稱后層數(shù)為偶數(shù)。

奇數(shù)層的對稱，如（xn，…，x2,x1,x2…xn)，也滿足對稱性要求。但只減少一層，在實(shí)際中影響不明顯。如有需要，可將偶數(shù)層的最中間層x1去掉一層，進(jìn)行驗(yàn)算，或是在優(yōu)化得到的層數(shù)的基礎(chǔ)上，減去一層，按固定層數(shù)問題，進(jìn)行優(yōu)化并比較。

2.2.3 染色體的逐位解釋

在迷宮問題中，開始時并不知道走到出口所需的步數(shù)，所以先估計一個較大的步數(shù)數(shù)量，然后隨機(jī)生成各種方向，形成一個方向序列，即一個染色體。按這種方法，隨機(jī)生成若干個染色體，構(gòu)成種群。這些染色體的長度是相等的，而且在進(jìn)化過程中也不會變化。

若將方向序列的每一步都執(zhí)行完，小人可能到達(dá)出口后又折回迷宮。將最后停止的位置距離出口的距離作為適應(yīng)度值評價，則該解的適應(yīng)度值會非常差。但是真正的解實(shí)際上已經(jīng)蘊(yùn)含在方向序列中了。所以需要小人每走一步就進(jìn)行一次評價。發(fā)現(xiàn)到達(dá)出口后，染色體中后續(xù)的方向就不再有意義。對染色體截取從第1位到某一位的片段，以這個片段作為一個可能的解，進(jìn)行評價，再分析從第1位到下一位的片段，再進(jìn)行評價，這個過程稱為逐位解釋。

到達(dá)出口后，若繼續(xù)讓小人運(yùn)動，其適應(yīng)度值將不會變好，通常是變差。將逐位解釋得到的適應(yīng)

度值組成適應(yīng)度值向量，該向量中的適應(yīng)度值將會逐漸變好，然后逐漸變差。假設(shè)最好的適應(yīng)度值對應(yīng)于從第1位到第k位的片段，（若有多個相同的最好適應(yīng)度值，則取最先出現(xiàn)的），則該染色體的有意義部分為從第1位到第k位的這一部分。這一部分，經(jīng)過剔除無效項后，即為真實(shí)染色體。

在復(fù)合材料鋪層數(shù)量優(yōu)化時，事先也不知道所需的最小層數(shù)。因此將層數(shù)數(shù)量取一較大的值，隨機(jī)生成各種方向，形成一個較長的染色體。從第一位開始，直到最后一位，依次計算適應(yīng)度值。例如染色體為（x1,x2，x3，x4）。其對應(yīng)的真實(shí)鋪層可能為(x1，x1)，(x2，x1，x1，x2)，(x3，x2，x1，x1，x2，x3)和(x4，x3，x2，x1，x1，x2，x3，x4)。其適應(yīng)度值分別為fitness1，fitness2，fitness3，fitness4。假設(shè)fitness3為最好的值，則該染色體的有意義部分為（x1,x2，x3），對應(yīng)的真實(shí)鋪層順序?yàn)?x3，x2，x1，x1，x2，x3)。

2.2.4 剔除無效方向

復(fù)合材料鋪層中，不允許出現(xiàn)連續(xù)4層方向相同的情況。

由于在此文章中，是偶數(shù)對稱鋪層，因此x2和x1不可以相同。若相同，則剔除x2，得到新的序列，再次判斷x2，直到得到一個x2不等于x1。然后從x1開始，判斷是否有連續(xù)4層方向相同。若存在，則剔除第4個方向，依次判斷并剔除。直到序列中不包含4個連續(xù)相同的值。

例如，假設(shè)在染色體逐位解釋到第6位時，得到的染色體片段為(4,4,3,3,3,3)。可看出應(yīng)該剔除第2位和第6位。剔除后得到的有效片段為(4,3,3,3)。對稱并解碼后，角度序列是[903/45]S。應(yīng)注意到這與逐位解釋到第5位時，得到的有效片段是相同的。也就是經(jīng)過逐位解釋和剔除過程后，有效片段可能會是重復(fù)的。

2.2.5 得到染色體的適應(yīng)度值和真實(shí)染色體

這樣，經(jīng)過逐位解釋、剔除無效項、對稱和角度變換后，一條染色體就解釋成為一系列長度不同的角度序列。用這些角度序列，分別計算適應(yīng)度值，其最好的適應(yīng)度值即為該染色體的適應(yīng)度值，進(jìn)行遺傳算法計算。最好的適應(yīng)度值所對應(yīng)的有效片段，即為真實(shí)染色體。

這樣一個變換的過程，可以單獨(dú)寫為一個函數(shù)。而用解釋出的角度序列求適應(yīng)度值的過程，寫為一個產(chǎn)品計算函數(shù)，被前者調(diào)用。

3、算法效果分析

使用一個簡單的算例，分析這種算法的效果。

算例1。已知單向碳纖維預(yù)浸料LT-02/T300B材料性能，E1=136GPa，E2=8.1GPa，G12=4.9GPa，V21=0.31，Xt=1560MPa，Xc=1380MPa，Yt=43.7MPa，Yc=215MPa，S=83.7MPa，預(yù)浸料厚度為0.127mm，密度為ρ=1800kg/m3。一矩形板長為a=0.5m，寬b=0.25m。在長度方向受拉力Fx=100kN。要求不能發(fā)生破壞，且長度方向變形量不得大于2mm。求滿足要求的最少的鋪層數(shù)量及其鋪層角度。暫不考慮連續(xù)4層方向不可以相同。

若不考慮連續(xù)4層方向不可以相同，因?yàn)橹皇躼方向的拉力，則該問題的最優(yōu)解明顯是由若干層0°構(gòu)成。由于該算法得到的鋪層順序是偶數(shù)層的。因此只計算偶數(shù)層情況。經(jīng)計算得，4層0°的變形量為2.9mm，6層0°的變形量為1.9mm，8層0°的變形量為1.4mm，且都不發(fā)生破壞。所以這個算例的最優(yōu)解為6層0°。

使用Matlab自帶GADS工具箱，結(jié)合整數(shù)規(guī)劃。將鋪層數(shù)量作為優(yōu)化目標(biāo)和適應(yīng)度值。將變形量和Hoffman準(zhǔn)則值作為約束，并使用罰函數(shù)將其集成到適應(yīng)度值函數(shù)中。將變量個數(shù)設(shè)定為10，也就是鋪層數(shù)量最大為20。設(shè)定種群個體數(shù)為20。將終止條件中，停滯代數(shù)（Stall generations）設(shè)置為

10，最大代數(shù)（generations）設(shè)置為20。進(jìn)行計算。

GADS返回的最優(yōu)染色體為[2,2,2,3,3,1,2,2,1,2]，最好的適應(yīng)度值為6。也就是說最優(yōu)解對應(yīng)的角度序列有6位，鋪層數(shù)量為6。染色體前6/2=3項有意義的值，組成這個染色體的真實(shí)染色體，為[2,2,2]（不考慮連續(xù)4層方向不可以相同）。解碼并對稱后，得到的角度序列為[06]。與之前計算的最優(yōu)解相同。

算例1的運(yùn)行過程顯示在圖4中。從圖4和GADS的運(yùn)行輸出中，都可以發(fā)現(xiàn)，在第一代中，最優(yōu)解已經(jīng)得到了。進(jìn)化是因?yàn)闈M足了停滯代數(shù)才終止的。

使用迷宮問題遺傳算法，最優(yōu)解在染色體中，作為一個模式（pattern）而存在，如此例中[2,2,2,*,*,*,*,*,*,*]，*表示任意取值。任何包含這種模式的染色體，都是最優(yōu)解。前言中所述優(yōu)化鋪層數(shù)量的第二種方法，其最優(yōu)解需要在兩倍長度的染色體上，生成前后兩個模式，兩個模式匹配后，才能得到最優(yōu)解。相比較，迷宮問題遺傳算法，得到最優(yōu)解的難度明顯較低。

在此例中，在第一代，隨機(jī)生成一個染色體時，生成這種模式的概率為1/43=1/64。對于種群數(shù)為20的初代種群，直接生成最優(yōu)解的概率相當(dāng)大。真正的最優(yōu)解的長度越短，則在初代中出現(xiàn)最優(yōu)解的概率越大，后續(xù)所需要的迭代次數(shù)也就越小。因此可以將停滯代數(shù)設(shè)置的少一些。而若真正的最優(yōu)解的長度較長，則在優(yōu)化時一定時間后得到的可行解長度也會較長，與真正的最優(yōu)解也較接近。因此若計算時間過長，則可以選擇一個較好的可行解，作為次優(yōu)解在工程中使用。故使用這種遺傳算法，停滯代數(shù)和最大代數(shù)都可以設(shè)置地比普通遺傳算法稍少一些，至少可以得到一個較好的次優(yōu)解以便工程使用。

4、算法改進(jìn)

若嚴(yán)格按照上述步驟進(jìn)行，則一個染色體要進(jìn)行n次逐位解釋，也即運(yùn)行n次適應(yīng)度值計算，（n為染色體長度）。若能估計出最優(yōu)解的大致長度，就沒必要從第1位到第n位全部逐位解釋，只需要在其附近逐位解釋，這樣將顯著減少計算量。若最優(yōu)解的大致長度完全未知，則可以將逐位解釋范圍分段，分階段進(jìn)行遺傳算法計算。

首先預(yù)估一個較大的范圍，比如染色體有20位，需要逐位解釋的范圍定在12到20位，然后進(jìn)行計算。若得到的最優(yōu)解在12到20之間，則可以認(rèn)為該解即為最優(yōu)解。若得到的最優(yōu)解為下界或更少，即12，則再縮減范圍為15到4，并將剛才得到的最優(yōu)解帶入初始種群中，進(jìn)行第二次遺傳算法計算，直到找到最優(yōu)解。第二次的范圍上界比第一次的下界稍大。這是因?yàn)閺娜旧w到鋪層順序的過程中，有剔除過程，所以應(yīng)將邊界范圍放松一些。邊界的變化順序，也可以是從小向大變化。

算例2。同算例1，但是這次計算考慮連續(xù)4層不能相同的約束，并分階段進(jìn)行遺傳算法計算。

首先，使用[0/+45/-45/90]準(zhǔn)各向同性鋪層方式，連續(xù)鋪層，并對稱。發(fā)現(xiàn)選用[90/45/-45/0/90/45/-45/0]S時，x方向變形量為1.9mm，小于2mm，最大Hoffman準(zhǔn)則值為0.6157，小于1，不破壞。將該解作為一個參考。該層數(shù)為16層。因此設(shè)置染色體長度為8。

分階段進(jìn)行遺傳算法計算。設(shè)置第一次遺傳算法計算中，染色體逐位解釋的范圍為5到8。

計算得到的最優(yōu)解為[2,2,2,4,2,2,1,4]。適應(yīng)度值為8。也就是說，前4個有效項組成真實(shí)染色體。前4個有效項為[2,4,2,2]，即鋪層順序?yàn)閇0/0/90/0]S。由于存在剔除過程，得到的解并不完全在限定的染色體范圍內(nèi)。比如此次限定的下限雖然為5，就得到了長度為4的解。

將這個第一次計算得到的有效染色體片段[2,4,2,2]，作為一種模式，生成一個染色體，比如[2,4,2,2,0,0,0,0]，放入第二次遺傳算法計算的初始種群中。設(shè)定此次逐位解釋范圍為1到5。

這次得到的最優(yōu)解為[1,2,2,2,1,2,3,1]，適應(yīng)度值為8。即真實(shí)最優(yōu)解的鋪層順序?yàn)閇03/-45]S，層數(shù)為8層。計算得x方向變形量為1.86mm，最大Hoffman準(zhǔn)則值為0.3981，滿足約束條件。

至此可以認(rèn)為[03/-45]S是最優(yōu)解。也可以嘗試將中間一層去掉，使用一個奇數(shù)層對稱結(jié)構(gòu)并對比。

將中間一層去掉，得[03/-45]S。計算這組解，得x方向變形量為1.89mm，最大Hoffman準(zhǔn)則值為0.3864，滿足約束條件。因此減去中間一層后的解，可以視為最優(yōu)解。即最優(yōu)解為7層，鋪層順序?yàn)橄啾容^優(yōu)化前使用準(zhǔn)各向同性鋪層方式，層數(shù)由16層減為7層，也就是減重56.25%。效果非常明顯。

在算例2中，可以發(fā)現(xiàn)前后兩階段中，兩個最優(yōu)解雖然不同，但其適應(yīng)度值是相同的，故也以認(rèn)為第一階段的最優(yōu)解是最終要得到的最優(yōu)解。所以這種分階段的方法，對于求一個滿意解或工程可以接受的次優(yōu)解，是非常有效的。

5、結(jié)論

本文通過找出迷宮問題和復(fù)合材料鋪層數(shù)量優(yōu)化問題的本質(zhì)相同之處，利用迷宮問題的遺傳算法解決方法，實(shí)現(xiàn)了對鋪層數(shù)量和鋪層角度的同時優(yōu)化。該方法保留普通遺傳算法的框架，只改造求染色體的適應(yīng)度值的計算過程，通用性好。

相較于常用的鋪層數(shù)量優(yōu)化方法，該方法可以處理鋪層角少于4層連續(xù)相同的要求。通過將逐位解釋范圍分段，改進(jìn)該方法后，可以快速得到最優(yōu)解或工程可用的次優(yōu)解。該方法計算后期主要為停滯，根據(jù)這個特點(diǎn)，可以引入自適應(yīng)措施繼續(xù)改進(jìn)。

[1] 劉昊, 楊和振. 基于多島遺傳算法的深海復(fù)合材料懸鏈線立管優(yōu)化設(shè)計[J]. 哈爾濱工程大學(xué)學(xué)報, 2013(07).

[2] 李偉國. 復(fù)合材料層合結(jié)構(gòu)可靠性優(yōu)化方法研究[D].南京航空航天大學(xué), 2005.

[3] 巴克蘭. 游戲編程中的人工智能技術(shù)[M]. 清華大學(xué)出版社, 2006.

[4] 王斌, 李元香. 用遺傳算法解迷宮問題[J]. 微型機(jī)與應(yīng)用, 2002(10):58-60.

Stacking number optimization of composite product by genetic algorithm based on maze problem

Li Shichun，Yang Shiwen

(North University of China School of Mechanical and Power Engineering ,ShanxiTaiyuan 030051)

This composite stacking optimization aims at the product meeting the target with least layers.Using genetic algorithm, referring to the solution to the maze problem, retaining the framework of the common genetic algorithm, changing the chromosome fitness value calculation process, the solution which has the minimum number of layers and meet the requirements was found.In the fitness value calculation process,the bit by bit explanation was added, to get solutions with various numbers of layers.In the fitness value calculation process, the encoding,removing invalid entries, symmetrization was added to meet the common requirements such as ply angles discrete, less than four contiguous plies in same direction, and symmetric.It pointed out with an example, that sectioning the range of the bit by bit explanation will improve efficiency. This method optimizes the stacking layer number and angles at the same time, which will achieve economical and lightweight.

stacking layers number optimization；maze problem；genetic algorithm

TB332

A

1671-7988(2014)02-17-06

李世春，碩士研究生，就讀于中北大學(xué)，主要研究方向：復(fù)合材料產(chǎn)品設(shè)計及結(jié)構(gòu)優(yōu)化設(shè)計。