算法介紹
並行算法根據對象的不同分為數值並行算法和非數值並行算法兩種。
多項式與線性代數方程組，矩陣與非線性方程，插值、逼近及其套用，數位訊號處理，小波
變換，快速傅利耶變換等內容屬於數值算法。非數值算法一般包括線性表、棧、佇列和串，
樹，圖，排序、查找與檔案操作，並行算法等，主要是為符號運算而設計的並行算法。
常用的非數值並行算法有模擬退火算法、遺傳算法、神經網路算法等 。
模擬退火算法
模擬退火算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體
內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平
衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis 準則，粒子在溫度T 時趨於
平衡的機率為e-ΔE/(kT)，其中E 為溫度T 時的內能，ΔE 為其改變數，k 為Boltzmann 常
數。用固體退火模擬組合最佳化問題，將內能E 模擬為目標函式值f，溫度T 演化成控制參數
t，即得到解組合最佳化問題的模擬退火算法：由初始解i 和控制參數初值t 開始，對當前解重
復“產生新解→計算目標函式差→接受或捨棄”的疊代，並逐步衰減t 值，算法終止時的當
前解即為所得近似最優解，這是基於蒙特卡羅疊代求解法的一種啟發式隨機搜尋過程。退火
過程由冷卻進度表(Cooling Schedule)控制，包括控制參數的初值t 及其衰減因子Δt、每個t
值時的疊代次數L 和停止條件S。
1、模擬退火算法可以分解為解空間、目標函式和初始解三部分 。
解空間
它為問題的所有可能(可行的或包括不可行的)解的集合，它限定了初始解選取和新解產
生時的範圍。對無約束的最佳化問題，任一可能解(possible solution)即為一可行解(feasible
solution)，因此解空間就是所有可行解的集合；而在許多組合最佳化問題中，一個解除滿足目
標函式最優的要求外，還必須滿足一組約束(constraint)，因此在解集中可能包含一些不可行
解(infeasible so1ution)。為此，可以限定解空間僅為所有可行解的集合，即在構造解時就考
慮到對解的約束；也可允許解空間包含不可行解，而在目標函式中加上所謂罰函式(penalty
function)以“懲罰”不可行解的出現。
目標函式
它是對問題的最佳化目標的數學描述，通常表述為若干最佳化目標的一個和式。目標函式的
選取必須正確體現對問題的整體最佳化要求。例如，如上所述，當解空間包含不可行解時，目
標函式中應包含對不可行解的罰函式項，藉此將一個有約束的最佳化問題轉化為無約束的最佳化
問題。一般地，目標函式值不一定就是問題的最佳化目標值，但其對應關係應是顯明的。此外，
目標函式式應當是易於計算的，這將有利於在最佳化過程中簡化目標函式差的計算以提高算法
的效率 。
初始解
基本思想：
(1) 初始化：初始溫度T(充分大)，初始解狀態S(是算法疊代的起點)， 每個T 值的迭
代次數L
(2) 對k=1，，L 做第(3)至第6 步：
(3) 產生新解S′
(4) 計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函式
(5) 若Δt′<0 則接受S′作為新的當前解，否則以機率exp(-Δt′/T)接受S′作為新的
當前解.
(6) 如果滿足終止條件則輸出當前解作為最優解，結束程式。
終止條件通常取為連續若干個新解都沒有被接受時終止算法。
(7) T 逐漸減少，且T->0，然後轉第2 步。
二、遺傳算法
遺傳算法的基本思想是基於Darwin 進化論和Mendel 的遺傳學說的。
Darwin 進化論最重要的是適者生存原理。它認為每一物種在發展中越來越適應環境。物種
每個個體的基本特徵由後代所繼承，但後代又會產生一些異於父代的新變化。在環境變化時，
只有那些能適應環境的個體特徵方能保留下來。
Mendel 遺傳學說最重要的是基因遺傳原理。它認為遺傳以密碼方式存在細胞中，並以基因
形式包含在染色體內。每個基因有特殊的位置並控制某種特殊性質；所以，每個基因產生的
個體對環境具有某種適應性。基因突變和基因雜交可產生更適應於環境的後代。經過存優去
劣的自然淘汰，適應性高的基因結構得以保存下來。
遺傳算法簡稱GA(Genetic Algorithm)，在本質上是一種不依賴具體問題的直接搜尋方法。
1、遺傳算法的原理
遺傳算法GA 把問題的解表示成“染色體”，在算法中也即是以二進制編碼的串。並且，在
執行遺傳算法之前，給出一群“染色體”，也即是假設解。然後，把這些假設解置於問題的
“環境”中，並按適者生存的原則，從中選擇出較適應環境的“染色體”進行複製，再通過
交叉，變異過程產生更適應環境的新一代“染色體”群。這樣，一代一代地進化，最後就會
收斂到最適應環境的一個“染色體”上，它就是問題的最優解。
長度為L 的n 個二進制串bi(i=1，2，，n)組成了遺傳算法的初解群，也稱為初始群體。
在每個串中，每個二進制位就是個體染色體的基因。根據進化術語，對群體執行的操作有三
種：
（1）．選擇(Selection)
這是從群體中選擇出較適應環境的個體。這些選中的個體用於繁殖下一代。故有時也稱這一
操作為再生(Reproduction)。由於在選擇用於繁殖下一代的個體時，是根據個體對環境的適
應度而決定其繁殖量的，故而有時也稱為非均勻再生(differential reproduction)。
（2）．交叉(Crossover)
這是在選中用於繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進行交換，從而
產生新的個體。
（3）．變異(Mutation)
這是在選中的個體中，對個體中的某些基因執行異向轉化。在串bi 中，如果某位基因為1，
產生變異時就是把它變成0；反亦反之。
2、遺傳算法的特點
（1）．遺傳算法從問題解的中集開始嫂索，而不是從單個解開始。
這是遺傳算法與傳統最佳化算法的極大區別。傳統最佳化算法是從單個初始值疊代求最優解的；
容易誤入局部最優解。遺傳算法從串集開始搜尋，覆蓋面大，利於全局擇優。
（2）．遺傳算法求解時使用特定問題的信息極少，容易形成通用算法程式。
由於遺傳算法使用適應值這一信息進行搜尋，並不需要問題導數等與問題直接相關的信息。
遺傳算法只需適應值和串編碼等通用信息，故幾乎可處理任何問題。
（3）．遺傳算法有極強的容錯能力
遺傳算法的初始串集本身就帶有大量與最優解甚遠的信息；通過選擇、交叉、變異操作能迅
速排除與最優解相差極大的串；這是一個強烈的濾波過程；並且是一個並行濾波機制。故而，
遺傳算法有很高的容錯能力。
（4）．遺傳算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。
這說明遺傳算法是採用隨機方法進行最優解搜尋，選擇體現了向最優解迫近，交叉體現了最
優解的產生，變異體現了全局最優解的覆蓋。
三、神經網路算法
“人工神經網路”(ARTIFICIAL NEURAL NETWORK，簡稱A.N.N.)是在對人腦組織結構和
運行機智的認識理解基礎之上模擬其結構和智慧型行為的一種工程系統。早在本世紀40 年代
初期，心理學家McCulloch、數學家Pitts 就提出了人工神經網路的第一個數學模型，從此開
創了神經科學理論的研究時代。其後，F.Rosenblatt、Widrow 和Hopf、J.J.Hopfield 等學者又
先後提出了感知模型，使得人工神經網路技術得以蓬勃發展。
神經系統的基本構造是神經元(神經細胞)，它是處理人體內各部分之間相互信息傳遞的基本
單元。據神經生物學家研究的結果表明，人的一個大腦一般有10 10 ～10 11
個神經元。每個神經元都由一個細胞體，一個連線其他神經元的軸突和一些向外伸出的其它
較短分支——樹突組成。軸突的功能是將本神經元的輸出信號(興奮)傳遞給別的神經元。其
末端的許多神經末梢使得興奮可以同時傳送給多個神經元。樹突的功能是接受來自其它神經
元的興奮。神經元細胞體將接受到的所有信號進行簡單地處理(如：加權求和，即對所有的
輸入信號都加以考慮且對每個信號的重視程度——體現在權值上——有所不同)後由軸突輸
出。神經元的樹突與另外的神經元的神經末梢相連的部分稱為突觸。
1、神經網路的工作原理
人工神經網路首先要以一定的學習準則進行學習，然後才能工作。現以人工神經網路對手寫
“A”、“B”兩個字母的識別為例進行說明，規定當“A”輸入網路時，應該輸出“1”，而
當輸入為“B”時，輸出為“0”。所以網路學習的準則應該是：如果網路作出錯誤的的判決，
則通過網路的學習，應使得網路減少下次犯同樣錯誤的可能性。首先，給網路的各連線權值
賦予(0，1)區間內的隨機值，將“A”所對應的圖象模式輸入給網路，網路將輸入模式加權
求和、與門限比較、再進行非線性運算，得到網路的輸出。在此情況下，網路輸出為“1”
和“0”的機率各為50%，也就是說是完全隨機的。這時如果輸出為“1”(結果正確)，則使
連線權值增大，以便使網路再次遇到“A”模式輸入時，仍然能作出正確的判斷。如果輸出
為“0”(即結果錯誤)，則把網路連線權值朝著減小綜合輸入加權值的方向調整，其目的在
於使網路下次再遇到“A”模式輸入時，減小犯同樣錯誤的可能性。如此操作調整，當給網
絡輪番輸入若干個手寫字母“A”、“B”後，經過網路按以上學習方法進行若干次學習後，
網路判斷的正確率將大大提高。這說明網路對這兩個模式的學習已經獲得了成功，它已將這
兩個模式分布地記憶在網路的各個連線權值上。當網路再次遇到其中任何一個模式時，能夠
作出迅速、準確的判斷和識別。一般說來，網路中所含的神經元個數越多，則它能記憶、識
別的模式也就越多。
2、人工神經網路的特點
人工神經網路是由大量的神經元廣泛互連而成的系統，它的這一結構特點決定著人工神經網
絡具有高速信息處理的能力。人腦的每個神經元大約有10 3～10 4 個樹突及相應的突
觸，一個人的大腦總計約形成10 14 ～10 15 個突觸。用神經網路的術語來說，
即是人腦具有10 14 ～10 15 個互相連線的存儲潛力。雖然每個神經元的運算
功能十分簡單，且信號傳輸速率也較低(大約100 次/秒)，但由於各神經元之間的極度並行互
連功能，最終使得一個普通人的大腦在約1 秒內就能完成現行計算機至少需要數10 億次處
理步驟才能完成的任務。
人工神經網路的知識存儲容量很大。在神經網路中，知識與信息的存儲表現為神經元之間分
布式的物理聯繫。它分散地表示和存儲於整個網路內的各神經元及其連線上。每個神經元及
其連線只表示一部分信息，而不是一個完整具體概念。只有通過各神經元的分散式綜合效果
才能表達出特定的概念和知識。
由於人工神經網路中神經元個數眾多以及整個網路存儲信息容量的巨大，使得它具有很強的
不確定性信息處理能力。即使輸入信息不完全、不準確或模糊不清，神經網路仍然能夠聯想
思維存在於記憶中的事物的完整圖象。只要輸入的模式接近於訓練樣本，系統就能給出正確
的推理結論。
正是因為人工神經網路的結構特點和其信息存儲的分散式特點，使得它相對於其它的判斷識
別系統，如：專家系統等，具有另一個顯著的優點：健壯性。生物神經網路不會因為個別神
經元的損失而失去對原有模式的記憶。最有力的證明是，當一個人的大腦因意外事故受輕微
損傷之後，並不會失去原有事物的全部記憶。人工神經網路也有類似的情況。因某些原因，
無論是網路的硬體實現還是軟體實現中的某個或某些神經元失效，整個網路仍然能繼續工
作。
人工神經網路是一種非線性的處理單元。只有當神經元對所有的輸入信號的綜合處理結果超
過某一門限值後才輸出一個信號。因此神經網路是一種具有高度非線性的超大規模連續時間
動力學系統。它突破了傳統的以線性處理為基礎的數字電子計算機的局限，標誌著人們智慧型
信息處理能力和模擬人腦智慧型行為能力的一大飛躍。
