神經樹

神經樹

神經樹的提出是為了解決人工神經網路的自動設計問題,它是一種利用進化計算的方法來輔助其結構和參數最佳化的類似於人工神經網路的智慧型計算系統,可將它看成是一個分級的、多層的和不規則的人工神經網,它採用樹結構編碼(樹的結點來自於事先定義好的函式指令集 F 和終端指令集 T),樹的每一個非終端結點都有一個非線性映射函式,該函式有一個或者多個可調節的控制參數,結點之間的都有相應的連線權值。目前的研究表明神經樹模型具有非常好的分類能力和函式逼近能力。,而模型中的可變參數則可用遺傳算法、禁忌搜尋算法、粒子群最佳化算法、模擬退火算法等最佳化算法來最佳化。

基本介紹

  • 中文名:神經樹
  • 外文名:Neural Tree
  • 基本理論:編碼特徵、結構特徵、參數特徵等
  • 相關概念:神經網路
  • 提出者:Byoung-Tak Zhang等
發展歷史,神經樹的編碼,適應度評價函式,結構最佳化算法,參數最佳化算法,粒子群最佳化算法,禁忌搜尋算法,模擬退火算法,神經樹設計流程,

發展歷史

1997年,Byoung-Tak Zhang等首次利用一個樹來表示神經網路形的模型,提出了稀少神經樹的進化感應法(evolutionary induction)。基於神經樹的表示,高階 sigma一pi 神經網路的結構和權值分別用遺傳規劃和遺傳算法進行進化。
2005年,Y.Chen等對神經樹進行了廣泛的研究,提出了靈活的神經樹模型(Flexible Neural Treemodel,FNT),利用混合進化算法,最佳化了模型結構及參數。將該模型套用到人臉識別,非線性系統建模,時間序列分析等,驗證了模型的有效性。

神經樹的編碼

神經樹的神經樹指令集 S 分為函式指令集 F 和終端指令集 T,函式指令集 F 和終端指令集 T 定義為:S=F∪T=
,這裡
(i=2, 3,…, N)表示非葉子結點的指令,有 i 個參數;
表示葉子結點的指令,它們沒有參數。一個非葉子結點的輸出可以看成是一個靈活神經元計算的結果,每個節點以指令集 S 進行編碼,其輸出可以看作一個靈活的神經網路的輸出,如圖1和圖2所示。
在神經樹的產生過程中當一個非葉子結點指令被選擇的話,也即
被選擇,就隨機產生 i 個值作為非葉子結點和它的孩子之間的連線權值,另外再隨機產生兩個數
作為該結點激勵函式的靈活參數。神經樹模型中的非葉子結點的激勵函式(或稱為映射函式)用下面的式子表示:
的總激勵結果是:
其中,
(j=2, 3,…, N)是
結點的輸入,結點
的輸出可以如下式計算得到:

適應度評價函式

適應度評價函式將神經樹映射為反映神經樹的性能的標量值,用於檢驗對於一個給定任務,神經樹的表現到底如何。要求神經樹的適應度值能夠表示出實際輸出和期望輸出的誤差,即MSERMSE,適應度值越小表示實際輸出和期望輸出之間的誤差就越小,也就是說適應值小的神經樹越好。
在不同的套用領域中的適應度評價函式的選擇也不同,在時間序列預測領域中一般用標準方差來計算神經樹的適應度。

結構最佳化算法

由於神經樹模型的基於樹編碼的結構特點,一些基於樹結構的進化算法,如螞蟻編程、遺傳編程以及遺傳編程的變異算法等都可以用來最佳化神經樹的結構。
螞蟻編程算法是一種受蟻群最佳化算法啟發的新的智慧型算法,它繼承了蟻群算法的基本特點、術語和基本理念。在螞蟻編程算法中,每隻螞蟻將根據每個節點上信息素的數量來構建或修改樹。信息素表看起來像一棵樹。每一個節點都擁有一個表格紀錄其對應各種可能的指令的信息素比率。如圖3所示。
首先,隨機產生程式的所有參數。每個節點的信息素表都被初始化為 0.5。這表示最初選擇每個終端(葉子節點)和函式(非葉子節點)的機率是相同的。信息素的比率越高,被選中的機率越高。使用預先定義好的目標函式去評價每個規劃(個體)。信息素表有兩種更新機制:
1.所有指令在節點上的信息素比率按照以下公式蒸發降低 :
其中,
表示第 g 代的信息素值,α是一個常數,α=0.15。
2.對於每一個樹,根據樹的適應度函式,樹的每一部分將得到加強。公式如下:
其中,s 是一個解決方案(樹),
是樹的適應度函式。
表示在這個個體中節點 i 的函式或終端集(指令集)。α是一個常數,α=0.1。
是指令
在節點 i 的信息素。
螞蟻編程算法可簡要描述為:
(1)將信息素樹的每個部分設為相同的均值;(2)根據信息素樹隨即生成樹;
(3)根據適應度函式評價每隻螞蟻(每一棵樹);
(4)根據上述兩種跟新機制更新信息素表;
(5)如果疊代次數達到最大值或者得到了滿意解,則終止程式並返回樹結構,否則重複步驟(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;
第四步,判斷是否滿足終止條件,若滿足就結束整個算法然後輸出搜尋結果,否則跳至第二步。

神經樹設計流程

第一步,初始化操作:隨機創建初始化數據,設定好進化算法的相關參數的初始值(樹結構及其相關參數);
第二步,結構最佳化:選擇一種基於樹結構的進化算法如遺傳編程,螞蟻編程等算法來最佳化神經樹模型的結構,根據套用的具體問題選擇合適的適應度評價函式;
第三步,如果找到一個結構合適的神經樹,跳到第四步執行,否則轉至第二步繼續結構最佳化;
第四步,參數最佳化:神經樹模型的參數主要是結點間的連線權值和激勵函式的可變參數,選擇一種參數最佳化算法來最佳化相關參數如遺傳算法、禁忌搜尋算法、粒子群最佳化算法、模擬退火算法等,這一階段神經樹的結構是固定的,這個結構來自於上一步的最佳化結果;
第五步,如果疊代次數已經最大,或者找不到更好的參數向量,則跳到第六步,否則轉至第四步;
第六步,當找到滿意的結果或者其他終止條件滿足就停止整個算法,否則轉至第二步。

相關詞條

熱門詞條

聯絡我們