從Random Walk談到Bacterial foraging optimization algorithm(BFOA)，再談到Ramdom Walk Graph S...

摘要： 1. 從細菌的趨化性談起 0x1：物質化學濃度梯度 類似於概率分佈中概率密度的概念。在溶液中存在不同的濃度區域。 如放一顆糖在水盆裡，糖慢慢溶於水，糖附近的水含糖量比遠離糖的水含糖量要高，也就是糖附近的水糖的濃度高，離糖越遠的水糖的濃度越低。 這種濃度的漸減（反...

1. 從細菌的趨化性談起

0x1：物質化學濃度梯度

類似於概率分佈中概率密度的概念。在溶液中存在不同的濃度區域。

如放一顆糖在水盆裡，糖慢慢溶於水，糖附近的水含糖量比遠離糖的水含糖量要高，也就是糖附近的水糖的濃度高，離糖越遠的水糖的濃度越低。

這種濃度的漸減（反方向就是漸增）叫做 濃度梯度 。可以用單位距離內濃度的變化值來表示。同樣，溫度、 電場強度 、磁場強度、重力場、都有梯度的。

化學溶液的濃度梯度的概念和概率分佈的梯度類似，都代表了 值下降的方向 。

0x2：趨化性細菌的運動方式

細菌趨化性是指有運動能力的細菌對物質化學濃度梯度作出的反應，使細菌趨向有益刺激，逃避有害刺激。

Engelmann 和 Pfeffer 發現細菌的運動不是任意的，而是定向移動。直到1960年，Alder深入研究了細菌趨化性的分子機制，提出大腸桿菌(Escherichia coli)對氨基酸以及糖的趨化性是由位於細胞表面的受體蛋白調節的，並由細胞內分子傳遞訊號最終影響細菌的運動。

以大腸桿菌為例，一個細胞有4~10根鞭毛，鞭毛快速旋轉使得細胞具有運動的能力。

鞭毛的運動方式分為 2 種：

1. 順時針旋轉(clockwise，CW) - 按照本輪計算的優化方向進行迭代調整

當鞭毛順時針旋轉時，細胞鞭毛分開，原地做翻滾運動，來調整運動方向

筆者思考： CW過程我們可以理解為LMS過程中計算最速下降梯度方向，但是生物機制沒法一步得到最速梯度方向，而且我們知道液體中轉動物體也存在粘滯慣性，因此，細菌在CW過程中實際上是在計算一個大致正確的梯度下降方向。它並不是一次得到最優結果，而是依靠多次地不斷迭代逐漸靠近最優 。

2. 逆時針旋轉(counter-clockwise， CCW)

1）在存在區域性濃度梯度變化的環境中調整方式 - GD過程

當鞭毛逆時針旋轉時，鞭毛擰成一束，產生向前的推動力。

CCW過程中前進的這段，我們可以理解為梯度下降中，每次調整的總距離，即。

但是細菌並不是說一次CW調整方向後，就一直保持前進。

細菌先直線運動一段距離 然後通過比較現有濃度和過去濃度（計算濃度梯度）來控制鞭毛接下來的運動方式（根據濃度梯度調整下一步大致方向）。

1. 當誘導劑濃度降低或趨避劑濃度增加時，翻滾頻率增加（縮短學習率），遠離不利環境；
2. 反之，翻滾頻率降低，細菌泳動，趨向有利環境（類似梯度下降中加入momentum動量因素，如果方向對了就繼續保持）；

2）在區域性環境中濃度梯度都相等時的調整方式 - Ramdom過程

我們知道，溶液中濃度的傳播是一種漸變衰減的形態，即一個濃度源的濃度梯度只能傳播一定的範圍，超過一定的範圍就會衰減到幾乎無法感知。這就造成了溶液中的濃度梯度看起來就像一個個的小山包此起彼伏。有山包就有山谷、平原。

在無化學刺激物質或濃度相同的化學環境中（可能剛好存在於一個濃度梯度的平原中），細菌先平穩地直線泳動一段距離，然後突然翻滾改變運動方向，再向前泳動， 再翻滾。

泳動和翻滾循序變化，其特點為 隨機選擇運動方向 。

這就為細菌提供了一種能力，即脫離困境的能力。即使不小心處於一個沒有營養的溶液區域，或者說當前離營養源距離比較遠。但是依靠自己的ramdom walk機制，在概率上，通過一定的步數後，是有機會到達存在濃度梯度的區域的，到達了濃度梯度區域後就簡單了，細菌自身的趨向性會開始發揮作用，幫助喜歡達到營養源中心。

筆者思考： 細菌的濃度梯度趨向性雖然很驚豔，但是也還算平常，畢竟冷熱氣流也存在密度交換形成暴風，濃度的趨向是自然現象。但是細菌的這個ramdom walk隨機試探機制就太神奇了，SGD（隨機梯度下降）的發明就是參考了細菌的這種ramdom walk思想。ramdom walk使優化過程具備脫離區域性鞍點的能力 。

0x3：細菌趨化性分子機制

趨化性的發現刺激了許多科學家的興趣，Julius Adler用基因、生物化學和行為學方法分析大腸桿菌的趨化行為，為詳細瞭解細菌趨化性分子機制做了鋪墊。

趨化細菌膜表面存在專一性的化學受體，以此來感知外界環境中化學物質的濃度變化，並將接收到的化學訊號轉化為細胞內訊號，進而來控制鞭毛的運動方式，表現出相應的趨化性。

通常訊號轉導途徑分 3個部分

1. 膜上趨化受體接收訊號；
2. 從膜 受體到鞭毛馬達的訊號轉導；
3. 對最初訊號輸入的適應。

Relevant Link:

http://www.casb.org.cn/PublishRoot/casb/2015/6/casb14110008.pdf

2. 隨機遊走數學模型

下圖中黑點表示了不同的隨機運動實驗，每個球的運動軌跡用不同的顏色表示，可以看到，每個球都呈現出不同的軌跡顏色。這些球的運動可以被統稱為 隨機運動 ，

0x1：一維空間下的等概論隨機運動（伯努利隨機遊走）

最簡單的隨機運動形式就是一維運動。

圖中的黑點從原點開始，它有各50%的概率向左和向右移動，黑點每次只能隨機選擇一個方向移動一格。

下圖展示了這個黑點執行5次後的可能的運動軌跡：

黑點最後停在了“-1”這個點上。這個時候我們肯定有疑問了，這是巧合嗎？還是有內在的規律在支配著這一切？

1. 黑點隨機運動的本質是什麼？

為了討論這個問題，我們對“黑點隨機運動（ramdom walk）”這個實驗進行數學抽象。

1. 設函式 F(x) 為每次移動遠離原點的距離（只針對這次移動而言，不考慮前一次的位置），這是一個隨機變數函式；
2. 同時，F(x) 由代表每次移動的隨機變數 an 決定，F(x) = F(an) = an。顯然，an 是一個離散型隨機變數，取值可能為 -1/+1，所以 F(x) 的可能取值也為 -1/+1；
3. F(x) 的損失函式 loss(E(x)) = loss（F(x) - 0）= loss（an - 0），代表了對黑點隨機運動的一種抽象化數值考量；

有了抽象表示，接下來我們從損失函式的角度來討論： 在不同損失函式的背景下，黑點的隨機運動 。

同時，筆者這裡要重點強調， 不同的損失函式代表的實際物理意義是不同的 。

1. 在均值損失函式背景下，對黑點隨機運動的計算本質上是在計算最後黑點停留的位置(相對原點)

在均值損失函式條件下，我們要求黑點N次隨機運動後停留的位置，就是在求函式 F(x) 的均值。

現在假設我們讓黑點執行N次（N可以為任意數字）作為一次實驗，記錄最後黑點停止的位置。

顯然，每次執行N次的結果都會不一樣，那我們該怎麼去形式化地認知這個現象呢？

這就要引入 極限 和 均值 的思想。

我們用<d>表示當 N趨向於無限 時，黑點最後距離原點的距離的均值；<an>表示黑點每次運動前進的均值。所以有下式：

<d> = <(a ₁  + a ₂  + a ₃  + ... + a _N )> = <a ₁ > + <a ₂ > + <a ₃ > + ... + <a _N >

同時，可以計算得到， <a ₁ >=0。 因為如果我們重複這個實驗趨向於無限次，a1有相同的概率得到 -1 或者 +1，所以均值為0。以此類推：

<d> = <a ₁ > + <a ₂ > + <a ₃ > + ... + <a _N > = 0 + 0 + 0 + ... + 0 = 0

這個分析過程可以使用數學中的 數學期望 進行抽象。

1）數學期望的定義

如果隨機變數只取得有限個值或無窮能按一定次序一一列出，其值域為一個或若干個有限或無限區間，這樣的隨機變數稱為離散型隨機變數。

離散型隨機變數的一切可能的取值 xi 與對應的概率 p(xi) 乘積之和稱為該離散型隨機變數的數學期望，記為 E(x)。它是簡單演算法平均的一種推廣，類似加權平均。

數學期望為描述隨機過程和隨機變數提供了一種可量化的工具。

2）黑點最後停止的位置等於黑點隨機運動的數學期望

E(x) = -1 * 0.5 + 1 * 0.5 = 0

當然，這種等價性只有在 N 趨近於無限次的前提下才能成立。

3）平均距離說明了什麼？

從平均的角度來看，這個結果表明在大量實驗下，黑點最終會停留在原點位置，這也是上帝是公平的一種數學抽象表示。

2. 在均方根(root-mean-squared)損失函式的背景下 ， 對黑點隨機運動的計算本質上是在計算 黑點總共執行的距離(恆正值)

1）計算均方根損失

在一次實驗中，d 可能為正值或者負值。但是 d ² 永遠是正值。

<d ² > = <(a ₁  + a ₂  + a ₃  + ... + a _N ) ² > = <(a ₁  + a ₂  + a ₃  + ... + a _N )  (a ₁  + a ₂  + a ₃  + ... + a _N )>

= (<a ₁ ² > + <a ₂ ² > + <a ₃ ² > + ... + <a _N ² >) + 2 (<a ₁ a ₂ > + <a ₁ a ₃ > + ... <a ₁ a _N > + <a ₂ a ₃ > + ... <a ₂ a _N > + ...)

我們逐項分解來看：

<a ₁ ² > = 1，因為a1取-1和+1的概率是相等的。同樣的道理 <a ₂ ² >,  <a ₃ ² >, ... <a _N ² >

接下來看<a ₁ a ₂ >，有4種可能的取值，每種取值的概率都相等：

可以計算得到，<a ₁ a ₂ > = 0，同樣的情況對<a ₁ a ₃ >, <a ₁ a _N >, <a ₂ a ₃ >, <a ₂ a _N >成立。所以：

<d ² > = (<a ₁ ² > + <a ₂ ² > + <a ₃ ² > + ... + <a _N ² >) + 2 (<a ₁ a ₂ > + <a ₁ a ₃ > + ... <a ₁ a _N > + <a ₂ a ₃ > + ... <a ₂ a _N > + ...)

= (1 + 1 + 1 + ... +1) + 2 (0 + 0 + ... + 0 + 0 + ...) = N

接著對<d>開根號，得到：

sqrt(<d ² >) = sqrt(N)

2）為什麼均方根損失函式比平均值損失要大？

在機器學習最優化過程中很常用的均方根損失，有一個很好的數學特性，就是“放大誤差”，即如果某次實驗出現了和預期不一致的結果，均方根可以將這個誤差放大，而不至於被掩蓋在均值為0的假象中。

也可以這麼理解，黑點每次實驗，不管是向前還是向後，都是在“執行一步的距離”，均方根並不關心前進的方向，只計算相對的前進值，因此永遠是正值。

0x2：在多維空間中的Ramdom Walk

多維空間中的ramdom walk分析方法和上一節的一維是一樣，區別只是隨機變數變成了多維隨機向量。

0x3：Ramdom Walk在現實生活中的例子

當空氣例子散佈在一個房間中時，ramdom walk原理決定了一個例子從一個位置移動到另一個位置的距離。

0x4：包含偏置的隨機遊走(biased random walk)

偏置可能由下列兩種情況組合而成：

1. 向不同方向行走的概率不相等，例如可能是 40%向左- 60%向右；
2. 向不同方向移動的步數(step size)不同，例如可能向左移動是1步，而向右是2步；

可以很容易想象，上述兩種偏置都是導致ramdom walk的軌跡向右偏移（net drift to the right）。換句話說，我們可以說隨機遊走向右偏置了。

下圖展示了第二種偏置情況下，黑點的可能執行軌跡。

0x5：細菌的趨化性本質上是一種偏置隨機遊走

1. 在沒有濃度梯度的環境下細菌呈現等概論隨機遊走

嚴格來說，這個小節的標題應該叫，在不存在 “區域性” 濃度梯度環境下，因為細菌沒有上帝視角，它只能感知到自己周圍一定範圍內的濃度梯度。

當不存在濃度梯度的時候， 細菌先平穩地直線泳動一段距離，然後突然翻滾改變運動方向，再向前泳動， 再翻滾 。這對應的就是等概論等步長的隨機遊走過程。

2. 在有濃度梯度的環境下細菌呈現偏置隨機遊走

當細菌感知到周圍存在濃度梯度的時候，細菌通過 鞭毛逆時針旋轉進行方向調整，超濃度梯度增加的方向移動。這對應的就是不同方向概率不同的偏置隨機遊走過程。

Relevant Link:

https://wenku.baidu.com/view/81d7a657a36925c52cc58bd63186bceb19e8edc2.html
http://www.mit.edu/~kardar/teaching/projects/chemotaxis%28AndreaSchmidt%29/random.htm
http://www.mit.edu/~kardar/teaching/projects/chemotaxis%28AndreaSchmidt%29/gradients.htm 
https://blog.csdn.net/u012655441/article/details/62216304

3. 細菌覓食優化演算法 - Bacterial foraging optimization algorithm(BFOA)

0x1： BFOA 的發展歷史

細菌覓食優化演算法(BFOA)被Passino所提出，對於 仿生學優化演算法 大家庭來說是一個新興技術。

對於過去的50年來，優化演算法（像遺傳演算法（GA）、進化規劃(EA)、進化策略（ES）），從 進化和自然遺傳 上給了研究人員許多的靈感，已經佔領了優化演算法領域。

最近幾年， 自然群體激發了演算法（ 像粒子群優化（PSO）演算法、蟻群演算法（ACO）），已經找到了它們應用領域。

跟隨著相同的群體演算法趨勢，Passino提出了BFOA演算法。

大腸桿菌群體覓食策略的應用在 多元函式最優化演算法 中是一個很關鍵的想法原型。

1. 細菌以一種可以最大限度的提高單位時間內獲得能量的方式去尋找食物；
2. 個體細菌通過傳送訊號來與其他的細菌進行交流；

細菌在考慮前面兩個因素之後做出進行覓食的決定。這個過程中，當尋找到食物後細菌做出最小的步長的移動，這個過程叫做 趨化 。

BFOA的關鍵思想是 在問題搜尋空間模仿細菌趨化運動 。

從該演算法出現以來，BFOA吸引了許多來自不同知識領域的研究人員的關注，主要是由於它的生物學驅動方式和神奇優美的結構。研究人員正在嘗試著去混合BFOA演算法與其他不同的演算法，儘量去探索該演算法的區域性和全域性兩個方面的特性。

它已經被應用到許多現實世界的真實問題上。可以預見，數學模型，適應性，演算法針對特定場景問題的定製化修改可能是BFOA將來的主要研究方向。

0x2：BFOA演算法的生物動力模型

1. 細菌系統中主要4種機制

1）趨化運動

在實際的細菌覓食過程中，運動是靠一系列拉伸的鞭毛來實現的。 鞭毛幫助的大腸桿菌細菌 翻滾 或 游泳 ，這是由細菌在覓食時執行兩個基本操作 。

1. 翻轉：當它們順時針方向翻轉時，每一根鞭毛都會拉動細胞。這導致了鞭毛的獨立運動，並且最終以最少的代價去翻轉。在糟糕的地方則頻繁地翻轉，去尋找一種營養梯度；
2. 游泳：逆時針方向移動鞭毛有助於細菌以非常快的速度游泳；

細菌經歷了趨化，朝著它們喜歡的營養梯度地方移動並且避免進入有害的環境。

通常情況下，細菌在友好的環境中會移動較長的一段距離。下圖展示了細菌的兩種運動模式：

Fig.1. Swim and tumble of a bacterium

2）複製

當它們獲得了足夠的食物，它們的長度增加以及面對著合適的溫度，它們將從自己本身的中間斷裂開來，形成兩個新的細菌。 這個現象啟發Passino在BFOA中引進 繁殖事件 。

3）消除-分散

由於突然的環境變化或攻擊發生後，趨化過程可能被破壞，一群細菌可能會轉移到其他地方或者一些細菌可能被引進到細菌群中。這些構成了真實細菌環境中的 消除-分散事件 。

4）群體

一個區域內的所有細菌被殺死或者一組細菌分散到環境的新部分

2. 形式化定義細菌系統機制

現在我們假設每個細菌的“人生終極目標”為 J( θ )，每個細菌的各種趨化、繁衍等機制，目的都是 想要找到最小的 J(θ)，其中θ ∈ R (θ is a p-dimensional vector of real numbers)。這樣，就可以在最優化理論的框架內對細菌的各種生存機制進行分析。

注意，我們沒有關於梯度∇J ( θ ) 的測量或者分析描述，實際上，細菌並能準確計算出本次移動的濃度 梯度∇J ( θ )

BFOA模擬了細菌系統中的四個觀察到的主要機制：趨化，群體，複製以及消除-分散。

BFOA解決的是一個 無梯度優化問題 。

一個虛擬細菌事實上是一個實驗方案（可能稱為 搜尋代理 ）在其優化面移動（見Figure2)，來尋找全域性最優解。

Fig.2. 每個細菌都在尋找全域性最優解，同時又一起構成一個整體群體

為了方便後續的套路，我們進行符號化定義：

1. 定義 j 作為趨化步驟索引、k 作為複製步驟索引、l 作為消除-分散步驟索引；
2. p：搜尋空間維度；
3. S：群體中細菌的總數；
4. Nc：趨化步驟的步數；
5. Ns：游泳長度；
6. Nre：複製步驟的次數；
7. Ned：消除-分散事件的次數；
8. Ped：消除-分散概率；
9. P( j , k , l ) = {θ ( j , k , l ) | i = 1,2,..., S}：代表 j 趨化步驟中，S細菌群體中的每一個成員的位置、k 複製步驟、l 消除-分散事件；
10. J( i，j，k，l )：表示在 i 細菌搜尋定位中的消耗（代價）。我們可以將J當作“cost”代價來做參考（用優化理論的術語）；

對於現實世界中的細菌種群，S可能(可以)可能是非常大的（例如：S=上萬），但是p=3。這很容易理解，一個培養皿中，有上萬的細菌在三維的溶液中進行移動。

在我們的BFOA計算模擬中，種群數代表了我們需要進行全域性最優化的目標函式數量，通常這個數字不會非常大（幾十、幾百最多了），例如後面會討論的ramdom walk圖分割演算法。

同時，BFOA允許p>3，以至於我們能夠運用這種方法在高維度優化問題中。

下面我們將簡要的描述這四種BFOA中的主要步驟。

1）趨化

這個過程模擬一個大腸桿菌細胞的運動，通過利用鞭毛的游泳和翻轉。它可以在一定時間內朝著一個相同的方向游去或者也可以翻轉，或者在整個生命週期中在兩中操作模式之間來回的輪流替換。
假設 θ<i>( j，k，l ) 代表 i 細菌在 j 趨化、k 複製，l 消除-分散步驟中。C(i) 是翻轉過程中採取指定的隨機方向的步長的大小（執行長度單元）。

在細菌的一次趨向過程中，細菌的運動方向可能根據下式表示：

其中 △i 指定為一個隨機方向向量，元素範圍為[-1，1]

2）群聚

群聚這個有趣的群體行為，已經在好幾種細菌物種裡被發現有類似的行為，包括大腸桿菌，鼠傷寒沙門氏菌。

其中複雜性和穩定性的時空格局（群聚）形成在半固體培養基。在群聚中，細胞不是但個體的行為，而是個體與個體間互相影響的複雜行為模式。

在一次實驗中，當使用一個營養化療效果器放置半固體基質到其中時，大腸桿菌細胞依靠 拉動營養梯度 來安排自己在一個群聚圈中。

在另一次獨立實驗中，當使用一個高等級的琥珀酸去刺激時，大腸桿菌細胞 釋放 一個有吸引力的穀草，這可以幫助他們去聚整合一個群組，從而移動成像高密度細菌群體的同心圓形狀圖案。

這種 細胞-細胞訊號傳導 在大腸桿菌群體中可以通過下面的函式來表示出來：

其中 Line"/> 表示是目標函式值；

S是細菌的總數；

p是將要被優化的變數的數量（即搜尋空間的維度）；

每一個細菌 都是p維搜尋域中的一個點；

是需要被搜尋優化的係數（超引數）。

3）複製

至少當每一個健康的細菌無性分裂成兩個細菌，然後放置在原先的位置，健康的細菌才最終死亡。這樣將保持細菌群體大小的不變。

4）消除和擴散

細菌生活的環境逐漸的改變或者突然的改變都可能由於各種各樣的原因而發生。

例如：當地顯著的氣溫上升可能殺死一組目前生活在一個區域內且有高濃度營養鹽梯度的細菌。以至於一個區域內的細菌都被殺死或者一組細菌擴散到一個新的區域。這是一種種群群體移動的現象。

BFOA對這一現象的模式方式如下：

一些細菌被以很小概率的隨機地清算掉，隨後新的替代品細胞們在搜尋空間被隨機初始化後。

0x3：BFOA演算法流程

引數：
【步驟 1】初始化引數 p，S，Nc，Ns，Nre，Ned，Ped，C(i)(i=1,2,…S)，θi
演算法：
【步驟 2】消除-擴散 迴圈 loop：l=l+1
【步驟 3】複製迴圈 Loop：k=k+1
【步驟 4】趨化迴圈 Loop：j=j+1
[a] i=1,2,……S 細菌 i 進化趨化移動

[b] 計算適應值函式 J（i，j，k，l）

[c] 讓 儲存值，因為通過移動我們可能找到更好的。

【步驟 5】如果 j < Nc，跳轉到步驟4。這種情況下繼續進行趨化，因為細菌的生命並未結束。
【步驟 6】複製 - 消除：
[a] 根據給定的 k 跟 l，對i=1,2,……S,迴圈，讓 

作為 i 細菌的一種它生命週期中度過多少營養以及怎樣成功的避免有害物質的數值化衡量。 高代價意味著低健康 。
[b] 擁有最高的 Jhealth值的 Sr 細菌死亡，擁有最低的Jhealth值的細菌分裂開來（結果放置在它們原先的父母的位置）。
【步驟 7】如果 K < Nre，跳到步驟3。這種情況下，我們沒有達到制定複製的數量，所以，我們開始下一次趨化迴圈，產生後代。
【步驟 8】驅散：以概率Ped 進行迴圈 i=1,2,……S，驅散每一個細菌（保持持續不變的細菌種群數量）。如果 l < Ned，然後跳轉到步驟2；否則結束。 

流程圖如下所示：

Relevant Link:

http://www2.ece.ohio-state.edu/~passino/PapersToPost/BFO-IJSIR.pdf
https://ieeexplore.ieee.org/document/1004010 
https://www.cnblogs.com/L-Arikes/p/3734353.html

4. 一種全域性最優化演算法  - 隨機遊走演算法(Random Walk)

0x1：隨機遊走演算法步驟

設目標函式 f ( x ) 是一個含有 n 個變數的多元函式， x = ( x 1 , x 2 , . . . , x n ) 為 n 維向量。f(x) 的超曲面空間就是我們要進行搜尋的向量空間。

1. 給定初始迭代點 x，初始行走步長 λ，控制精度 ϵ ( ϵ是一個非常小的正數，用於控制結束演算法)；
2. 給定迭代控制次數 N， k 為當前迭代次數，置 k = 1 ；
3. 當  k < N 時 ，隨機生成一個 ( − 1 , 1 ) 之間的 n 維向量 u = ( u 1 ，並將其標準化得到 。令 x ，完成第一步 遊走嘗試（注意這一步僅僅只是嘗試） 。
4. 計算函式值
   1. 如果  f ( x 1 ) < f ( x ) ，即找到了一個比初始值好的點，那麼 k 重新置為1，同時將 x 1 變為 x（完成實際的前進） ，回到第2步；
   2. 否則 k = k + 1 ，回到第3步，繼續其他方向的隨機遊走的嘗試。
5. 如果連續 N 次都找不到更優的值，則認為，最優解就在以當前最優解為中心，當前步長為半徑的 n 維球內(如果是三維，則剛好是空間中的球體)。此時：
   1. 如果 λ < ϵ ，則結束演算法，即演算法已經收斂；
   2. 否則，令 λ = ，回到第1步，開始新一輪遊走。

0x2：隨機遊走的程式碼實現

我們假設目標函為 ，實際的目標函式可能是任意形式的，根據你自己在專案裡的實際場景而定。

我們的目標是 求 f ( r ) 的最大值。

該函式是一個多峰函式，在 ( 50 ， 50 ) 處取得全域性最大值 1.1512 ，第二最大值在其全域性最大值附近，採用一般的優化方法很容易陷入區域性極大值點。

這裡是求解函式的最大值問題，可以將其轉化為求目標函式的相反數的最小值問題，即對偶求解思想。具體程式碼如下：

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__import print_function
import math
import random

N = 100# 迭代次數
step = 0.5# 初始步長
epsilon = 0.00001# 收斂閾值
variables = 2# 變數數目，搜尋空間的維度
x = [49, 49]# 初始點座標
walk_num = 1# 初始化隨機遊走次數

print("迭代次數:", N)
print("初始步長:", step)
print("epsilon:", epsilon)
print("變數數目:", variables)
print("初始點座標:", x)


# 定義目標函式
def obj_function(p):
r = math.sqrt((p[0]-50)**2 + (p[1]-50)**2) + math.e
f = math.sin(r) / r + 1
return -f


# 開始隨機遊走
while(step > epsilon):# 判斷是否收斂停止演算法
k = 1# 初始化計數器
while(k < N):
u = [random.uniform(-1, 1) for i in range(variables)]# 隨機向量
# u1 為標準化之後的隨機向量
u1 = [u[i] / math.sqrt(sum([u[i]**2 for i in range(variables)])) for i in range(variables)]
x1 = [x[i] + step*u1[i] for i in range(variables)]# 隨機遊走嘗試
if(obj_function(x1) < obj_function(x)):# 如果找到了更優點
k = 1# 重置 k
x = x1# 更新座標
else:
k += 1# 繼續下一次隨機遊走嘗試
step = step/2
print("第 %d 次隨機遊走完成。" % walk_num)
walk_num += 1
print("隨機遊走次數:", walk_num-1)
print("最終最優點:", x)
print("最終最優值:", obj_function(x))

1. 隨機遊走依然容易陷入區域性鞍點

基本的隨機遊走演算法對於初始點比較敏感，可以看出，當初始點位於最優點附件時，可以很好地達到全域性最優點；

如果將初始點設定得離最優點較遠，比如設定初始點為 ( 10 , 10 ) 時，其他引數不變，得到結果為：

可以發現，隨機遊走陷入了局部最優點。

2. 擴大嘗試次數 N、以及步長 λ 有助於脫離區域性最優點

不管是SGD，還是隨機遊走，都一樣面臨陷入區域性最小值的問題中。解決(或者說緩解)這一問題的方法是增大迭代次數 N 以及初始步長 λ ，可以在一定程度上增加尋優能力。

當然，增大迭代次數 N 以及初始步長 λ 也會引入新的問題，就是增大收斂過程的抖動，可以想象，如果目標函式已經優化到真正的全域性最小值點附近了，因為步長 λ 過大，目標函式會不斷在極值點附近來回擺動。

0x3：改進的隨機遊走演算法

改進的隨機遊走演算法的不同之處是在於第3步，原來是產生一個隨機向量 u ，現在則是產生 n 個隨機向量 u 1 , u 2 , ⋯ , u n ， n 是給定的一個正整數。

將 n 個 u i ( i = 1 , 2 , 標準化得到 u ′ 1 ， ，利用公式 x i = x + λ 令 替換原來的 x 1 ，其他步驟保持不變。

改進的核心思想在於：增加了ramdom process的干預程度，原本只有一次ramdom process，即決定一個確定的方向後進行隨機遊走嘗試。改進後變為在各個維度上全部ramdom，

同時在各個向量維度上進行隨機遊走嘗試，最後再綜合評價本次隨機遊走嘗試的優劣。

通過這種方式改進之後， 隨機遊走演算法的尋優能力大大提高，而且對於初始值的依賴程度也降低了。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__import print_function
import math
import random

N = 100# 迭代次數
step = 10.0# 初始步長
epsilon = 0.00001
variables = 2# 變數數目
x = [-100,-10]# 初始點座標
walk_num = 1# 初始化隨機遊走次數
n = 10# 每次隨機生成向量u的數目

print("迭代次數:", N)
print("初始步長:", step)
print("每次產生隨機向量數目:", n)
print("epsilon:", epsilon)
print("變數數目:", variables)
print("初始點座標:", x)


# 定義目標函式
def obj_function(p):
r = math.sqrt((p[0]-50)**2 + (p[1]-50)**2) + math.e
f = math.sin(r)/r + 1
return -f


# 開始隨機遊走
while(step > epsilon):
k = 1# 初始化計數器
while(k < N):
# 產生n個向量u
x1_list = []# 存放x1的列表
for i in range(n):
u = [random.uniform(-1,1) for i1 in range(variables)]# 隨機向量
# u1 為標準化之後的隨機向量
u1 = [u[i3]/math.sqrt(sum([u[i2]**2 for i2 in range(variables)])) for i3 in range(variables)]
x1 = [x[i4] + step*u1[i4] for i4 in range(variables)]
x1_list.append(x1)
f1_list = [obj_function(x1) for x1 in x1_list]
f1_min = min(f1_list)
f1_index = f1_list.index(f1_min)
x11 = x1_list[f1_index]# 最小f1對應的x1
if(f1_min < obj_function(x)): # 如果找到了更優點
k = 1
x = x11
else:
k += 1
step = step / 2
print("第%d次隨機遊走完成。" % walk_num)
walk_num += 1

print("隨機遊走次數:",walk_num-1)
print("最終最優點:",x)
print("最終最優值:", obj_function(x))

可以發現，即使迭代次數 N = 100 不大，初始點 ( − 100 , − 10 ) 離最優點 ( 50 , 50 ) 非常遠，改進的隨機遊走演算法依然可以達到最優點。

這說明了改進的隨機遊走演算法具有更強大的尋優能力以及對於初始點更低的依賴性。

筆者思考： 不管是SGD/GD還是batch-SGD，每次FP和BP過程的權重調整都是針對所有神經元同時進行的，同一個層上的神經元收到的調整反饋都是相同的。

在這一點上，SGD跳出區域性鞍點的能力就沒有改進後的隨機遊走演算法強 。

0x4：步長  λ 的意義

無論是隨機遊走演算法還是改進的隨機遊走演算法，對於步長都是非常依賴的。

步長 λ 越大，意味著初始可以尋找最優解的空間越大 ，但同時也意味著更多的迭代次數(要搜尋空間變大，尋找次數變多，相應時間自然要增加)。

如果步長取得過小，即使 N 很大，也很難達到最優解，過早陷入區域性最優。

無論對於隨機遊走演算法還是改進的隨機遊走演算法皆是如此。所以理論上步長 λ 越大越好。但是步長越大，迭代總次數越高，演算法執行時間越長。所以實踐中可以多試驗幾次，將 取得適當地大即可。

Relevant Link:

http://www.cnblogs.com/lyrichu/p/7209529.html
http://www.cnblogs.com/lyrichu/p/7209529.html 

5. Ramdom Walk Graph Segmentation 隨機遊走影象分割演算法

假設我們要對一個網路進行 模組挖掘 ，那麼一種可行的方法就是隨機挑選網路中的一些節點作為種子節點，然後進行隨機遊走(計算馬爾科夫矩陣)，對於計算結果，我們可以只取概率較高的前幾個作為可到達節點，之後採用一種類似於序列比對的方法來將所有種子節點遊走的結果進行比對拼接，然後獲得不同的模組。這樣做的一個好處就是結果較為穩定，並且所挖掘的模組更加完整可靠。

下面是採用上述方法得到的結果

其中相同顏色的節點屬於一個模組。

0x1：基於隨機遊走的影象分割演算法思想

隨機遊走演算法是一種基於圖論的分割演算法，它的分割思想是，以影象的畫素為圖的頂點，相鄰畫素之間的四鄰域或八鄰域關係為圖的邊(轉移概率)。以此構建網路圖。

如圖所示，圖中小圓圈代表影象上的每個畫素點，畫素點間的折線可看為權重。L1，L2，L3三個種子代表“打標點”，它可以由使用者互動式輸入，也可以是有監督學習中的打標樣本。

以未標記畫素節點為初始點，RandomWalk從未標記頂點開始隨機漫步，首次到達各類 標記頂點 的概率代表了未標記點歸屬於標記類的可能性，把最大的概率所在類的標籤賦給未標記頂點，完成一次分割，或者說完成一次歸屬，原本未標記的頂點現在歸屬到了一個類別中。
在上圖中可以看到，L1/L2/L3 作為標記的種子點。把影象分割成對應的三部分。

0x2：演算法流程

1. 建立 圖模型

1）無向連通圖

首先，定義一個連通無向圖G=(V,E)，用圖G 給影象建模。其中V是頂點集合，E是圖中任意兩個頂點的無向邊集合，對應影象畫素的連線關係，連線兩個頂點 vi 和的邊 用 vj 表示。

2）邊權重矩陣

帶權圖要為每條邊賦權值，邊 eij 的權值用 wij 表示，權重的計算公式如下：

，其中，gi 表示個畫素點的灰度值、或紋理資訊等引數；

3）節點轉移概率矩陣

對於圖中任意一點 vi 的轉移概率，其滿足 隨機遊走概率公式 ：

Lij = di：如果 i = j：di為頂點vi的度，是連線頂點的所有邊權值之和，di=sumj wij；
Lij = -wij：如果 i j 是相鄰節點，wij 是節點i 和節點j 之間的權重；
Lij = 0：other；

可構建 圖的拉普拉斯矩陣 ，然而拉普拉斯是非滿秩矩陣，需要新增邊界約束條件，才可根據方程組解出個各未知點的概率。也就是將影象分割問題轉換為Dirichlet問題進行求解。Dirichlet問題即就是尋找一個滿足邊界條件的調和函式。

2. 求解狄利克雷方程

隨機遊走模型的建立，可以理解為狄利克雷積分條件的離散化。其可以使用拉普拉斯矩陣來進行描述，即對隨機遊走模型的求解，可以描述為如下方程的最小化求解：

以已標記的K類頂點作為邊界約束條件，求解未知點到各個類的概率。例如，求解各未知點遊走到L1的概率，則以 ，作為約束條件。L2和L3也是同理。

因此，狄利克雷方程可以變形如下：

3. 模型的求解

對上述稀疏矩陣線性方程組的求解，最長用的是 共軛梯度法 。 

Relevant Link:

https://yq.aliyun.com/ziliao/522808
https://blog.csdn.net/hjimce/article/details/45201263
https://blog.csdn.net/u011773995/article/details/50438018
https://blog.csdn.net/menjiawan/article/details/47086423
https://blog.csdn.net/Broccoli_Lian/article/details/79739299