基于遺傳算法的多分區結構化網格自動優化分區的研究

趙 璐 劉 勇 張 祥 岳孟赫

(南京航空航天大學能源與動力學院 江蘇 南京 210016)

0 引 言

隨著計算流體力學CFD己成為一門獨立的學科，而且在能源、環境、航空、航天、船舶等許多科學研和工程應用領域中發揮著日益顯著的作用，現在對于很多工程上的問題都是先進行數值模擬，得到理想的結果后再進行實驗論證[1]。數值模擬的第一步是建立模型并生成網格，網格質量的好壞嚴重影響到數值解的收斂性和精度。結構化網格的求解精度高，是三維工程分析的首選單元類型。對于結構簡單的模型來說，ICEM、Gambit等軟件可以在短時間內對模型劃分出高質量的網格。然而在面對復雜結構，例如帶冷卻結構的渦輪葉片結構化網格生成的工作量很大。在建立網格上所花的人力時間比在分析物理解所花的人力時間高出許多倍，而且網格質量也并不能達到最優化。當前對于邊界形狀復雜的六面體幾何體，不能直接生成相應的結構化網格。通常的做法是用手工方法將全局域中的區域分解成幾何形狀規則的子域，然后在各子域內進行網格映射。在這個過程中存在以下幾個問題：

1) 手工方法耗時長，且不具有普適性；

2) 不能確定各子域的質量是否最優。

為了解決這些問題，代星等[2]引入頂點分類理論對復雜多邊形子域的邊界進行簡化，但只提出了對于圓形和三角形區域劃分子域的方法，不具有普適性。White等[3]提出了一種可以自動劃分分區的方法，但此方法只適用于可掃略的幾何圖形，不能用于分解復雜模型。目前對于復雜形體，尚缺乏具有高效性、高質量的結構化分區網格自動優化方法。Jonathan[4]根據厚/薄分解方法提出了一種自動分解復雜幾何體的方法，但此方法劃分出來的長/細區域適用于結構化網格，剩余子區域適用于非結構化網格。目前對于復雜形體，尚缺乏具有高效性、高質量的結構化分區網格自動優化方法。

針對以上問題，本文首先建立分區的評價指標，然后將分區的產生構造成一個尋找此指標最佳的優化過程，最后采用遺傳算法[5-9]來進行分區尋優。通過組合基本的二進制編碼來表述分區切割點的空間位置信息，以自動求得結構化的優化分區。

1 分區質量評價體系

設計一個結構化網格分區優化算法的第一步是要先確定結構化網格分區的質量。近幾十年來，網格優化技術的研究一直是人們研究的重點內容，各大商業軟件中也有對網格質量進行評價的指標，如雅可比、正交性和縱橫比[10]等。本文基于結構化網格質量的度量對分區質量進行了深入的研究，提出了一套分區質量評價體系。網格分區評價體系基于以下幾個指標。(1) 翹曲度η(-1≤η≤1，理想值為1)；(2) 歪斜度Ω(0≤Ω≤1，理想值為1)；(3) 相似度ε(0≤ε≤1，理想值為1)。對于標準長方體分區，這些參數均為1。

1.1 分區結構

結構化分區為六面體結構，本文規定其六個面分別為E、S、W、N、T、B。其中E面與W面互為對應面，S面與N面互為對應面，T面與B面互為對應面。每個面有四條邊，分別記為e、s、w、n，邊e與邊w相對應，邊s和邊n相對應。分區結構越接近于長方體，劃分出的網格質量也就越高。由于模型幾何結構的限制，分區結構通常為不規則的六面體，即分區存在扭曲的不規則面，分區面間存在過大或過小的夾角。如圖1所示，(a) 為理想分區，(b) 為工程中經常遇到的不規則分區。對于各種不規則的分區結構，由于缺乏經驗，直接劃分出高品質的結構化網格的概率比較低。因而需對分區結構進行優化使之接近規則分區，以便劃分結構化網格。

圖1 分區結構

1.2 分區質量指標

1.2.1 翹曲度η

翹曲度表征了分區面的翹曲程度，面外翹曲發生在分區面的四個頂點不共面的情況下。該指標的計算過程如下：分區面的四個頂點共可劃分出兩對三角形，依次計算每對三角形所構成的面的夾角θ，尋找出最大值，并按照線性關系將角度進行歸一化，即為翹曲度η，如圖2所示。當四個點共面時，θ=0。當出現兩個三角形面片法向逆向時，-1<η<0，此時分區極有可能產生負體積網格。

(1)

圖2 分區翹曲

1.2.2 歪斜度Ω

歪斜度表征了分區面內的歪斜程度，反應了該分區面與矩形的類似程度。該指標的計算過程如下：四個頂點對應四個角，依次計算四個空間角度值θ，尋找出最大和最小的角度值，并按照線性關系進行歸一化，其中最小的數值解即為歪斜度Ω。

(2)

1.2.3 相似度ε

相似度表征了分區對應曲面的相似程度，包括對應線相似度ε1，對應角相似度ε2和對應面積相似度ε3。該指標的計算過程如下：

(1) 結構化分區共有三組對應邊：(T.s=>T.n=>B.s=>B.n)、(T.w=>T.e=>B.w=>B.e)、(E.e=>E.w=>W.e=>W.w)，每組對應邊共有四條線，依次計算每組對應邊每條線的長度，每組對應邊中最短長度與最大長度之比為ξa。

(3)

對應線相似ε1則為

ε1=(ξa1,ξa2,ξa3)min

(4)

(2) 結構化分區共有十二組對應角，每組對應角共有兩個角，依次計算每組對應角每個角的角度θ，最小角與最大角的比值為ξb。

(5)

對應角相似度則為:

ε2=(ξb1,ξb2,ξb3,…,ξb12)min

(6)

(3) 結構化分區中共包含三組對應面：(T=>B)、(E=>W)、(S=>N)每組對應面包含兩個面，每組對應面中最小面面積與最大面面積之比為ξc。

對應面積相似度則為:

ε3=(ξc1,ξc2,ξc3)min

(7)

目前大體上有兩種定義網格質量的方法[11]，一類是將網格質量定義為所有單元質量的總和或平均值[12]，另一類是以網格中最差的一個單元質量來表示整個網格的質量[13-14]。為了在優化過程中分區質量的改進有一定的取向性，使盡可能多的低質量分區變為高質量分區，本文參照網格質量定義的方法，選用分區質量度量中最差的一個指標來表示整個分區的質量Q。

Q=(η,Ω,ε1,ε2,ε3)min

(8)

2 優化遺傳算法

2.1 問題描述

為了自動劃分最優結構化分區，首先要確定好幾何體上一些特征結構的位置：比如葉片上的氣膜孔列、擾流柱、尾緣劈縫和擋板等結構變化的位置。這些位置會在固體域的內外表面產生必須的結構分區，從而產生一些固定點。本文優化算法的思路是通過幾何特征計算得到每個分區產生的固定點，之后用遺傳算法確定切割點，使得這個分區的質量達到最優。如圖3所示，在這個復雜幾何體中，固定點為A1，A2，…，A6，C1，C2，…，C6，切割點為B1，B2，…，B6。如何優化確定Bi系列的切割點，本文采用了兩種辦法：串行優化和整體優化。串行優化是對分區依次進行優化，當第一個分區優化結束后再對第二個分區優化，以此類推，直至最后一個分區優化結束，每一次優化都使得當前分區質量指標最高。在算法上表現為從起點開始逐次確定Bi點對，如圖3中，首先通過優化算法確定(B1B2)，然后再確定(B3B4)，依此類推將Bi點全部優化完。整體優化是對所有分區同時進行優化，優化結果確保所有分區的平均質量指標最高。在算法上表現為同時將所有Bi點作為待求點，通過優化算法一次性確定這些點。兩種優化算法均為了優化結構化分區，提高分區網格質量。

圖3 結構化分區計算示意圖

2.2 串行優化遺傳算法

串行算法的步驟為：

步驟1首先根據A1、A2、A3、A4、C1、C2為已知點，在邊A4-A8(頂邊)和A2-A6(底邊)上分別確定點B2、B1，使A1、A2、A3、A4、C1、C2、B1、B2這八個點形成第一個最優分區。

步驟2根據C1、C2、C3、C4、B1、B2為已知點，在邊B2-A8(頂邊)和B1-A6(底邊)上分別確定點B4、B3，使C1、C2、C3、C4、B1、B2、B3、B4這八個點形成第二個最優分區。

步驟3依此計算，當計算最后節點對，即B9、B10時，要同時保證最后兩個分區都為最優，避免最后一個分區質量變差。

首先對個體染色體進行編碼。由于同時求解的是兩個變量，所以采用一個二元值val[2]來表征一個染色體，每個值采用傳統的32位二進制串來表示(0～1)之間的浮點值，該浮點值表征該點在求解域中的比例位置：

(9)

因此B1和B2點的計算公式為：

B1=A2+val[0](A2-A6)

(10)

B2=A4+val[1](A4-A8)

(11)

其次隨機產生初始種群，種群規模大小可根據實際情況設定。之后進行適應度計算。遺傳算法中以個體適應度大小來判斷各個個體的優劣程度，從而決定每個個體的遺傳概率。在本算法中，目標函數即為分區的質量度量Q。

質量度量總是非負的，且優化目標是求得目標函數的最大值，因此直接將目標函數設為個體的適應度。此方法是依次對每個分區尋優，因而適應度f則是單個分區的質量度量。

f=Q[i]=(η[i],Ω[i],ε1[i],ε2[i],ε3[i])min

(12)

式中：i代表第i個分區。

最后依次進行選擇運算、交叉運算和變異運算。選擇運算會將當前群體中適應度較高的個體按照某種準則傳遞到下一群體中去。其具體操作是計算每個個體的適應度fi與當前群體中所有個體適應度的總和的比值，即個體的相對適應度fref：

(13)

相對適應度就是每個個體被傳遞到下一代群體中的概率。最后隨機產生一個0到1之間的數，依據這個隨機數出現在上述哪個概率內來確定每個個體被選擇的次數。交叉運算以某一概率互相交換某兩個個體間的部分染色體。本算法選用單點交叉法，其具體操作是對群體中個體的染色體設置交叉點位置并進行隨機配對，互相交換配對的兩個染色體間的基因。變異運算是對某個或某些基因值按某一小概率進行改變。本算法選用基本位變異法，具體操作為確定每個個體上基因變異的位置，根據一小概率將變異點位置的基因值取反。對當代群體進行選擇、交叉、變異運算后可以得到一個新的群體。遺傳算法的終止條件有兩類常見條件，一類是設定最大進化代數；另一類是根據個體的差異來判斷，即所有基因位相似程度來進行控制。針對本文問題，設定最大進化代數簡單易行，且可以得到較為精確的最優解，因此選取設定最大進化代數作為遺傳算法的終止條件。經過迭代運算，求得最優分區。當此分區優化完成后，此分區計算得出的上點和下點則變為下一分區的確定點，如此再進行下一分區的優化。

2.3 整體優化遺傳算法

整體優化時，染色體中的二元值對的個數n是變值，根據具體的問題由外部確定，例如在圖3所示的實例中，n=5。染色體中采用二維數組來表示個體：val[n][2]。每個二進制串翻譯成0～1之間的值，表示該點在頂邊和底邊上的比例位置。為了保證這些點的順序：例如B4在B2-A8之間，B6在B4-A8之間等等，除第一對點以后的每對點的比例位置需要重新計算：

B2=A4+val[0][0](A4-A8)

(14)

B4=B2+val[1][0](B2-A8)=A4+

[val[0][0]+val[1][0](1+val[0][0])](A4-A8)

(15)

…

本算法旨在使得所有分區的質量平均，因而目標函數即為所有分區網格的質量度量的平均值。個體的適應度f為：

(16)

式中：i代表第i個分區。

3 優化應用

為了證明這兩種優化算法的適用性，本文選取航空發動機中具有代表性的渦輪葉片作為分區優化對象。

現代的渦輪葉片都設計為結構復雜的空心葉片，其主要部分為葉身、緣板和榫頭三部分。由于這個幾何體的的各個部分間存在著類似結構，故選取葉盆側尾緣-前緣之間的結構進行優化，如圖3所示。其中A1-A3-A7-A5面為葉盆固體的外表面，A2-A4-A8-A6為計算域的外流場邊界。面A1-A3-C2-C1中包含了一列擾流柱，這在固體域的內外表面產生必須的結構分區，故本例中C1-C2為已知點，由葉盆表面結構確定。對應面的點B1-B2則由本文提出的優化算法所確定。同理，點C3-C4,C5-C6,C7-C8,C9-C10都為已知的固定點，通過優化算法求得對應的切割點：B3-B4,B5-B6,B7-B8,B9-B10。

本例中共需劃分6個分區：P1，P2，P3，P4，P5，P6，如圖4所示。串行優化算法的思想是依次優化每個分區，即首先根據固定點C1-C2確定P1分區的兩個切割點B1-B2。當此區域優化完成后，點B1-B2隨之成為P2分區的固定點，由此確定P2分區的切割點B3-B4。如此依次優化，直至求得P6分區的切割點B9-B10，優化結束。整體優化算法是一種多變量尋優的方法，因而需保證點與點之間位置關系的正確性(B3在B1與B5之間，B5在B3與B7之間，B7在B5與B9之間，B9在B7與A6之間，B4在B2與B6之間，B6在B4與B8之間，B8在B6與B10之間，B10在B8與A8之間)。約束這些點的位置之后則可根據目標函數同時確定切割點B1-B2,B3-B4,B5-B6,B7-B8,B9-B10的位置。

圖4 葉盆分區

為了更清楚地展現出優化分區，將葉片結構進行隱藏。對同一計算域，兩種優化算法劃分出的分區如圖5、圖6所示。

圖5 串行優化算法劃分的分區

圖6 串行優化算法劃分的分區

4 結果分析

整個渦輪葉片分為外流場、固體域、內流場和榫頭四部分。外流場共劃分了47個分區，固體域劃分了30個分區，內流場劃分了85個分區，榫頭劃分了4個分區，此工作量十分繁重。本文利用這兩種優化算法分別對葉片進行了分區處理，并進行了比較。

應用本文開發的渦輪葉片管理軟件及提出的評價分區質量體系分別對兩種優化方法劃分出的分區進行質量檢驗，如圖7所示。

(a) 分區最大質量指標

(b) 分區最小質量指標

(c) 分區平均質量指標圖7 分區質量指標

串行優化算法的目標函數是單個分區的質量指標。在尋優時，每次只考慮一個分區的質量指標，因此此算法得到的分區質量指標最大值更大，且各個分區的質量相差也略大，這也與數據結果一致。整體優化算法的目標函數是所有分區網格質量度量的平均值，因此尋優結果的趨勢是使得分區的質量分布較為集中，即各個分區的質量都大致相近。

實驗結果表明隨著迭代次數的增大，兩種優化算法均可提高分區的質量。串行優化算法提高了分區的最大質量，而整體優化算法提高了分區的最小質量及平均質量。在提高分區質量的能力上，整體優化算法更為適用。

由本文設計的一種參數化網格管理軟件分別對兩種優化方法劃分出的分區進行結構化網格劃分，并進行網格質量檢驗，得出的結果如圖8所示。(a) 為串行優化分區算法劃分出的網格的質量。(b) 為整體優化分區算法劃分出的網格的質量。由此可以看出，分區質量越高，網格質量也就越高。

(a) 串行優化分區的網格質量

(b) 整體優化的網格分區質量圖8 葉盆網格質量

串行優化算法每次單獨優化一個分區，尋優完成后再進行第二個分區的優化，因此耗時較長；整體優化算法則同時對所有的分區進行優化，屬于多變量尋優，耗時較短。而由人工對此計算域進行分區并優化的過程至少需要兩小時。表1為兩種優化方法所消耗的時間。實驗結果表明隨著迭代次數的增加，兩種優化算法分區耗時也在增加。而整體優化算法分區耗時普遍比串行優化算法分區耗時短。

表1 分區耗時

5 結 語

本文對具有復雜邊界的幾何體的結構化分區優化進行了研究，基于遺傳算法提出了兩種用于優化網格分區的方法，有效解決了復雜形體結構化分區的自動優化，極大縮短了分區時間。本文通過組合的二進制編碼來表述分區切割點的空間位置信息，采用遺傳算法將分區的產生構造成一個尋找分區質量最佳的優化過程，從而確定切割點，得到優化分區。其優化過程分為兩種，一種是串行優化，即按照順序依次產生優化分區；另一種是整體優化，使得所有分區的質量平均化。實例驗證表明，本文提出的兩種自動優化方法可靠，都能夠保證高質量網格的生成。而整體優化算法在提高網格質量及計算耗時上更具有優越性。