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

郭廣頌,王燕芳

(鄭州航空工業管理學院機電工程學院,鄭州450015)

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

郭廣頌,王燕芳

(鄭州航空工業管理學院機電工程學院,鄭州450015)

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

遺傳算法;自適應交叉;變異概率;適應值;交互環境;不確定性

1 概述

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

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

的操作負擔是互為矛盾的,這也是交互式遺傳算法的一個研究難題。

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

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

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

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

2 算法分析與設計

2.1 適應值不確定度

若記第t代進化種群x(t)中的第i個進化個體為xi(t),i=1,2,…,N,N為種群規模,xi(t)的適應值為f(xi(t)),xi(t)∈x(t),則進化個體量測值f(x(t))構成的數值序列為:

因為f(xi(t))難以準確確定,所以f(xi(t))具有不確定性［8］。

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

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

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

則每一進化代的適應值不確定度記為:

且滿足下式成立:

證明:

證畢。

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

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

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

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

2.2 自適應交叉和變異算子

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

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

其中,k1是調節系數。

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

其中,k2是調節系數。

3 算法步驟

本文算法過程如下:

(1)設定種群進化控制參數,初始化進化種群x(t)。

(2)評價進化個體,給出個體適應值f(xi(t))。

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

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

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

(6)判斷進化結果是否達到滿意程度,若滿足,轉步驟(7);否則,轉步驟(2)。

(7)輸出最優進化個體,算法終止。

4 實驗結果與分析

4.1 實驗參數設定

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

表1 服裝顏色與款式編號

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

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

4.2 結果分析

分別對本文算法和傳統交互式遺傳算法,按設定參數獨立運行20次,對比性能指標包括進化代數、滿意解數目和耗時等,其中,滿意解是指每代中精確數適應值最高和次高的個體。2種算法的進化代數統計如圖1所示。

圖1 2種算法進化代數統計

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

圖2 2種算法滿意解數對比

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

5 結束語

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

［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］.計算機工程與應用,2010,46(28): 51-53.

［8]孫曉燕,任 潔,鞏敦衛.基于半監督學習的變種群規模區間適應值交互式遺傳算法［J］.控制理論與應用, 2011,28(5):610-618.

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

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

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

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

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

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

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

［16]郭廣頌,趙紹剛.基于個體適應值灰模型的交互式遺傳算法［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］.計算機工程,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

河南省基礎與前沿技術研究計劃基金資助項目(122300410295)。

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

2014-03-17

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