基于權重估計與混合多標準決策的帕累托最優解篩選

摘 要 對于多目標優化問題，傳統的多標準決策方法在求得帕累托最優解集時就會結束。但在實際問題中，往往需要基于決策者的偏好從解集中選取單一的最優方案。基于該問題，創新性地提出基于最小生成樹算法的權重學習方法，用于整合決策者的偏好，并結合層次分析法與消除和選擇表達現實法的思想，提出一種混合多標準決策方法，幫助選擇最符合要求的帕累托最優解。為了驗證該方法的可靠性，基于某地區天然氣管網銷售多目標模型求得的帕累托最優解數據進行測試與分析，結果表明：該方法選出的帕累托最優解能夠很好地契合決策者偏好，并為帕累托前沿的選擇提供有效的建議。

關鍵詞 多目標優化 權重學習 多標準決策 混合方法 層次分析法 消除和選擇表達現實法" 天然氣管網銷售

中圖分類號 TP273"" 文獻標志碼 A"" 文章編號 1000-3932（2024）05-0854-10

最優化問題源于眾多復雜的決策場景，涵蓋生產調度、工程設計、數據處理、投資分配等領域。而多目標優化問題（Multi-objective Optimization Problem，MOP）在工程應用和科學研究中是一種最常見的問題形式，因而在最優化問題中占據了重要地位。多目標優化需要同時考慮兩個及以上的優化目標，這些目標函數往往存在關聯而又相互沖突，因此很難找到同時優化所有目標函數的解。換句話說，這種情況下不可能找到一種解決方案，既可以改善一個目標函數又不會導致至少一個其他目標函數的惡化。因此，求解MOP的目標實際是找到一個包含一些折中解的集合，稱之為帕累托最優解集（Pareto-optimal Set，POS）。相應地，帕累托最優解集在目標空間中的映射稱為帕累托最優前沿（Pareto-optimal Front，POF）［1～3］。目前，求解帕累托最優解集的主要算法有基于數學的規劃方法和基于進化的算法兩類方法［4～8］。

POS代表了不同目標之間的權衡，不是單一的解決方案，這些帕累托最優解彼此“并不差”。此時，決策者的任務是根據得到的帕累托最優解和前沿，按照實際需求與自身偏好選擇最佳方案。過去數十年間，有學者考慮到了帕累托最優解和前沿的進一步選擇問題，并展開了研究。文獻［9］提出一種參考點方法，這個參考點通常代表的是決策者的偏好或問題的特定背景，通過與參考點的距離來度量解的優劣，帕累托前沿上的解應盡可能接近或達到參考點，這是一種先驗方法。加權度量法也是一種常見方法，它通過引入權重來平衡不同目標之間的關系，這種方法的核心思想是將多目標問題轉化為單一目標問題，通過為每個目標引入一個權重，將多個目標的優劣綜合考慮［10］。此外，對于一些常見的多目標規劃具體應用問題，許多學者也進行了進一步研究。文獻［11］提出一種基于雙層模糊的協商方法來模擬分散制造供應鏈中許多合作伙伴之間的協同規劃，在協商過程中，利用遺傳算法對雙目標規劃模型進行了優化，生成帕累托最優解前沿，并提出了一種模糊邏輯方法，對得到的帕累托前沿進行協商，以做出適當的決策。文獻［12］提出一個雙目標、多產品、多站點的供應鏈規劃問題，考慮的目標函數是總成本的最小化和產品質量水平的最大化，采用字典法的極大極小法從帕累托前沿中尋找到了一個公平的解，該解同時滿足不同的目標函數。然而，將上述方法應用于實際問題時的不足之處：首先，這些方法都具有較大的依賴性，需要決策者在每次選擇前設定權重或參考點，甚至可能需要多次嘗試才能找到滿足特定需求的解；其次，在一些問題中，目標之間可能有潛在的關聯性，而加權度量法和參考點法通常難以處理這種關聯性。對于這些傳統方法的劣勢，近些年來多標準決策在幫助決策者從帕累托最優解前沿中選擇折衷解的諸多評價方法中顯得尤為突出。多標準決策（Multiple-Criteria Decision-Making，MCDM）是在存在多個相互沖突標準的情況下根據決策者的偏好做出選擇的方法［13］，是運籌學的一個分支，用于在具有各種指標和相互沖突的目標和標準的復雜場景中尋找最佳結果。

多標準決策的解決過程通常涉及沖突的目標，因此需要分配權重以優先考慮不同的目標。傳統上，權重確定一直是個具有挑戰性的任務。筆者提出了一種新穎的方法，通過決策者參與選擇帕累托解來學習多目標規劃中的目標權重，并以此記錄決策者的偏好，以便后續可以完成帕累托最優解的自主選擇，為決策者提供最佳的可選方案。此外，本研究結合層次分析法（Analytic Hierarchy Process，AHP）與消除和選擇表達現實法（Elimination Et Choice Translating Reality，ELECTRE）提出一種混合多標準決策方法，充分利用AHP的權重分配以及ELECTRE的排除和選擇能力，同時綜合考慮決策者的偏好和多個準則，最終決策結果將更全面、可靠，并兼顧不同的決策要求。

1 基于最小生成樹的權重學習算法

1.1 最小生成樹算法

最小生成樹是圖論中一個經典的問題，該問題指的是在一個連通加權圖中尋找一個子圖，要求找到的子圖符合以下4點要求：

a. 子圖無回路；

b. 子圖中任意兩個頂點之間都存在路徑；

c. 子圖所有邊的權重之和最小；

d. 子圖包含所有頂點。

符合上述要求的子圖被稱為最小生成樹（Minimum Spanning Tree，MST）。與此同時，最小生成樹算法也是一種基本的圖論技術，可以用于找到連接圖中所有節點的邊的最小可能總權重子集，它確保了一個連通且無環的結構，同時最小化邊權重之和，因此也可以將其應用于權重計算［14］。

常用的尋找最小生成樹的算法有兩種，分別是Kruskal算法和Prim算法，兩種算法都基于貪心策略，但是兩個算法的執行方式存在一定差異。Kruskal算法是將圖中分散的樹結構合并進而生成最小生成樹。Prim算法是以單個的起始頂點逐漸添加邊線以生成最小生成樹。由于兩個算法執行方式的差異，兩者的應用場景也有所不同，其中Kruskal算法常用于邊數較少的圖中，而Prim算法常用于邊數較多的圖中［15］。

1.2 權重學習過程

權重學習過程分為4個步驟完成，具體如下：

2 混合多標準決策方法

2.1 層次分析法

層次分析法（AHP）是解決多標準決策問題最流行的方法之一，用于幫助決策者在多標準問題中確定優先級和評估備選方案。AHP方法的原理是對不同的備選方案和準則進行兩兩比較，以獲得它們的相對權重，并在備選方案中做出最優決策［16］。下面闡述層次分析法解決決策問題的主要步驟。

c. 消除和選擇表達現實法階段。將AHP中計算的權重與ELECTRE中的偏好關系相結合，以獲得綜合權重。定義每個準則的表達式或規則，以描述哪些備選方案符合或不符合該準則。基于準則表達式排除那些不符合準則的備選方案。構建偏好關系矩陣，以確定備選方案之間的偏好關系。

d. 基于優勢度與劣勢度進行篩選，保留最優的方案作為最佳選擇。

3 計算結果

3.1 實驗環境

本實驗使用來自131節點的實際天然氣銷售多目標優化問題產生的帕累托解集進行篩選。同時，應用混合多標準決策方法，根據決策者的偏好從帕累托解集合中選擇最優帕累托解。實驗采用Excel 2021軟件和Python3.7環境，在一臺64位Windows 10計算機AMD RYZEN 7 4800H八核中央處理器（CPU）實現解決方案，程序總體運行時間均在4 s之內。

3.2 實驗數據

131節點天然氣銷售多目標優化問題求得的帕累托解依照年份分為18年，每年的求解數據為10組，以Excel表格數據形式存儲。后續實驗均按不同年份進行篩選、排序，并分別測試了18年完整的180組數據。鑒于篇幅限制，只將第1年的10組帕累托解集列于表2。

由表2數據可以看出，銷量與效益是相互矛盾的，天然氣銷量提高時，對于天然氣管網末端用戶而言，天然氣的供給更加充足，少氣或停氣的可能性降低，因此用戶滿意度與評價也隨之上升。然而當天然氣銷量過高時，天然氣管網中的各組件負擔較大，導致運營資源消耗急劇上升，天然氣輸送分配總成本的增長超過了銷量增大帶來的銷售額，效益隨之下降。因此，天然氣總銷量的最大化和效益的最大化往往是相互矛盾的目標。因此，本實驗旨在幫助決策者根據自己的偏好（決策者的偏好作為一種先驗知識），在生成的帕累托解中選擇最優解。

3.4 實驗程序與輸出結果

3.4.1 實驗結果

編寫程序執行上述完整步驟，并對共計18年的完整180組數據進行測試，得出的篩選結果匯總于表5。

此外選取其中4年的帕累托解集，繪制三維散點折線圖，如圖1所示。

3.4.2 數據定性分析

從數據的角度來分析圖1中4組最優帕累托解，可以看出混合多標準決策方法篩選出的最優解均具有以下優勢：

a. 綜合性能優越性。以第1年為例，雖然方案4的效益不是最大，但在銷量、效益和用戶滿意度這3個關鍵指標上都表現出色，表明它在多個方面具有很高的性能。這種綜合性能優越性使其成為一個有吸引力的選擇。

b. 平衡性較好。利用混合多標準決策方法篩選出的最優解在銷量、效益和用戶滿意度之間取得了很好的平衡。這種平衡性意味著它既可以在銷售方面表現出色又可以提供相對高的效益和用戶滿意度。這對于長期業務成功至關重要。

c. 風險分散特性。選擇出的方案均不具備很大風險。依賴于單一最大值指標的選擇可能使業務更容易受到外部因素的影響。選擇多標準平衡的方案可以在不同情況下具有更好的韌性。

d. 用戶滿意度考量。用戶滿意度對于保持客戶忠誠和口碑很重要。應用此方法篩選出的方案用戶滿意度均達到0.75及以上，促進重復購買和口碑傳播。

e. 長期利潤。以第1年為例，雖然效益可能不是最大的，但方案4的銷量和用戶滿意度高，這可能會在長期內帶來更高的利潤。滿足客戶需求和建立品牌聲譽，產生長期回報。

綜合來看，通過混合多標準決策篩選出的方案在多個方面表現出優勢。考慮到各種因素，所選方案仍然可以作為最佳選擇，尤其是在一個綜合性能和平衡性都非常重要的決策情境中。

4 結束語

為了有效解決天然氣銷售多目標優化模型中無法準確給出最佳帕累托解的問題，中國石油大學（北京）高小永團隊創新性地提出一種混合多標準決策方法，將層次分析法與消除和選擇表達現實法的思想融合在一起。通過這一方法，能夠為用戶選擇最佳可選方案提供可靠參考。并且，通過對天然氣管網銷售優化模型的帕累托解集的驗證證實了其實用性。這種混合多標準決策方法為決策者在帕累托前沿中做出最優解選擇提供了有效幫助。

在未來的研究中，可以考慮深入研究如何更好地整合其他多標準決策方法，包括改進算法、擴展方法、考慮不確定性等因素。并且通過在其他實際案例中應用這種混合多標準決策方法，來驗證其有效性和實際可行性，能夠更全面地挖掘這種方法的性能和潛在局限。此外，還可以探索這種混合多標準決策在其他領域中的潛在應用。

參 考 文 獻

［1］"" FONSECA C M，FLEMING P J.Genetic Algorithms for Multiobjective Optimization：Formulation Discussion and Generalization［C］// Proceedings of the 5th International Conference on Genetic Algorithms.Urbana-Champaign，IL，USA，1993：416-423.

［2］"" MARLER R T，ARORA J S.Survey of multi-objective optimization methods for engineering［J］.Structural and Multidisciplinary Optimization，2004，26：369-395.

［3］"" CARLOS A C C.Evolutionary multi-objective optimization：A historical view of the field［J］. IEEE Computational Intelligence Magazine，2006（1）：28-36.

［4］"" 公茂果，焦李成，楊咚咚，等.進化多目標優化算法研究［J］.軟件學報，2009，20（2）：271-281.

［5］" "DEB K，PRATAP A，AGRAWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ［J］.IEEE Transactions on Evolutionary Computation，2022，6（2）：182-197.

［6］"" ZITZLER E，LAUMANNS M，THIELE L.SPEA2：Improving the Strength Pareto Evolutionary Algorithm［R］.TIK Report，2001：1-22.https：//doi.org/10.3929/ethz-a-004284029.

［7］""" ZHANG Q F，HUI L.MOEA/D：A Multiobjective Evolutionary Algorithm Based on Decomposition［J］.IEEE Transactions on Evolutionary Computation，2007，11（6）：712-731.

［8］"" NASIR A，SHA’AKMAL S. MOSDA：A Proposal for Multiple Objective Spiral Dynamics Algorithm［J］.Journal of Telecommunication，Electronic and Computer Engineering，2018（10）：15-19.

［9］"" DEB K，SUNDAR J.Reference point based multi-objective optimization using evolutionary algorithms［C］//Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation.2006：635-642.

［10］"" MIETTINEN K.Nonlinear multiobjective optimization［J］.International Series in Operations Research and Management Science，1998，12：115-129.

［11］"" YAHIA W B，AYADI O，MASMOUDI F.A sensitivity analysis of multi-objective cooperative planning optimization using NSGA-Ⅱ［C］//Multiphysics Modelling and Simulation for Systems Design and Monitoring：Proceedings of the Multiphysics Modelling and Simulation for Systems Design Conference.MMSSD，2014：17-19.

［12］"" FELFEL H， AYADI O， MASMOUDI F.A decision-making approach for a multi-objective multisite supply network planning problem［J］.International Journal of Computer Integrated Manufacturing，2016，29（7）：754-767.

［13］""" LERTPRAPAI S.Review：Multiple Criteria Decision Making Method with Applications［J］. International Mathematical Forum，2013，8（7）：347-355.

［14］"" CHAZELLE B，RUBINFELD R，TREVISAN L.Approximating the Minimum Spanning Tree Weight in Sublinear Time［J］.International Colloquium on Automata，Languages and Programming，2001：190-200.

［15］"" TANG C，HOU C P， WANG P C，et al.Salient object detection using color spatial distribution and minimum spanning tree weight［J］.Multimedia Tools and Applications，2016，75：6963-6978.

［16］" ""AYADI O， FELFEL H， MASMOUDI F.Analytic hierar-

chy process-based approach for selecting a Pareto-optimal solution of a multi-objective，multi-site supply-chain planning problem［J］.Engineering Optimization，2017，49：1264-1280.

［17］"" 李坤，韓德春，李芝.基于ELECTRE法的供應商選擇研究［J］.中國市場，2014（6）：11-14.

［18］"" 劉定智，張元濤，梁嚴，等.基于“全國一張網”的天然氣管輸優化模型構建及應用［J］.油氣與新能源，2021，33（5）：64-70.

（收稿日期：2023-11-29，修回日期：2024-03-12）

Pareto Optimal Solution Screening Based on Weight Estimation

and Hybrid Multi-criteria Decision Making

GAO Xiao-yong1， ZHOU Jun-feng1， LIU Ding-zhi2， GUO Jia-ming1，

ZHANG Xi2， ZHANG Yuan-tao2， PAN Kai2

（1. College of Information Science and Engineering， China University of Petroleum （Beijing）；

2. PetroChina Planning and Engineering Institute）

Abstract"" As for the multi-objective optimization， the traditional multi-criteria decision-making method will end when the Pareto optimal solution set is obtained. In practice， selecting a single optimal solution from the solution set based on the preferences of decision makers become necessary. Considering this situation， a weight learning method based on the minimum spanning tree algorithm was proposed to integrate the preferences of decision makers， and combines analytic hierarchy process （AHP） with the ideas of elimination and selection of expression reality（ELECTRE） to propose a hybrid multi-criteria decision-making method to benefit the selection of the most suitable Pareto optimal solution. For purpose of verifying reliability of this method， having the Pareto optimal solution data obtained based on the multi-objective model of natural gas pipeline network sales in a certain area analyzed and tested to show that， the Pareto optimal solution selected by this method can well fit the preferences of decision makers and provide effective suggestions for the selection of Pareto frontier.

Key words"" multi-objective optimization， weight learning， multi-standard decision-making， mixed approach， AHP，" ELECTRE，" natural gas pipeline sales

基金項目：國家自然科學基金（批準號：22178383，21706282）資助的課題；北京市自然科學基金（批準號：2232021）資助的課題；中國石油大學（北京）科研基金（批準號：2462020BJRC004）資助的課題。

作者簡介：高小永（1985-），教授，從事復雜工業過程計劃調度優化的研究，x.gao@cup.edu.cn。

引用本文：高小永，周峻峰，劉定智，等.基于權重估計與混合多標準決策的帕累托最優解篩選［J］.化工自動化及儀表，2024，51（5）：854-863.