包含交叉和變異操作的交互式遺傳算法

郭廣頌,王燕芳

(鄭州航空工業(yè)管理學(xué)院機(jī)電工程學(xué)院,鄭州450015)

包含交叉和變異操作的交互式遺傳算法

郭廣頌,王燕芳

(鄭州航空工業(yè)管理學(xué)院機(jī)電工程學(xué)院,鄭州450015)

傳統(tǒng)交互式遺傳算法在優(yōu)化隱式性能指標(biāo)時會使用戶產(chǎn)生疲勞,影響優(yōu)化質(zhì)量與優(yōu)化效率。為此,提出一種改進(jìn)的交互式遺傳算法。采用二元排序確定適應(yīng)值評價的不確定度,根據(jù)評價序列的最大信息差異計(jì)算種群的收斂率,通過收斂率衡量種群進(jìn)化狀態(tài),基于適應(yīng)值不確定度和種群收斂率設(shè)計(jì)自適應(yīng)交叉算子和變異算子,給出交叉概率和變異概率的計(jì)算公式,利用包含用戶偏好信息的遺傳策略引導(dǎo)進(jìn)化,從而使進(jìn)化結(jié)果更加客觀。將該算法應(yīng)用于服裝進(jìn)化設(shè)計(jì)系統(tǒng),結(jié)果表明,與傳統(tǒng)交互式遺傳算法(T-IGA)相比,該算法可獲取更多的滿意解,提高了優(yōu)化效率。

遺傳算法;自適應(yīng)交叉;變異概率;適應(yīng)值;交互環(huán)境;不確定性

1 概述

交互式遺傳算法(Genetic Algorithm,GA)是20世紀(jì)80年代在傳統(tǒng)遺傳算法的基礎(chǔ)上提出的一種進(jìn)化優(yōu)化算法［1-2］。它與傳統(tǒng)遺傳算法的最大區(qū)別在于交互式遺傳算法的個體適應(yīng)值由人評價,這樣可以將人的主觀活動引入進(jìn)化過程中,利用遺傳進(jìn)化對隱式性能指標(biāo)或混合性能指標(biāo)進(jìn)行優(yōu)化。由于該算法實(shí)現(xiàn)簡單,能體現(xiàn)強(qiáng)烈的個性化需求,因此目前在圖像識別、藝術(shù)設(shè)計(jì)、虛擬現(xiàn)實(shí)等領(lǐng)域獲得了有效應(yīng)用［2］。

由于個體適應(yīng)值由人評價產(chǎn)生,因此適應(yīng)值反映了人的主觀偏好,而人的偏好會使適應(yīng)值具有不確定性,不確定性增加,適應(yīng)值的精確程度便會降低,進(jìn)化優(yōu)化效果將會變差。提高適應(yīng)值精確程度,降低不確定性的直接方法是人在評價個體時投入更多的注意力,但這樣無疑會造成人的疲勞,評價不確定性反而會增強(qiáng)。所以,提高適應(yīng)值精度與降低人

的操作負(fù)擔(dān)是互為矛盾的,這也是交互式遺傳算法的一個研究難題。

目前,大致有2種思路解決這一問題:(1)通過建立合理的適應(yīng)值賦值方式,改善人機(jī)交互環(huán)境,降低人的操作負(fù)擔(dān),提高適應(yīng)值精度;(2)針對評價特點(diǎn)抽取個體適應(yīng)值的不確定度,采用合適的代理模型代替用戶估計(jì)進(jìn)化個體的適應(yīng)值,減輕用戶疲勞。

對于思路(1),文獻(xiàn)［3］提出離散適應(yīng)值賦值方法,一定程度減輕了人的操作負(fù)擔(dān),但離散適應(yīng)值本身精度較差,這種方法實(shí)質(zhì)并未考慮降低評價的不確定性。文獻(xiàn)［4-6］提出區(qū)間數(shù)和模糊數(shù)適應(yīng)值賦值方法,相比精確數(shù)與離散數(shù),區(qū)間數(shù)與模糊數(shù)可以較好地反映出評價過程的不確定性與漸進(jìn)性,大大提高了適應(yīng)值精度。但在進(jìn)行適應(yīng)值賦值操作時,區(qū)間數(shù)要進(jìn)行適應(yīng)值上限與下限的2次評價;模糊數(shù)要進(jìn)行中心值與寬度的確定,這其實(shí)都增加了人的負(fù)擔(dān)。相似的問題還存在于文獻(xiàn)［7］。

對于思路(2),文獻(xiàn)［8-11］提出多種交互式遺傳算法的機(jī)器學(xué)習(xí)技術(shù),通過代理模型預(yù)測評價結(jié)果,減少人的部分評價工作。機(jī)器學(xué)習(xí)技術(shù)拓展了算法搜索能力,減輕了操作負(fù)擔(dān),提高了算法性能。但這些代理模型是依據(jù)于不同的適應(yīng)值賦值方式,提取有價值信息而建立,所以,適應(yīng)值賦值方式的影響依然存在。

針對上述問題,本文提出一種新的交互式遺傳算法。對進(jìn)化個體的評價過程進(jìn)行分析,依據(jù)二元排序方法獲得評價的不確定度,基于該不確定度設(shè)計(jì)自適應(yīng)交叉算子和變異算子。

2 算法分析與設(shè)計(jì)

2.1 適應(yīng)值不確定度

若記第t代進(jìn)化種群x(t)中的第i個進(jìn)化個體為xi(t),i=1,2,…,N,N為種群規(guī)模,xi(t)的適應(yīng)值為f(xi(t)),xi(t)∈x(t),則進(jìn)化個體量測值f(x(t))構(gòu)成的數(shù)值序列為:

因?yàn)閒(xi(t))難以準(zhǔn)確確定,所以f(xi(t))具有不確定性［8］。

遺傳進(jìn)化是一個馬爾科夫鏈過程,每次進(jìn)化結(jié)果都會為偏好提供新環(huán)境,所以,用戶的偏好是波動的,保持偏好的一致性也是相對的。根據(jù)實(shí)際經(jīng)驗(yàn),對每一代個體逐一評價時,個體的排列順序如果不同,同一個體的評價結(jié)果往往會發(fā)生變化,例如第一個被評價的個體大多結(jié)果偏低,這便是偏好波動的體現(xiàn)?；谶@樣的事實(shí),可以對評價過程進(jìn)行分析:在每一進(jìn)化代中,個體適應(yīng)值評價的實(shí)質(zhì)是對個體的兩兩對比來確定某種偏好特征下的順序,即是一個二元排序過程。具體地說,偏好對相鄰2個個體的適應(yīng)值影響是最大的,適應(yīng)值評價是對相鄰個體建立比較等級的過程,相鄰個體的適應(yīng)值是對滿意解的相似程度的體現(xiàn)。依據(jù)評價次序,后評價的個體結(jié)果受前一個評價對象的影響最明顯,當(dāng)相鄰2個個體差異較大時,偏好波動會比較大,評價的不確定性相應(yīng)增加;反之,則偏好趨于一致,評價不確定性降低?？梢哉J(rèn)為評價過程是以相鄰個體為單元的鏈?zhǔn)竭^程,相鄰個體適應(yīng)值評價是評價過程的最小環(huán)節(jié)。

對于相鄰個體xi(t)和xi-1(t),f(xi(t))和f(xi-1(t))可以看作是對真實(shí)適應(yīng)值fbest(x(t))的比較結(jié)果。如前所述,對于個體xi(t),f(xi(t))的不確定性受f(xi-1(t))的影響最大,f(xi(t))的不確定度由f(xi(t))本身和f(xi-1(t))決定。若令有界閉區(qū)間:

則fs(t)可以認(rèn)為是f(xi(t))和f(xi-1(t))信息差異的數(shù)值覆蓋,而信息差異可以反映評價的不確定性［12］。若記f(xi(t))的不確定度為(xi(t)),由于fs(t)為有界閉區(qū)間,則有:

則每一進(jìn)化代的適應(yīng)值不確定度記為:

且滿足下式成立:

證明:

證畢。

式(4)表明適應(yīng)值不確定度小于同代的最大信息差異,這也說明了人對相鄰個體的評價在每一進(jìn)化代內(nèi)最為客觀。

衡量進(jìn)化的另一重要指標(biāo)是收斂率［11］。若將種群f(xi(t))的收斂率記為δ(xi(t)),則有:

收斂率δ(xi(t))反映了每一進(jìn)化代中相似個體的平均“擁擠”距離。隨著進(jìn)化不斷深入,不同個體的適應(yīng)值會逐漸接近,個體間的差異將逐漸減小,并且,θ(xi(t))≤δ(xi(t))。

從式(3)和式(5)可以看出,在進(jìn)化初期用戶對個體的認(rèn)知程度較低,所以,θ(xi(t))和δ(xi(t))都比較大。隨著進(jìn)化過程加深,用戶評價的個體數(shù)量不斷增加,認(rèn)知目標(biāo)會逐漸清晰,評價不確定性相應(yīng)減小,所以,θ(xi(t))和δ(xi(t))也逐漸減小。

2.2 自適應(yīng)交叉和變異算子

θ(xi(t))和δ(xi(t))描述了適應(yīng)值在種群進(jìn)化過程中的變化,反映了個體適應(yīng)值品質(zhì)的不同方面,這為設(shè)計(jì)自適應(yīng)交叉和變異操作提供了基礎(chǔ)。

交叉算子的設(shè)計(jì)主要基于以下2個方面:(1)選擇S函數(shù)作為操作函數(shù)。這是因?yàn)镾函數(shù)具有平滑、單調(diào)和非線性等數(shù)學(xué)特性,這與進(jìn)化優(yōu)化特性一致［13-14］。(2)當(dāng)評價的不確定性比較大時,采用較大的交叉概率增強(qiáng)新個體的數(shù)量;當(dāng)評價的不確定性較小時,采用較小的交叉概率加快算法收斂。由此,設(shè)計(jì)交叉算子為:

其中,k1是調(diào)節(jié)系數(shù)。

變異操作同樣會為算法帶來新個體,變異算子的設(shè)計(jì)主要基于以下2個方面:(1)當(dāng)評價的不確定性比較大時,為了增加種群的多樣性,此時變異概率應(yīng)該較大;當(dāng)評價的不確定性較小時,采用較小的變異概率加快算法收斂。(2)在進(jìn)化后期,為了保證算法收斂,應(yīng)使變異概率降低。為此將變異概率限定在區(qū)間(0,0.5)內(nèi)［15-16］。由此,設(shè)計(jì)變異算子為:

其中,k2是調(diào)節(jié)系數(shù)。

3 算法步驟

本文算法過程如下:

(1)設(shè)定種群進(jìn)化控制參數(shù),初始化進(jìn)化種群x(t)。

(2)評價進(jìn)化個體,給出個體適應(yīng)值f(xi(t))。

(3)依據(jù)式(3)和式(5)計(jì)算個體適應(yīng)值的不確定度θ(xi(t))和收斂率δ(xi(t))。

(4)按輪賭法選擇個體。

(5)按式(6)和式(7)進(jìn)行交叉和變異操作,產(chǎn)生子代種群x(t),令t=t+1。

(6)判斷進(jìn)化結(jié)果是否達(dá)到滿意程度,若滿足,轉(zhuǎn)步驟(7);否則,轉(zhuǎn)步驟(2)。

(7)輸出最優(yōu)進(jìn)化個體,算法終止。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)參數(shù)設(shè)定

本文實(shí)驗(yàn)對象是服裝進(jìn)化設(shè)計(jì)系統(tǒng)。該系統(tǒng)用18 Byte二進(jìn)制串對染色體編碼。上衣由二進(jìn)制串的前5 Byte表示,款式由6 Byte～10 Byte表示,顏色由11 Byte～14 Byte表示,裙子的顏色由15 Byte～18 Byte表示。上衣和裙子款式各有32套,名稱分別是從0～31的整數(shù),對應(yīng)于二進(jìn)制編碼的十進(jìn)制值［9-10］。表1給出了服裝顏色與款式的編號。

表1 服裝顏色與款式編號

為了說明本文算法性能,算法的比較對象是傳統(tǒng)交互式遺傳算法(T-IGA)。本文算法和T-IGA均采用輪賭法選擇算子。T-IGA采用單點(diǎn)交叉和單點(diǎn)變異,交叉概率和變異概率均為固定值,根據(jù)經(jīng)驗(yàn), T-IGA的交叉和變異概率如表2所示。個體適應(yīng)值評價范圍是0～100,最大進(jìn)化代數(shù)為20,種群規(guī)模為8。當(dāng)進(jìn)化已經(jīng)收斂或人對進(jìn)化結(jié)果滿意時,手動終止種群進(jìn)化。在式(6)和式(7)中,參數(shù)k1=k2=10。

表2 T-IGA的交叉概率和變異概率

4.2 結(jié)果分析

分別對本文算法和傳統(tǒng)交互式遺傳算法,按設(shè)定參數(shù)獨(dú)立運(yùn)行20次,對比性能指標(biāo)包括進(jìn)化代數(shù)、滿意解數(shù)目和耗時等,其中,滿意解是指每代中精確數(shù)適應(yīng)值最高和次高的個體。2種算法的進(jìn)化代數(shù)統(tǒng)計(jì)如圖1所示。

圖1 2種算法進(jìn)化代數(shù)統(tǒng)計(jì)

由圖1可以看到,本文算法的進(jìn)化代數(shù)較少。算法獲得滿意解的統(tǒng)計(jì)情況如圖2所示,可以看出,本文算法獲得的滿意解數(shù)目較多。主要原因是采用基于適應(yīng)值不確定度和收斂率的自適應(yīng)交叉變異操作使種群多樣性增強(qiáng),算法可以利用的信息也更多,這也說明了采用二元排序分析適應(yīng)值的有效性。

圖2 2種算法滿意解數(shù)對比

結(jié)合圖1和圖2可以看出,本文算法可以在較少的進(jìn)化代內(nèi)獲得較多的滿意解數(shù)目,這加快了算法收斂速度,顯示了較好的進(jìn)化優(yōu)化能力。最后,統(tǒng)計(jì)算法的耗時情況為T-IGA算法為9 min 26 s;本文算法為7 min 44 s。由于本文算法的進(jìn)化代數(shù)少,因此每次實(shí)驗(yàn)的耗時也比較少。而耗時減少意味著縮短了人的操作時間,自然有效降低了人的操作負(fù)擔(dān)。

5 結(jié)束語

本文提出一種包含交叉和變異操作的交互式遺傳算法。與同類算法相比,其創(chuàng)新點(diǎn)主要體現(xiàn)在如下3個方面:(1)利用二元排序分析個體適應(yīng)值的不確定性,從相鄰個體適應(yīng)值中抽取適應(yīng)值不確定度;(2)采用收斂率衡量種群的收斂情況;(3)采用不確定度和收斂率設(shè)計(jì)自適應(yīng)交叉算子和變異算子。將算法應(yīng)用于服裝進(jìn)化設(shè)計(jì)系統(tǒng),結(jié)果表明,該算法在獲得滿意解和縮短耗時等方面能取得較好的效果。今后將繼續(xù)研究交互式遺傳算法優(yōu)化過程中適應(yīng)值的變化規(guī)律,并依據(jù)適應(yīng)值變化規(guī)律探尋提高算法性能的方法。

［1]Takagi H.Interactive Evolutionary Computation:Fusion of the Capabilities of EC Optimization and Human Evolution［J］.Proceedings of the IEEE,2001,89(9): 1275-1296.

［2]Takagi H,Ohsaki M.Interactive Evolutionary Computation Based Hearing Aid Fitting［J］.IEEE Transactions on Evolutionary Computation,2007,11(3):414-427.

［3]Ohsaki M,Takagi H,Ohya K.An Input Method Using Discrete Fitness Values for Interactive GA［J］.Journal of Intelligent&Fuzzy Systems:Applications in Engineering and Technology,1998,6(1):131-145.

［4]Gong Dunwei,Guo Gangsong,Lu Li.Adaptive Interactive Genetic Algorithms with Interval Fitness of Evolutionary Individuals［J］.Progress in Natural Science,2008,18(3): 359-365.

［5]Sun Xiaoyan,Gong Dunwei.Interactive Genetic Algorithms with Individual’s Fuzzy and Stochastic Fitness［J］.Chinese Journal of Electronics,2009,18(4):619-624.

［6]Gong Dunwei,Yuan Jie,Sun Xiaoyan.Interactive Genetic Algorithms with Individual’s Fuzzy Fitnesss［J］.Computers in Human Behavior,2011,27(5):1482-1492.

［7]胡曉輝,陳俊蓮,張曉穎.改進(jìn)的區(qū)間值模糊集交互式遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用,2010,46(28): 51-53.

［8]孫曉燕,任 潔,鞏敦衛(wèi).基于半監(jiān)督學(xué)習(xí)的變種群規(guī)模區(qū)間適應(yīng)值交互式遺傳算法［J］.控制理論與應(yīng)用, 2011,28(5):610-618.

［9]鞏敦衛(wèi),任 潔,孫曉燕.區(qū)間適應(yīng)值交互式遺傳算法神經(jīng)網(wǎng)絡(luò)代理模型［J］.控制與決策,2009,24(10): 1522-1530.

［10]孫曉燕,鞏敦衛(wèi).自適應(yīng)分區(qū)多代理模型交互式遺傳算法［J］.控制與決策,2009,24(2):170-180.

［11]鞏敦衛(wèi),陳 健,孫曉燕.新的基于相似度估計(jì)個體適應(yīng)值的交互式遺傳算法［J］.控制理論與應(yīng)用,2013, 30(5):558-566.

［12]鄧聚龍.灰理論基礎(chǔ)［M］.武漢:華中科技大學(xué)出版社,2003.

［13]郭廣頌,崔建鋒.基于進(jìn)化個體適應(yīng)值灰度的自適應(yīng)交互式遺傳算法［J］.計(jì)算機(jī)應(yīng)用,2008,28(10):2525-2528.

［14]郭廣頌,何琳琳.基于區(qū)間適應(yīng)值灰度的交互式遺傳算法［J］.計(jì)算機(jī)工程,2009,35(14):233-235.

［15]郭廣頌,李秀娟.基于離散適應(yīng)值灰度的交互式遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用,2010,46(24):225-228.

［16]郭廣頌,趙紹剛.基于個體適應(yīng)值灰模型的交互式遺傳算法［J］.計(jì)算機(jī)工程,2010,36(3):209-212.

編輯 劉 冰

Interactive Genetic Algorithm Containing Crossover and Mutation Operation

GUO Guangsong,WANG Yanfang
(School of Mechatronics Engineering,Zhengzhou Institute of Aeronautical Industry Management,Zhengzhou 450015,China)

The traditional interactive Genetic Algorithm(GA)can make user fatigue on optimizing the implicit performance index which affects the optimization quality and optimization efficiency.It is necessary to enhance the performance of interactive GA in order to apply it to complicated optimization problems successfully.The uncertainty of individual fitness is calculated based on the evaluation difference between the adjacent individuals;the convergence rate is abstracted according to the biggest information differences in evaluation sequence which reflecting the convergence of evolutionary population.Based on these,the probabilities of crossover and mutation operation of evolutionary individuals are presented.It makes the results more objective by guiding the evolutionary strategy through user preference information,and it allows a better exploration of the searching space and gives better findings compared with the traditional interactive GA(T-IGA).

Genetic Algorithm(GA);adaptive crossover;mutation probability;fitness value;interactive environment;uncertainty

郭廣頌,王燕芳.包含交叉和變異操作的交互式遺傳算法［J］.計(jì)算機(jī)工程,2015,41(3):182-185.

英文引用格式:Guo Guangsong,Wang Yanfang.Interactive Genetic Algorithm Containing Crossover and Mutation Operation［J］.Computer Engineering,2015,41(3):182-185.

1000-3428(2015)03-0182-04

:A

:TP399

10.3969/j.issn.1000-3428.2015.03.035

河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃基金資助項(xiàng)目(122300410295)。

郭廣頌(1978-),男,副教授、碩士,主研方向:智能控制;王燕芳,副教授、碩士。

2014-03-17

:2014-05-07E-mail:guogs78@126.com