基于迷宮問題遺傳算法的復合材料鋪層數量優化

李世春，楊世文

（中北大學機械與動力工程學院，山西 太原 030051）

基于迷宮問題遺傳算法的復合材料鋪層數量優化

李世春，楊世文

（中北大學機械與動力工程學院，山西 太原 030051）

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

鋪層數量優化；迷宮問題；遺傳算法

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

前言

以力學性能為主要目標的復合材料產品，通常使用層合結構。其原材料通常為單向帶預浸料。預

浸料的剛度和強度在平行纖維方向很高，而垂直纖維方向很差。因此在層合結構中，預浸料鋪放的角度順序，將極大地影響產品最終的性能。

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

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

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

1、迷宮問題與復合材料鋪層優化介紹

1.1 迷宮問題

迷宮問題[3,4]即，為小人B尋找一條，從起點到出口，能夠走出迷宮，且路程盡量短的路徑,見圖1。迷宮問題有三個特點。第一，在任意一個位置，小人的每一步有上下左右4種方向可選。第二，當選定的方向遇到障礙物時，該方向會被認為無效，將跳過該步進行下一步。第三，每走一步，就需要判斷當前位置與出口的距離，一旦到達出口，就停止。將有效的方向記錄在一個序列中。可行解為能夠到達出口的序列。解的長度作為解的評價指標。最優解則為長度最短的可行解。最優解的長度未知。

1.2 復合材料鋪層優化

由單向帶預浸料構成的復合材料產品的性能，除材料本身的性能和產品尺寸外，主要由鋪層組合決定。

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

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

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

2、遺傳算法實現

2.1 算法流程

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

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

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

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

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

2.2 關鍵步驟

2.2.1 角度值的變換

遺傳算法所處理的染色體，并不是直接由角度值構成的。因為角度為離散值，所以使用一些整數來代表角度。染色體由整數值構成。在將染色體解釋完成后，才將整數還原為角度值，帶入產品計算函數計算該角度序列的適應度值。

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

2.2.2 染色體的對稱

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

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

2.2.3 染色體的逐位解釋

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

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

到達出口后，若繼續讓小人運動，其適應度值將不會變好，通常是變差。將逐位解釋得到的適應

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

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

2.2.4 剔除無效方向

復合材料鋪層中，不允許出現連續4層方向相同的情況。

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

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

2.2.5 得到染色體的適應度值和真實染色體

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

這樣一個變換的過程，可以單獨寫為一個函數。而用解釋出的角度序列求適應度值的過程，寫為一個產品計算函數，被前者調用。

3、算法效果分析

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

算例1。已知單向碳纖維預浸料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，預浸料厚度為0.127mm，密度為ρ=1800kg/m3。一矩形板長為a=0.5m，寬b=0.25m。在長度方向受拉力Fx=100kN。要求不能發生破壞，且長度方向變形量不得大于2mm。求滿足要求的最少的鋪層數量及其鋪層角度。暫不考慮連續4層方向不可以相同。

若不考慮連續4層方向不可以相同，因為只受x方向的拉力，則該問題的最優解明顯是由若干層0°構成。由于該算法得到的鋪層順序是偶數層的。因此只計算偶數層情況。經計算得，4層0°的變形量為2.9mm，6層0°的變形量為1.9mm，8層0°的變形量為1.4mm，且都不發生破壞。所以這個算例的最優解為6層0°。

使用Matlab自帶GADS工具箱，結合整數規劃。將鋪層數量作為優化目標和適應度值。將變形量和Hoffman準則值作為約束，并使用罰函數將其集成到適應度值函數中。將變量個數設定為10，也就是鋪層數量最大為20。設定種群個體數為20。將終止條件中，停滯代數（Stall generations）設置為

10，最大代數（generations）設置為20。進行計算。

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

算例1的運行過程顯示在圖4中。從圖4和GADS的運行輸出中，都可以發現，在第一代中，最優解已經得到了。進化是因為滿足了停滯代數才終止的。

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

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

4、算法改進

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

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

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

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

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

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

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

這次得到的最優解為[1,2,2,2,1,2,3,1]，適應度值為8。即真實最優解的鋪層順序為[03/-45]S，層數為8層。計算得x方向變形量為1.86mm，最大Hoffman準則值為0.3981，滿足約束條件。

至此可以認為[03/-45]S是最優解。也可以嘗試將中間一層去掉，使用一個奇數層對稱結構并對比。

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

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

5、結論

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

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

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

[2] 李偉國. 復合材料層合結構可靠性優化方法研究[D].南京航空航天大學, 2005.

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

[4] 王斌, 李元香. 用遺傳算法解迷宮問題[J]. 微型機與應用, 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

李世春，碩士研究生，就讀于中北大學，主要研究方向：復合材料產品設計及結構優化設計。