[發明專利]一種求解完整Pareto前沿的多目標優化方法

在審

• 申請號: 201610030464.6
• 申請日: 2016-01-19
• 公開（公告）號: CN105488601A
• 公開（公告）日: 2016-04-13
• 發明（設計）人: 胡小兵;廖建勤
• 申請（專利權）人: 北京師范大學;廖建勤
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域：

本發明提供了一種求解完整Pareto前沿的多目標優化方法，屬于計算機算法和管理優化 領域。

背景技術：

多目標優化問題(multi-objectiveoptimizationproblem，簡稱MOP)涉及生活的方方 面面，相關的求解方法對解決政治、金融、軍事、環境、生產制造、社會保障等各方面的規 劃決策問題起著至關重要的作用。Pareto最優解和Pareto前沿是MOP中的核心概念，它們 起源于經濟學中對收入分配優化的研究。簡單地說，對于一個給定的解，如果不存在任何一 個解在各個指標上都不比它差，而且至少在一個指標上比它好，則這個給定解就是一個Pareto 最優解。所有Pareto最優解在目標函數空間里的投影就構成了完整Pareto前沿。求解MOP 的關鍵就在于尋找Pareto前沿。然而，現有的絕大多數MOP求解方法都只能尋找部分的、 或近似的Pareto前沿。

現有的求解MOP的方法大體可以分為三大類：重構單目標函數法(aggregateobjective function，簡稱AOF)，約束目標函數法(constrainedobjectivefunction，簡稱COF)，和 Pareto標準評級法(Pareto-compliantranking，簡稱PCR)。AOF會把MOP中的所有原始 目標函數整合到一個單一的重構目標函數中，然后針對這個重構單目標函數進行單目標優化， 即可得到一個Pareto最優解。然而，定義重構單目標函數時存在主觀性，并且很多重構單 目標函數的定義從理論上就決定了AOF不可能找到Pareto前沿上的凹面所對應的Pareto最 優解。COF把MOP轉化成一個帶約束的單目標優化問題，即僅針對MOP的一個目標進行優化， 而把所有其它目標當成額外的約束條件。PCR基本都是基于種群的各種進化算法，通過篩選 和進化種群中的當前非劣解，在種群進化結束后將當前非劣解集作為近似的Pareto前沿輸 出。PCR雖然沒有AOF的問題(如主觀性等)，但AOF的輸出肯定是Pareto最優解，而PCR 的輸出有可能根本就不包含任何Pareto最優解。

對一些基于非線性重構單目標函數的AOF而言，對任一給定的Pareto最優解，在理論 上總可以證明存在一組重構參數，使得AOF的輸出為該指定的Pareto最優解。然而，卻缺 少實際有效可行的理論和方法保證找出能夠對應涵蓋所有Pareto最優解的重構參數集合。 COF在理論上，通過將優化目標轉化成約束條件，是可能求解完整Pareto前沿的。但是和 AOF的情況一樣，COF缺少實際有效可行的理論和方法來確定所需的轉化參數集合，因而難 以確保所生成的約束條件能找到完整Pareto前沿。在目前為數不多的關于求解完整Pareto 前沿的研究報導中，基本都是通過精心設計針對特殊類型問題的AOF重構參數集合或COF轉 化參數集合，從而把所有Pareto最優解都找出來。盡管PCR是MOP研究中最熱門的方法，但 是因為其所依賴的進化算法具有隨機特性，所以PCR在理論上根本不能保證找到完整Pareto 前沿。

最近在文獻[1]和文獻[2]中提出了一種利用漣漪擴散算法求解前k個單目標最優解，進 而再基于各個目標函數下的前k個單目標最優解求解MOP的完整Pareto前沿的方法。需要 強調的是：(1)文獻[1]和文獻[2]中的漣漪擴散算法本身不能解決MOP，而是僅僅針對單目 標優化問題的，即，文獻[1]和文獻[2]中的漣漪擴散算法是單目標漣漪擴散算法；(2)為了 求解MOP的完整Pareto前沿，需要在各個目標函數下多次運行文獻[1]和文獻[2]中的單目 標漣漪擴散算法；(3)在多目標路徑優化問題中，每當求解給定起點到另外一個網絡結點的 完整Pareto前沿時，都需要單獨運行一次文獻[1]或文獻[2]中的方法，換句話說，假設路 網中有N_N個結點，其中一個結點為給定起點，如果我們需要求解給定起點到另外(N_N-1)個 結點中每一個結點的完整Pareto前沿，那么我們總共需要運行(N_N-1)次文獻[1]或文獻[2] 中的方法(在每一次方法運行中，又需要運行若干次單目標漣漪擴散算法)。所以文獻[1]和 文獻[2]中求解完整Pareto前沿的方法是非常低效的。