基于云理論的進化計算模型

1、基于云理論的進化計算模型論文標題：基于云模型的進化算法論文作者:張光衛(wèi)：何銳： 劉禹北京航空航天大學計算機學院，北京，100083北京航空航天大學計算機學院，北京, 100083北京航空航天大學計算機學院，北京，100083中國電子工程系統(tǒng)研究所，北京， 100040中國電子工程系統(tǒng)研究所，北京，100040李德毅：陳桂生中文摘要：基于云模型在非規(guī)范知識的定性、定量表示,及其相互轉換過程中的優(yōu)良特征,結合進 化計算的基本思想,提出一種基于云模型的進化算法.該算法利用云模型對物種的遺傳變異 進化統(tǒng)一建模，能夠自適應控制遺傳變異的程度和搜索空間的范圍,從而可以快速收斂到 最優(yōu)解.較好地避免了傳統(tǒng)遺

2、傳算法易陷入局部最優(yōu)解和選擇壓力過大造成的早熟收斂等 問題.仿真結果表明該算法具有精度高、收斂速度快等優(yōu)點.云模型和進化計算思想的有效 結合一方面拓寬了云模型的應用領域，也為進化計算的研究進行了新的探索和嘗試.關鍵字：云模型；進化計算，數值優(yōu)化，遺傳算法，數值優(yōu)化，人工智能-1 -基r-云模型的進化算法*張光衛(wèi)，何銳,劉禹，李德毅，陳桂生（1北京航空航天大學計算機學院北京1000832中國電子工程系統(tǒng)研究所北京 100840）111摘要：基r云模型在非規(guī)范知識的定性、定量表示,及其相互轉換過程中的優(yōu)良特征,結合進 化計算的基本思想,提出一種基于云模型的進化算法.該算法利用云模型對物種的遺傳變異

3、 進化統(tǒng)一建模，能夠自適應控制遺傳變異的程度和搜索空間的范圍,從而可以快速收斂到 最優(yōu)解.較好地避免了傳統(tǒng)遺傳算法易陷入局部最優(yōu)解和選擇壓力過大造成的早熟收斂等 問題.仿真結果表明該算法具有精度高、收斂速度快等優(yōu)點.云模型和進化計算思想的有效 結合一方面拓寬了云模型的應用領域,也為進化計算的研究進行了新的探索和嘗試.關鍵 詞：云模型;進化計算;遺傳算法;數值優(yōu)化，人工智能引言遺傳算法(GA) 16是智能計算的重要分支.問題解按照一定編碼方案被表示成遺傳空 間的串結構個體,用適應度函數進行評價以選擇出優(yōu)秀個體,通過交換和變異操作產生新一 代更適應環(huán)境的種群.系統(tǒng)初始化為一組隨機解,經過逐代演化，

4、收斂到一個最適應環(huán)境的 串上,求得問題的最優(yōu)解.7-10云模型是李德毅院士提出的一種定性知識描述和定性概念與其定量數值表示之間的不 確定性轉換模型，已經在智能控制、模糊評測等多個領域得到應用.正態(tài)云模型是最重要的 一種云模型，由于其具有良好的數學性質，可以表示白然科學、社會科學中大量的不確定現象.云模型在知識表達時具有不確定中帶有確定性、穩(wěn)定之中乂有變化的特點,體現了白 然界物種進化的基本原理.對于云模型C(Ex, En, He), Ex可以代表父代個體遺傳的優(yōu)良特征, 是子代對父代的繼承，En和He可以表示繼承過程的不確定性和模糊性,表現了物種進化過 程中的變異特征.用正向云算子可以完成概念

5、空間到數值空間的轉換,在三個參數的控制 下產生子代種群,完成遺傳操作.一方面這種轉換是確定的和精確的，因為數值空間的每一 個云滴都是定性概念的一次量化實現,都在一定程度上是該定性概念的代表；另一方面,這 種轉換乂是隨機的和模糊的,每一次變換得到不同的云滴集合,而且同一定性概念可用云滴 集合中的任何一個代表,不同的云滴代表該概念的確定程度不同.基r云模型的優(yōu)良特性，結合進化計算的基本原理本文提出一種基于云模型的進化算 法,該算法不但比傳統(tǒng)遺傳算法精度高,而且能夠很好地避免遺傳算法易陷入局部最優(yōu)解和 選擇壓力過大造成的早熟收斂等問題.本文組織如下：首先對云模型進行簡單介紹;然后重點給出了 CBEA

6、的思想和詳細算法 流程;仿真實驗部分對本文提出的算法進行測試和對比分析;最后總結全文并給出下一步的 研究方向.1云模型簡介定義1. 1云和云滴設U是一個用數值表示的定量論域,C是U上的定性概念,若定量值 x?U是定性概念Cx?(x),則x在論的一次隨機實現,x對C的確定度？(x)?0, 1是有穩(wěn)定傾向的隨機 數:？:U?0, 1 ?x?U7域U上的分布稱為云(Cloud),記為云C(X).每一個x稱為一個云滴.如果概念對應的 論域是n維空間,那么可以拓廣至n維云.云模型所表達概念的整體特性可以用云的數字 特征來反映，云用期望 Ex (Expected value )，端 En (Entropy

7、),超燧 He (Hyper entropy)這 3個數字特征來整體表征一個概念,多維云模型的整體特征可由多組數字特征表示.期望Ex 是云滴在論域空間分布的期望,是最能夠代表定性概念的點,或者說是這個概念量化的最典 型樣本;燔En代表定性概念的可度量粒度，炳越大通常概念越宏觀,也是定性概念不確定 性的度量，由概念的隨機性和模糊性共同決定.一方面En是定性概念隨機性的度量,反映了 能夠代表這個定性概念的云滴的離散程度；另一方面乂是定*國家自然科學基金(60496323, 60375016),現代設計大型應用軟件的共性基礎973計 劃(2021CB719401)作者簡介:張光衛(wèi)(1970-)，男，

8、山東濟南人,博士生，研究方向為人工智能，電 話 E-mail:ezhang263. net;李德毅(1944 ),男，江蘇泰縣人，博士生導師， 中國工程院院士,主要研究領域為人工智能,指揮自動化.-1 -性概念亦此亦彼性的度量，反映了在論域空間可被概念接受的云滴的取值范圍;超嫡 He (Hyper entropy)是燃的不確定性度量，即燃的嫌，由燃的隨機性和模糊性共同決定.用三 個數字特征表示的定性概念的整體特征記做C(Ex, En, He).定義1. 2 一維正態(tài)云算子ArForward(C(Ex, En, He)是一個把定性概念的整體特征變 換為定量表示的映射？:

9、C?,滿足以下條件：(l)?ti |Norm(En,He)的一次實現 i=l. N)(2)X? xi xi 為 Norm (Ex, ti)的一次實現 ti?, i=l. N22(3)?=(xi, yi) xi?X, ti?, yi=e_(xi-Ex)/(2ti)其中Norm(?, ?)為期望為？方差為？的正態(tài)隨機變量,N為云滴的個數利用正態(tài)云算子,就可以把定性概念C(Ex, En, He)變換為數值表示的云滴集合,實現了 概念空間到數值空間的轉換.一維正態(tài)云算子可以拓廣至n維正態(tài)云算子.2基于云模型的進化算法(CBEA)通過正向云算子根據三個數字特征產生云滴的過程能夠刻畫遺傳和變異的思想，以一

10、 維正態(tài)云模型C(0, En, He)為例，它表達的概念為“坐標軸原點附近”，以不同的嫌和超燧 可以把這個定性概念轉化為定量表示,如圖分別做出通過正向云算子得到的500個云滴的 圖形.圖形上的每個云滴可以理解為以0 (期望)為種子個體，以不同的嫡和超端得到的后 代個體,云滴形成的每個云相當于一個種群,可以看到四個種群的在覆蓋范圍和離散程度的 明顯差異,即燃越大個體的覆蓋范圍越大,超嫡越大種群中的個體越離散.C(0, 0. 5, 0. 1) 10. 80. 60. 40. 20-210. 80. 60. 40. 20-2-1012-10C(0, 0. 5, 0. 2) 10. 80. 60. 4

11、0. 20-4-20241210. 80. 60. 40. 20-4-20C (0, 1, 0. 2) 24C (0, 1, 0. 1)圖1用云表達概念“坐標軸原點附近”可見期望體現了遺傳的穩(wěn)定性，嫡體現了變異的范圍,可以表示搜索的廣度,超燧體現 了進化的穩(wěn)定程度,可以表示求精的粒度.根據人類搜索的經驗，“當前優(yōu)秀個體周圍往往 存在更加優(yōu)秀的個體”，制定下面的搜索過程：首先，求出優(yōu)秀個體,對一個進化代所有的 個體(云滴)根據被優(yōu)化的函數進行適應度計算(fitness value),根據適應度選擇得到 前m個最適應的優(yōu)秀個體,稱為優(yōu)秀個體向量；其次，以優(yōu)秀個體為母體繁殖下一代個體， 即分別以m個

12、個體為種子產生一定數量的云滴作為下一代個體，給定規(guī)則使得越優(yōu)秀的種 子產生的下一代個體數量越多，這樣得到新一代的個體中存在更加優(yōu)秀的個體的可能性較 大,反復疊代便可逐步尋優(yōu)；另外,根據歷史進化代的情況可以對下一個進化代燧和超燃的 值進行自適應控制(放大或縮小)，以控制搜索的范圍和求精的粒度，這個控制過程一方面 要防止算法陷入局部最優(yōu)和早熟收斂，另一方面還要滿足在可能存在最優(yōu)解的范圍內迅速 求精,當然這兩個方面是矛盾的，需要制定合適的控制策略.在這個過程中,遺傳和變異是統(tǒng)一在一起的，都融合在新個體的產生過程中，因為由正 向云算子產生的子代個體(云滴)都會聚集在母體(云期望)周圍，充分體現了 “龍

13、生龍, 鳳生鳳”的遺傳特征，同時這也是一個充滿不確定性的過程,是隨機的和模糊的,每一次變 換得到不同的云滴集合,體現了 “一母生九子九子各不同”的變異-2 -特征.當算法在若干進化代都不能產生新的優(yōu)于歷史個體的最優(yōu)個體時,就要考慮突變 操作,生物學認突變是能夠影響生物遺傳性狀的變異,但它并不經常發(fā)生,本算法中最深度 的突變操作是系統(tǒng)重新進行初始化.以此上面的思想為基礎本文提出一種新穎的演化算法-CBEA (Cloud Based Eevolutionary Algorithm).類似大多數演化計算技術遵循的過程,CBEA的計算過程為：1 .系統(tǒng)初始化為一組隨機解，即隨機初始化群落中個體的值.2

14、 .計算所有個體的適應度,并選擇出適應度最好的前m個最優(yōu)秀個體,形成優(yōu)秀個體向 量.3.前m個個體分別繁殖一個種群.4 .如果達到演化代數則算法停止,最優(yōu)秀的個體即為最優(yōu)解,否則轉步驟2.13, 14CBEA與粒子群算法(Particle Swarm Optimization, PSO)和遺傳算法有很多共同之處， 都是基于疊代的優(yōu)化過程,都隨機初始化種群,而且都使用適應值來評價系統(tǒng),進而根據適 應值來進行一定的隨機搜索，它們都不能保證一定能找到最優(yōu)解.CBEA與遺傳算法的不同之處在于,雖然也是通過疊代搜尋最優(yōu)值,但沒有遺傳算法的二 進制編碼工作，也沒有相應的交叉(crossover)、變異(m

15、utation)等操作，而是通過正向云 算子完成新一代種群的產生，通過燧、超燃控制產生子代種群的位置、范圍(搜索的范圍) 以及子代種群集聚程度(求精的粒度)，算法的實現也較遺傳算法簡單.CBEA和PSO都采用實數編碼,都沒有相應的交叉、變異操作,PSO根據粒子的速度來決 定搜索,粒子們追隨當前的最優(yōu)粒子在當前解空間中搜索,而CBEA在各個進化代是個體不 斷產生和被淘汰的過程，既體現了進化論的思想,也體現了人類搜索的特點.假設參加疊代尋優(yōu)的個體總數為n,稱為一個群落C,群落中的個體被分成m個種群,m 也稱為群落的豐富度.群落和種群的關系為C?Pi,其中Pi表示第i個種群，各個種群包括 的個體的數

16、目可以不同，個體被編碼為一個ki?lk元組,xij表示第i個種群的第j個個體的第k個分量，由于個體能且只能屬于一 個種群,所以n=jl+j2+-+jm ,種群是m個體的集合,表示為：12kl2kl2kPl ? (xll, xll,. , xll) , (xl2, xl2,., xl2) (xl jl, xljlxljl) P2 ? (xl21,x221,. ., xk21) , (xl22,x222xk22),., (xl2j2, x22j2,., xk2j2) Pm ? (xlml, x2ml,. ., xkml) , (xlm2, x2m2,xkm2) ,. . ., (xlmjm, x2

17、mjm>., xkmjm) 按照群落中種群的規(guī)模對種群的地位進行劃分,分為建群種、優(yōu)勢種和劣勢種,其中優(yōu) 勢種是擁有較多個體的種群,建群種為優(yōu)勢種中的最優(yōu)者.一個群落中建群種只有一個,是 群落中的最具代表性的種群,優(yōu)勢種和劣勢種則可以有多個,其中劣勢種規(guī)模最小但個數最 多.根據當前最優(yōu)個體周圍存在更加最優(yōu)個體的概率較大的原則,越優(yōu)秀的個體將產生更多 的子代個體.在每一個進化代,挑選適應度最好的前m個最優(yōu)個體,m為群落中種群的個數， 淘汰群落中所有其余個體，以m個最優(yōu)個體為母體產生m個種群,構成新一代群落,最優(yōu)秀 的個體產生建群種，依此類推使得越優(yōu)秀的個體產生的種群規(guī)模越大.比如假設群落C

18、的個體總數n=1000,種群數m=10,種群大小依次為300, 200, 150, 50, 50, 50, 50, 50, 50, 50,在每個進化代的優(yōu)秀個體向量大小為10,算法在每 一個進化代根據個體的適應度挑選出10個優(yōu)秀個體,下一代的種群由這10個優(yōu)秀個體產 生,其中最優(yōu)秀的個體將作為母體產生建群種，其它次優(yōu)秀的個體將依次產生優(yōu)勢種和劣勢 種群,則種群結構與優(yōu)秀個體的關系如圖2所示.基于云模型的進化算法不像遺傳算法那樣注重父代與子代的遺傳細節(jié)(通過基因表達 遺傳操作)上的聯系,而是通過云模型把進化和遺傳作為一種定性知識進行描述,進而通過 不確定的定性定量轉換,把定性知識轉化成-3 -圖

19、2種群結構與優(yōu)秀個體的關系若干定量實現(子代個體).在每一個進化代,一方面通過對子代個體的適應性評估得到 優(yōu)秀個體，另一方面根據歷史進化情況確定下一步進化的范圍,從而形成新的知識,為下一 步進化做好了準備.為了便于表述算法思想首先定義以下基本概念.定義2.1進化模型(Evolving Pattern) EP(Ex, En, He)是用云模型表達的進化模型.其 中Ex稱為種子個體,表達祖先遺傳的優(yōu)良特性；En稱為進化燧，代表變異的大概范圍； He稱為進化超燧表示進化的穩(wěn)定性,He越大則不確定性越強.進化模型包括一維模型和多 維模型,多維模型用EP(Exl, Eni, Hei,，Exn, Enn,

20、 Hen)表示,其中維數n為大于等于1的 整數.給定父代個體(Ex)作為母體，指定帽和超燧(En, He),利用正向云算子便可以產生任 意數量的云滴,所有云滴均是該母體的后代個體,形成一個種群,因而進化模型可以看成是 種群的產生模型.定義2.2進化(Evolvement)是指以父代種群中適應度較好的優(yōu)秀個 體為母體,按照進化模型產生新種群的操作.進化操作包含有一定的變異成分，因為個體即 繼承了母體的優(yōu)良特征，乂與母體有一定程度的不同，由于這種變異為穩(wěn)中求變，故稱為進 化式變異.進化式變異的變化程度主要受進化模型的參數En控制，其變化程度可能較小 (En較小時)，也可能較大(En較大時).定義2.3突變（Mutation）是指進化過程中全部或部分拋棄父代種群的優(yōu)秀個體，并 按照一定策略生成新的個體作為母體產生新種群的操作.經過突變產生的群落相對與父代 群落差異較大.定義2.4進化代（Evolving Generation）進化過程中新群落的一次產生稱為一個進化 代.定義2.5適應度（Fitness）群落中各個個體對環(huán)境的適應程度，是衡量個體優(yōu)劣的程 度，根據適應度的大小，決定某個個體是被保留還是被淘汰.適應度通常是費用、盈利、方 差等目標的表達式，適應度函數的構造可以