非數值算法

並行算法根據對象的不同分為數值並行算法和非數值並行算法兩種。

多項式與線性代數方程組，矩陣與非線性方程，插值、逼近及其應用，數字信號處理，小波變換，快速傅利耶變換等內容屬於數值算法。非數值算法一般包括線性表、棧、隊列和串，樹，圖，排序、查找與文件操作，並行算法等，主要是為符號運算而設計的並行算法。

常用的非數值並行算法有模擬退火算法、遺傳算法、神經網絡算法等 ^[1]  。

模擬退火算法來源於固體退火原理，將固體加温至充分高，再讓其徐徐冷卻，加温時，固體內部粒子隨温升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個温度都達到平衡態，最後在常温時達到基態，內能減為最小。根據Metropolis準則，粒子在温度T時趨於平衡的概率為e-ΔE/（kT），其中E為温度T時的內能，ΔE為其改變量，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，温度T演化成控制參數t，即得到解組合優化問題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重複“產生新解→計算目標函數差→接受或捨棄”的迭代，並逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基於蒙特卡羅迭代求解法的一種啓發式隨機搜索過程。退火過程由冷卻進度表（CoolingSchedule）控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。

1、模擬退火算法可以分解為解空間、目標函數和初始解三部分。

它為問題的所有可能（可行的或包括不可行的）解的集合，它限定了初始解選取和新解產生時的範圍。對無約束的優化問題，任一可能解（possiblesolution）即為一可行解（feasiblesolution），因此解空間就是所有可行解的集合；而在許多組合優化問題中，一個解除滿足目標函數最優的要求外，還必須滿足一組約束（constraint），因此在解集中可能包含一些不可行解（infeasibleso1ution）。為此，可以限定解空間僅為所有可行解的集合，即在構造解時就考慮到對解的約束；也可允許解空間包含不可行解，而在目標函數中加上所謂罰函數（penaltyfunction）以“懲罰”不可行解的出現。

它是對問題的優化目標的數學描述，通常表述為若干優化目標的一個和式。目標函數的選取必須正確體現對問題的整體優化要求。例如，如上所述，當解空間包含不可行解時，目標函數中應包含對不可行解的罰函數項，藉此將一個有約束的優化問題轉化為無約束的優化問題。一般地，目標函數值不一定就是問題的優化目標值，但其對應關係應是顯明的。此外，目標函數式應當是易於計算的，這將有利於在優化過程中簡化目標函數差的計算以提高算法的效率 ^[2]  。

基本思想：

（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（GeneticAlgorithm），在本質上是一種不依賴具體問題的直接搜索方法。

遺傳算法GA把問題的解表示成“染色體”，在算法中也即是以二進制編碼的串。並且，在執行遺傳算法之前，給出一羣“染色體”，也即是假設解。然後，把這些假設解置於問題的“環境”中，並按適者生存的原則，從中選擇出較適應環境的“染色體”進行復制，再通過交叉，變異過程產生更適應環境的新一代“染色體”羣。這樣，一代一代地進化，最後就會收斂到最適應環境的一個“染色體”上，它就是問題的最優解。

長度為L的n個二進制串bi（i=1，2，…，n）組成了遺傳算法的初解羣，也稱為初始羣體。

在每個串中，每個二進制位就是個體染色體的基因。根據進化術語，對羣體執行的操作有三種：

（1）選擇（Selection）

這是從羣體中選擇出較適應環境的個體。這些選中的個體用於繁殖下一代。故有時也稱這一操作為再生（Reproduction）。由於在選擇用於繁殖下一代的個體時，是根據個體對環境的適應度而決定其繁殖量的，故而有時也稱為非均勻再生（differentialreproduction）。

（2）交叉（Crossover）

這是在選中用於繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進行交換，從而產生新的個體。

（3）變異（Mutation）

這是在選中的個體中，對個體中的某些基因執行異向轉化。在串bi中，如果某位基因為1，產生變異時就是把它變成0；反亦反之。

（1）遺傳算法從問題解的中集開始嫂索，而不是從單個解開始。

這是遺傳算法與傳統優化算法的極大區別。傳統優化算法是從單個初始值迭代求最優解的；容易誤入局部最優解。遺傳算法從串集開始搜索，覆蓋面大，利於全局擇優。

（2）遺傳算法求解時使用特定問題的信息極少，容易形成通用算法程序。

由於遺傳算法使用適應值這一信息進行搜索，並不需要問題導數等與問題直接相關的信息。遺傳算法只需適應值和串編碼等通用信息，故幾乎可處理任何問題。

（3）遺傳算法有極強的容錯能力。

遺傳算法的初始串集本身就帶有大量與最優解甚遠的信息；通過選擇、交叉、變異操作能迅速排除與最優解相差極大的串；這是一個強烈的濾波過程；並且是一個並行濾波機制。故而，遺傳算法有很高的容錯能力。

（4）遺傳算法中的選擇、交叉和變異都是隨機操作，而不是確定的精確規則。

這説明遺傳算法是採用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最優解的產生，變異體現了全局最優解的覆蓋。

“人工神經網絡”（ARTIFICIALNEURALNETWORK，簡稱A.N.N.）是在對人腦組織結構和運行機智的認識理解基礎之上模擬其結構和智能行為的一種工程系統。早在本世紀40年代初期，心理學家McCulloch、數學家Pitts就提出了人工神經網絡的第一個數學模型，從此開創了神經科學理論的研究時代。其後，F.Rosenblatt、Widrow和Hopf、J.J.Hopfield等學者又先後提出了感知模型，使得人工神經網絡技術得以蓬勃發展。神經系統的基本構造是神經元（神經細胞），它是處理人體內各部分之間相互信息傳遞的基本單元。據神經生物學家研究的結果表明，人的一個大腦一般有1010～1011個神經元。每個神經元都由一個細胞體，一個連接其他神經元的軸突和一些向外伸出的其它較短分支——樹突組成。軸突的功能是將本神經元的輸出信號（興奮）傳遞給別的神經元。其末端的許多神經末梢使得興奮可以同時傳送給多個神經元。樹突的功能是接受來自其它神經元的興奮。神經元細胞體將接受到的所有信號進行簡單地處理（如：加權求和，即對所有的輸入信號都加以考慮且對每個信號的重視程度——體現在權值上——有所不同）後由軸突輸出。神經元的樹突與另外的神經元的神經末梢相連的部分稱為突觸。

人工神經網絡首先要以一定的學習準則進行學習，然後才能工作。現以人工神經網絡對手寫“A”、“B”兩個字母的識別為例進行説明，規定當“A”輸入網絡時，應該輸出“1”，而當輸入為“B”時，輸出為“0”。所以網絡學習的準則應該是：如果網絡作出錯誤的的判決，則通過網絡的學習，應使得網絡減少下次犯同樣錯誤的可能性。首先，給網絡的各連接權值賦予（0，1）區間內的隨機值，將“A”所對應的圖象模式輸入給網絡，網絡將輸入模式加權求和、與門限比較、再進行非線性運算，得到網絡的輸出。在此情況下，網絡輸出為“1”和“0”的概率各為50%，也就是説是完全隨機的。這時如果輸出為“1”（結果正確），則使連接權值增大，以便使網絡再次遇到“A”模式輸入時，仍然能作出正確的判斷。如果輸出為“0”（即結果錯誤），則把網絡連接權值朝着減小綜合輸入加權值的方向調整，其目的在於使網絡下次再遇到“A”模式輸入時，減小犯同樣錯誤的可能性。如此操作調整，當給網絡輪番輸入若干個手寫字母“A”、“B”後，經過網絡按以上學習方法進行若干次學習後，網絡判斷的正確率將大大提高。這説明網絡對這兩個模式的學習已經獲得了成功，它已將這兩個模式分佈地記憶在網絡的各個連接權值上。當網絡再次遇到其中任何一個模式時，能夠作出迅速、準確的判斷和識別。一般説來，網絡中所含的神經元個數越多，則它能記憶、識別的模式也就越多。

人工神經網絡是由大量的神經元廣泛互連而成的系統，它的這一結構特點決定着人工神經網絡具有高速信息處理的能力。人腦的每個神經元大約有103～104個樹突及相應的突觸，一個人的大腦總計約形成1014～1015個突觸。用神經網絡的術語來説，即是人腦具有1014～1015個互相連接的存儲潛力。雖然每個神經元的運算功能十分簡單，且信號傳輸速率也較低（大約100次/秒），但由於各神經元之間的極度並行互連功能，最終使得一個普通人的大腦在約1秒內就能完成現行計算機至少需要數10億次處理步驟才能完成的任務。

人工神經網絡的知識存儲容量很大。在神經網絡中，知識與信息的存儲表現為神經元之間分佈式的物理聯繫。它分散地表示和存儲於整個網絡內的各神經元及其連線上。每個神經元及其連線只表示一部分信息，而不是一個完整具體概念。只有通過各神經元的分佈式綜合效果才能表達出特定的概念和知識。

由於人工神經網絡中神經元個數眾多以及整個網絡存儲信息容量的巨大，使得它具有很強的不確定性信息處理能力。即使輸入信息不完全、不準確或模糊不清，神經網絡仍然能夠聯想思維存在於記憶中的事物的完整圖象。只要輸入的模式接近於訓練樣本，系統就能給出正確的推理結論。

正是因為人工神經網絡的結構特點和其信息存儲的分佈式特點，使得它相對於其它的判斷識別系統，如：專家系統等，具有另一個顯著的優點：健壯性。生物神經網絡不會因為個別神經元的損失而失去對原有模式的記憶。最有力的證明是，當一個人的大腦因意外事故受輕微損傷之後，並不會失去原有事物的全部記憶。人工神經網絡也有類似的情況。因某些原因，無論是網絡的硬件實現還是軟件實現中的某個或某些神經元失效，整個網絡仍然能繼續工作。

人工神經網絡是一種非線性的處理單元。只有當神經元對所有的輸入信號的綜合處理結果超過某一門限值後才輸出一個信號。因此神經網絡是一種具有高度非線性的超大規模連續時間動力學系統。它突破了傳統的以線性處理為基礎的數字電子計算機的侷限，標誌着人們智能信息處理能力和模擬人腦智能行為能力的一大飛躍。