[發明專利]一種多圖融合方法

在審

• 申請號: 201911044229.4
• 申請日: 2019-10-30
• 公開（公告）號: CN110750689A
• 公開（公告）日: 2020-02-04
• 發明（設計）人: 張偉;趙海燕;金芝
• 申請（專利權）人: 北京大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06N3/00
• 代理公司: 11732 北京睿智保誠專利代理事務所(普通合伙)
• 代理人: 周新楣

1.一種多圖融合方法，其特征在于，包括如下步驟：

S0，接收一組圖作為被融合圖；

S1，對一組被融合圖進行預處理，將其中的每一個圖轉化為一個節點具有類型、邊具有類型、邊具有方向的被融合圖，作為后繼處理活動的輸入；

S2，采用隨機方式生成一組多圖融合方案，作為父代種群的初始值；

S3，對于父代種群中的多圖融合方案，計算多圖融合方案的信息熵；

S4，將父代種群中每一個多圖融合方案的信息熵轉化為多圖融合方案的適應度；

S5，檢查父代種群中是否存在信息熵為零的多圖融合方案，如果存在這樣的多圖融合方案，則返回該多圖融合方案，并終止當前多圖融合過程；

S6，檢查當前的多圖融合過程是否滿足終止條件，如果滿足終止條件，則返回當前父代種群中適應度最高的多圖融合方案，并終止當前多圖融合過程；

S7，在父代種群中，把所有多圖融合方案按適應度從大到小的順序排列，選擇適應度排名靠前的若干多圖融合方案，并將這些多圖融合方案放入子代種群中；

S8，基于融合方案的適應度，從父代種群中確定一組待交叉的多圖融合方案對；

S9，對于每一對待交叉的多圖融合方案，選取兩者之間的一條最短編輯路徑上的某個點作為這兩個融合方案的一個交叉結果，然后把這個交叉結果放入子代種群中；

S10，當所有待交叉的多圖融合方案對都完成交叉后，把父代種群清空后再把子代種群中的所有多圖融合方案加入初始父代種群中，然后把子代種群清空，然后跳轉至S3。

2.根據權利要求1所述的多圖融合方法，其特征在于：所述步驟S9中，對于每一對待交叉的多圖融合方案，選取兩者之間的一條最短編輯路徑上的某個點作為這兩個融合方案的一個交叉結果，具體包括如下步驟：

對兩個待交叉多圖融合方案對應的兩個融合圖，對每一種類型的節點計算每一對分別來自這兩個融合圖的節點的權重，形成兩個融合圖節點之間具有最大權值之和的一一映射關系，基于這種一一映射關系，對于每一個被融合圖，形成其這種類型的節點在兩個融合圖之間的排列，并將這種排列轉化為不相交的環形表示方式；

基于所有被融合圖所有類型節點在兩個融合圖之間的排列，計算兩個融合圖之間的最短編輯路徑，并計算本次交叉操作需要進行的編輯次數；

隨機從所有被融合圖所有類型節點在兩個融合圖之間的排列中選擇一個排列，隨機從這個排列中選擇一個環并隨機選擇環中的兩個元素，對這兩個元素進行交換，形成一次編輯操作；

重復進行指定次數的編輯操作，從產生的排列中還原出對應的多圖融合方案，作為這兩個待融合圖的一個交叉結果。

3.根據權利要求1所述的多圖融合方法，其特征在于：所述步驟S3中，對于父代種群中的多圖融合方案，計算多圖融合方案的信息熵，多圖融合方案的信息熵形成多圖融合方案的適應度，具體包括如下步驟：

基于融合方案形成一個融合圖；

對于融合圖中每一個節點每一種類型的出邊集合的冪集，計算冪集中每一個元素的概率值，計算冪集中每一對元素之間的相似度，基于冪集元素概率值和冪集元素對相似度計算該節點該種類型出邊產生的信息熵，把該節點所有類型出邊產生的信息熵相加形成該節點出邊產生的信息熵；

對于融合圖中每一個節點每一種類型的入邊集合的冪集，計算冪集中每一個元素的概率值，計算冪集中每一對元素之間的相似度，基于冪集元素概率值和冪集元素對相似度計算該節點該種類型入邊產生的信息熵，把該節點所有類型入邊產生的信息熵相加形成該節點入邊產生的信息熵；

將融合圖中每一個節點的出邊和入邊產生的信息熵相加，形成該節點的信息熵；

基于融合圖中每一個節點的信息熵綜合形成融合圖的信息熵。

4.根據權利要求1所述的多圖融合方法，其特征在于：所述步驟S2中，采用隨機方式生成一組多圖融合方案，作為父代種群的初始值，具體包括如下步驟：

對于每一種類型的節點，生成一個行數為被融合圖數量、列數為所有被融合圖中這種類型節點數量之和的表格，在被融合圖和表格行之間建立一一映射關系，對每一個被融合圖，把其包含的所有這種類型的節點隨機放置到該被融合圖關聯的表格行中的單元格中，且保證該表格行中的每一個單元格至多被放置一個節點，把表格每一列的所有單元格中的節點聚合在一起形成一個集合，把表格所有列對應的集合聚集在一起形成一個集合，然后去除該集合中的空集元素，形成這種類型節點的多圖融合方案，把所有類型節點的多圖融合方案聚合在一起，形成一個多圖融合方案；

重復上述步驟，直到生成的多圖融合方案的數量等于父代種群要求的數量。