人機協(xié)同演化算法研究

人機協(xié)同演化算法研究現(xiàn)實世界中大量的應(yīng)用問題可看成優(yōu)化問題來解決,演化算法一直是解決此類問題的有效方法之一。對于顯式目標(biāo)優(yōu)化問題,演化算法表現(xiàn)出極大的優(yōu)勢,不要求目標(biāo)函數(shù)滿足連續(xù)、可微、凸等限制條件。然而,對于隱式目標(biāo)優(yōu)化問題,傳統(tǒng)的演化算法顯得有些力不從心。實際上,現(xiàn)實世界中有很多問題都可以看成是隱式目標(biāo)優(yōu)化問題。例如,藝術(shù)創(chuàng)作、CAD設(shè)計、圖像檢索等等。這類問題的優(yōu)化目標(biāo)一般取決于用戶的藝術(shù)修養(yǎng)、偏好、經(jīng)驗、直覺等各種主觀因素,很難被量化,表示成函數(shù)作為優(yōu)化目標(biāo)幾乎不太可能。交互式演化算法是解決隱式目標(biāo)優(yōu)化問題的主要方法,引起了國內(nèi)外學(xué)者的廣泛關(guān)注。然而,在“狹義”的范疇,交互式演化算法中用戶只充當(dāng)了適應(yīng)值函數(shù)的功能,用戶干預(yù)的潛力無法得到有效釋放。對于更加“廣義”的范疇,即人為干預(yù)作用于演化算法的多個方面,近年來才得到學(xué)者們的關(guān)注。如何在交互式演化算法中融入更多人為干預(yù)因素,提高算法求解效率的同時又能極大限度的減輕用戶疲勞,這是非常有意義的研究課題。本文將“廣義”的交互式演化算法及其相關(guān)技術(shù)定義為“人機協(xié)同演化計算(User-systemCooperativeEvolutionaryComputation,USCEC)"?；诓罘盅莼惴▽崿F(xiàn)了USCEC系統(tǒng)框架,允許用戶在種群、個體和基因三個層次進行干預(yù)。USCEC摒棄了適應(yīng)值賦值交互方式,使用成對比較選擇和基因直接編輯兩種人機交互方式,引入多種工作模式,并能自由切換,從而有效利用人和算法各自的優(yōu)勢。本文的主要研究工作有以下幾個方面：(1)提出了兩種減少編輯特征數(shù)目的方法,分別為基于區(qū)間熵和基于辨別因子的可編輯特征提取方法?；趨^(qū)間熵的可編輯特征的提取主要分析用戶滿意解中的特征分布情況,而基于辨別因子的方法則需要同時分析滿意解和不滿意解。實驗結(jié)果表明,在高維特征向量上,采用辨別因子的編輯特征提取方法效果要好于基于區(qū)間熵的方法,能在保證算法效率的同時減少可編輯特征的數(shù)目,減輕用戶疲勞。(2)提出了一種局部搜索策略,基于SVM建立了能區(qū)分滿意解和非滿意解的決策超平面,通過評價積累的樣本不斷調(diào)整此超平面的位置,從候選解集中選擇離超平面距離最遠(yuǎn)的若干個體作為精英,并在人為操作下用于劣質(zhì)解的替換。實驗表明此方法能減少基因編輯的次數(shù)。換言之,就是解的評價操作代替了解的編輯操作,從而減輕用戶由于過多的編輯行為產(chǎn)生的疲勞。(3)提出了一種基于透鏡成像原理的反學(xué)習(xí)策略,在USCEC系統(tǒng)評價交互界面上增加了一個反向解窗口,為每個演化個體提供了一次接近最優(yōu)目標(biāo)區(qū)域的機會。此方法通過引入“搜索半徑”和“縮放因子”兩個參數(shù),實現(xiàn)了算法在搜索區(qū)域廣度和深度上的一種平衡,可以看成是當(dāng)前種群在用戶的作用下與反向種群之間的“較量”。實驗表明,該方法加速了算法的收斂,能在較少的迭代次數(shù)內(nèi)找到滿意解。(4)為進一步減輕USCEC中的用戶疲勞問題,本文構(gòu)造了用戶評價代理模型,在一定程度上代替用戶評價。由于USCEC使用了成對比較選擇的評價交互方式,代理模型被設(shè)計成比較器。本文使用有向圖表示用戶偏好信息,并基于極限學(xué)習(xí)機建立分類器模型,使用改進的粒子群算法優(yōu)化極限學(xué)習(xí)機的相關(guān)參數(shù)。實驗表明,相對于傳統(tǒng)的基于神經(jīng)網(wǎng)絡(luò)的模型,本文提出的代理模型能獲得較好的精度,并且通過與反向?qū)W習(xí)策略的結(jié)合,在少量的迭代次數(shù)下就能獲得較多的樣本用于訓(xùn)練模型。本文的研究成果分別在人臉卡通圖像設(shè)計和基于內(nèi)容的圖像檢索問題中得到了驗證。研究結(jié)果表明,本文的研究成果為交互式演化計算提供了