交互式遺傳算法入門

1、1.3 交互式遺傳算法交互式遺傳算法也可稱為人機交互進化優(yōu)化算法，即在進化計算過程中，根據(jù)需要，人通過與計算機的交互，實現(xiàn)對進化過程的干預和引導，以解決傳統(tǒng)遺傳算法無法解決的如式(1.1)所示的一類隱式性能指標優(yōu)化問題。由于人的參與，使得遺傳算法得到了很好的擴展，不再簡單依賴于適應度函數(shù)等，從而大大拓寬了傳統(tǒng)遺傳算法的應用領域。若無特殊說明，后續(xù)討論均針對式(1.1)所示的問題進行研究。1.3.1 交互式遺傳算法的起源、發(fā)展、原理1986年，Dawkins最早提出了交互式演化算法的思想，并用于生物圖形的生成1。20世紀90年代初，日本學者Takagi在Dawkins算法思想的基礎上，對交互式演

2、化算法從應用和理論研究等方面，開展了大量卓有成效的工作24，并逐漸引起了廣大學者對交互式進化優(yōu)化算法的關注。交互式進化優(yōu)化算法主要有狹義和廣義兩種定義24。其中，狹義定義認為“交互式進化優(yōu)化算法是一種以人的主觀評價作為進化個體適應值的進化優(yōu)化方法”。該定義把人的主觀評價作為進化個體適應度賦值的依據(jù);廣義定義認為“交互式進化優(yōu)化算法是一種有人機交互過程的進化優(yōu)化方法，這種人機交互過程不僅僅是對個體進行適應度賦值，還包括其他更多的人對進化過程的干預，如優(yōu)勢個體的選擇、交叉對的選擇等”25。我們這里僅討論狹義定義模式下的交互式進化優(yōu)化算法，即交互式遺傳算法，該算法形象表述如圖1.2所示，流程如圖1.

3、3所示。圖1.2 交互式遺傳算法示意圖 圖1.3 交互式遺傳算法流程圖從上述圖示中可知，與傳統(tǒng)遺傳算法相比，交互式遺傳算法可分割為兩個模塊:用戶評價模塊和種群進化模塊。其中，用戶評價模塊即為傳統(tǒng)遺傳算法中適應值計算模塊，主要通過人機交互，由用戶給出進化個體適應值。具體地說，就是計算機將進化個體的表現(xiàn)型呈現(xiàn)給用戶，如服裝、工程設計草案、一段樂曲等，然后用戶根據(jù)個人認知和偏好，通過交互界面以打分的形式給出進化個體適應值，代替?zhèn)鹘y(tǒng)遺傳算法中基于顯式適應度函數(shù)的適應值計算;種群進化模塊由計算機完成傳統(tǒng)進化過程，包括編碼、解碼、種群初始化、基于用戶賦予的進化個體適應值的選擇，以及相應的進化算子，如遺傳算

4、法中的交又（重組）、變異算子。在每個進化代中，上述兩個模塊進行交互，并基于交互結果，實施進化操作，重復該過程，直至算法滿足設定的終止條件，如找到滿意解或達到設定的進化代數(shù)等。與傳統(tǒng)遺傳算法相比，交互式遺傳算法在對進化個體的評價中融合了人的偏好、直覺、情感、心理特征等主觀因素，使得該算法在依賴現(xiàn)有遺傳算法的基礎上，又有其白身的特點，主要體現(xiàn)在如下三個方面。個體適應值具有不確定性 交互式遺傳算法建立在被優(yōu)化變量空間向人的心理空間映射的基礎上,人直接評價由個體基因型決定的個體表現(xiàn)型,從而為進化個體賦予適應值。在進化過程中,評價者會對評價對象逐漸獲得更多的知識.,使得其認知不斷發(fā)生變化。由于用戶對個體

5、的評價建立在用戶對被評價對象認知的基礎上,那么認知的不確定性和漸進性,將使得進化個體適應值具有不確定性。個體評價過程具有難持久性 交互式遺傳算法面向一類難以用精確定義的函數(shù)描述的優(yōu)化問題，而直接由人評價優(yōu)化方案的優(yōu)劣。與傳統(tǒng)遺傳算法中計算機不知疲倦地計算進化個體適應值的過程相比，頻繁的人機交互和大量的評價需求，將使得評價者極易疲労，用戶評價疲勞將導致評價不可信，甚至不可用，使得算法不得不終止。在交互式遺傳算法中，一般人參與評價的進化代數(shù)不多于30，顯然，與傳統(tǒng)選傳算法相比，該進化過程較短暫，難以持久，且評價個體總數(shù)量有限。優(yōu)化結果具有非唯一性 交互式遺傳算法優(yōu)化結果的非唯一性表現(xiàn)在如下兩個方面

6、。一是用戶評價的偏好導致優(yōu)化結果具有一定個性。因為不同用戶在對進化個體評價時基于其知識背景、文化趨向及個人喜好等諸多因素，這些因素最終表現(xiàn)為用戶對個體的偏好。二是由于人在心理空間上可以區(qū)分的系統(tǒng)輸出有一定限制，即很難區(qū)分兩個表現(xiàn)型差異細微的個體，因此交互式遺傳算法的優(yōu)化解是一個區(qū)域優(yōu)化區(qū)域，而不像傳統(tǒng)遺傳算法那樣是一個或多個離散點。但對圖像生成、樂曲創(chuàng)作、數(shù)據(jù)挖掘及其他復雜問題的優(yōu)化來講已經(jīng)能夠滿足要求。綜上所述，由于人的參與，使得交互式遺傳算法相對于傳統(tǒng)遺傳算法具有難以比擬的復雜性和不確定性。下面，我們將從應用和理論方法研究上，闡述近年來交互式遺傳算法的研究現(xiàn)狀，以發(fā)現(xiàn)其存在的不足，進而確定

7、我們的研究內(nèi)容，并給出解決方法。1.3.2 交互式遺傳算法的研究現(xiàn)狀IEEE Transactionson Evolutionary Computation等關于進化計算的國際學術期刊大量報道了交互式遺傳算法的研究成果。Gneticand Evolutionary Computation Conference（遺傳與進化計算會議）從2002年開始開設關于交互式進化計算的專題研討會。而關于交互式遺傳算法在各領域的應用成果也不斷涌現(xiàn)，如Parmee等將交互式遺傳算法與工業(yè)設計相結合，提出交互式優(yōu)化設計系統(tǒng)，并與多目標優(yōu)化、Agent決策支持等方法結合，廣泛應用于橋梁設計、工業(yè)產(chǎn)品設計、概念軟件設計

8、等26,27，進一步豐富了交互式遺傳算法的理論與應用成果。交互式遺傳算法是應實際優(yōu)化問題需要而發(fā)展起來的一種進化優(yōu)化方法，因此它自誕生之日起就具有鮮明的應用背景和廣闊的應用前景。交互式遺傳算法的應用主要集中在藝術、工程設計和教育等領域，下面將分別介紹交互式遺傳算法在各領域的應用情況。圖像處理與檢索 交互式遺傳算法廣泛應用于圖像處理和檢索中。最早的應用是Dawkins的生物圖形，他用L系統(tǒng)表示生物圖形的遞歸過程，通過主觀選擇L系統(tǒng)的輸出和基因變異繪制出類似生物的二維計算機圖形1。Sims在遺傳規(guī)劃中由人評價數(shù)學方程生成的計算機圖形，并不斷進化該數(shù)學方程，從而使計算機圖形更加美觀28。Takeka

9、ta用交互式遺傳算法調(diào)整3D設備中觸覺感知器的參數(shù)，無需專業(yè)技術知識就可使觸覺設備的參數(shù)滿足使用者的要求29。Li等把交互式遺傳算法用于圖像色彩的轉(zhuǎn)換，轉(zhuǎn)換后的圖像色彩能夠滿足用戶情感和心理需要30。Rodri9uez等將交互式遺傳算法應用于建筑物外觀顏色的設計中，考慮用戶評價疲勞，利用交互式遺傳算法和神經(jīng)網(wǎng)絡相結合，構造用戶對顏色的偏好模型31。Cho等把交互式遺傳算法應用于基于內(nèi)容的圖像檢索中，將人的直覺和情感與檢索內(nèi)容融合，搜索出用戶滿意的圖片32。Miguel等將基于內(nèi)容的圖像檢索與用戶的相關反饋相結合，在混合交互式遺傳算法的優(yōu)化框架下，找到用戶滿意度高的圖像33。語言和聲音處理 Fo

10、rmiga等把交互式遺傳算法用于文本到語言合成系統(tǒng)的單元權重調(diào)節(jié)中34。Sato等利用交互式遺傳算法合成語音，通過進化影響語音的韻律參量改變音色，反映出平和、憤怒、快樂等情感35。Rho等基于用戶相關反饋原理，設計音樂信息檢索，給出根據(jù)用戶滿意程度進行排序的結果36。Takagi等將交互式遺傳算法用于助聽器的調(diào)整，根據(jù)用戶對聲音效果的評價在線調(diào)整助聽器的各參數(shù)，直到用戶滿意為止37。另外，交互式遺傳算法還用于音樂旋律和節(jié)奏的生成，創(chuàng)作個性化樂曲38。工業(yè)產(chǎn)品和藝術創(chuàng)作設計 任何設計過程都需要設計者的廣泛參與，包括確定設計主題、評判設計產(chǎn)品或作品是否滿足需求。在工業(yè)設計中，李圣清等通過交互式遺傳

11、算法優(yōu)化電路板中元器件的布局，使整體結構既美觀又不影響電路的功能39。Kamalian等把交互式遺傳算法用于微電機系統(tǒng)的設計，通過人評價微電機的結構特性設計其參數(shù)40。Ono等將交互式遺傳算法和非交互式遺傳算法相結合，進行二維編碼條的裝飾性設計41。Meghna等提出基于實例的少用戶疲勞交互式遺傳算法，并將其應用于地下水監(jiān)控系統(tǒng)的設計42。Byren等將交互式遺傳算法直接應用于產(chǎn)品設計的友好交互界面和交互工具的設計中，使得用戶可以直接通過該界面與滿意方案的編碼進行交互，可有效減輕其評價負擔43。Kowa11w等則研究如何在交互式遺傳算法的框架下，更好地激發(fā)用戶的創(chuàng)造性，以進行富有新意的設計44

12、。教育和娛樂 交互式遺傳算法可以給使用者提供寫作線索或靈感，還能夠給學習者提供參考。交互式遺傳算法已經(jīng)成功地應用于3D計算機圖形的輔助教育，使用者通過人機交互方式可以學習3D圖形的繪制方法，掌握各種計算機繪圖技巧45。交互式遺傳算法可以激發(fā)使用者的創(chuàng)新思維，Kuriyama等開發(fā)了供少兒使用的寫作支持系統(tǒng)46。此外，Goldberg等開發(fā)了不確定環(huán)境下的分布式創(chuàng)新與可擴展合作(distributed innovation and scalable co1laboration in uncertain set-things，DISCUS)產(chǎn)品設計系統(tǒng)，利用交互式遺傳算法的優(yōu)化結果不斷激發(fā)人的創(chuàng)造

13、思維47。機器人控制 1992年，Lewis等將交互式遺傳算法用于控制一個六腿機器昆蟲48這是交互式遺傳算法第一次用于控制工程。Suga等用交互式遺傳算法訓練機器人的表情和溝通能力，使機器人個性化并能夠快速適應周圍環(huán)境49。Moshaiov等用交互式遺傳算法進行機器人路徑規(guī)劃，系統(tǒng)采用兩層模型，底層用計算機直接計算路徑長度，上層通過人的評價提供用戶對機器人經(jīng)過地點的偏好信息，從而實現(xiàn)個性化的路徑規(guī)劃50。交互式遺傳算法在上述各領域的成功應用，彰顯了算法的勃勃生機。另外，在應用過程中，人們發(fā)現(xiàn)交互式遺傳算法核心問題的有效解決尤為必要，如個體適應值評價的不確定性、用戶疲勞導致的評價過程的難持久性等

14、。因此，進一步研究交互式遺傳算法理論與關鍵技術，有效解決其核心問題，從而進一步擴大交互式遺傳算法的應用領域，具有重要的理論意義和實際應用價值。根據(jù)交互式遺傳算法的特性，其理論方法研究主要可分為兩類：一是研究進化個體適應值評價的不確定性；二是減輕用戶評價疲勞，改進算法搜索性能的研究。交互式遺傳算法中用戶對進化個體的評價具有認知不確定性和隨機不確定性，對這些不確定性的研究，可分為如下兩類。將不確定性視為噪聲信號 這些不確定性對進化個體適應值而言可視為噪聲信號:_對于交互式遺傳算法是個極大的擾動,甚至可能導致算法無法在用戶疲勞時找到、術意解24 。 由于人的評價具有強烈的主觀意識,因此在評價過程中難

15、以避免目標偏好的漂移甚至改變。為了盡可能保持用戶偏好一致,Sastry等基于用戶評價獲得各個體偏序,程據(jù)偏序值基于多目標非占優(yōu)思想,給出個體在種群中的全序,再基于支持向量機獲得適應度函數(shù)的代理模型5',52。該算法考慮了維持用戶評價標準的一致性問題,從而在收斂速度、搜索性能等各方面得到極大改進。但算法只是被動地維持評價備好,沒有考慮其他干擾信號,如日標的不明確性對用戶偏好的影響、評價疲勞對偏好的影響等。 Breukelaar 等給出了交互優(yōu)化框架下多種優(yōu)化策略的比較，基于色彩選擇優(yōu)化實例，說明了交互式遺傳算法中存在的噪聲問題，指出選擇過程中用戶評價偏好及疲労造成的噪聲對算法性能有極大的

16、破壞性，因此在交互式遺傳算法中，應考慮建立用戶評價的噪聲模型、去噪策略和用戶監(jiān)視策略等，并根據(jù)優(yōu)化結果說明噪聲模型與時問，以及用戶心理空間和實際優(yōu)化目標問的距離有關，同時說明用戶在評價過程中若采取一些策略也會對算法性能有影響53。但其僅僅根據(jù)某個優(yōu)化實例，給出定性結論，沒有給出解決方法等。采用不確定數(shù)表示不確定性 除了上述處理進化個體評價不確定性的方法外，改變傳統(tǒng)的采用精確數(shù)表示進化個體適應值的方法也是研究方向之一。實際上，用戶對進化個體的認知具有模糊性和漸進性，再加上評價過程中多種因素的影響，使得評價結果具有隨機性。這樣一來，用具體數(shù)值表示進化個體適應值就不能很好地反映用戶對評價對象認知的規(guī)

17、律，而強行要求用戶給出具體的適應值會加速人評價的疲勞。這正是本書即將討論的第一部分內(nèi)容，將在第24章對上述策略進行詳細闡述。其次，關于用戶評價疲勞問題。由于交互式遺傳算法需要人參與進化過程并給出進化個體適應值，與計算機計算相比，人評價具有易疲勞性，使得交互式遺傳算法一般只能采用小的種群規(guī)模和少的進化代數(shù)，從而影響了算法的捜索性能。因此，減輕用戶評價疲勞、改進算法性能一直是交互式遺傳算法理論方法研究的重點和熱點24，目前國內(nèi)外的研究主要包括如下三個方面?；诖砟Ｐ偷倪m應值估計 利用進化個體適應值的估計值代替人的評價，.減少人評價進化個體的數(shù)量，從而減輕人的疲勞。Biles和周勇等采用人工神經(jīng)網(wǎng)

18、絡學習人的智能評價，并在適當時機用神經(jīng)網(wǎng)絡估計進化個體的適應值，減少人對進化個體評價的次數(shù)54，55。Sastry等在對用戶評價進行排序的基礎上，利用支持向量機構造用戶認知的代理模型，并在后續(xù)進化中應用其實現(xiàn)交互式遺傳算法的大種群規(guī)模進化51。Rodriguez在建筑圖外觀顏色設計系統(tǒng)中，利用神經(jīng)網(wǎng)絡構建適應度模型，以擬合用戶認知，從而減輕用戶疲勞31。加快算法收斂 通過加快算法收斂以降低進化代數(shù)來減輕人的疲勞。王上飛等采用支持向量機重構父代種群的個體，以擴大優(yōu)良父代個體的范圍，從而加快算法收斂，減輕人的疲勞56。胡靜等將粗糙集理論應用于進化過程中的信息提取，以提高算法的收斂速度57。蔣姍姍等

19、通過對前幾代進化種群遺傳操作的結果進行歸納計算，得到人的特異性偏好，并以此指導選擇、交叉和變異等進化操作，從而加快算法的收斂速度58。增強算法局部搜索 通過縮小搜索區(qū)域提高算法的局部搜索能力。鞏敦衛(wèi)等在進化種群滿足一定條件時將搜索區(qū)域縮小，并在縮小后的區(qū)域上重新生成進化種群，以提高算法的局部搜索能力59。郝國生等將搜索區(qū)域劃分為滿意域、禁忌域和未知域，通過將求同算子和求異算子作用于進化個體，從而進化上述區(qū)域，最終使得滿意域不斷減小，從而提高算法的局部搜索能力60。綜上所述，我們可以看出，在短短的二十年時間里，雖然交互式遺傳算法的應用和理論方法研究均取得了長足進展，但仍存在大量問題需要進一步解決

20、。1.3.3 交互式遺傳算法存在的不足交互式遺傳算法的已有研究尚存在如下四點不足。1)對交互式遺傳算法評價的不確定性研究不夠到日前為止，已有交互式遺傳算法解決隱式性能指標優(yōu)化問題時，用戶給出的進化個體適應值均為具體數(shù)值(連續(xù)或者離散數(shù))，這不符合人的認知規(guī)律，不能有效處理交互式遺傳算法中存在的模糊、隨機等不確定性信息。2)對交互式遺傳算法用戶認知模型的構建和應用研究不夠為了解決用戶疲勞問題，常常采用構造用戶認知代理模型的方法，該方法首先獲取一定量的用戶對進化個體的評價知識，再利用機器學習的方法對該認知知識建模，最后將該模型視為個體適應度函數(shù)，利用其估計進化個體適應值，代替用戶對部分或者全部進化個體進行評價，顯然，該過程本質(zhì)是一個知識獲取和機器學習的過程。在已有研究成果中，研究重點均在于利用若干進化過程中的數(shù)據(jù)采用監(jiān)督學習機制，構建認知模型，沒有考慮如何提取知識，以及采用哪類機器學習方法學習已獲得的知識更有效等問題。3)在考慮評價不確定性的情況下，對減輕用戶疲勞的方法研究不夠如前所述，利用區(qū)間數(shù)表示進化個體適應值后，用戶仍需確定兩個區(qū)間端點，大量的人機交互將極易導致用戶疲勞。同樣的，如果采用其他不確定數(shù)表示進化個體適應值，仍需考慮減輕用戶疲勞的策略。若仍考慮采用構建認知代理模型的策略，則與傳統(tǒng)的精確數(shù)模型將有較大的差別，新模型如何實現(xiàn)?這些目前都還處于研究的起始階段