[發明專利]基于MAB的超啟發式算法求解多目標優化問題的方法

有效

• 申請號: 201811230929.8
• 申請日: 2018-10-22
• 公開（公告）號: CN109460862B
• 公開（公告）日: 2021-04-27
• 發明（設計）人: 張淑艷;楊太龍;郭一
• 申請（專利權）人: 鄭州大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06N3/00
• 代理公司: 鄭州隆盛專利代理事務所(普通合伙) 41143
• 代理人: 余菲

1.一種基于MAB的超啟發式算法求解多目標優化問題的方法，其特征在于：該方法包括：

(1)給出低層啟發式算子的集合H＝{h₁,h₂...h_num}，其中num為低層啟發式算子的個數，h₁,h₂...h_num為多目標優化算法或算子；

(2)構造大小為N的隨機初始種群P₀，在決策空間X內，隨機生成N個解；

(3)計算各低層啟發式算子在四個已有的性能評估指標上的性能值；每個低層啟發式算子h₁,h₂...h_num對同一初始種群P₀分別獨立運行一次，每次運行執行h_i(i＝1,2...num)共M代，并分別計算各啟發式算子h_i的四個性能評估指標AE、RNI、SSC和UD；M為一次迭代中執行低層啟發式算子的次數，M取(0，∞)范圍內的整數；

1)AE：評估算法獲得近似解集的計算量，其取值范圍為(0，∞)，AE值越小表示性能越好；

2)RNI：評估算法獲得的近似解集中非支配解的比例，其取值范圍為(0，1]，RNI值越大表示近似解集中非支配解的比例越高；若RNI＝1，則表明近似解集中的所有個體都是非支配的；

3)SSC：評估算法獲得的近似解集所能覆蓋的目標空間的大小，其取值范圍為[0，∞)；SSC值越高表示似近解集的覆蓋空間越大，也表明收斂性以及分布性上性能越好；

4)UD：評估近似解集在目標空間的分布情況，其取值范圍為(0，1]；在非支配解數量相同的情況下UD值越高表示近似解集在目標空間上的分布性越好；

(4)使用算子性能評估機制計算各低層啟發式算子的回報值r_i，各低層啟發式算子評估機制包括如下步驟：

1)對各低層啟發式算子獲取的性能數據進行歸一化處理，使得各性能評估指標映射到同一個取值范圍[0,1]之內，低層啟發式算子h_i在四個性能評估指標上的歸一后的值分別記為AE_{i_nor}、RNI_{i_nor}、SSC_{i_nor}和UD_{i_nor}；

2)根據歸一化后得到的性能評估指標值，使用公式①計算各低層啟發式算子的回報值r_i：

r_i＝(1-AE_{i_nor})+2RNI_{i_nor}+SSC_{i_nor}+UD_{i_nor} ①

在公式①中：因為AE_{i_nor}的值越小越好，而其他三個指標越大越好，因此在回報值r_i的計算中使用了低層啟發式算子h_i的AE_{i_nor}反轉值，即1-AE_{i_nor}的值；SSC_{i_nor}可以反映出算法執行后獲得的種群的分布性與收斂性，UD_{i_nor}可以反映出算法執行后獲得種群的分布性；在種群大小一致的情況下，SSC_{i_nor}和UD_{i_nor}的值越大越好；為了避免種群大小的變化對SSC_{i_nor}和UD_{i_nor}值的影響，因此在r_i的計算中給SSC_{i_nor}和UD_{i_nor}分別搭配了一個非支配解的比例RNI_{i_nor}；

(5)根據回報值r_i，計算各低層啟發式算子的MAB值，步驟如下：

1)對于有num個低層啟發式算子的集合H＝{h₁,h₂...h_num}，為每個h_i(i∈{1，...，num})設置一個由三個變量構成的性能元組其中r_i是回報值、是平均回報值、k_i為h_i被選擇的次數，在算法初始階段，所有值初始化為0；

2)使用公式②更新h_i的性能元組

3)根據低層啟發式算子h_i的性能元組V_i計算當前階段低層啟發式算子的MAB_i值，如下公式③：

其中C為控制參數，控制各低層啟發式算子h_i的平均性能與框架運行中算子執行的次數之間的一種平衡；

(6)選擇MAB值最大的低層啟發式算子h_top，即top＝argmax{MAB_i},i＝1,2,...,num；若擁有最大MAB值的算法有多個，則從中隨機選擇一個；

(7)使用h_top進化種群P_t，執行h_top共M代，得到新種群P′，并計算應用低層啟發式算子h_top得到的種群P′在四個性能評估指標上的性能值；

(8)采用改進接受策略更新種群P_t+1，使用SSC判斷執行h_top后種群是否有改進，若無改進，則下一次迭代(t+1代)的種群P_t+1被第t代的種群替換，即P_t+1＝P_t；若有改進，則第t+1代的種群P_t+1被剛獲取的種群P′替換，即P_t+1＝P′；

(9)判斷迭代次數是否超過設定的最大值W，如果超過，HH-MAB算法結束；如果沒有超過，進入下一輪迭代，返回(4)；W為算法的最大迭代次數，取(0，∞)范圍內的整數。