1.3　知識導向的智能優化算法

智能優化算法是當前研究的熱點問題，其主要缺點是容易出現早熟收斂和收斂速度慢。導致這些缺點的一個重要原因就是智能優化算法中缺乏明確的導向因子。國內外學者一方面通過傳統人工智能手段和特定知識模型來實現對智能優化算法的進化引導，同時也采用具有雙層進化機制的文化算法對智能優化算法進行引導。

1.3.1　傳統人工智能引導的智能優化算法

采用傳統人工智能手段對智能優化算法進行引導，如采用禁忌搜索^[3]、文化算法^[4]和機器學習^[5]來控制進化等^[6]。在具體實施時，必須首先抽取一些進化過程中盡可能一般和重要的規則，利用禁忌搜索、文化算法和機器學習等算法進行學習，然后根據學習得到的規則控制個體進化。這些工作的缺點在于很難找到盡可能一般和重要的規則，而且這些規則缺乏全局性，沒有考慮到隨著個體的進化，個體所處的環境也在不斷變化，因而相應的規則也應該變化^[6]。

為了平衡進化過程中選擇操作正向作用和交叉（變異）操作破壞性影響，范磊等采用歸納學習方法來引導進化過程^[7]：采用歸納學習方法從進化歷史進程中抽取出能反映過去進化的錯誤和成功的規則，進而用它們來引導后續進化過程，保證在避免重復錯誤的同時加速進化。基于函數優化和布局求解的實驗驗證了其有效性。

曹先彬等借鑒個體進化的生命周期性，提出了一種基于生命期引導的生態進化模型^[8]。基于此模型的算法在個體生命期的各個階段設置了相應的引導算子，使個體在整個生命期都基于其生態特征而被引導進化。實驗結果驗證了其優越性。

為了提高粒子群算法中粒子搜索全局最優解的準確度，岑宇森等提出了基于知識空間的分組式粒子群算法^[9]。該算法使用k-means算法對粒子群進行分組，利用較小的最大飛行速度加強粒子在組內的局部搜索能力，并將“知識空間”的概念引入到分組中，由知識空間中的粒子來引導群中粒子前往更好的解空間搜索。

李亞男等在遺傳算法中采用專家知識輔助尋優，并將該改進遺傳算法應用到無功規劃優化中^[10]。依據專家知識對少數被選中的個體動態形成本廠、站的就地無功／電壓控制的有效變量集進行人工調整，可改善遺傳算法的局部尋優能力。對某實際系統的計算表明，結合專家知識的遺傳算法能夠更有效地找到全局最優。

柴嘯龍將領域知識通過禁忌連接集的形式加入蟻群規劃算法中^[11]，相鄰動作層的很多互斥信息通過禁忌連接集只需計算一次，不進入主循環計算中，這樣可以較好地提升算法的執行效率。實例分析表明這一策略是有效的。

1.3.2　特定知識模型引導的智能優化算法

采用特定知識模型對智能優化算法進行引導時，在智能優化算法運行之初就已確定了知識的基本形式，相關知識按照固定規則隨著算法演化而不斷調整，然后采用已獲得知識來指導后續個體的進化。采用特定知識模型對智能優化算法進行引導也可理解為演化與學習之間的交互（interaction between evolution and learning）^[12-17]。

根據現有文獻，研究人員一般通過以下兩種途徑來實現演化和學習之間的交互^[18]：學習已獲得個體的一些優良特征，采用這些優良特征來改進后續產生的個體；學習已獲得個體的一些不良特征，采取措施防止這些不良特征出現在后續個體中。現有研究表明：演化和學習之間的交互是可能的，可采用多種途徑來實現演化和學習之間的交互，例如版本空間（version space）^[19]、基于案例的記憶單元^[20]、Q-學習系統（Q-learning system）^[21]，[22]和AQ-學習系統（AQ-learning system）^[23]等。通過演化和學習之間的交互可有效提高智能優化方法的優化效率^[18]。

1.3.2.1　采用記憶單元對智能優化算法進行引導

很多學者嘗試采用記憶單元（memory cell）來實現演化和學習之間的交互。Chung和Reynolds將個體優良特征看作是信念（beliefs），將這些信念保存到記憶單元中，采用這些信念來改進后續個體^[24]。Branke將一些已獲得的較優個體保存到記憶單元中，采用這些較優個體來改進后續個體^[25]。

Gantovnik等采用記憶單元在遺傳算法中實現演化和學習之間的交互^[26]，[27]，并使用這種改進遺傳算法來解決混合變量優化設計問題。Louis和Li采用帶有記憶單元的遺傳算法來求解旅行商問題^[28]。Yang采用基于記憶單元的移民方式在遺傳算法中實現演化和學習之間的交互^[29]，[30]，并使用這種改進遺傳算法求解動態優化問題。

蘇淼等采用免疫記憶方式在蟻群算法中實現演化和學習之間的交互^[31]，并使用這種改進蟻群算法來求解武器目標分配問題。Acan使用外部記憶單元（external memory）在蟻群算法中實現演化和學習之間的交互^[32]。在此基礎上，Acan在外部存儲器中加入了局部置換（partial permutations）功能^[33]，進一步提高了改進蟻群算法的效率。Shamsipur使用外部記憶單元在蟻群算法中實現演化和學習之間的交互^[34]。

1.3.2.2　基于案例對智能優化算法進行引導

很多學者也采用案例（case）在智能優化方法中實現演化和學習之間的交互^{[20]，[35]，[36]}。Louis和McDonnell采用案例推理（case-based reasoning）方法從案例記憶單元（case-based memory cell）中選擇特征來改進后續個體^[20]。Louis和Li在遺傳算法中采用案例注入方式來實現演化和學習之間的交互^[35]，并使用這種改進遺傳算法來求解旅行商問題。Rasheed和Hirsh采用案例學習方式在遺傳算法中實現演化和學習之間的交互^[36]。Babbar-Sebens和Minsker提出了一種基于案例的宏觀交互式遺傳算法（case-based micro interactive genetic algorithm）^[37]，主要通過案例記憶單元和案例推理來實現演化和學習之間的交互。

1.3.2.3　采用學習演化模型對智能優化算法進行引導

不同于基于達爾文進化論的演化計算方法，學習演化模型（learnable evolution model，LEM）主要采用機器學習方法來指導整個演化進程。Coletti對學習演化模型進行了初步研究^[38]，Wojtusiak研究了學習演化模型中的約束優化問題^[39]，Kaufman和Michalski采用學習演化模型來解決熱交換器設計問題^[40]，Jourdan等使用學習演化模型來解決多目標水系統設計問題^[41]，Domanski等采用學習演化模型來求解優化設計問題^[42]。目前，學習演化模型的最新版本為LEM3。Wojtusiak和Michalski應用LEM3來解決復雜函數優化問題^[43]。

近年來，越來越多的學者開始使用學習演化模型在智能優化方法中實現演化和學習之間的交互^[18]，[23]。Michalski等在總結學習演化模型最新進展^[44]的基礎上，在智能優化方法中采用學習模型來實現演化和學習之間的交互^[45]。在Michalski構建的學習演化模型中，主要采用機器學習方法來實現演化和學習之間的交互^[23]。Ho等采用學習型遺傳框架（learnable genetic architecture，LEGA）來實現演化和學習之間的交互^[18]。Wojtusiak設計了一種可用于多種智能優化方法的LEM3系統^[46]。

1.3.2.4　采用神經網絡對智能優化算法進行引導

針對遺傳算法個體進化缺乏明確導向的缺點，顧慧等提出了一種基于知識模型的改進遺傳算法^[6]：利用神經網絡的學習功能，從當前兩代個體的信息中獲取一定知識，用于控制下一代某些個體的進化。該算法既保留了遺傳操作算子，同時利用神經網絡構造相應的知識模型，用于引導個體進化，使得改進遺傳算法既保留了遺傳算法強大的全局隨機搜索能力，又具有神經網絡的自學習能力和強魯棒性。

1.3.3　具有雙層進化機制的文化算法

文化算法模擬人類社會的文化進化過程，由實現個體進化的種群空間和實現知識更新的信度空間構成。文化算法通過信度空間實現對進化信息的有效提取和管理，并利用進化信息指導種群空間的進化過程。文化算法可實現隱含進化信息的顯性歸納和描述，在種群空間之上擴展信度空間，以獨立實施知識管理，實現知識進化過程。目前文化算法已被成功用于解決農業進化、概念學習、實值函數優化和制造裝配過程的重新設計等問題。已經證明，在文化加速進化作用下的進化遠優于單純依靠基因遺傳的生物進化^[47]。

在傳統進化算法的基礎上，文化算法通過構建信度空間來提取隱含在進化過程中的各類信息，并以知識形式加以存儲，最終用于指導進化過程，其基本結構如圖1.2所示^[48]。文化算法由種群空間、信度空間和接口函數構成一種雙層進化結構。上層信度空間中的知識進化是以底層種群空間中的個體進化為基礎，且知識是個體經驗的高度概括。該雙層進化結構體現為個體微觀進化和知識宏觀進化兩個不同粒度的進化層面^[48]。

• 種群空間用于實現基于種群的進化算法。一方面對個體進行評價，并面向種群實施進化操作；另一方面將優良個體作為樣本提供給信度空間。
• 信度空間通過接受函數從已評價種群中選取樣本個體，在知識更新函數的作用下，提取樣本個體所攜帶的隱含信息，并以知識形式加以概括、描述和儲存。各類知識通過影響函數作用于種群空間，從而實現對進化操作的引導。
• 接受函數和影響函數為上層知識模型和下層進化過程提供了作用通道，稱為接口函數。

1.3.3.1　種群空間

隨著智能計算研究的不斷深入，遺傳算法、進化規劃、遺傳規劃、粒子群優化算法及微分進化算法等諸多智能優化方法被引入種群空間。

• 遺傳算法最早被引入種群空間。Reynolds等針對概念學習問題，采用基于遺傳算法的種群空間，討論了信度空間的知識構成^[49]。采用遺傳算法的優點在于，知識對進化過程的引導作用可體現在不同進化算子上。
• 進化規劃僅采用變異算子，知識對進化過程的影響程度易于觀察和分析。Jin使用基于進化規劃的文化算法解決非線性約束優化問題^[50]，將信度元的概念引入到信度空間。
• 遺傳規劃采用遺傳操作來動態改變程序所描述的問題模型，采用遺傳規劃作為種群空間的文化算法，在軟件工程、基于代理模型的策略優化問題中得到較好應用^[51]。
• 有學者采用粒子群優化算法作為種群空間，分析了在信度空間各類知識進行交流的情況下個體間的信息傳播^[52]，[53]。
• 微分進化本質上是一類基于概率分析的進化算法，研究人員將微分進化引入文化算法的種群空間，用于解決非線性約束優化和多目標優化等問題^[54]，[55]。
• 交互式進化計算是一類由人參與個體評價的算法。研究人員將該算法引入種群空間，通過提取人的認知和偏好等知識來縮小搜索空間，加速進化收斂^[56]。

1.3.3.2　信度空間

信度空間的核心在于知識如何描述和更新。種群空間采用的進化策略不同和應用領域不同，相應的知識形式也有所不同。一般而言，信度空間知識被劃分為5類：狀況知識、規范知識、拓撲知識、領域知識和歷史知識^{[50]，[56-58]}。這5類知識本質上都是進化過程中隱含信息的顯性描述，但在某些需要人參與的實際優化問題中，反映人類經驗的常識知識也對進化過程具有重要引導作用。

根據底層種群進化層提供的信息來源及其特征，也有學者將知識劃分為常識知識、進化知識和評價知識三部分，分別用來存儲以對象形式描述的顯性常識知識、以特征向量形式描述的進化過程隱含知識和以代理模型形式描述的用戶評價隱含知識^[59]，從而拓展了知識描述形式，豐富了知識內容。

1.3.3.3　接受函數

接受函數從種群空間選取較優個體提交給信度空間用于知識更新，其研究核心在于選取較優個體數目。目前，已有的接受函數有3類：固定比率接受函數、動態接受函數和模糊接受函數^[48]。這3類接受函數各有特點，在實際應用中應根據具體優化問題進行選擇。

1.3.3.4　影響函數

影響函數的主要作用是使用信度空間中各類知識引導種群進化。進化初期，種群探索整個搜索空間，此時規范知識及拓撲知識處于控制地位，一方面限定探索區域，另一方面引導搜索趨于具有高屬性值的單元。進化中期，更新狀況知識和規范知識，進一步縮小搜索范圍，并重新劃分拓撲知識，引導種群在更小粒度單元上進行搜索。進化后期，搜索集中在某一局部區域，容易導致早熟收斂，于是引入歷史知識，幫助種群跳出局部較優點。在整個進化過程中，領域知識一直為種群進化提供進化方向的指引。從知識對進化過程的引導作用可以看出，影響函數的關鍵問題在于各類知識何時作用于種群及其所引導的種群比例。在各類知識的引導作用下，文化算法顯示出了優于以往進化算法的收斂性、搜索能力及對環境的適應能力。