基于多目標優化模型的扇葉最優分組與排列方案

薛煌鎧 宋佳怡 苗育睿

收稿日期：2023-08-04

DOI：10.19850/j.cnki.2096-4706.2024.07.022

摘? 要：衡量某種機械單片扇葉結構優劣的指標有“質量”與“轉動頻率”兩種參數，為了合理地裝配整個風扇，需要相鄰組的扇葉質量差達到最小，同時相鄰葉片的頻率差達到最大。首先構建一個單目標優化的質量分組模型，其后引入遞推型動態規劃算法，使得相鄰組的扇葉質量差達到最小。同時考慮轉動頻率的影響，再建立一個多目標優化的質量分組模型，采用動態權重線性加權法，通過對比不同權重下相鄰扇葉組的最大質量差和相鄰扇葉的最大頻率差，發現當A目標和B目標的權重均為0.5時，該模型所給出的方案效果最佳。

關鍵詞：遞推型動態規劃算法；多目標優化分組模型；動態權重線性加權法

中圖分類號：TP391? 文獻標識碼：A? 文章編號：2096-4706（2024）07-0100-07

Optimal Grouping and Arrangement Scheme of Fan Blades Based on

Multi-objective Optimization Model

XUE Huangkai， SONG Jiayi， MIAO Yurui

（Beijing Institute of Technology， Beijing? 102401， China）

Abstract： The indicators for measuring the quality of a single fan blade structure of a certain machinery include two parameter：“mass”and“rotational frequency”， In order to assemble the entire fan reasonably， it is necessary to minimize the mass difference between adjacent groups of fan blades and maximize the frequency difference between adjacent blades. Firstly， a mass grouping model with single objective optimization is constructed， and then a recursive dynamic planning algorithm is introduced to minimize the mass difference between adjacent groups of fan blades. At the same time， considering the influence of rotational frequency， a mass grouping model with multi-objective optimization is established， and the dynamic weight linear weighting method is used， by comparing the maximum mass difference between adjacent groups of fan blades and maximum frequency difference between adjacent blades under different weights， it is found that when the weights of target A and target B are both 0.5， the scheme provided by the model has the best effect.

Keywords： recursive dynamic planning algorithm; multi-objective optimization grouping model; dynamic weight linear weighting method

0? 引? 言

某機器的核心部件是由一個中心轉軸和多個扇葉構成，轉軸和扇葉是分開制造的，然后組裝到一起，如圖1所示。

圖1? 某機械扇葉組合安裝效果圖

在實際加工制造時扇葉的各種參數會產生隨機誤差，為了使這些扇葉能和轉軸配合組裝，正常運轉，組裝時需要在一定條件下進行分組和排序。這里考慮24個扇葉的情況，所有扇葉均勻分布在轉軸邊上，圍成一圈，表1和表2給出了兩組扇葉的相關參數值。

扇葉裝配時需滿足兩個目標：

A目標即所有24個扇葉按位置分成6組，每4個連續的扇葉為1組，每組4個扇葉總質量與相鄰組4個扇葉總質量的差要小于等于某個盡可能小的定值。

B目標即所有相鄰扇葉的頻率差要大于等于某一盡可能大的定值。

兼顧目標A和B建立模型，給出使相鄰組扇葉質量差盡可能小、相鄰扇葉頻率差盡可能大、不同參考標準下合理的扇葉分組及排序方式。

1? 數據的處理與分析

對于引言中給出的兩張表，我們利用Excel分別繪制出葉片的質量分布圖和頻率分布，如圖2所示。

從圖2中我們不難看出：兩組葉片的質量和頻率分布并不是均勻的，而是呈現一個周期性的規律，以6個葉片為單位，相互間具有相近的質量和頻率，這也為后續我們對這兩項指標的處理提供了重要的信息。

2? 單目標優化的質量分組模型

2.1? 目標A分析

我們先考慮目標A。從扇葉質量的角度出發，進行分組。共給出了24片扇葉，每4片連續的葉片為1組，總計6組。要求相鄰各組的扇葉質量之和的差盡可能小。若用Mci （i ∈ 1，2，…，6）表示這6組分組中第i組的總質量，且考慮到風扇的裝配是圓周狀，需考慮首尾兩組葉片組的質量差，故增加Mc7 = Mc1。由此，我們可以把問題表述為：

min | Mci - Mc（i+1） |? ? ? ? ? ? ? ? ? ? ? ?（1）

當各個組的差均達到最小，考慮最大的那個質量差，可以進一步寫成：

min max | Mci - Mc（i+1） |? ? ? ? ? ? ? ? ? ?（2）

將絕對值改寫為平方的形式：

min max（Mci - Mc（i+1））2? ? ? ? ? ? ? ? ? （3）

令函數y = min max（Mci - Mc（i+1））2，由平方的非負性可知y≥0。當且僅當Mci = Mc（i+1）即Mc1 = Mc2 = … = Mc6 =? 時（其中 ），函數y達到最小值，且ymin = 0。

于是目標A? 每組扇葉質量和越接近6組均值越好

2.2? 單目標優化模型建立

基于上述的分析，我們很容易知道這屬于一個離散的最優化問題，如何分組才能達到最佳的效果，也就是目標A所要求的質量差最小，各組的質量都接近平均值。于是我們著手構建一個單目標優化[1]的質量分組模型。

2.2.1? 確定決策變量

對于本問題而言，決策變量即為分組的方式。我們可以定義一個映射f（f為雙射），建立起從葉片編號NO.X到片在分組時的位置Cij的對應關系。而此時的映射關系f即為我們的決策變量：

（4）

2.2.2? 確定目標函數

在2.1小節的問題分析中我們知道，我們已經把問題轉化成了：每組扇葉質量和越接近6組均值越好，于是我們的目標函數便可參照式（2）寫成：

（5）

2.2.3? 確定約束條件

在本題中，扇葉的分組方式是有稍加限定的，24個扇葉要被均分成6組，每組有且只有4個扇葉，我們可以利用Cij中i與j的取值來加以限定：

（6）

2.3? 模型求解

2.3.1? 遞推型動態規劃算法求解

為了解決最佳質量分組的問題，我們引入動態規劃算法[2]，先不考慮全局最優解，也就是不能一步劃分成6組。而是將該問題分解成若干個子問題，考慮如果每組只有1個元素，該如何劃分；如果每組有2個元素，又該如何劃分；這些若干的子問題具有相互的關聯性。我們按照這個思路，設計了遞推的動態規劃算法，圖3可以清楚地展示出我們的思路。

為了更直觀地展示上述算法的過程，我們繪制了流程示意圖，如圖4所示。

2.3.2? 求解結果分析

利用上述的動態規劃算法，我們用Python進行了實現，將最佳分組方案以圖表形式進行呈現，最后得到ci的分組策略，如圖5所示。

上述得到的ci分組方案，一共有216種組合，且這些組合的相鄰組質量差均一致，下面列出表格進行詳細說明，如表3所示。

如表3所示，每一組的葉片質量和近乎相等，最大的質量差不超過1 g。可以認為是最大程度符合條件A的最佳分組策略。

我們以同樣的思路處理第二組的24個數據，得到的分組策略如圖6所示。

第二組葉片的最佳分組方案一共有48種，每一種的各組質量和均相同，我們同樣以列表的方式進行了呈現，如表4所示。

如表4所示，第二組數據分組后，每組質量和的差稍大，但最大的質量差不超過2 g。可以認為是最大程度符合條件A的最佳分組策略。

圖6? 第二組葉片的最佳分組方案圖

2.4? 模型敏感性分析

當扇葉數量變為36、48個時，我們的模型是否仍有效？我們將輸入的扇葉葉片數量i×j作為自變量，利用題中所給的兩組數據，來分別模擬36個和48個葉片的情況，并再次使用我們的動態規劃法求解，并比較與在24個葉片時的分組的差距。結果如圖7所示。

圖7? 不同葉片數量下分組差異圖

由圖7可以明顯地看出，隨著葉片數量不斷增加，組與組之間的質量波動會越來越明顯，但總體來看波動均不超過±50 g，故可以認為模型一仍然有效。

3? 多目標優化的質量分組模型

3.1? 雙目標分析

同時兼顧目標A和目標B，在上一節中我們已經知道，目標A的目標就是讓各組的質量差?Mci盡量達到最小，而目標B則是要求在此基礎上讓每兩個相鄰葉片的頻率差盡可能大，即? fij盡可能大（表示第i組的第j個扇葉與下一扇葉頻率差值）。這屬于一個典型的多目標離散分組問題，下面我們建立多目標優化的分組模型[3]來解決問題。

3.2? 多目標優化模型建立

3.2.1? 確定決策變量

這次我們將24組葉片的排列順序直接當成一個解，用ck表示24個葉片中的第k（k≤24）個葉片，此時我們用g來表示當前的一個順序解，g = c1c2…c24c25（c25 = c1）。要說明的是g代表一種排列方案，所有可行的解g構成解空間（決策空間）G = g。所以我們的決策變量就是排序方案g。

3.2.2? 確定目標函數

根據上一節我們可以由式子（5）導出A條件對應的目標函數：

（7）

式（7）表示了組與組之間的質量差最小。接下來同樣給出條件B對應的目標函數：

（8）

這個函數表示了所有相鄰葉片的頻率差最大化。

3.2.3? 確定約束條件

本問的約束條件同上一問，但由于重新規定了排序，因此在數值上有一些小改動：

（9）

3.3? 模型求解

3.3.1? 動態權重線性加權法

在上一節中，我們已經知道現在需要求解的是一個多目標的離散的組合優化問題，可以把時（7）至式（9）的所有方程組列出如下：

一般來說，對于這種多目標規劃問題的絕對最優解是不常見的，對絕大多數的多目標決策的實際問題，我們一般偏好的方案是有效解或非劣解，也稱為Pareto最優解[4]。

首先，我們先將2個最大和最小的不同方向的函數轉化成方向一致的求最小值問題：

（10）

之后考慮到A條件與B條件的重要程度可以不同，于是采用動態權重線性加權法[5]，給予每項不同的權系數wj （0≤wj≤1，j = 1，2），從而充分體現出每個目標的不同重要程度對結果的影響：

（11）

3.3.2? 交替迭代的模擬退火算法

我們已經對目標函數做了一定的處理，接下來我們需要引入模擬退火算法。示意圖如圖8所示。

圖8? 模擬退火算法示意圖

模擬退火算法是一種通用的隨機搜索算法，其基本的思想來源于固體的退火過程，是一種基于概率的算法：將固體加溫至充分高，再讓其徐徐冷卻。加溫時，固體內部粒子隨溫度升高變為無序狀態，內能增大；而徐徐冷卻時粒子漸漸趨于有序。在每個溫度都達到平衡態后在常溫下達到基態，內能減為最小，以優化問題的求解與物理過程退火的相似性為基礎，適當地控制溫度的下降過程，實現模擬退火從而達到全局優化的目的[6]。

本文通過PDMOSA求解，PDMOSA是Suman[7]在2004年提出的多目標模擬退火算法。該算法通過基于Pareto支配的適應度計算劣解的接受概率。該適應度被定義為當前Pareto解集中支配該解的數量加1。PDMOSA比其他多目標模擬退火算法效率更高。此外，作為一種單軌跡搜索算法，PDMOSA在求解VRP問題上有優勢[8，9]。

模擬退火算法被用于解決各種組合優化問題，下面是本模型使用模擬退火算法求解的基本過程：

1）定義狀態：將每個扇葉的排序g = c1c2…cu…cv…c24作為問題的一個狀態，其中每個狀態表示一種扇葉的排序方式。

2）初始化當前狀態為一個隨機的初始分組方式。

3）設置初始溫度T0和終止溫度Tend，以及溫度下降的速率e = 0.99（退火率）。

4）迭代執行以下步驟直到達到終止條件（例如達到終止溫度或達到最大迭代次數）：

步驟1：產生當前狀態的鄰域狀態，可以通過交換兩個不同編號的扇葉（如cu與cv）排序得到鄰域狀態g' = c1c2…cv…cu…c24。

步驟2：計算當前狀態和鄰域狀態之間的目標函數值差異? fij = min f （g） - min f （g'）（即相鄰組的目標函數差值）。

步驟3：如果目標函數值差異為負（即鄰域狀態更優），則接受鄰域狀態作為新的當前狀態。

步驟4：如果目標函數值差異為正（即鄰域狀態較差），則以一定概率接受鄰域狀態。接受劣解的概率由Metropolis準則[10]來確定。

步驟5：更新溫度，降低溫度值。

5）返回最終收斂到的當前狀態作為最優分組方式及相鄰關系。

在每次迭代中，通過接受劣解的策略，退火算法能夠逐步減小溫度，使算法逐漸趨向于全局最優解。最終，退火算法將收斂到一種扇葉分組方式，使得相鄰組之間的總質量差值最小。

用圖9所示的流程圖可以更直觀地描述模擬退火算法。

3.4? 最終結果分析

我們利用Python程序運行模擬退火算法，求出了在不同權重下的Pareto最優解，下面我們將分情況展示：

1）情況一：Wm = 0.5、Wf = 0.5時，最優分組編號排序如表5所示。

在權重配比都為0.5時，我們的結果很好地符合了組與組之間質量差小、片與片之間頻率差大的規律。從圖10中也可以直觀地看出，兩組數據均滿足條件。

2）情況二：Wm = 0.7、Wf = 0.3時，最優分組編號排序如表6所示。

當我們把質量差的權重調到0.7，頻率差的權重為0.3時，從圖11可以看到在最大質量差基本沒有改變的情況下，頻率的波動有減小的趨勢，最小頻率差也在減小。

3）Wm = 0.3、Wf = 0.7時，最優分組編號排序如表7所示。

當我們把質量差的權重調到0.3，頻率差的權重為0.7時，可以從圖12中看出質量差的波動稍有變大，而頻率差則基本無變化。

綜上所述，我們發現當A條件和B條件的權重均為0.5時，該模型所給出的方案是效果最佳的，既滿足組與組質量差最小，又滿足片與片頻率差最大化。其余兩種權重下，雖然與第一種方式有差異，但差異較小，也可作為不同裝配方案的參考。

4? 結? 論

本文針對扇葉裝配的常見要求，以24個葉片規格的扇葉為基礎，依次分析質量與轉動頻率兩種參數對裝配方案產生的影響和最佳分組策略。

首先考慮單目標質量指標，即使得相鄰組的扇葉質量差達到最小，構建單目標優化的質量分組模型，其后引入遞推型動態規劃算法輔助最優分組。表1扇葉經處理得到216種相鄰組質量差均一致的組合，每一組最大的質量差不超過1 g；表2組葉片的最佳分組方案一共有48種，最大的質量差不超過2 g。此外，對于不同葉片數量的情況進行了模型靈敏度分析，應用模型和算法，帶入不同數量（36、48個）的葉片質量和頻率，發現隨著葉片數量不斷增加，組與組之間的質量波動會越來越明顯，但總體來看波動均不超過±50 g，可以得出該分組策略對于不同數量扇葉基本適用。

在此基礎上同時考慮“轉動頻率”的影響，即滿足相鄰個的葉片的頻率差達到最大化。建立多目標優化的質量分組模型，采用動態權重線性加權法，給予質量與轉動頻率兩種參數不同的權系數，從而充分體現出每個目標的不同重要程度對結果的影響。在模型的基礎上，使用交替迭代的模擬退火算法得到最優解。通過對比不同權重下，相鄰扇葉組的最大質量差和相鄰扇葉的最大頻率差，發現當A條件和B條件的權重均為0.5時，該模型所給出的方案是效果最佳的。

綜上，本文通過合理構建數學模型與計算機輔助求解的方法，創新性提出合理的加工裝配方案，該機械渦扇的技術人員可依據上述方案，為該類型的扇葉提供更準確的理論安裝指導。

參考文獻：

[1] 王依凡，葉宏達，邱子杰，等.基于單目標優化的眾包任務定價模型 [J].實驗科學與技術，2018，16（5）：1-5+29.

[2] 王茂萍，潘大志.求解集值折扣{0-1}背包問題的改進動態規劃算法 [J].計算機應用與軟件，2022，39（9）：274-277.

[3] 吳瑞霞.模糊多目標優化的分類與特征選擇方法和應用 [D].煙臺：魯東大學，2021.

[4] 劉仁云，張美娜，姚亦飛，等.一種新的全局排序高維多目標優化算法 [J].吉林大學學報：理學版，2022，60（3）：664-670.

[5] 王一華.中國大陸圖書情報專業期刊的綜合評價——基于熵權法、主成分分析法和簡單線性加權法的比較研究 [J].情報科學，2011，29（6）：943-947.

[6] 賈天理，喻若舟，王思凱，等.函數最值計算的模擬退火算法設計與應用研究 [J].黑龍江科學，2022，13（1）：149-151.

[7] SUMAN B.Study of simulated annealing based algorithms for multiobjective optimization of a constrained problem [J].Computers & Chemical Engineering，2004，28（9）：1849-1871.

[8] WANG J H，ZHOU Y，WANG Y，et al. Multiobjective Vehicle Routing Problems With Simultaneous Delivery and Pickup and Time Windows： Formulation， Instances， and Algorithms [J].IEEE Transactions on Cybernetics，2016，46（3）：582-594.

[9] 畢志升.基于多目標模擬退火的團隊定向問題 [J].自動化與儀器儀表，2017（5）：41-44+47.

[10] 鄧紹強，郭宗建，李芳，等.基于Metropolis準則的自適應模擬退火粒子群優化 [J].軟件導刊，2022，21（6）：85-91.

作者簡介：薛煌鎧（2003—），男，漢族，福建福州人，本科在讀，研究方向：數學建模與應用；宋佳怡（2004—），女，漢族，山東青島人，本科在讀，研究方向：數學建模與應用；苗育睿（2004—），女，漢族，北京人，本科在讀，研究方向：數學建模與應用。