2014-04-12

學校課程/計算型智慧

計算型智慧 - 學習 (Computational Intelligence)

計算型智慧

文章簡介

下學期修了這門課，這其中會與另一門類神經網路有關。
中間穿插工數和微積分的一些數學名詞。
接著，您將會看到一系列筆者對計算型智慧的認知。
看到以下內容，雖有數學模型、演算法成份，但主體為模擬自然界的各種思維。

算法設計

特定型最佳化法則

根據函數的特性，衍伸出來的搜尋方式，目標函數有特別性質，例如：線性、微分 … 等。微分法、梯度法都是屬於此類。再講白一點，一般大學時學的演算法都是如此，通常是具有最佳化結構的情況，因此會有最短路徑算法、二分搜尋、三分搜尋 … 等。

廣義型最佳化法則

不管目標函數的特性為何，無須修改設計法則，亂做一通、隨機搜索、以及接下來講的主題都屬此類。

模糊系統

模型簡介

一般程式撰寫判斷條件相當精準，同時也不好做修正，畢竟一般人看不懂那麼多 if-else 語句。
那有沒有更好一點的描述方式？這就是接下來要講的。
如果硬要說明，模糊系統相當於一個精準輸入→亂來一通→精準輸出，也就是多了中間那個過程。

模型介紹

是或不是，僅有 0/1 描述。
真實世界是按照是的相似度有多高，不是的話就是有多高。或者描述多是有多多，少是有多少。
歸屬函數 (membership function)
值介於 [0, 1] 同時也是相似度的描述。
詳細請參照 wiki 模糊集
模糊關係 (fuzzy relation)
簡單的說，一般用稀疏矩陣是用 N * N 的陣列，並且裡面存放 0/1 數值，但是在模糊關係中，將會使用 [0, 1] 之間的實數來代替。
詳細請參照 wiki 模糊關係
- 有什麼樣的操作 ?
  對於關係運算，也有關係合成或者是條件機率。對於關係合成就可以自訂函數來合成，而條件機率通常會使用積分去查閱，但是模糊關係至少三維空間 (因為多一個歸屬函數值)，所以必須走投影擴充的方式，當然可能有其他的做法。
單一規則，單一變數
if x = p, then y = q.
模糊起來
```
x = p 的關聯性多少，y = q 的多少比率。
```
舉個例子來說
```
x 相當靠近 p, 假使說相似度 50%, 則 y = 0.5 * q
```
以上是函數是說法，當然您可以自由選擇越接近反而越低，或者是客製化。
單一規則，多變數
if x1 = p1 and x2 = p2, then y = q
- 由上一條，會有一點想法，那把兩個相似度取最小值如何？或者是相乘(假使相似度小於 1)。
- 模糊沒有標準答案，覺得合理就行。
單一規則，多變數
if x1 = p1 or x2 = p2, then y = q
- 由上一條，會有一點想法，那把兩個相似度取最大值如何？或者是相加後約束小於 1。
- 模糊沒有標準答案，覺得合理就行。
多規則，單一變數
if x1 = p1, then y1 = q1
if x2 = p2, then y1 = q2
- 再藉由上一條相乘，那接著相加如何？還是要來個加權平均？
- 一樣沒有標準答案，加權就是拿相似度出來當權重。
多規則，多變數
想必已經自動推論出來，在此就不多說。
怎麼來亂？(隨便說說)
- 函數式：多少相似度 p 根據多項式 f(p) 產出 y 值。
- 語意式：畫出 f(y) = p 的圖，計算 p 所占有面積的面積(劃一條線取交集)，來決定 y 要取多少。
- 中間要不要遵守遞移律、交換律、結合律？照理來講是要的。
```
不過想吐槽的是，都這麼模糊了，還要遵守這三律嗎？
```
建造模糊規則
- 通常由有經驗的專家口頭描述，然後讓程式慢慢演化。
- 如果沒有專家可問，先把參數空間做切割，分別定義產出。
```
最簡單的大小分，如果有 n 個參數，將會產出 2^n 個空間，定義起來就很累。
```
模糊化類神經網路 … 略

結語

運算方式，跟編程複雜度有關。
函數式最好寫，但是彈性不高，產出結果通常有限(多樣性)。
如果採用非連續性的就很痛苦，通常會使用離散化取數值分析，可用重心法。
有重心法、肯定有眾數、中數法。
一般來說函數式就夠用，世界萬物都是簡單構成複雜。
可以利用收集資料，讓類神經網路產生演化結果 (稍後會提到)，神經應該也是模糊的！
收集到的資料正確性不知道有多高，根據簡單的投影法則，也可以變成模糊系統(初版)。

模擬退火

簡介

「模擬退火來自冶金學的專有名詞退火。退火是將材料加熱後再經特定速率冷卻，目的是增大晶粒的體積，並且減少晶格中的缺陷。」取自 wiki

簡單的說，膨脹去雜質，冷卻來精煉。冷卻得到區域最佳解，膨脹增加得到全局最佳解的機率。

操作

以 f(x, y) = z 的函數，要找到全局最小值，圖形看起來就是 3D 模型。
```
水往低處流，人往低處走
```
當現在在 (x, y) 時，笨的方式就是往四處看看，看哪邊更小就往哪裡走出下一步。而高明的作法則是根據梯度(微分來了)低的地方走，您就講想您有一個重力感測器。
步伐將會越來越小，這樣才能步步靠近區域最佳解。
當相當靠近區域最佳解時，變小幅度(dx/dt)太小，那就跳到更遠的地方去吧，相當於容忍較差的環境。
什麼時候容忍？可以根據某些指數函數結果跟隨機亂數比大小。

結語

寫 ACM 題目時，通常會選擇隨機撒點，然後對於每一個點根據相同步伐走相同步數，逐一縮小步伐。因為跳出的容忍不好設計。
```
foreach 隨機點
    for stepSize big to small
        for i = 0 to stepCount
            四處看看找更好的，Update 當前隨機點。
```
簡單運用，找出多邊形費馬點、最小覆蓋圓 … 等。
與隨機搜索差別在哪？隨機搜索相當於對每個子空間猜測，分布密度高才會準，空間越大，連區域最佳解都得不到。
講到區域最佳解－看看咱們的政治人物，不外乎都是講那些事情，這樣就是區域最佳解。思維跳脫機率不夠高，看來是火不夠大。

基因算法

簡介

又稱 GA 算法，模擬生物遺傳的過程，根據「物競天擇，適者生存」的演化論，最後會得到最好的解答。而進行演化就是染色體的事情了，當一開始的多樣性夠，再搭配突變情況交織出來，那崇高的自然藝術便會出現。

看看人類，您覺得有適者生存嗎？那這樣會進化嗎？
有空去搜尋電影－《蠢蛋進化論》看看不願面對的真相？

操作

將資料表示成基因片段，最簡單為二進編碼，當然也可以用實數。
資料是什麼？函數的常數參數，來驅使我們的模型可以更接近收集出來的數據。
第一步－初始化物種
隨機產生基因片段，或者來個生物大滅絕保留可能好的再隨機生成。
第二步－適應環境
越接近收集出來的數據(差值總和越小)，適應力越高。這就相當於成長階段。
第三步－擇偶
通常適應度高的會配在一起，就如人類有反例，這沒有絕對。
第四步－交配
交配方式如同染色體行減數分裂後的運作，將某幾段進行交換，而生物染色體只會切一刀然後配對，因為當初的雙股螺旋 … 各種原因，反正就是生物物質關係。如果是實數，則可以想像成會生成拉近關係或者是拉遠關係的結果。

兩個好的物種交配，也不見得子代會好。
第五步－突變
個體突變，染色體的 01 互換機率，或者在實數方面特化或者是弱化(就是乘實數)。

設定集

基因種類
- 一般型基因原則
  DNA[i] 只會有 0 或 1
- 實數型基因原則
  DNA[i] 可以是任意實數
- 為什麼這麼分類？IEEE floating-point format 感覺不是好的方法？請自行思考，其中最大的原因是不應該侷限基因。
一般型交配手法
- 單點交配
  對兩段基因，隨機找索引 i，交換索引 i 之後的所有基因。
```
i = rand_generate();
for j = i to length
    swap(dna1[j], dna2[j])
```
- 兩點交配
  與單點交配類似，不過是找一個區間 [l, r] 進行交換
```
for i = l to r
    swap(dna1[j], dna2[j])
```
- 字罩交配
  隨機挑數個隨機位置做交換。
- 更多，您可以妄想。

實數型交配手法

DNA1[i]' = DNA1[i] + k * (DNA1[i] - DNA2[i])
DNA2[i]' = DNA2[i] - k * (DNA1[i] - DNA2[i])
k 取 [-1, 1] 的微量亂數。

繁殖
因為繁殖池大小有限，物種數量將會被約束。
- 輪盤式選擇
  根據適應函數反應分布群族大小，四捨五入填滿整個繁殖池。
- 競爭式選擇
  每次隨機挑選兩個，對於這兩個挑一個好的留下，直到繁殖池滿。
更多設定
- 基因長度：
  反應精準度、編碼方式。
- 交配機率：
  機率高，容易產生混種！看看混血兒多聰明且吸引人，通常子代就不是如此。
- 突變機率：
  機率太高反而是隨機搜索，調適好相當於爆炸式搜索。
- 適應函數：
  如何反應好的物種？

結語

應用－使用類神經網路的模型，利用基因算法找到最佳解。而每個神經元都有搭配的參數，就是把參數基因化，調用基因算法。
幾句話說明類神經網路

每個神經元根據所受到的刺激產出一個定值，而神經元也有階層關係，每一個階層間會互相刺激，最外層吸收外界資訊，慢慢細化傳入最後階段的神經元來反應。而 ‘刺激到產出’ 可以猜想為加權平均。
實作後，這種算法必須應用在接近連續層面上會比較好，離散函數的問題效果不彰，也就是會有一些額外的判斷條件。
擇偶相當困擾，通常根據隨機亂數，在排序後做選擇。
交配相當刺激，同時也是最難抉擇的地方，個人造化。
要不要適應繁殖？都行，適應好的物種就多複製幾個！// 看您要不要固定，不然數量會爆炸，或者加入篩選。
大量繁殖大量突變，造就爆炸效應！(在鄰近空間進行爆炸找更好的地方)
最後根本就是在玩突變，突變算法就此誕生！

螞蟻算法

簡介

螞蟻單一功能低，群體完成最佳化。螞蟻行動過程中會留下費洛蒙，隨著時間費洛蒙也會下降，在這反反覆覆的過程中，蟻群很有機會開創出全局最佳解。

螞蟻雖小，亦能驅象。

操作

鮮少有人根據時間做迭代模擬的基底。
由於模擬上相當困難，所以來點不科學的寫法，但仍要抓住費洛蒙的核心。
第一版本－對於最短路徑搜索
- 決定有多少隻螞蟻
- 所有路徑上的費洛蒙初始為 0。
- 決定要跑多少次迭代
- 每次迭代，依序放出螞蟻，螞蟻會根據路徑上費洛蒙隨機走(也並不是越高越好)，對於走比較好的路徑，將其走過路徑上的費洛蒙濃度增加。
- 每次迭代，消散一點費洛蒙，來減少重複的錯誤區域解。
```
這樣有什麼缺點？因為是依序放出螞蟻，所以相當不自然。
再者每隻螞蟻還要有能力記錄走過的路徑。
螞蟻的記憶能力有多高？
```

虛擬碼

Initialize
    Loop /* at this level each loop is called an iteration */
        Each ant is positioned on a starting node
        Loop /* at this level each loop is called a step */
            Each ant applies a state transition rule to     incrementally build a solution and a local pheromone     updating rule
        Until all ants have built a complete solution
        A global pheromone updating rule is applied
    Until End_condition

第二版本－收集食物
- 決定有多少隻螞蟻，並且隨機撒下。
- 每隻螞蟻會搜索鄰近的食物
- 根據概率撿起某個食物，朝向費洛蒙高的地方搬運。
- 再根據概率將食物放下，放下時增加該地費洛蒙。

設定集

費洛蒙的濃度消散函數
螞蟻根據費洛蒙濃度的選擇函數
- 不遵守？機率為何？
- 遵守？又是根據什麼條件機率。

結語

應用方面
- 分群，把文章分類。
- 搜索，各種 NPC 問題都可以拿來玩玩。
小遊戲
感覺攻城遊戲對於這方面相當有意思，不過此遊戲有炒地皮的設定，基礎建設越來越貴，各種不科學的情況，七八千分還算正常人吧，沒有搭載最佳化系統的素人。
另外可見 DJWS的說明

粒子算法

簡介

英文名稱 Particle Swarm Optimization，粒子群聚演算法。看過鳥群群舞嗎？魚群穿梭嗎？

圖片來源地址

在相互模仿效應中，牠們會向鄰近學習，部分保留、部分學習，這也是向其好的一面靠攏。

借由互相學習來調整群體面向，最後演化應該是會非常接近的群體。以人類來說，演化時間還不夠久看起來個體智慧與能力的分歧度還相當大。根據演化結果，由於互動機率因歧異性而下降，導致演化不會趨近于一。

粒子演算法三項重點：評估，比較，模仿

評估 - 目標函數值
比較 - 根據評估結果比較，根據機率還是特定條件符合後
模仿 - 將部分屬性（參數）模仿過來

操作

一開始把族群撒在特定區域，並且賦予牠一個初速度。
接著將會根據這個速度飛行。
但是同時會根據鄰近或區域最佳進行模仿，速度矢量會有兩條(原本和模仿)，兩個矢量根據參數調整後相加。
慢慢地朝著某個方向飛行，帶頭的也會往其他的地方飛行。

結語

單純模仿也行，只是要明白模仿對象是鄰居還是全局最佳。
單純模仿的壞處在於搜索中的過程路徑會相當短，但是迭代次數應該會比較少次。
如果是向鄰近模仿，可能是按照歐幾里德距離找最近幾個資料點。說不定會運用到 K-d Tree 這個資料結構。

反思題目

(25%) 請說明模糊系統的構成要件為何 ? 其功能分別是 ? 如何建立模糊系統 ?
其優缺點分別是 ?
大體要件：模糊化機構、模糊推論引擎、模糊規則庫、去模糊化系統。

模糊化機構：輸入有可信度問題，加以模糊。
模糊推論引擎：將數個模糊規則合併篩選用途。
模糊規則庫：每條規則將根據輸入產出相對應模糊輸出。
去模糊化系統：將模糊產出的圖，進行調整最後以向量形式輸出。

細節要件：模糊集合、模糊運算、模糊關係。

模糊集合：用來表示一個函數對於某個條件的歸屬程度。
模糊運算：表示每一個模糊集合之間的合成方法，用以做更複雜的組合。
模糊規則：明確判斷條件 if else 轉換成模糊的判斷條件，即為模糊規則。
模糊關係：在龐大的關係中，輔助綜合條件判斷的模型。

建造模糊系統：通常由專家提供的語意規則建造，否則將會使用均勻切割的方式去建造模糊系統。
優點：語意式的描述給予程式判斷上更大的彈性，不用撰寫非常明確的判斷條件於程式中，也能讓結果相當符合一般人的需求，而且後期可調整參數。
缺點：可能沒有專家協助，模糊定義上很難得到好的結果。相較於明確判斷，去模糊化的過程速度會慢上許多，以及模糊運算上動用到的函數複雜度與所需時間成正比。
(25%) 螞蟻是如何找到最短路徑 ? 請詳述 AS-TSP algorithm。
就是那個每次回合，依序放出螞蟻，螞蟻根據費洛蒙走判斷條件走，最佳的走法將會在下一次運行時，路徑上的費洛蒙額外增加。
(20%) 請詳述 RBF network 的架構為何 ? 如何訓練 RBF network ?
全名：Radial basis function network
架構有三層輸入層、隱藏層、輸出層。
要素為非線性激活函數、向量形式的輸入輸出。
在這門課中，採用基因算法來訓練它，根據與收集資料的誤差來當作適應程度，不斷地調整至好的參數。
而在線性可分割的高維空間中，可以利用數學函數的運算再加上一個微量調整的偏量相乘，將整個函數慢慢導向至最好結果。(曾經所說的向量疊加，新的法向量 = 所在的法向量 + 微量 * 資料表誤差表示出來的向量。)
(10%) 請說明有哪兩大類最佳化工具 ? 其優缺點分別為何 ?
- 特定型最佳化法則
  快，一個問題一個算法。同一算法能解決的問題少，幾乎都要客製化。
- 廣義型最佳化法則
  慢，無須根據問題調整算法。
(20%) 請詳述 Genetic algorithm。其優缺點分別為何 ? 如何改進其缺點 ?
優點

1 与问题领域无关切快速随机的搜索能力。
2 搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较，robust。
3 搜索使用评价函数启发，过程简单。
4 使用概率机制进行迭代，具有随机性。
5 具有可扩展性，容易与其他算法结合。

缺點

1 遗传算法的编程实现比较复杂，首先需要对问题进行编码，找到最优解之后还需要对问题进行解码。
2 另外三个算子的实现也有许多参数，如交叉率和变异率，并且这些参数的选择严重影响解的品质，而目前这些参数的选择大部分是依靠经验。
3 没有能够及时利用网络的反馈信息，故算法的搜索速度比较慢，要得要较精确的解需要较多的训练时间。
4 算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进。
5 算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的一个研究热点方向。

參考
(20%) 請詳述螞蟻算法。其優缺點分別為何 ? 如何改進其缺點 ?
優點

1 求解性能上，具有很强的鲁棒性（对基本蚁群算法模型稍加修改，便可以应用于其他问题）和搜索较好解的能力。
2 蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。
3 蚁群算法很容易与多种启发式算法结合，以改善算法性能。

缺點

基本蚁群算法计算量大，求解所需时间较长。

參考
(20%) 請詳述粒子算法。其優缺點分別為何 ? 如何改進其缺點 ?
優點

简单、易实现、计算量小和计算效率高

缺點

问题最主要的是它容易产生早熟收敛（尤其是在处理复杂的多峰搜索问题中）、局部寻优能力较差等。PSO 算法陷入局部最小，主要归咎于种群在搜索空间中多样性的丢失。

改善

（1）全局优化算法与局部优化算法混合
（2）全局优化算法与全局优化算法混合。纵观各种与 PSO 算法相关的混合算法，大多数基本上采用一种策略对其改进，要么与其他算法，要么加入变异操作，同时采用两种策略的混合算法较少。

參考

題外話

關於單一感知機
- 假設現在處於平面上，也就是說 f(xi, yi) = ci
  根據感知機會有三個變數，猶如 w[1] x + w[2] y + w[0]
  現在得到一堆 (xi, yi, ci) 是實際的情況，如何訓練感知機得到 w[] ?
  假設感知機會根據 (xi, yi) 產出 di
  根據調整參數 w’[i] = w[i] + wwww((yi - di))
  wwww 可以是任意函數，不過盡可能地介於 [0, 1]。
  會發現地，最後產出 di 會相當接近於 yi。
- 當處於線性可分割，也就是可以一刀把兩個群族分開，那麼感知機是會收斂得到好的結果。
- 也有另外一種方式，採用偏離向量的迭加，這個向量也會來自於產出的誤差效應。

Reference

NCU CSIE 計算型智慧課程

Morris' Blog