基于信息維的協(xié)同進(jìn)化算法研究.pdf

1、協(xié)同進(jìn)化算法(CoevolutionaryAlgorithm，CEA)是借鑒生態(tài)學(xué)上多物種相互作用、彼此驅(qū)動(dòng)、協(xié)同進(jìn)化機(jī)理而建立的一組新型進(jìn)化算法。協(xié)同進(jìn)化算法擴(kuò)展了傳統(tǒng)進(jìn)化算法的應(yīng)用范圍，能有效地解決一些傳統(tǒng)進(jìn)化算法難以解決的復(fù)雜問(wèn)題。在人工智能的機(jī)器學(xué)習(xí)領(lǐng)域，有相當(dāng)一部分問(wèn)題無(wú)明確的目標(biāo)評(píng)價(jià)函數(shù)，候選解的性能需要通過(guò)測(cè)試進(jìn)行評(píng)價(jià)，比如分類(lèi)策略學(xué)習(xí)問(wèn)題、博弈策略學(xué)習(xí)問(wèn)題等。典型情況下，可能的測(cè)試樣本數(shù)目巨大，無(wú)法在完整測(cè)試集上進(jìn)行評(píng)價(jià)

2、，而選擇一個(gè)固定測(cè)試集又易于造成過(guò)適應(yīng)。協(xié)同進(jìn)化算法將候選解和測(cè)試樣本構(gòu)造成兩個(gè)競(jìng)爭(zhēng)關(guān)系的種群，讓它們一起進(jìn)化，個(gè)體適應(yīng)度通過(guò)與對(duì)方個(gè)體直接競(jìng)爭(zhēng)獲得，從原理上為解決該類(lèi)問(wèn)題開(kāi)辟了一條有效的途徑。
　　 但是，協(xié)同進(jìn)化算法的動(dòng)態(tài)性評(píng)價(jià)方式容易導(dǎo)致評(píng)價(jià)的不穩(wěn)定，以至在進(jìn)化中常常出現(xiàn)復(fù)雜的動(dòng)態(tài)性，如循環(huán)、特化等，致使進(jìn)化脫離預(yù)定的目標(biāo)，不能可靠地進(jìn)化。如何組織、設(shè)置這種動(dòng)態(tài)性評(píng)價(jià)才能確保協(xié)同進(jìn)化算法成為一個(gè)有效、可靠的搜索方法是算法研

3、究面臨的一個(gè)主要挑戰(zhàn)。
　　 研究顯示“基于測(cè)試”(test-based)問(wèn)題域內(nèi)隱含存在一組信息維，它們架構(gòu)了問(wèn)題域的評(píng)價(jià)空間。可將評(píng)價(jià)信息壓縮到一個(gè)小的維度集上，每一個(gè)維度可看作一個(gè)基本目標(biāo)，并按照進(jìn)化多目標(biāo)優(yōu)化的觀點(diǎn)，對(duì)候選解進(jìn)行評(píng)價(jià)。本文以此為研究基礎(chǔ)，提出了幾種針對(duì)“基于測(cè)試”問(wèn)題的可靠協(xié)同進(jìn)化算法設(shè)計(jì)方案。
　　 (1)提出了一個(gè)基于信息維識(shí)別的協(xié)同進(jìn)化存檔方案，改善了目前可靠存檔算法存檔量過(guò)大，執(zhí)行效率低的

4、現(xiàn)狀。在協(xié)同進(jìn)化期間，借助動(dòng)態(tài)維度識(shí)別，僅選擇代表各維度最新進(jìn)展的測(cè)試個(gè)體進(jìn)檔保留，并以它們作為評(píng)價(jià)基準(zhǔn)，選擇保留優(yōu)秀候選解，以此阻止進(jìn)化倒退，輔助協(xié)同進(jìn)化可靠有效地推進(jìn)。本方案在確?？煽康剡M(jìn)化的同時(shí)最小化存檔量。其中，維度識(shí)別是本方案的實(shí)施關(guān)鍵。針對(duì)問(wèn)題類(lèi)型的難易，提供了兩種維度識(shí)別方法和配套實(shí)施策略：針對(duì)COMPARE-ON-ONE類(lèi)問(wèn)題，其特征是域內(nèi)每一個(gè)測(cè)試個(gè)體僅能提供一個(gè)維度上的評(píng)價(jià)信息，構(gòu)建了算法EPCA；針對(duì)一般二值收益問(wèn)

5、題，構(gòu)建了算法DI-CA。兩算法均通過(guò)實(shí)驗(yàn)進(jìn)行了驗(yàn)證，結(jié)果顯示較以前的存檔算法均有更好的性能和效率。
　　 (2)提出了一個(gè)在線維度抽取方法，并在此基礎(chǔ)上構(gòu)建了一個(gè)帶有維度抽取的協(xié)同進(jìn)化算法PCA-DE。在線維度抽取方法借助個(gè)體間的特征收益關(guān)系來(lái)實(shí)施維度抽取，再根據(jù)維度固有的順序性對(duì)抽取的維度進(jìn)行修正，使抽取到的維度具有更高的準(zhǔn)確性。在PCA-DE算法的執(zhí)行過(guò)程中，同步抽取問(wèn)題域的維度系統(tǒng)，并以此對(duì)個(gè)體實(shí)施準(zhǔn)確評(píng)價(jià)，保留最優(yōu)個(gè)體

6、，引導(dǎo)進(jìn)化單調(diào)有效地進(jìn)展。實(shí)驗(yàn)證實(shí)了PCA-DE的可行性，并顯示出比同類(lèi)算法更高的性能和維度抽取準(zhǔn)確率。
　　 (3)提出了一個(gè)非確定性雙向維度抽取方案，降低了維度抽取條件，并在此基礎(chǔ)上構(gòu)建了一個(gè)基于雙向維度抽取的協(xié)同進(jìn)化存檔算法CA-BDE。在進(jìn)化過(guò)程中，算法借助測(cè)試端的維度抽取，選擇具有維度代表特征的測(cè)試個(gè)體存檔保留，用于為后續(xù)進(jìn)化提供完整評(píng)價(jià)支持；同時(shí)算法借助于從對(duì)偶端進(jìn)行的候選維度抽取，選擇具有維度代表特征的高性能候選個(gè)