[發明專利]一種浮標數據的多目標關聯度劃分處理方法

有效

• 申請號: 201710041585.5
• 申請日: 2017-01-20
• 公開（公告）號: CN106919783B
• 公開（公告）日: 2019-04-19
• 發明（設計）人: 黃冬梅;趙丹楓;徐宸弋軒;王建;梅海彬;王麗琳
• 申請（專利權）人: 上海海洋大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12
• 代理公司: 上海卓陽知識產權代理事務所(普通合伙) 31262
• 代理人: 周春洪

本發明涉及一種浮標數據的多目標關聯度劃分處理方法，所述浮標數據的多目標關聯度劃分處理方法包括以下步驟：獲取歷年臺風與浮標數據；構建浮標關系圖；多目標問題公式化；構建針對浮標數據定制的NSGA?II算法(帶精英保存策略的非支配排序遺傳算法)；輸出適合浮標數據的多目標布局方法。其優點在于，將海區中所有的浮標構成圖，將浮標分布劃分區域存儲；使微區內浮標數據相關性最大化、微區間的相關性最小化、跨微區通信時間最小化，并且使微區負載平衡；對海洋應急預警、預報、臺風資料分析提供高效檢索方式，并提高預報精度；促進業務化常規預報的質量、數值模式同化的效果、防災減災與應急預報決策的正確制定以及維權執法等海上活動的保障能力。

技術領域

本發明涉及海洋數據劃分處理技術領域，具體地說，是一種浮標數據的多目標關聯度劃分處理方法。

背景技術

現有的浮標按海區單點存儲不能及時響應跨海區災害的數據獲取，無法為海洋災害發生時提供快速高效的數據訪問服務，將浮標依賴災害影響程度構建成圖，利用圖劃分方法進行劃分后應用，能夠更高效的使用浮標數據。圖劃分方法是將具有相關性的、復雜的邊關系根據頂點與頂點間的緊密程度聚類的一種方法，良好的圖劃分算法能夠對數據關聯性布局提供依據。

在無結構圖多層級劃分方法METIS中，利用圖粗糙方法(Coarsening Phase)將復雜圖規模逐步縮減，然后進行圖劃分(Initial Partitioning Phase)并對圖進行處理，在處理結束后，執行圖復原方法(Uncoarsening Phase)。其中圖粗糙方法利用“超點”(CreateMultinode)以及最大化匹配(Maximal Matching)，圖劃分方法與圖復原方法中應用了如Kernighan-LinAlgorithm等多種算法。該方法的優點在與：①圖粗糙時能得到較好的全局視圖(global view)，②圖復原中利用KL算法可以得到較好的本地視圖(local view)③結合全局視圖與本地視圖在圖劃分步驟時的選擇對圖影響較小的劃分算法④圖粗糙的并行化較為容易且運算時間得到優化。

METIS結合幾種啟發式算法在圖粗糙、圖劃分、圖復原上提升了切分規模，使用貪婪算法(GR)等進行改進，使METIS優于原始的MGP方法。但這種做法將粗糙圖進行劃分后，反映在原始圖上可能不是最優結果。

一種過程工程的矩陣排序策略：并行化圖劃分算法，通過重新對矩陣排序成塊鑲嵌對角形式(borderedblock–diagonal form)來進行劃分。由于這種結構并不都是從等式產生程序(equation generation routine)中獲得，必須要有一個重新排序系數矩陣的行與列的算法。該算法創建一個塊鑲嵌對角形式，適用于使用并行算法在高度非對稱稀疏矩陣中產生結果，并在過程工業上應用。這個方法目的在創建若干相似大小的對角塊并保持接口矩陣大小不變，可以反映出并行計算瓶頸。結果表明該重新排序算法大多數情況下能夠尋找一個結構，并且使用重新排序時間少于提前使用圖劃分方法，但在時間上并沒有很高的提升。

利用遺傳算法對圖劃分可以進行多對象優化。其進一步改善的方法是將上一次運行的最優結果注入到下一次運行的第一代中，并且將前一代存儲的非支配集與后一代非支配集相結合。改善阻止了遺傳算法(GeneticAlgorithms)陷入到局部優值并且增加尋找到更優結果的可能性。并證明了算法的有效性。該方法特點在于使用了混合細胞自動學習(hybrid cellular learning automata)和遺傳算法相結合，優化了本地速度。

還有一種DiDiC算法，隱含了優化切割質量的相關措施，比如說模塊化，這使得結算結合其他高質量的分布式集群算法措施與圖集群算法優化了全局知識的切分相關措施。通過實驗證明：通過每個節點開始的隨機集群數，可能在圖內交流的僅有一個直接相鄰的節點，并且僅僅需要少量的額外存儲空間，與非分布式圖集群MCL庫(library mcl)相比，通過DIDIC計算的結果匯集在集群中有很高的質量，這些主要的算法使用了全局知識(globalknowledge)。