知識進化算法

摘 要:根據卡爾#8226;波普爾的知識進化理論，建立了知識進化算法的基本框架，詳細地闡述了該算法的原理和具體實施方案。知識進化算法主要由一個知識空間和多個群體空間組成，群體空間根據知識的指導通過選擇操作不斷地提出新的假說，并通過猜測操作和反駁操作與知識空間協同進化來不斷地提高真理度(即不斷地接近問題的最優解)。為了驗證方法的有效性，選取了來自其他文獻中的五個經典測試函數作為算法的測試對象，通過對其他文獻中的仿真實例進行計算和結果比較，證明了算法的可行性和有效性。

關鍵詞:進化計算; 知識進化算法; 知識進化論; 函數優化

中圖分類號:TP18; TP301.6文獻標志碼:A

文章編號:1001-3695(2009)09-3282-03

doi:10.3969/j.issn.1001-3695.2009.09.023

Knowledge evolution algorithm

MA Hui-min1，2， YE Chun-ming1， ZHANG Shuang1

(1.Business School， University of Shanghai for Science Technology， Shanghai 200093， China; 2.Business School， Shanghai Dianji University， Shanghai 200245， China)

Abstract:Based on evolutionary epistemology proposed by Popper， proposed the framework of knowledge evolution algorithm(KEA)and illustrated the detailed realization of the method. Knowledge evolution algorithm had a number of group space and one knowledge space. In accordance with the guidance of knowledge， the group spaces by selecting operation put forward the new hypothesis. The group spaced and knowledge space which connected with conjecture and refutation operation evolve into the truth cooperatively. Computed the example of other literatures. By comparison of the result， it can be found that this proposed algorithm illustrated its higher searching efficiency and better stability than the binary differential evolution and the binary particle swarm optimization algorithm of other literatures. Simulation results of the example demonstrate the effectiveness of this algorithm.

Key words:evolutionary computation; knowledge evolution algorithm; evolutionary epistemology; function optimization

以遺傳算法為代表的生物進化算法是建立在達爾文自然選擇學說的基礎上，是對生物進化過程的模擬，是人們對從自然演化過程中抽象出來的概念、原則和機制的類比應用，被廣泛用來解決復雜的計算問題。目前的研究工作大多仍集中在生物自然選擇層面上[1]。英國哲學家卡爾#8226;波普爾認為，“知識的增長是類似于達爾文所謂的自然選擇過程的結果，也就是對假說的自然選擇。任何時候，知識都是由那些為自身的存在的斗爭中已被證明具有適應性(或比較意義上的適應性)的假說組成，那些在競爭中被證明不適應的假說則被淘汰了”[2]。 卡爾#8226;波普爾把生物進化與科學發展結合起來，闡明了科學是如何合理進化的，這就是他的知識進化論[3]。

知識進化與生物進化一樣，也存在著群體與個體進化。個體進化中突變的累積效應最終導致和構成了群體進化的結果[4]。然而，世界進化的歷史顯示，“科學知識的增長遠比生物進化過程快得多，一個肯定性變異擴展開來需要200或更多的子代，對人類來說要數萬年，相反科學是上個世紀的產物”[5]。

知識進化算法是受知識進化論的啟發而提出的，目的是提出一種模擬知識進化機制的可以解決復雜問題的新方法。

1 知識進化算法的基本原理

1.1 知識進化算法的哲學基礎

知識是一個集合名詞，它表示人類全部認識結果的總和，而知識的進化和增長就是人類認識結果的進化和增長。科學知識僅僅是人類知識的最典型形式，而不是人類全部的知識。人類知識還包括許多其他形式的知識，如常識和經驗等。正因為如此，從知識進化的角度看，科學知識的進化和增長只不過是人類總知識進化和增長的一部分，它表示科學理論的進步和發展[6]。

卡爾#8226;波普爾提出了三個世界理論來形象地說明從普遍進化到知識世界進化的連續鏈條。從連續鏈條看，三個世界組成了先后相繼的歷史演化過程，即由世界1—世界2—世界3。最早存在的是純粹的無機自然界;在較高一級層次上出現了有機體;接下來是更高層次上的生命現象;再高一個層次是意識狀態即人類認識能力的突現;最后出現人類精神的產物，如科學理論、藝術作品等各種客觀知識，進化鏈條可以由圖1所示[6]。

無論是世界2的主觀認知活動，還是世界3的客觀知識發展，都遵循著共同的類似于生物世界的試錯法的基本規律。如果一種有機體特征不能適合環境，就必然被淘汰;而另一種特征會出現，直到形成相適合的穩定性特征。與此類似，主觀知識的進化也是一個試錯過程。由于客觀知識是主觀世界的產物，既然主觀知識世界遵循試錯法則，那么客觀知識必然也要遵循這一普遍的生物學法則[6，7]。

1.2 知識進化算法的基本框架

本文受卡爾#8226;波普爾的三個世界理論以及知識進化理論的啟發，根據知識進化的特點，提出了知識進化算法(knowledge evolution algorithm， KEA)模型，如圖2所示。知識進化算法主要由一個知識空間(卡爾#8226;波普爾的世界3)和N個群體空間(卡爾#8226;波普爾的世界2)組成。知識空間擁有社會知識;第n個群體空間中擁有In個認知的個體，每個認知個體分別擁有對認知問題(即各種優化問題)的假說和個體知識。群體空間(第2世界)中的認知個體根據個體對認知問題的知識，并通過選擇操作和猜測操作提出新的假說和新的社會知識備選個體;知識空間(第3世界)通過真理度計算函數來確定哪些知識被列入世界3的范圍，并同時通過反駁操作將社會知識傳遞給各群體空間。群體空間中的認知個體在原有知識的基礎上，通過對社會知識和群體經驗學習以及對本身個體經驗的不斷總結形成新的個體知識。以上的過程不斷循環往復，便完成了社會知識和個體知識等各種知識的不斷進化。

2 知識進化算法方案

2.1 知識進化算法的總體方案

1)假說和知識的編碼方案 進化算法的常用編碼方式有二進制編碼和實數編碼。在知識進化算法中，認知個體對認知問題(即優化問題)的假說采用二進制編碼方式，第n個群體空間中的第i個認知個體對認知問題的假說可以用一個J維向量表示:Xn，i=(xn，i，1，xn，i，2，…，xn，i，J)。其中:xn，i，j∈{0，1}(n=1，2，NA1AD，N;i=1，2，NA1AD，In;j=1，2，NA1AD，J)，每個向量Xn，i表示一個假說，而每一分向量xn，i，j表示該假說對認知問題的第j個子問題的解釋。認知個體對認知問題的知識采用實數編碼方式，第n個群體空間中的第i個認知個體對認知問題的知識可以用一個J維向量表示:Pn，i=(pn，i，1，pn，i，2，…，pn，i，J)。

2)選擇操作 每個認知個體根據該認知個體對認知問題的個體知識，通過選擇操作形成認知個體的新假說。選擇操作的目的是使那些對認知問題有較好適應值的假說存活下來，使那些對認知問題有較差適應值的假說被淘汰，達到優勝劣汰的目的。

3)猜測操作 經過進化，每個認知個體都不斷更新自己對認知問題的個體經驗。與此同時，每個群體對群體內的各個個體經驗進行總結，不斷更新對認知問題的群體經驗，并根據群體經驗形成新的群體假說，通過猜測操作將群體假說傳遞給知識空間進行驗證。

4)反駁操作 知識空間通過真理度計算函數對各群體空間提出的假說進行真理度計算，并形成社會知識，通過反駁操作傳遞給各群體空間供各認知個體學習。

5)認知個體對認知問題的知識積累過程 每個認知個體在進化過程中都擁有自身對認知問題的個體經驗，整個群體同時也擁有對認知問題的群體經驗，而整個社會也擁有對認知問題的社會知識。認知個體在對個體經驗不斷總結的同時，對社會知識和群體經驗進行不斷學習，不斷地積累個體對認知問題的知識，這是一個典型的個體知識進化過程。具體可以由式(1)表示。

新個體知識=c1×原個體知識+c2×個體經驗+c3×群體經驗+c4×社會知識(1)

其中:c1為個體知識進化參數，c2為個體經驗認知參數，c3為群體經驗認知參數，c4為社會知識認知參數。

6)知識進化算法的通用流程

知識進化算法的通用流程如圖3所示。

2.2 知識進化算法的具體步驟

知識進化算法的具體步驟如下:

a)初始化算法的參數。確定群體空間數N和群體空間的規模In，確定認知參數c1、c2、c3和c4，并令進化代數k=0。

b)認知個體知識的初始化。每個群體空間中認知個體知識由式(2)初始化為

pkn，i，j=0.5;n=1，2，NA1AD，N;i=1，2，NA1AD，In;j=1，2，NA1AD，J(2)

c)通過選擇操作形成個體假說。每個認知個體的新假說由式(3)計算。

xkn，i，j=1 if R(0，1)>pkn，i，j0 otherwisen=1，2，NA1AD，N;i=1，2，NA1AD，In;j=1，2，NA1AD，J(3)

其中R(0，1)表示產生[0，1]之間隨機數。

d)計算認知個體假說的適應值。每個群體空間中認知個體假說的適應值由式(4)計算:

fitness=f(Xkn，i)n=1，2，NA1AD，N;i=1，2，NA1ADIn(4)

e)通過猜測操作形成各群體假說。令PBkn，i=(pbkn，i，1，pbkn，i，2，…，pbkn，i，J)表示個體的經驗，令GBkn=(gbkn，1，gbkn，2，…，gbkn，J)表示群體的經驗(即群體假說)。如果k=0，則PB0n，i=X0n，i，否則PBkn，i可由式(5)計算。GBkn可由式(6)計算。檢查結束條件是否滿足，滿足則結束，否則繼續。

PBkn，i=PBk-1n，i if f(Xkn，i)>f(PBk-1n，i)Xkn，iotherwisen=1，2，NA1AD，N;i=1，2，NA1ADIn(5)

GBkn=min(PBkn，i)n=1，2，NA1AD，N(6)

f)反駁操作。知識空間通過真理度函數計算各群體假說的真理度，并形成社會知識，式(7)為真理度計算式。

zj=∑Nn=1gbkn，j/Nj=1，2，NA1AD，J(7)

其中Z=(z1，z2，…，zJ)為認知個體對認知問題的社會知識。

g)個體知識的進化。本文根據二進制編碼方案的特點，將式(1)的個體知識進化公式進行了改進，具體如式(8)所示。因此，群體空間中認知個體知識的更新通過式(8)和(9)來計算，式(9)使個體知識處于0和1之間。然后，令k=k+1，轉c)。

pk+1n，i，j=0.5+c1(pkn，i，j-0.5)+c2(0.5-pbkn，i，j)+c3(0.5-gbkn，j)+c4(0.5-zj)(8)

g(pk+1n，i，j)=1ifpk+1n，i，j≥1pk+1n，i，jif1>pk+1n，i，j>00ifpk+1n，i，j≤0(9)

3 仿真實驗

為了更好地說明算法的運行效果，本文用VB6.0為上文提到的算法編寫了程序，選取文獻[8]中仿真實驗的五個測試函數進行仿真，將仿真的結果與文獻[8]中算法的計算結果進行了對比。

a)Sphere函數:f1(x)=∑ni=1x2i

b)Rosenbrock函數:f2(x)=100(x21-x2)2+(1-x1)2

c)Schaffer’s F6函數:f3(x)=0.5+(sin2x21+x22-0.5)/1.0+0.001(x21+x22)2

d)Griewank函數:f4(x)=(1/4000)∑ni=1(xi-100)2-∏ni=1cos((xi-100)/i)+1

e)Rastrigin函數:f5(x)=∑ni=1(x2i-10cos(2πxi)+10)

本文的知識進化算法采用二進制編碼，編碼長度為20，每個函數獨立運行20次，認知參數c1=0.8，c2=0.05，c3=0.05和c4=0.095，測試函數的基本參數和知識進化算法的其他參數如表1所示。

表1 測試函數的基本參數及知識進化算法的參數設置方案

f1(x)f2(x)f3(x)f4(x)f5(x)

維數3223030

在五個函數中，Sphere函數和Rosenbrock函數為單峰函數。其中Rosenbrock函數是一個非凸、病態函數，它的全局最優點位于一個平滑、狹長的拋物線性峽谷內，由于函數僅為優化算法提供了少量信息，很難全局最小化求解，是一個經典的優化問題。Schaffer’s F6 函數、Griewank函數和Rastrigin 函數為多峰函數，Schaffer’s F6函數在距全局極小點大約3.14 范圍內的隆起部有一圈局部極小點，由于其強烈的振蕩性質以及它的全局最小點被局部極小點所包圍的特性，使得一般算法很難找到它的全局最優解。Rastrigin函數為極多峰函數，大約有n11個局部極小點。因此，五個測試函數被認為是很難優化的問題，通常被用來評價算法的效率。

為了具有可比性，本文采用與文獻[8]相同的評價指標:平均最優適應值(mean best fitness， MBF)、標準差(standard deviation， SD)。其中MBF、SD分別為算法獨立運行20次的平均最優值和標準差。MBF反映了在給定迭代次數下算法所能達到的精度;SD反映了算法的穩定性和魯棒性。表2給出了本文的知識進化算法和文獻[8]中二進制粒子群算法及二進制差異演化算法對測試函數求解結果的對比。

從表2可以看出，無論是單峰函數還是多峰函數，本文提出的知識進化算法在求解精度和穩定性方面均取得了比較好的優化效果，表明知識進化算法在函數優化方面取得了令人鼓舞的結果。知識進化算法同樣可以廣泛應用于組合優化問題，筆者已利用知識進化算法的框架和方案設計了背包問題、生產批量計劃問題、供應鏈協同計劃問題等NP難題的知識進化算法求解方案，均取得了令人鼓舞的結果。求解其他問題的知識進化算法將陸續成文。

4 結束語

本文將進化認識論的相關哲學思想和最優化理論聯系起來，以知識進化為背景，提出了一種知識進化算法(KEA)，詳細地闡述了該算法的原理和具體實施方案。為了驗證本文方法的有效性，選取了文獻[8]中的五個經典函數作為算法的測試對象，通過對測試函數進行計算和與文獻[8]中二進制差異進化算法、二進制粒子群算法的結果比較，證明了本文算法取得了較好的優化效果。

該算法在很多方面還需要進一步深入的研究，如從理論上證明知識進化算法的收斂性、算法的參數設置分析以及算法的魯棒性分析等將是今后研究工作的重點。

參考文獻:

[1]FOGEL D B. An introduction of simulated evolutionary optimization [J]. IEEE Trans on Neural Nerworks， 1994， 5(1): 3-14.

[2]朱祖平.知識進化與知識創新機理研究[J].研究與發展管理，2000，12(6):16-19.

[3]劉純青，楊莘元，張穎.知識進化策略[J].系統工程與電子技術，2007，29(6):1017-1020.

[4]林啟者，張際平.知識進化理論對教育技術研究的啟發[J].廣西教育學院學報，2006， 3(3):4-6.

[5]張超.文本下的知識進化[J].東華大學學報:社會科學版，2004，4(4):58-62.

[6]何云峰.從普遍進化到知識進化——關于進化認識論的研究[M].上海:上海教育出版社，2001.

[7]波普.客觀知識[M].上海:上海譯文出版社，1987.

[8]王志剛，郭廣寒，郝志峰.二進制差異進化算法及其應用[J].計算機工程與應用，2008，44(18):48-50.