基于BP神經網絡代理模型的交互式遺傳算法

朱苗苗，潘偉杰，劉 翔，呂 健，趙慧亮

1.貴州大學 現代制造技術教育部重點實驗室，貴陽550025

2.貴州民族大學，貴陽550025

1 引言

交互式遺傳算法（Traditional Interactive Genetic Algorithm，IGA）思想起源于20 世紀80 年代Dawkins 創建的基于交互式進化計算的可視化應用[1]。作為傳統進化計算的擴展，其主要特征是融入人的智能，在解決人的偏好、認知、情感、心理特征等隱式性能指標優化問題效果顯著。因此，目前交互式遺傳算法已成功應用于圖像檢索[2]、控制工程[3]、樂曲生成[4]、產品設計[5]等眾多領域。

IGA將用戶主觀評價值作為進化個體適應值，因此需要用戶頻繁參與評價決策，而用戶評價行為存在評價不確定性和易疲勞性，極易導致進化方向偏離、進化代數不足、優化效率低下等問題，在很大程度上限制了該算法應用于實際問題的性能。目前，提高個體適應值質量、減輕用戶疲勞是改善交互式遺傳算法在實際復雜問題優化應用中人-機交互能力研究的熱點[6]。

針對以上問題，本文提出基于BP 神經網絡認知代理的交互式遺傳算法（Interactive Genetic Algorithm based on BP neural network user Cognitive surrogate Model，IGA-BPCM）。該方法通過高斯函數構建用戶評價噪聲模型，形成進化個體區間適應值；采用BP神經網絡擬合進化個體區間適應值；預測代數為初始種群個體數，之后將每代最優個體呈現給用戶，若預測適應值偏離用戶期望，用戶可重新提交個體適應值，擴大搜索空間加速用戶尋找滿意方案；采樣用戶對偏離期望的精英個體適應值，更新代理模型訓練集，度量代理模型均方誤差，實現代理模型的更新策略。該方法優點在于：（1）構建用戶評價噪聲模型，提高進化個體適應值質量；（2）采用機器學習方法預測進化個體適應值，代替用戶評價行為，減輕用戶操作疲勞；（3）BP 神經網絡按照誤差逆傳播訓練，通過度量均方誤差MSE，能夠及時更新代理模型，獲取更精確的用戶偏好信息。

2 相關研究工作

IGA在復雜優化問題的應用中性能受限，其根本原因在于用戶認知、偏好和進化個體適應值映射關系的復雜性，難以精確表征。對此，構建符合用戶認知偏好的代理模型是解決上述問題的有效途徑之一。針對降低用戶評價噪聲，郭廣頌等人在用戶滿意度最大化條件下采用熵極大準則估計進化個體適應值[6]；Dou 等人通過建立基于猶豫度模型的適應值估計策略，提高進化個體適應值度量質量[7]。針對擴充進化種群規模，Gong等人利用最近鄰協同過濾算法構建基于相似偏好用戶知識的代理模型[8]；Sun等人利用聚類策略，通過少量標記樣本和大量無標記樣本構建半監督徑向基函數（Radial Basis Function，RBF）神經網絡代理模型[9]。針對減輕用戶操作疲勞，孫曉燕等人通過用戶評價噪聲特性獲取學習樣本對代理模型的影響度權重系數，并構建兩輸出高斯過程代理模型[10]；孟偉東等人利用云模型和進化個體相似性產生自適應交叉、變異概率，提高優化效率[11]。由于用戶認知具有不確定性，使得用于構建代理模型的學習樣本數據存在較大的評價噪聲，而在不同認知階段用戶評價同一個體評價噪聲強度也不盡相同；由于代理模型的學習樣本數據來源于用戶歷史評價信息，數據規模往往較小；由于用戶認知具有漂移性，及時識別并響應用戶偏好波動的代理模型，有助于提高優化效率。目前，研究代理模型訓練數據的噪聲特性和含噪環境下用戶偏好的擬合性能尚不充足。

3 算法設計

本文算法旨在構建融合用戶認知特性、機器代理模型和進化知識于一體的統一架構。由于用戶認知存在不確定或模糊感，降低用戶評價噪聲有利于提高進化個體適應值質量；由于頻繁人-機交互會使得用戶疲勞，構建代理模型有利于減輕用戶疲勞，擴大算法搜索范圍，增加種群多樣性。

3.1 代理模型訓練數據獲取

通常情況下，人-機交互環境中噪聲類型可分為加性噪聲、乘性噪聲和隨機噪聲三種噪聲類型[12]，三種噪聲類型可單獨存在亦可混合作用。在IGA中，評價噪聲主要來源于用戶認知的模糊性和漸進性導致的個體適應值漂移以及評價易疲勞性在很大程度上對評價客觀性的影響[13]。在進化初期，由于用戶對進化個體不熟悉，所以進化個體適應值具有較大的不確定性，因此評價噪聲強度較大；隨著進化過程的推進，用戶認知由模糊逐漸清晰，具有較為穩定的偏好信息，因此評價噪聲強度較?。浑S著進化代數的繼續增加，頻繁人-機交互使得用戶產生疲勞感，從而影響用戶評價的客觀性，因此評價噪聲強度逐漸增大。此外，評價噪聲強度還與優化問題的復雜程度、用戶的先驗知識等有關?？紤]該問題的一般性，評價噪聲強度Er與進化代數關系T 可分為三個階段，即認知模糊階段、認知確定階段和審美疲勞階段。如圖1 所示。圖中，en為評價噪聲強度閾值，當Er≤en時，即進化代數處于T1-T2時，則認為用戶認知可信度較高。

圖1 噪聲強度曲線

僅考慮認知確定階段，構建評價噪聲強度模型Er～N(0,，即構建服從高斯分布的評價噪聲強度模型，其中，σe如式（1）所示：

式中，σe(xi)為模糊適應值)的函數，β 為調節系數，γ 為常數。適應值越模糊，噪聲強度越大。采用熵刻畫適應值模糊度，H(f~(xi))如式（2）所示：

針對評價噪聲強度，調整進化個體適應值，最大程度地降低個體適應值對進化過程的影響。根據上述評價噪聲強度模型，給定置信水平(1-?)%，則噪聲強度Er所確定的置信區間為[-Z?σe(xi), ]Z?σe(xi) ，其中Z?為標準正態分布N(0,1)的?/2 分位點。采用λ 截集獲取所表征的適應值區間數，結合區間數加法，則含噪環境下的區間適應值如式（3）所示：

3.2 代理模型構建與更新

BP 神經網絡作為非線性信息動力學模型，可以實現從輸入到輸出的非線性映射，具備較好的容錯、自適應和泛化特性，主要應用于函數逼近、模式識別、數據壓縮和分類等問題。本文代理模型在用戶歷史評價信息的基礎上，通過式（3）獲取含噪環境下修正的適應值作為訓練數據，采用K 折交叉驗證訓練BP神經網絡代理模型，將這些數據等分為k 份，輪流選取每份數據D(k)=,i=1,2,…,Nk}作為測試數據，其余k-1 份數據作為訓練數據?？紤]3層BP神經網絡具備任意輸入到輸出的連續映射能力[14]，本文代理模型采用3層BP神經網絡，即輸入層、隱含層和輸出層，其中wih、who分別代表輸入層和隱含層、隱含層和輸出層神經元節點的連接權值；采用單極性Sigmoid 函數即作為傳遞函數；輸入層神經元節點數i 由進化個體xi組成部分數確定，輸出層神經元節點數o 為2，即代表預測區間適應值的上限和下限，隱含層神經元節點數h 采用文獻[15]中確定；利用梯度下降技術動態調整wih和who，使得由MSE度量的目標函數，即滿足誤差精度要求時，訓練結束，從而得到基于BP神經網絡的認知代理模型，代理模型拓撲結構如圖2所示。利用該模型預測后續進化個體區間適應值，從而減少用戶操作負擔。

圖2 代理模型拓撲結構

由于代理模型的構建來源于用戶歷史評價信息，隨著進化過程的推進，用戶偏好往往會有波動，代理模型預測的某些進化個體適應值可能偏離用戶期望。此時，則需要識別用戶偏好更新代理模型。考慮IGA 的最終目標是求解最優個體，代理模型每代理一次，進化個體進化M 代，其中M 為初始種群規模，保存每代最優個體，將預測的M 個歷代最優個體呈現給用戶，如若預測個體適應值與用戶期望偏離，用戶可重新提交用戶評價數據，評價數據隨機納入某份數據集D(k)作為樣本數據，通過K 折交叉驗證訓練樣本數據，若MSE ≥e，e為誤差精度，則代理模型自動更新。

3.3 算法流程

本文算法基本思想：通過構建用戶評價噪聲模型，采用噪聲補償策略修正進化個體適應值，刻畫用戶認知不確定性；在用戶審美疲勞階段，則基于用戶認知確定階段歷史評價信息，采用K 折交叉驗證獲取穩定的BP 神經網絡認知代理模型；代理模型每代理一次，進化個體進化M 代之后，則呈現M 個歷代最優個體以及預測適應值，如若預測值與用戶期望偏離，用戶可重新提交用戶評價，系統自動更新訓練數據集。通過度量MSE，識別用戶偏好波動，更新代理模型。算法流程如圖3所示。

4 在蠟染風格圖案進化設計系統中的應用

貴州蠟染圖形豐富多樣、變化自然。利用已有紋樣自動化生成更具風格特色的圖形圖像，有助于復雜民族圖案的設計風格、文化內涵的傳承以及再應用?；诮换ナ竭M化計算的創新設計方法有助于根據不同用戶的偏好，滿足不同用戶的個性化需求，并能夠在一定程度上提高設計實例的重用性與設計速度。

本文建立的計算機輔助圖形設計系統，基于蠟染圖案結構組成部分編碼，圖案結構包含m 個模塊，指定或隨機選取n 種紋樣，因此搜索空間包含nm個候選解。系統采用PyQt 5編程開發。

4.1 實驗環境及參數設置

圖3 基于BP神經網絡認知代理模型的交互式遺傳算法流程

為衡量本文算法的性能，對比文獻[16]中區間適應值交互式遺傳算法（Interactive Genetic Algorithms with Individual's Interval Fitness，IGA-IIF）和文獻[17]中算法。三種算法均設置相同的控制參數，選擇算子設置為文獻[16]中區間概率占優聯賽規模為2 的輪盤賭選擇，兩點交叉，單點變異；進化參數設置為初始種群規模M=9，交叉概率pc=0.85，變異概率pm=0.05；論域均為。本文算法中其余參數設置為：σ(xi)=10；評價噪聲強度參數β=0.5，γ=0，置信水平為90%，即Z?=1.64；MSE 精度閾值e=0.01。圖案結構相同共12 個模塊，每個模塊隨機選取4 種紋樣。進化終止條件為用戶找到滿意解或用戶評價個體數超過225 個。進化設計系統的交互界面如圖4 所示，點擊初始化按鈕，系統自動生成初始進化種群并顯示；用戶根據偏好評價進化個體，點擊下一代按鈕，種群進行選擇、交叉和變異操作，生成新的種群；若用戶評價超過5代，則可選擇代理模型代替用戶評價，系統自動將第2代之后的用戶評價結果作為初始訓練數據，采用K 折交叉驗證訓練BP神經網絡認知代理模型并估計每代進化個體適應值，種群進行遺傳操作生成新的種群。代理模型代理一次，進化個體進化9 代之后，則呈現每代最優個體以及預測適應值，如若預測值與用戶期望偏離，用戶可重新提交用戶評價，系統自動更新訓練數據集。如果MSE ＞0.01，則更新代理模型。重復上述過程，直至用戶找到滿意的進化個體。

圖4 系統交互界面

4.2 實驗結果與分析

本文算法和文獻[17]中算法均在進化第5代之后選擇代理模型，從進化的總代數、用戶評價的個體數、進化系統評價的總個體數和尋優成功率4 個方面對比本文算法、IGA-IIF和文獻[17]中算法的性能差異。每種方法由10 個被試者獨立運行10 次后計算平均值，對比結果如表1所示。

由表1 可知，相比于IGA-IIF，文獻[17]中基于神經網絡代理模型區間適應值的交互式遺傳算法中算法達到收斂條件時的用戶評價個體數明顯降低，說明文獻[17]中算法能夠有效減輕用戶參與評價帶來的用戶疲勞，而進化終止代數則不占優勢；相比于其他兩種算法，本文算法在算法達到收斂條件時的進化終止代數、用戶評價個體數等方面均有所降低，平均進化終止代數、平均用戶評價個體數分別占IGA-IIF的48.3%和31.1%，占文獻[17]中算法的45.8%和92.7%，且尋優成功率為100%，而對于系統評價總個體數則明顯增長，平均系統評價總個體數分別占IGA-IIF 的215.1%，文獻[17]中算法的204.2%。設T 為進化終止代數，T1和T2分別為應用代理模型前和應用代理模型后的進化代數，則T=T1+T2。在IGA-IIF中，用戶評價個體數和系統評價總個體數均為T×M ；對于文獻[17]中方法，用戶評價個體數為T1×M+T2，系統評價總個體數為T×M 。在進化代數T 一定的情況下，由于T2×(M-1)＞0，文獻[17]中方法能夠有效降低用戶評價個體數。對于本文中的方法，用戶評價個體數T1×M ≤N ≤T×M ，系統評價總個體數為T1×M+T2×M2，由于代理模型代理一次，需要進化個體進化M 次并呈現每代最優個體，若個體預測適應值偏離用戶期望才需用戶評價，因此，在系統評價總個體數一定的情況下，本文算法中的T2為文獻[17]算法中T2的1/M,令文獻[17]算法中T2=t,由于N-t×M ≤0，所以本文算法中用戶評價個體數低于文獻[17]中用戶評價個體數，能夠反映出本文算法在減輕用戶參與評價帶來的用戶疲勞的有效性。

表1 算法性能對比

為對比本文算法的收斂性，圖5為進化個體適應值對比圖，其縱坐標代表平均適應值，為每一代所有進化個體的平均適應值即，其中區間適應值均值由區間上下限確定，即橫坐標代表迭代次數。三條曲線分別代表IGA-IIF、文獻[17]算法和本文算法每一代進化個體的平均適應值走勢。從圖5 中可以看出本文算法平均適應值隨進化代數的增多而逐漸提高，且本文算法的收斂性優于對比算法。由于文獻[17]中算法應用代理模型前期采用IGA-IIF 中區間適應值，因此平均適應值并無顯著差異。圖6 為進化個體互異個體數目比例對比，從圖6 可知，三種算法的進化個體互異個體數目隨迭代次數的增加而增加。在迭代15次之后，IGA-IIF和文獻[1]中算法所表征的互異個體數目不再明顯增長，而本文算法所表征的互異個體數目仍呈增長趨勢，表明本文算法在時間復雜度上高于其他三種算法，盡管如此，IGA 面臨的核心問題是人的疲勞，本文算法具有更多找到滿意解的機會，對比表1 中數據，本文算法搜索效率高于其余對比算法，且在一定程度上避免了過早收斂。原因在于，本文通過構建評價噪聲強度模型修正進化個體適應值，在降低用戶評價噪聲的同時有利于增加種群多樣性，增強本文算法的搜索性能。由此，可在一定程度上反映出本文算法在降低用戶評價噪聲，加速用戶尋找到滿意解的有效性。

圖5 進化個體適應值對比

圖6 互異個體數目比例對比

由于本文算法中系統評價總個體數呈指數式增長，且通過構建噪聲強度模型修正進化個體適應值，從而在一定程度上降低用戶評價噪聲，進而有利于用戶盡快尋找到滿意個體。綜上所述，與上述兩種方法相比，本文算法能夠在一定程度上提高進化個體質量、減輕用戶疲勞，改善IGA優化性能。

5 結束語

針對構建符合用戶偏好的代理模型能夠有效改善交互式遺傳算法性能的問題，考慮用戶認知不確定性對代理模型訓練數據的影響，提出基于BP 神經網絡用戶認知代理模型的交互式遺傳算法。構建評價噪聲強度模型刻畫用戶認知不確定性，提取訓練數據噪聲特性，提高個體適應值質量；采用K 折交叉驗證訓練穩定的BP神經網絡代理模型；通過度量MSE，識別用戶偏好波動，更新代理模型。在計算機輔助蠟染風格圖案設計中的應用，表明該算法在減輕用戶疲勞、提高優化效率方面的有效性。如何設計噪聲補償策略更好地提高個體適應值質量以及改進機器學習算法更好地擬合用戶認知還有待進一步深入研究。