計算型智慧
文章簡介
- 下學期修了這門課，這其中會與另一門類神經網路有關。
- 中間穿插工數和微積分的一些數學名詞。
- 接著，您將會看到一系列筆者對計算型智慧的認知。
- 看到以下內容，雖有數學模型、演算法成份，但主體為模擬自然界的各種思維。
算法設計
特定型最佳化法則
根據函數的特性，衍伸出來的搜尋方式，目標函數有特別性質，例如：線性、微分 … 等。微分法、梯度法都是屬於此類。再講白一點，一般大學時學的演算法都是如此，通常是具有最佳化結構的情況，因此會有最短路徑算法、二分搜尋、三分搜尋 … 等。
廣義型最佳化法則
不管目標函數的特性為何，無須修改設計法則，亂做一通、隨機搜索、以及接下來講的主題都屬此類。
模糊系統
模型簡介
- 一般程式撰寫判斷條件相當精準，同時也不好做修正，畢竟一般人看不懂那麼多 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 要取多少。
- 中間要不要遵守遞移律、交換律、結合律？照理來講是要的。
不過想吐槽的是，都這麼模糊了，還要遵守這三律嗎？
建造模糊規則
模糊化類神經網路 … 略
結語
- 運算方式，跟編程複雜度有關。
- 函數式最好寫，但是彈性不高，產出結果通常有限(多樣性)。
- 如果採用非連續性的就很痛苦，通常會使用離散化取數值分析，可用重心法。
- 有重心法、肯定有眾數、中數法。
- 一般來說函數式就夠用，世界萬物都是簡單構成複雜。
- 可以利用收集資料，讓類神經網路產生演化結果 (稍後會提到)，神經應該也是模糊的！
- 收集到的資料正確性不知道有多高，根據簡單的投影法則，也可以變成模糊系統(初版)。
模擬退火
簡介
「模擬退火來自冶金學的專有名詞退火。退火是將材料加熱後再經特定速率冷卻，目的是增大晶粒的體積，並且減少晶格中的缺陷。」取自 wiki
簡單的說，膨脹去雜質，冷卻來精煉。冷卻得到區域最佳解，膨脹增加得到全局最佳解的機率。
操作
- 以 f(x, y) = z 的函數，要找到全局最小值，圖形看起來就是 3D 模型。
水往低處流，人往低處走
- 當現在在 (x, y) 時，笨的方式就是往四處看看，看哪邊更小就往哪裡走出下一步。而高明的作法則是根據梯度(微分來了)低的地方走，您就講想您有一個重力感測器。
- 步伐將會越來越小，這樣才能步步靠近區域最佳解。
- 當相當靠近區域最佳解時，變小幅度(dx/dt)太小，那就跳到更遠的地方去吧，相當於容忍較差的環境。
- 什麼時候容忍？可以根據某些指數函數結果跟隨機亂數比大小。
結語
基因算法
簡介
又稱 GA 算法，模擬生物遺傳的過程，根據「物競天擇，適者生存」的演化論，最後會得到最好的解答。而進行演化就是染色體的事情了，當一開始的多樣性夠，再搭配突變情況交織出來，那崇高的自然藝術便會出現。
看看人類，您覺得有適者生存嗎？那這樣會進化嗎？
有空去搜尋電影－《蠢蛋進化論》看看不願面對的真相？
操作
- 將資料表示成基因片段，最簡單為二進編碼，當然也可以用實數。
資料是什麼？函數的常數參數，來驅使我們的模型可以更接近收集出來的數據。
- 第一步－初始化物種
隨機產生基因片段，或者來個生物大滅絕保留可能好的再隨機生成。
- 第二步－適應環境
越接近收集出來的數據(差值總和越小)，適應力越高。這就相當於成長階段。
- 第三步－擇偶
通常適應度高的會配在一起，就如人類有反例，這沒有絕對。
- 第四步－交配
交配方式如同染色體行減數分裂後的運作，將某幾段進行交換，而生物染色體只會切一刀然後配對，因為當初的雙股螺旋 … 各種原因，反正就是生物物質關係。如果是實數，則可以想像成會生成拉近關係或者是拉遠關係的結果。
兩個好的物種交配，也不見得子代會好。
- 第五步－突變
個體突變，染色體的 01 互換機率，或者在實數方面特化或者是弱化(就是乘實數)。
設定集
結語
- 應用－使用類神經網路的模型，利用基因算法找到最佳解。而每個神經元都有搭配的參數，就是把參數基因化，調用基因算法。
幾句話說明類神經網路
每個神經元根據所受到的刺激產出一個定值，而神經元也有階層關係，每一個階層間會互相刺激，最外層吸收外界資訊，慢慢細化傳入最後階段的神經元來反應。而 ‘刺激到產出’ 可以猜想為加權平均。
- 實作後，這種算法必須應用在接近連續層面上會比較好，離散函數的問題效果不彰，也就是會有一些額外的判斷條件。
- 擇偶相當困擾，通常根據隨機亂數，在排序後做選擇。
- 交配相當刺激，同時也是最難抉擇的地方，個人造化。
- 要不要適應繁殖？都行，適應好的物種就多複製幾個！// 看您要不要固定，不然數量會爆炸，或者加入篩選。
- 大量繁殖大量突變，造就爆炸效應！(在鄰近空間進行爆炸找更好的地方)
- 最後根本就是在玩突變，突變算法就此誕生！
螞蟻算法
簡介
螞蟻單一功能低，群體完成最佳化。螞蟻行動過程中會留下費洛蒙，隨著時間費洛蒙也會下降，在這反反覆覆的過程中，蟻群很有機會開創出全局最佳解。
螞蟻雖小，亦能驅象。
操作
設定集
- 費洛蒙的濃度消散函數
- 螞蟻根據費洛蒙濃度的選擇函數
結語
- 應用方面
- 分群，把文章分類。
- 搜索，各種 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
