[發明專利]一種基于特征層次的多目標系統發育樹構建方法

有效

• 申請號: 202010168038.5
• 申請日: 2020-03-11
• 公開（公告）號: CN111462812B
• 公開（公告）日: 2023-03-24
• 發明（設計）人: 馮筠;劉澤云;劉蒙;侯剛;馮宏偉
• 申請（專利權）人: 西北大學
• 主分類號: G16B5/00
• 分類號: G16B5/00;G06N3/126
• 代理公司: 西安恒泰知識產權代理事務所 61216
• 代理人: 李鄭建

1.一種基于特征層次的多目標系統發育樹構建方法，其特征在于，具體包括以下步驟：

步驟一，構建并形式化特征層次關系

結合特征描述和先驗知識等相關信息，分析特征間的依賴關系，從而構建特征層次關系；對構建的特征層次關系進行形式化表示，使其轉化為計算機能夠處理的數據矩陣；

步驟二，基于特征層次的馬爾科夫蒙特卡洛算法進行形態數據缺失值估計，具體方法是；

步驟2.1，對不完整的形態矩陣D_incom進行缺失值初始化，根據列取值對缺失數據進行隨機插補；

步驟2.2，結合特征層次關系進行列分析，分析每一列的參數分布，以便估計參數的后驗分布，主要包括以下幾種情況：

(1)存在主特征，但無從屬特征：

根據主特征的不同取值，計算從屬特征的取值分布；

(2)存在從屬特征，但不存在主特征：

根據從屬特征的不同取值，計算主特征的取值分布；

(3)存在從屬特征，且存在主特征：

分別計算主特征和從屬特征取值分布；

(4)既不存在從屬特征，也不存在主特征：

獨立計算特征的取值分布；

步驟2.3，記錄插補當前值x_t，并進行隨機抽樣逐次確定候選值x_t+1，即根據步驟2.2得到的概率密度分布Q(x_t+1|x_t)生成候選采樣x_t+1；將當前值x_t和候選值x_t+1分別代入列分析中，分別計算x_t和x_t+1在已有觀測列分布下的概率密度函數值，記為pOld和pNew；

在U(0，1)中抽取隨機數u，若u＜pNew/pOld，則接受候選值x_t+1為缺失值新采樣；否則維持當前缺失插補值x_t不變；

步驟2.4，迭代執行步驟2.2-2.3，直到滿足迭代次數k，輸出最終的插補后的形態數據記為D_com；

步驟三，構建多目標系統發育樹

步驟3.1，根據完整的形態矩陣D_com構建初始化樹群P₁，樹群大小為N，分別計算樹群中每一個體的簡約值得分和似然值得分：

給定系統發育樹結構τ，其中節點集合為V(τ)，邊集合為E(τ)，簡約值得分可表示為：

其中，w_j表示特征j的權重，v_j和u_j分別表示節點v，u在位點j的特征狀態取值，C(v_j，u_j)為代價矩陣，表示從狀態v_j轉化到狀態u_j的代價；

系統發育樹τ的似然值L(τ)是產生該樹的觀測數據D與進化模型M的概率，即L(τ)＝P(D|τ，M)，在給定D和M的條件下，樹τ的似然函數L(τ)可寫作：

其中，P(D_i/T，M)為第i個位點的似然值；

對每一個體進行編碼，染色體結構為{樹結構，簡約得分，似然得分}；

步驟3.2，對初始種群P₁進行快速非支配排序和擁擠度計算；

步驟3.3，對當前種群進行染色體選擇、交叉操作和變異操作，并生成新的種群；

步驟3.4，將父代種群與子代種群合并，進行快速非支配排序，同時對每個非支配層中的個體進行擁擠度計算，根據非支配關系以及個體的擁擠度選取合適的個體組成新的父代種群；

步驟3.5，重復上述操作，直到滿足程序結束的條件。

2.如權利要求1所述的方法，其特征在于，步驟3.2所述對初始種群P₁進行快速非支配排序和擁擠度計算，具體優化過程如下：

針對每一代進化群體，尋找出其當前最優個體，稱為一個進化群體的當前最優解為非支配解；所有非支配解的集合稱為當前進化群體的非支配集，并使非支配集不斷逼近真正的最優解集，最終達到最優；

其中，快速非支配排序是根據個體非劣解對種群進行分層，從而使搜索向Pareto最優解集方向進行；具體過程如下：

設進化種群為P，同時設置進化種群的非支配集P^*；首先將第一個個體放入非支配集P^*中，依次將進化種群P中的個體取出并放入P^*中，同時將當前取出的p依次與P^*中的所有個體進行比較，刪除P^*中所有被p支配的個體，若個體p被P^*中的任意一個個體所支配，則將p從P^*中刪除；

為了能夠在具有相同非支配序集的個體內進行選擇性排序，采用個體擁擠距離進行度量，具體計算過程如下：

設P[i]_distance為個體i的聚集距離，P[i].m為個體i在子目標m上的函數值，計算公式如下：

P[i]_distance＝(P[i+1].ps-P[i-1].ps)+(P[i+1].l-P[i-1].l)

其中，ps，l分別為樹個體的簡約得分、似然值得分。