基于進化個體混雜型適應值的交互式遺傳算法

郭廣頌,李 響,郝國生

(1.鄭州航空工業管理學院 機電工程學院,鄭州 450046; 2.江蘇師范大學 計算機科學與技術學院,江蘇 徐州 221116)

0 概述

自交互式遺傳算法概念提出以來,其作為一種情感計算的新方法獲得了廣泛關注。基于傳統遺傳算法的優化流程,對于很難用顯式性能指標表達的用戶偏好、經驗等隱式性能指標優化問題,交互式遺傳算法表現出算法實現簡單、優化效果顯著的特點。因此,近年來交互式遺傳算法在圖像處理[1]、機器人控制[2]、語音合成[3]、城市景觀設計[4]等眾多領域獲得了成功的應用。

由于人的主觀偏好具有波動性,會導致個體的評價值與真實值之間產生偏差,帶來個體適應值噪聲[5]。交互式遺傳算法適應值噪聲會使進化方向發生偏移;另一方面,受交互式遺傳算法進化代數較少和種群規模不大限制,適應值噪聲還會更容易使進化早熟收斂。因此,提高適應值精度與降低人的疲勞一直是交互式遺傳算法研究的主要方向。文獻[6]提出通過主成分分析降低優化噪聲影響,提高了信號優化質量;文獻[7]提出稀疏表示的去噪方法,過濾信號噪聲;文獻[8]提出基于耦合約束的調度優化方法用于飛機維修作業。

本文提出基于進化個體混雜型適應值的交互式遺傳算法IGA-IHF,根據交互式遺傳算法中偏好不確定性和適應值噪聲特性對適應值形態分類,設計混雜型適應值進化策略,通過修正不同類型適應值提高算法性能。

1 適應值不確定度

不失一般性,考慮優化問題:maxf(x,t)=f(x(t)),x∈S?d,x是d維決策變量,S是其取值范圍,f(x,t)是被優化的性能指標,且不能用顯式函數表示。記第t代進化種群x(t)中的第i個進化個體為xi(t),i=1,2,…,N,N為種群規模,xi(t)的適應值為f(xi(t)),xi(t)∈x(t),則f(x(t))=(f(x1(t)),f(x2(t)),…,f(xN(t)))構成個體適應值數值序列。

人的主觀評價是一種具有不確定性的相對評價,因此,人在不同進化代對相同個體的評價值可能并不相同,或在不同的進化代對不同的個體可以給出相同的評價值。這意味著人的評價結果是一個存在矛盾的數據,這導致交互式遺傳算法進化個體適應值具有明顯的不確定性。根據文獻[9],f(xi(t))的不確定度可以表示為θ(xi(t)):

i=2,3,…,N

(1)

其中,min(f(xi-1(t)),f(xi(t)))表示相鄰個體f(xi-1(t)),f(xi(t))中的較小值,max(f(xi-1(t)),f(xi(t)))表示f(xi-1(t)),f(xi(t))中的較大值。

式(1)的意義是:在進化初期,由于人對產品的偏好具有模糊性,因此對系統呈現的樣本款式的認知程度比較低,對樣本個體評價差異很大,評價的不確定性較大,θ(xi(t))也較大。隨著種群的進化,個體差異逐漸減小,適應值趨于一致,適應值不確定度相應變小。進一步地,有:

(2)

式(2)的意義[9]是:同一進化代的樣本評價不確定度小于個體適應值信息的最大差異,即在每一進化代中,偏好對適應值不確定性的影響主要體現在相鄰個體的評價上。

2 適應值噪聲特性

在交互式遺傳算法中,用戶期望的進化目標是最能滿足自身偏好的個體,即滿足maxf(x,t)的個體。而實際進化的結果則是用戶賦予的適應值為f(x(t))的個體。在數值優化中maxf(x,t)和f(x(t))是相等的,但在交互式進化優化中由于人的偏好原因,進化目標與進化結果之間會存在差異,即maxf(x,t)和f(x(t))并不相等,這便是評價噪聲的體現。

假設第t代進化個體xi(t)的真實適應值為F(xi(t)),人給出的評價值為f(xi(t)),噪聲函數為δ(t)。噪聲可以表示為個體量測值與真實值之間的偏差,記為δ(t)=f(xi(t))-F(xi(t))。交互式遺傳算法的進化過程可以按人對被優化問題的認知程度劃分為初始、穩定和疲勞3個階段[10]。在進化初期,人對被優化問題的認識比較模糊,給出的評價可信度較低,性能指標受到的噪聲影響較大,評價不確定性比較大;隨著種群的進化,人對被優化問題的認識相對清晰,給出的評價相對可靠,性能指標受到的噪聲影響較小,評價不確定性較小;當進化代數太多人疲勞時,給出的評價又變得不可靠,性能指標受到的噪聲影響變大,評價不確定性又較大(該階段并非進化后期認知已達成熟和收斂趨勢下的適應值精確評價,該階段生理疲勞會導致適應值噪聲迅速增加)。這些帶有噪聲的評價結果將使個體適應值變得不客觀,影響算法性能。

由此可知,適應值噪聲主要由偏好的不確定性造成,在不同進化階段,偏好不確定性決定了噪聲不同的特性,這為分析噪聲特性提供了依據,具體如下:

(3)

隨著認知程度的成熟,評價的穩定期很快到來。在這一階段內,對于不同進化代內出現的相同個體,評價結果差異較小,即有θ(xi(t))<ε。此時噪聲較小,這也是評價的主要階段。這一時期噪聲主要是隨機噪聲,因此,噪聲仍可看成是加性。在偏好穩定階段可近似認為噪聲強度不變。此時適應值表達式為:

f(x(t))=F(x(t))+δ2(t)·N(0,1)

(4)

其中,δ2(t)是噪聲強度。

隨著進化過程不斷深入,在進化后期,不同個體之間差異越來越小,對這些個體做相對優劣的評價會越來越困難,此時心理壓力加大,疲勞開始上升,直至明顯疲勞狀態出現。由于疲勞增強,此時噪聲對評價的影響程度變大,因此評價偏差程度較前兩個階段大幅增加,即θ(xi(t))>>ε。用戶疲勞是這一時期影響噪聲的主要原因,因此,噪聲性質為乘性,適應值表達式為:

(5)

閾值ε主要反映每一進化代中相似個體的平均距離[11]:

(6)

在進化初期,個體適應值差異較大,ε較小;隨著進化不斷深入,不同個體的適應值會逐漸接近,個體間的差異將逐漸減小,ε較大。可以看到,ε刻畫的種群特性與適應值噪聲模型的形態是一致的,因此,可以將ε作為適應值不確定度閾值。

3 進化個體混雜型適應值

根據以上對偏好不確定和適應值噪聲的分析可以看到,進化過程中個體適應值[9]采用單一形態表示不能全面反映評價的客觀性。采用適應值估計策略是解決適應值不確定性的代表性策略:文獻[12]采用遞歸神經網絡估計個體適應值;文獻[13]根據個體與上代最優個體相似度估計個體適應值;文獻[14]根據決策者偏好估計區間多目標優化問題中的個體適應值;文獻[15-16]提出適應值加權多輸出高斯過程代理模型和適應值CP-nets估計模型。基于此,本文提出擬合噪聲的進化個體混雜型適應值形態:如果個體評價不確定度較大,噪聲較強,個體適應值表現為區間數值類型;如果個體評價不確定度較小,噪聲較弱,個體適應值表現為單一數值類型。其中,適應值區間數值類型可由單一數值類型擴展得到。

當θ(xi(t))>ε或θ(xi(t))>>ε時,定義σ(xi(t))為個體單一數值適應值f(xi(t))擴展成區間適應值f′(xi(t))的區間半徑。由于θ(xi(t))反映了評價不確定性,因此本文在θ(xi(t))和σ(xi(t))之間用函數關系σ=g(θ)映射,函數擬合式如下:

σ(xi(t))=K(1-e-λθ(xi(t)))

(7)

其中,K、λ為調節系數。

式(7)的函數形式通過“置信法”樣本評價統計獲得,并且σ(xi(t))與噪聲δ(t)分布相同,即σ(xi(t))～N(0,δ(t))。據此,根據式(7)可將單一評價值f(xi(t))擴張成區間數值f′(xi(t)),表示如下:

[f(xi(t))-σ(xi(t)),f(xi(t))+

σ(xi(t))]

(8)

進一步對區間適應值進行估計,令:

(9)

(10)

其中,θ表示對設計人員滿意程度的點估計值,m表示點估計的盲度,m越小,估計的把握越大,m=0意味著對滿意程度絕對有把握。

當θ(xi(t))<ε時,適應值表現為單一數值。此時,為進一步降低噪聲影響,采用灰Verhulst模型對適應值建模,通過對適應值修正,降低噪聲。假設個體的單一數值評價值f(x(t))構成原始序列f(0)(x(t))=(f(0)(x1(t)),f(0)(x2(t)),…,f(0)(xN(t)))。在每一進化代內,個體評價值序列先進行灰生成序列和平均值序列的轉化,灰生成序列為f(1)(xi(t))=AGOf(0)(xi(t)),平均值序列為F(1)(xi(t))=MEANf(1)(xi(t)),再構建進化個體適應值灰Verhulst模型GM(1,1,V)為:

f(0)(xi(t))+aF(1)(xi(t))=b(F(1)(xi(t)))2

(11)

GM(1,1,V)的白化響應式為:

(12)

(13)

由于進化個體適應值序列是偏好環境下各種因素作用的結果,因此可以通過灰模型滾動檢驗預測偏好分布。個體適應值的滾動殘差ε(i+1)為:

(14)

根據滾動殘差,可得個體xi(t)的適應值可信度pr(xi(t))為:

pr(xi(t))=[100-|ε(i)|]×100%

(15)

通過適應值可信度對評價后的進化個體適應值進行修正:

f′(xi(t))=pr(xi(t))·f(xi(t))

(16)

其中,f′(xi(t))為進化個體xi(t)修正后的適應值。

混雜型適應值的特點是:在進化過程中,用戶通過操作界面采用單一數值對個體評價,通過將適應值轉化為區間數值或進行修正,實現對噪聲的擬合。在每一進化代內,區間數適應值與單一數值適應值共存,再通過遺傳操作進化優化,從而獲得用戶滿意的滿意解。這種方法相比直接區間適應值賦值或模糊適應值賦值,可以在只有一半操作工作量的前提下,獲得與區間適應值賦值相同的評價信息量,為進化優化提供更大的進化數據和優化空間。本文算法流程如圖1所示,其中,對于擴展成區間數的區間適應值,可以按區間占優進行個體選擇;對于通過灰模型預測的修正后的單一數值適應值,可以按輪賭法進行個體選擇。

圖1 本文算法流程

4 應用結果與分析

4.1 染色體編碼

便攜式酒壺是一種流行的戶外消費品,它具有高雅精致、美觀小巧、便于隨身攜帶的特點。隨著白酒市場小瓶化趨勢增強,酒壺外觀對產品價格的影響日益增大。為了增強市場競爭力,便攜式酒壺的外觀設計逐漸趨向個性化,這使得酒壺的外觀設計成為提高市場占有率的重要因素。基于此,筆者借助遺傳算法的優化能力開發便攜式酒壺外觀設計系統,幫助用戶獲得符合偏好的設計方案。由于目前針對便攜式酒壺設計尚無應用交互式遺傳算法的報道,因此本文同時為便攜式酒壺企業提供了一種新的設計思路。

鑒于酒壺貼皮紋樣與酒壺材質造型無關,所以將酒壺外觀分為壺口(帶壺蓋)和壺身兩部分討論,這樣個體的染色體編碼便由壺口和壺身編碼構成。壺口類型分為圓型、柱型、方型、異型、不對稱和帶連桿6類;壺身類型分為圓型、柱型、方型、異型、不對稱和壺型6類。壺口和壺身的三維結構模型以bmp格式儲存在圖片庫中。編碼過程是將壺口和壺身分別在[0,1 023]內取整數值,然后再分別將整數值轉化為10位二進制編碼,兩者共同構成酒壺個體的20位染色體。酒壺壺口和酒壺壺身的類型及編碼段如表1所示。圖2給出了個體編碼過程,其中FS和FB分別為壺口和壺身的十進制編碼,該個體記為(880,343),染色體編碼為1101110000 0101010111,這是一種壺口為帶連桿型、壺身為方型的酒壺類型。

表1 酒壺壺口與壺身類型

圖2 個體編碼過程

4.2 交互界面設計及操作方法

系統采用Visual Basic 6.0、SQL Sever2005數據庫實現,遵循Johnson2007用戶界面設計9項準則,并充分考慮人記憶的2個功能——識別和回憶對交互系統設計的影響。系統中各任務流程采用翻頁式結構,盡可能減輕用戶短期記憶負擔。系統運行時,首先對種群初始化,用戶需設定交叉、變異概率等遺傳操作參數。然后,系統會根據壺口和壺身兩部分的二進制編碼,啟動模型載入模塊,輸出完整的三維酒壺模型。接著啟動處理模塊,實現模型的貼皮和可旋轉,增強樣本的真實感。重復該過程直至生成初始種群,即8個酒壺樣本。系統的人機交互界面如圖3所示,在每個樣本下方用戶根據偏好通過滑動條為樣本打分,評價結果作為輸入提交給系統,打分范圍為[1,100]。評價結束后,點擊“下一代”按鈕,啟動交互式遺傳算法模塊,實現進化優化,生成新種群。循環這一過程,直至進化收斂。最后,點擊“結束”按鈕,將最滿意個體作為優化結果輸出。界面同時顯示點估計值、盲度值、進化代數和耗時等信息,提示用戶修正偏好和把握操作節奏。在整個進化過程中,如果設計人員對當前的酒壺方案始終不夠滿意,可重新初始化酒壺種群,開始新的進化。

圖3 系統交互界面

4.3 應用結果分析

為客觀檢測本文系統的設計效果,以傳統交互式遺傳算法(Traditional Interactive Genetic Algorithm,T-IGA)和區間適應值交互式遺傳算法(Interactive Genetic Algorithm with Individuals Interval Fitness,IGA-IIF)為比較對象,驗證所提方法在減輕用戶疲勞、搜索效率、優化質量等方面的有效性。由于交互式遺傳算法不需要適應值函數,因此不能采用公測函數進行數值優化。基于此,本文采用固定優化解測試數值統計方法與已有算法進行對比實驗,測試實驗有5位在校大學生參與,以圖2所示個體(880,343)為目標樣本,在相同參數(設置變異概率0.02,交叉概率0.6;在式(6)中,參數K=20,λ=10)下每種算法每人獨立進行6次實驗,總計進行90人次的獨立實驗。采用3種終止進化條件:進化至最大進化代數T,系統收斂(相同個體占種群75%及以上),用戶對優化結果滿意。當任意終止條件滿足時,系統結束進化,并輸出進化優化結果。統計進化代數、評價耗時、互異個體數目和搜索效率(搜索效率=評價的互異個體數/總評價個體數)等性能指標,箱形圖和曲線如圖4和圖5所示;然后統計3種算法在不同時間內找到互異個體數目的比例,如表2所示;最后采用Mann-Whitney U方法,對實驗數據進行非參數檢驗。取顯著性水平為0.05,漸進顯著性水平如表3所示。

圖4 算法性能指標箱形圖

圖5 算法性能指標曲線

表2 算法在不同時間內找到互異個體數目比例 %

表3 算法漸進顯著性水平

由上述實驗結果可知:

1)在進化代數方面,本文算法與對比算法的漸進顯著性水平均小于0.05,說明本文算法與對比算法存在顯著差異;再結合圖4的數據分布可知,本文算法優于其他2種方法。原因在于:本文的適應值表達策略在一定程度上抑制了噪聲對進化的影響,使進化方向更接近人的偏好,算法收斂較快。

2)在用戶評價耗時方面,與IGA-IIF和T-IGA算法相比,本文算法需要的評價時間最短,只有傳統交互式遺傳算法耗時的一半左右,并且本文算法與對比算法的差異顯著。原因在于:本文算法的適應值修正策略使適應值更為接近真實值,加快了算法收斂,用戶評價時間更短。

3)在找到互異個體數目方面,本文算法獲得的互異個體數目最多,說明其獲得的種群多樣性最好。原因在于:通過將適應值單一數值類型擴張為區間數值類型豐富了進化信息,加強了算法搜索能力,增加了種群多樣性。

4)在搜索效率方面,由于本文算法搜索到的互異個體最多,且收斂速度最快,因此其搜索效率也顯著高于其他2種算法。

上述實驗結果與分析表明,本文算法對個體只評價精確數值即可獲得比對個體進行區間賦值評價更豐富的種群多樣性,并且該算法能夠以最少的進化代數和用戶評價耗時,找到最多的互異個體,提高了算法優化效率,而耗時減少意味著縮短了人的操作時間,降低了操作負擔。

5 結束語

本文提出基于混雜型個體適應值的交互式遺傳算法,該優化算法分為兩部分:第一部分利用友好的人機交互平臺,提取設計人員設計信息;第二部分是進化單元。首先,算法利用適應值的不確定度作為個體適應值類型劃分依據,保證評價值分類的合理性;然后,系統對適應值的單一數值類型和區間數值類型分別構建相應數學模型,提高評價的準確性;最后,針對不同類型的適應值個體采取不同的進化策略,實現產品外觀的自動設計。

本文算法能夠有效減輕設計人員的操作負擔,設計人員只需粗略評價少量個體即可,系統在后臺自動完成適應值形態轉換與修正。同時通過算法對評價結果的轉換與修正,擬合了評價噪聲,提高了個體評價準確性和優化質量。此外,不同形態的評價結果共同參與優化,更符合人的設計行為,優化效率高于單一類型適應值形態。后續將開發更合理的適應值估計與預測方法,進一步提高算法效率。