神經樹

1997年，Byoung-Tak Zhang等首次利用一個樹來表示神經網絡形的模型，提出了稀少神經樹的進化感應法(evolutionary induction)。基於神經樹的表示，高階 sigma一pi 神經網絡的結構和權值分別用遺傳規劃和遺傳算法進行進化。

2005年，Y.Chen等對神經樹進行了廣泛的研究，提出了靈活的神經樹模型(Flexible Neural Treemodel，FNT)，利用混合進化算法，優化了模型結構及參數。將該模型應用到人臉識別，非線性系統建模，時間序列分析等，驗證了模型的有效性。 ^[1] 

神經樹的神經樹指令集 S 分為函數指令集 F 和終端指令集 T，函數指令集 F 和終端指令集 T 定義為：S=F∪T=

∪

，這裏

(i=2, 3,…, N)表示非葉子結點的指令，有 i 個參數；

表示葉子結點的指令，它們沒有參數。一個非葉子結點的輸出可以看成是一個靈活神經元計算的結果，每個節點以指令集 S 進行編碼，其輸出可以看作一個靈活的神經網絡的輸出，如圖1和圖2所示。 ^[2] 

在神經樹的產生過程中當一個非葉子結點指令被選擇的話，也即

被選擇，就隨機產生 i 個值作為非葉子結點和它的孩子之間的連接權值，另外再隨機產生兩個數

和

作為該結點激勵函數的靈活參數。神經樹模型中的非葉子結點的激勵函數（或稱為映射函數）用下面的式子表示：

的總激勵結果是：

其中，

(j=2, 3,…, N)是

結點的輸入，結點

的輸出可以如下式計算得到：

適應度評價函數將神經樹映射為反映神經樹的性能的標量值，用於檢驗對於一個給定任務，神經樹的表現到底如何。要求神經樹的適應度值能夠表示出實際輸出和期望輸出的誤差，即MSE或RMSE，適應度值越小表示實際輸出和期望輸出之間的誤差就越小，也就是説適應值小的神經樹越好。 ^[3] 

在不同的應用領域中的適應度評價函數的選擇也不同，在時間序列預測領域中一般用標準方差來計算神經樹的適應度。

由於神經樹模型的基於樹編碼的結構特點，一些基於樹結構的進化算法，如螞蟻編程、遺傳編程以及遺傳編程的變異算法等都可以用來優化神經樹的結構。

螞蟻編程算法是一種受蟻羣優化算法啓發的新的智能算法，它繼承了蟻羣算法的基本特點、術語和基本理念。在螞蟻編程算法中，每隻螞蟻將根據每個節點上信息素的數量來構建或修改樹。信息素表看起來像一棵樹。每一個節點都擁有一個表格紀錄其對應各種可能的指令的信息素比率。如圖3所示。

首先，隨機產生程序的所有參數。每個節點的信息素表都被初始化為 0.5。這表示最初選擇每個終端（葉子節點）和函數（非葉子節點）的概率是相同的。信息素的比率越高，被選中的概率越高。使用預先定義好的目標函數去評價每個規劃（個體）。信息素表有兩種更新機制：

1.所有指令在節點上的信息素比率按照以下公式蒸發降低 ：

其中，

表示第 g 代的信息素值，α是一個常數，α=0.15。

2.對於每一個樹，根據樹的適應度函數，樹的每一部分將得到加強。公式如下：

其中，s 是一個解決方案（樹），

是樹的適應度函數。

表示在這個個體中節點 i 的函數或終端集（指令集）。α是一個常數，α=0.1。

是指令

在節點 i 的信息素。

螞蟻編程算法可簡要描述為：

（1）將信息素樹的每個部分設為相同的均值；（2）根據信息素樹隨即生成樹；

（3）根據適應度函數評價每隻螞蟻（每一棵樹）；

（4）根據上述兩種跟新機制更新信息素表；

（5）如果迭代次數達到最大值或者得到了滿意解，則終止程序並返回樹結構，否則重複步驟（1）。 ^[1] 

神經樹模型中的可變參數（結點之間的連接權值和激勵函數的相關參數）則可用遺傳算法、禁忌搜索算法、粒子羣優化算法（PSO）、模擬退火算法等等進化算法來優化。下面先簡介一下這些參數優化算法的基本實現思想。

PSO 初始化為一羣隨機粒子(隨機解)，然後通過疊代找到最優解。在每一次疊代中，粒子通過跟蹤兩個 “極值”來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值 pBest；另一個極值是整個種羣找到的最優解，這個極值是全局極值 gBest。另外也可以不用整個種羣而只是用其中一部分作為粒子的鄰居，那麼在所有鄰居中的極值就是局部極值。

PSO 算法主要計算步驟為:

第一步，初始化,設定位移因子

和

，最大進化代數

，將當前進化代數設為 t，在定義空間

中隨機產生 S 個粒子

，組成初始種羣 x(t)；隨機產生各粒子初始位移變化

，組成位移變化矩v(t)；

第二步，評價種羣x(t)；

第三步，更新速度和位置；

第四步，粒子的位移方向和步長，產生新種羣x(t+1)；

第五步，檢查結束條件，若滿足，則結束整個算法；否則 t=t+1，轉至第二步。

禁忌搜索算法（Tabu Search，TS）是一種全局優化算法。禁忌搜索算法通過引入一個靈活的存儲結構和相應的禁忌準則來避免迂迴搜索，同時採用藐視準則去赦免一些被禁忌的優良狀態。它最重要的思想就是標記對應已經搜索到的局部最優解的一些對象，並在進一步的迭代搜索中儘量避開這些對象，從而保證對不同的有效搜索途徑的探索。

禁忌搜索算法一般涉及到領域、禁忌表、禁忌長度、候選解和藐視準則等概念，它們是影響禁忌搜索算法性能的關鍵。其中，領域是用來決定當前解的領域解的產生形式數目以及各個解之間的關係；禁忌長度決定了禁忌對象的任期，其大小直接影響整個算法的搜索效率；候選解是一個集合，它通常是當前狀態的領域解集的一個子集，在設計算法的過程中它的取值一般較小，但是過小將容易造成早熟收斂；藐視準則的設置是算法避免遺失優良狀態，激勵對優良狀態的局部搜索，進而實現全局優化的關鍵步驟。

簡單禁忌搜索算法步驟描述如下：

第一步，初始化算法的相關參數，隨機產生初始解向量 x，設置禁忌表為空；

第二步，利用當前解向量 x 的領域函數產生一些領域解，並從中選擇一些作為候選解；

第三步，判斷候選解是否滿足藐視準則，若成立，則用滿足藐視準則的最佳狀態 y 替代 x 成為新的當前解，並用於 y 對應的禁忌對象替代最早進入禁忌表的禁忌對象，同時用 y 替換“best so far”狀態，然後跳至第五步，否則，執行第四步；

第四步，判斷候選解對應的各對象的禁忌屬性，選擇候選集中非禁忌對象對應的最佳狀態為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象元素。

第五步，判斷是否滿足算法終止條件，若滿足，結束整個算法並輸出優化結果；否則，跳至第二步。

模擬退火算法（Simulated Annealing,SA）的是基於 Mente Carlo 迭代求解策略的一種隨機搜索算法，其出發點是基物理中固體物質的退火過程和一般的優化問題之間的相似性。模擬退火算法在某一始温度下，伴隨着温度參數的不斷下降，結合概率突跳特性在解空間中隨機搜索目函數的全局最優解，即在局部最優解中能概率性地跳出並最終趨於全局最優。模擬退化算法包括新狀態產生函數、新狀態接受函數、退温函數、抽樣穩定準則和退火結束準則以及初始温度等幾個主要結構，它們直接影響算法優化的結果，通常要求算法具有較高的初始温度、較慢的降温速率、較低的終止温度以及各温度下足夠次數的抽樣等條件。

標準模擬退火算法的一般步驟描述如下：

第一步，設定初始温度 t=

，隨機產生初始狀態 s=

，令 k=0；

第二步，產生新狀態

=Generate(s)；如果1和

中的較小數大於或等於0到1之間的一個隨機數，則令 s=

；重複執行該步驟直到滿足抽樣穩定準則，繼續往下執行；

第三步，退温

=update(

)並令k=k+1；

第四步，判斷是否滿足終止條件，若滿足就結束整個算法然後輸出搜索結果，否則跳至第二步。 ^[1] 

第一步，初始化操作：隨機創建初始化數據，設置好進化算法的相關參數的初始值(樹結構及其相關參數)；

第二步，結構優化：選擇一種基於樹結構的進化算法如遺傳編程，螞蟻編程等算法來優化神經樹模型的結構，根據應用的具體問題選擇合適的適應度評價函數；

第三步，如果找到一個結構合適的神經樹，跳到第四步執行，否則轉至第二步繼續結構優化；

第四步，參數優化：神經樹模型的參數主要是結點間的連接權值和激勵函數的可變參數，選擇一種參數優化算法來優化相關參數如遺傳算法、禁忌搜索算法、粒子羣優化算法、模擬退火算法等，這一階段神經樹的結構是固定的，這個結構來自於上一步的優化結果；

第五步，如果迭代次數已經最大，或者找不到更好的參數向量，則跳到第六步，否則轉至第四步；

第六步，當找到滿意的結果或者其他終止條件滿足就停止整個算法，否則轉至第二步。 ^[1]