全局搜索演算法

❶ 粒子群演算法為什麼具有全局搜索能力

粒子群演算法中每個粒子都記憶自己的最好位置，即從進化開始到現在這個粒子能使目標函數達到最大或是最小的那個時刻粒子的位置。個體極值就是粒子在最好位置所得到的目標函數的值。全局極值就是在所有粒子的個體極值中最大或是最小的那個值，與只對應的就是全局最優粒子的位置。對有約束的優化函數，一般是將約束條件加入到目標函數中，然後計算總體的值，以此來作為評價標准。
粒子群演算法，也稱粒子群優化演算法（Particle Swarm Optimization），縮寫為 PSO， 是近年來發展起來的一種新的進化演算法(Evolutionary Algorithm - EA)。PSO 演算法屬於進化演算法的一種，和模擬退火演算法相似，它也是從隨機解出發，通過迭代尋找最優解，它也是通過適應度來評價解的品質，但它比遺傳演算法規則更為簡單，它沒有遺傳演算法的「交叉」(Crossover) 和「變異」(Mutation) 操作，它通過追隨當前搜索到的最優值來尋找全局最優。這種演算法以其實現容易、精度高、收斂快等優點引起了學術界的重視，並且在解決實際問題中展示了其優越性。粒子群演算法是一種並行演算法。

❷ 什麼是局部搜索演算法

局部搜索演算法是從爬山法改進而來的。
簡單來說，局部搜索演算法是一種簡單的貪心搜索演算法，該演算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。
在計算機科學中，局部搜索是解決最優化問題的一種元啟發式演算法。局部搜索從一個初始解出發，然後搜索解的鄰域，如有更優的解則移動至該解並繼續執行搜索，否則返回當前解。
1、局部搜索演算法的基本思想：
在搜索過程中，始終選擇當前點的鄰居中與離目標最近者的方向搜索。
2、局部搜索的優點：
簡單、靈活及易於實現，缺點是容易陷入局部最優且解的質量與初始解和鄰域的結構密切相關。常見的改進方法有模擬退火、禁忌搜索等。
3、局部搜索廣泛應用：
計算機科學（主要是人工智慧）、數學、運籌學、工程學、生物信息學中各種很難找到全局最優解的計算問題。

❸ 啟發式搜索全局擇優搜索和局部擇優搜索的區別是什麼

根據問題的實際情況不斷尋找可利用的知識，從而構造成一條代價較少的推理路線，使問題得到圓滿解決的過程稱為搜索。

尋找問題的解的一種可靠的方法是首先列出所有候選解，然後依次檢查每一個解，即可以找到所需要的問題的答案。這是一種「萬能」的方法，理論上，當候選解的數量可以窮盡並且通過檢查所有或部分候選解能夠得到所需解時，問題就能得到解決。

但是，在實際應用中，因為候選解的數量通常都非常大（比如指數級），並且計算機的速度和內存都有限制，因此對問題不加分析的窮盡演算法通常只能解決規模很小的問題。

在實際運用中常採用回溯和分枝定界法對問題進行求解。按照這兩種方法對候選解進行系統檢查通常會使問題的求解時間大大減少（無論對於最壞情形還是對於一般情形）。這二種方法由於都是按規定的路線進行，基本沒有使用與問題有關的啟發性信息，屬於盲目搜索策略。在涉及人工職能的有些問題如博弈問題時，還會用到啟發是搜索策略，如A*演算法等。

一、回溯法和分枝限界法

問題的表示

狀態空間表示法是表示問題及其搜索過程的一種形式表示方法。可以用解空間樹來表示問題的結構。 對於一棵樹，樹中的每一個結點確定所求問題的一個問題狀態，由根結點到其它結點的所有路徑確定了這個問題的狀態空間。解狀態是一些問題狀態S，對於這些問題狀態，由根到S的那條路徑確定了這解空間的一個元組。答案狀態則是由解狀態到根的路徑。

對於一種狀態空間樹，可以先系統地生成問題的狀態，接著確定問題狀態的解狀態，最後確定那些解狀態是答案狀態從而將這些問題解出。

從根結點開始解問題，如果已經生成一個結點而它的所有兒子結點還沒有全部生成，則這個結點叫做活結點。當前正在生成其兒子的活結點叫E結點，不再進一步擴展或者其兒子結點已經全部生成的生成結點就是死結點。

回溯演算法使用深度優先方法搜索樹結構，而分枝定界一般用寬度優先方法來搜索這些樹。

回溯方法的步驟如下：

1) 定義一個解空間，它包含問題的解。

2) 用適於搜索的方式組織該空間。

3) 用深度優先法搜索該空間，利用限界函數避免移動到不可能產生解的子空間。

回溯演算法的特性是在搜索執行的同時產生解空間。在搜索期間的任何時刻，僅保留從開始節點到當前E -節點的路徑。因此，回溯演算法的空間需求為O（從開始節點起最長路徑的長度）。

分枝限界法的步驟和回溯的唯一區別是採用了寬度優先的方法來搜索樹，因此分枝法消耗的空間比回溯法要多。

這二種搜索策略從本質上來講都是屬於窮盡法的搜索，由於在搜索路徑上的不同也造成這二種方法各自都有其優缺點、適用的求解問題也就不同。

寬度優先佔有優勢的問題：

九宮重排問題

九宮重排問題是一個可以回溯法和分枝法都能解決的問題。但是，對於這個問題運用分枝法是有利的。

九宮重排問題，在3*3的方格棋盤上放置標由數字1、2、3、4、5、6、7、8共8個棋子，初始狀態為S 0 ，目標狀態為Sg ，當找到一個解時結束搜索。

從根結點到葉子結點的路徑即為解，演算法為空格左移，空格上移，空格右移，空格下移。

S0

Sg

2
8
3

1
2
3

1

4

8

4

7
6
5

7
6
5

用寬度優先搜索，如下圖：

f'(x) = g(x) + h(x)

2 8 3

14

7 6 5

2 8 3

1 4

7 6 5

23

1 8 4

7 6 5

3 8 2

1 6 4

75

3 8 2

1 4

7 6 5

8 3

2 1 4

7 6 5

3 8 2

14

7 6 5

82

2 1 4

7 6 5

2 3 4

1 8

7 6 5

1 2 3

8 4

7 6 5

2 3

1 8 4

7 6 5

2 3

1 8 4

7 6 5

2 8 3

1 6 4

7 5

2 8 3

1 6 4

7 5

3 8 2

14

7 6 5

2 8 3

1 6

7 5 4

2 8 3

6 4

1 7 5

2 8 3

1 4 5

76

28

1 4 3

7 6 5

2 8 3

1 4 5

7 6

28

1 4 3

7 6 5

2 8 3

7 1 4

6 5

2 8 3

74

6 1 5

8 1 3

24

7 6 5

8 3 2

2 1 4

7 6 5

1 2 3

84

7 6 5

16

26

9

8

7

6

2

1

S0

4

3

5

Sg

圖示解的路徑是 S0-3-8-16-26(Sg)

寬度優先搜索的盲目性較大，當目標結點距離初始結點較遠時將會產生許多無用結點，空間浪費較大，搜索效率低，但是只要問題有解，用寬度優先搜索總可以得到解，而且得到的路徑最短的解。

用深度優先策略搜索，如下圖：

2 8 3

14

7 6 5

2 8 3

1 4

7 6 5

23

1 8 4

7 6 5

3 8 2

1 6 4

7 5

3 8 2

1 4

7 6 5

2 8 3

1 6 4

7 5

2 8 3

1 6 4

7 5

2 8 3

1 6

7 5 4

1

S0

2

2 8

1 6 3

7 5 4

2 8 1 6 3

7 5 4

2 8

1 6 3

7 5 4

3

4

5

6

在深度優先搜索中，搜索一旦進入某個分枝，就將沿著該分枝一直向下搜索，如果該節點恰好在此分支上，則可較快地得到解。但是，如果目標節電不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。

顯然該問題用寬度優先搜索的策略是較好的。

經典的N皇後問題

N皇後問題要求求出N個皇後在棋盤上的所有擺法，（該問題很多書籍上都有詳細介紹，這兒圖表省略），該問題是適合用回溯法來描述和解決的問題，通過深度優先搜索至多需要檢索N!個元組，而如果用分枝法，因為要生成所有問題的解，則必須儲存檢索過程中的E結點，造成儲存空間的極度膨脹，這類問題明顯是用回溯法佔優勢的。

回溯法和分枝法是基本的搜索策略，大多數情況下如果找不到更好的解決方案，總是可以用這二種方法嘗試。

但是它們有一個很大的缺陷就是都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。它的效率實在太低，甚至不可完成。



二、啟發式搜索演算法
通常在搜索中能直接運用回溯、分枝法的問題並不多，回溯和分枝的過程中，施加一定的條件，對搜索過程中出現的結點進行判斷，可以提高效率。

啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是關鍵。採用了不同的估價可以有不同的效果。

啟發式搜索有很多的演算法，如：局部擇優搜索法、最好優先搜索法等等。A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。

局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。

局部擇優搜索法它是對深度優先搜索方法的一種改進。

全局擇優搜索是 局部擇優搜索的一種改進，試圖克服局部擇優搜索的的局限性。再搜索時，每次總是從全體的活結點中選取一個估價值最小的節點，

在搜索過程中，啟發式搜索的關鍵是要確定下一個要考察的節點，用於估價節點重要性的函數稱為估價函數

f'(x) = g(x) + h(x)

其中g(x)為從初始節點So到節點X已經實際付出的代價；h(x)是從節點X到節點Sg的最優路徑的估計代價。h(x)稱為啟發函數。

九宮重排

當用全局擇優搜索求解該問題時，可以設估價函數為 f'(x) = d(x) + h(x)

d(x)表示節點x的深度，h(x)表示節點x的棋局與目標節點棋局位置不相同的棋子數。

2 8 3

14

7 6 5

2 8 3

1 4

7 6 5

23

1 8 4

7 6 5

3 8 2

1 6 4

75

3 8 2

1 4

7 6 5

8 3

2 1 4

7 6 5

3 8 2

14

7 6 5

1 2 3

8 4

7 6 5

2 3

1 8 4

7 6 5

2 3

1 8 4

7 6 5

1 2 3

84

7 6 5

4

6

4

6

6

4

1

S0

4

4

5

Sg

1 2 3

7 8 4

6 5

5

5

S3

S2

S1

圖中節點旁標明的數字是該節點的估價函數值。

該問題的解路徑為： So-S1-S2-S3-Sg

以上論述一些樹型問題基本的搜索的策略，當問題的狀態空間是有向圖時，節點的重復將導致大量冗餘的搜索，甚至時搜索過程陷入無效的循環而無法找到解，這時就需要對估價函數進行限制，A*演算法就是針對圖的有序搜索的演算法。



問題的求解可以有很多方法，而如何建立數學模型，選擇問題的求解方式是十分重要的，方法的好壞是面向一個具體的問題的，需要具體問題具體分析

❹ 什麼搜索演算法是全局優化的呀，不要局部的

梯度下降或者牛頓法？要是能夠確定函數式凸函數這樣似乎可以解決。要是不行的話，就只能用一些啟發性的搜索演算法了

❺ 混合遺傳演算法和遺傳演算法有什麼區別

遺傳演算法是一種全局搜索演算法，不需要目標函數的導數信息，它能夠很快搜索到最優值所處范圍范圍。
而混合遺傳演算法是在遺傳演算法的基礎上引入其它優化演算法（如局部尋優能力強的演算法），以保證遺傳演算法全局性能的基礎上大大減小計算量，提高收斂速度。一般引入的演算法有：傳統梯度類演算法、單純形法及模擬退火等等）這些演算法都很容易與遺傳演算法兼容。

❻ 智能演算法的演算法分類

模擬退火演算法的依據是固體物質退火過程和組合優化問題之間的相似性。物質在加熱的時候，粒子間的布朗運動增強，到達一定強度後，固體物質轉化為液態，這個時候再進行退火，粒子熱運動減弱，並逐漸趨於有序，最後達到穩定。
模擬退火的解不再像局部搜索那樣最後的結果依賴初始點。它引入了一個接受概率p。如果新的點（設為pn）的目標函數f（pn）更好，則p=1，表示選取新點；否則，接受概率p是當前點（設為pc）的目標函數f（pc），新點的目標函數f（pn）以及另一個控制參數「溫度」T的函數。也就是說，模擬退火沒有像局部搜索那樣每次都貪婪地尋找比現在好的點，目標函數差一點的點也有可能接受進來。隨著演算法的執行，系統溫度T逐漸降低，最後終止於某個低溫，在該溫度下，系統不再接受變化。
模擬退火的典型特徵是除了接受目標函數的改進外，還接受一個衰減極限，當T較大時，接受較大的衰減，當T逐漸變小時，接受較小的衰減，當T為0時，就不再接受衰減。這一特徵意味著模擬退火與局部搜索相反，它能避開局部極小，並且還保持了局部搜索的通用性和簡單性。
在物理上，先加熱，讓分子間互相碰撞，變成無序狀態，內能加大，然後降溫，最後的分子次序反而會更有序，內能比沒有加熱前更小。就像那隻兔子，它喝醉後，對比較近的山峰視而不見，迷迷糊糊地跳一大圈子，反而更有可能找到珠峰。
值得注意的是，當T為0時，模擬退火就成為局部搜索的一個特例。
模擬退火的偽碼表達：
procere simulated annealing
begin
t:=0;
initialize temperature T
select a current string vc at random;
evaluate vc;
repeat
repeat
select a new string vn in the neighborhood of vc; (1)
if f(vc)<f(vn)
then vc:=vn;
else if random [0,1] <exp ((f (vn)-f (vc))/T) (2)
then vc:=vn;
until (termination-condition) (3)
T:=g(T,t); (4)
T:=t+1;
until (stop-criterion) (5)
end;
上面的程序中，關鍵的是(1)新狀態產生函數，(2)新狀態接受函數，(3)抽樣穩定準則，(4)退溫函數，(5)退火結束准則（簡稱三函數兩准則）是直接影響優化結果的主要環節。雖然實驗結果證明初始值對於最後的結果沒有影響，但是初溫越高，得到高質量解的概率越大。所以，應該盡量選取比較高的初溫。
上面關鍵環節的選取策略：
（1）狀態產生函數：候選解由當前解的鄰域函數決定，可以取互換，插入，逆序等操作產生，然後根據概率分布方式選取新的解，概率可以取均勻分布、正態分布、高斯分布、柯西分布等。
（2）狀態接受函數：這個環節最關鍵，但是，實驗表明，何種接受函數對於最後結果影響不大。所以，一般選取min [1, exp ((f (vn)-f (vc))/T)]。
（3）抽樣穩定準則：一般常用的有：檢驗目標函數的均值是否穩定；連續若干步的目標值變化較小；規定一定的步數；
（4）退溫函數：如果要求溫度必須按照一定的比率下降，SA演算法可以採用，但是溫度下降很慢；快速SA中，一般採用 。目前，經常用的是 ，是一個不斷變化的值。
（5）退火結束准則：一般有：設置終止溫度；設置迭代次數；搜索到的最優值連續多次保持不變；檢驗系統熵是否穩定。
為了保證有比較優的解，演算法往往採取慢降溫、多抽樣、以及把「終止溫度」設的比較低等方式，導致演算法運行時間比較長，這也是模擬退火的最大缺點。人喝醉了酒辦起事來都不利索，何況兔子？ 「物競天擇，適者生存」，是進化論的基本思想。遺傳演算法就是模擬自然界想做的事。遺傳演算法可以很好地用於優化問題，若把它看作對自然過程高度理想化的模擬，更能顯出它本身的優雅——雖然生存競爭是殘酷的。
遺傳演算法以一種群體中的所有個體為對象，並利用隨機化技術指導對一個被編碼的參數空間進行高效搜索。其中，選擇、交叉和變異構成了遺傳演算法的遺傳操作；參數編碼、初始群體的設定、適應度函數的設計、遺傳操作設計、控制參數設定五個要素組成了遺傳演算法的核心內容。作為一種新的全局優化搜索演算法，遺傳演算法以其簡單通用、健壯性強、適於並行處理以及高效、實用等顯著特點，在各個領域得到了廣泛應用，取得了良好效果，並逐漸成為重要的智能演算法之一。
遺傳演算法的偽碼：
procere genetic algorithm
begin
initialize a group and evaluate the fitness value ; （1）
while not convergent （2）
begin
select; （3）
if random[0,1]<pc then
crossover; （4）
if random (0,1)<pm then
mutation; （5）
end;
end
上述程序中有五個重要的環節：
（1）編碼和初始群體的生成：GA在進行搜索之前先將解空間的解數據表示成遺傳空間的基因型串結構數據，這些串結構數據的不同組合便構成了不同的點。然後隨機產生N個初始串結構數據，每個串結構數據稱為一個個體， N個體構成了一個群體。GA以這N個串結構數據作為初始點開始迭代。
比如，旅行商問題中，可以把商人走過的路徑進行編碼，也可以對整個圖矩陣進行編碼。編碼方式依賴於問題怎樣描述比較好解決。初始群體也應該選取適當，如果選取的過小則雜交優勢不明顯，演算法性能很差（數量上佔了優勢的老鼠進化能力比老虎強），群體選取太大則計算量太大。
（2）檢查演算法收斂准則是否滿足，控制演算法是否結束。可以採用判斷與最優解的適配度或者定一個迭代次數來達到。
（3）適應性值評估檢測和選擇：適應性函數表明個體或解的優劣性，在程序的開始也應該評價適應性，以便和以後的做比較。不同的問題，適應性函數的定義方式也不同。根據適應性的好壞，進行選擇。選擇的目的是為了從當前群體中選出優良的個體，使它們有機會作為父代為下一代繁殖子孫。遺傳演算法通過選擇過程體現這一思想，進行選擇的原則是適應性強的個體為下一代貢獻一個或多個後代的概率大。選擇實現了達爾文的適者生存原則。
（4）雜交：按照雜交概率（pc）進行雜交。雜交操作是遺傳演算法中最主要的遺傳操作。通過雜交操作可以得到新一代個體，新個體組合了其父輩個體的特性。雜交體現了信息交換的思想。
可以選定一個點對染色體串進行互換，插入，逆序等雜交，也可以隨機選取幾個點雜交。雜交概率如果太大，種群更新快，但是高適應性的個體很容易被淹沒，概率小了搜索會停滯。
（5）變異：按照變異概率（pm）進行變異。變異首先在群體中隨機選擇一個個體，對於選中的個體以一定的概率隨機地改變串結構數據中某個串的值。同生物界一樣，GA中變異發生的概率很低。變異為新個體的產生提供了機會。
變異可以防止有效基因的缺損造成的進化停滯。比較低的變異概率就已經可以讓基因不斷變更，太大了會陷入隨機搜索。想一下，生物界每一代都和上一代差距很大，會是怎樣的可怕情形。
就像自然界的變異適和任何物種一樣，對變數進行了編碼的遺傳演算法沒有考慮函數本身是否可導，是否連續等性質，所以適用性很強；並且，它開始就對一個種群進行操作，隱含了並行性，也容易找到「全局最優解」。 為了找到「全局最優解」，就不應該執著於某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索，導致一葉障目，不見泰山。禁忌搜索就是對於找到的一部分局部最優解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區間。兔子們找到了泰山，它們之中的一隻就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈後，把找到的幾個山峰一比較，珠穆朗瑪峰脫穎而出。
當兔子們再尋找的時候，一般地會有意識地避開泰山，因為他們知道，這里已經找過，並且有一隻兔子在那裡看著了。這就是禁忌搜索中「禁忌表（tabu list）」的含義。那隻留在泰山的兔子一般不會就安家在那裡了，它會在一定時間後重新回到找最高峰的大軍，因為這個時候已經有了許多新的消息，泰山畢竟也有一個不錯的高度，需要重新考慮，這個歸隊時間，在禁忌搜索裡面叫做「禁忌長度（tabu length）」；如果在搜索的過程中，留守泰山的兔子還沒有歸隊，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當一個有兔子留守的地方優越性太突出，超過了「best to far」的狀態，就可以不顧及有沒有兔子留守，都把這個地方考慮進來，這就叫「特赦准則（aspiration criterion）」。這三個概念是禁忌搜索和一般搜索准則最不同的地方，演算法的優化也關鍵在這里。
偽碼表達：
procere tabu search;
begin
initialize a string vc at random,clear up the tabu list;
cur:=vc;
repeat
select a new string vn in the neighborhood of vc;
if va>best_to_far then {va is a string in the tabu list}
begin
cur:=va;
let va take place of the oldest string in the tabu list;
best_to_far:=va;
end else
begin
cur:=vn;
let vn take place of the oldest string in the tabu list;
end;
until (termination-condition);
end;
以上程序中有關鍵的幾點：
（1）禁忌對象：可以選取當前的值（cur）作為禁忌對象放進tabu list，也可以把和當然值在同一「等高線」上的都放進tabu list。
（2）為了降低計算量，禁忌長度和禁忌表的集合不宜太大，但是禁忌長度太小容易循環搜索，禁忌表太小容易陷入「局部極優解」。
（3）上述程序段中對best_to_far的操作是直接賦值為最優的「解禁候選解」，但是有時候會出現沒有大於best_to_far的，候選解也全部被禁的「死鎖」狀態，這個時候，就應該對候選解中最佳的進行解禁，以能夠繼續下去。
（4）終止准則：和模擬退火，遺傳演算法差不多，常用的有：給定一個迭代步數；設定與估計的最優解的距離小於某個范圍時，就終止搜索；當與最優解的距離連續若干步保持不變時，終止搜索；
禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的。 人工神經網路（Artificial Neural Network，ANN）
神經網路從名字就知道是對人腦的模擬。它的神經元結構，它的構成與作用方式都是在模仿人腦，但是也僅僅是粗糙的模仿，遠沒有達到完美的地步。和馮·諾依曼機不同，神經網路計算非數字，非精確，高度並行，並且有自學習功能。
生命科學中，神經細胞一般稱作神經元，它是整個神經結構的最基本單位。每個神經細胞就像一條胳膊，其中像手掌的地方含有細胞核，稱作細胞體，像手指的稱作樹突，是信息的輸入通路，像手臂的稱作軸突，是信息的輸出通路；神經元之間錯綜復雜地連在一起，互相之間傳遞信號，而傳遞的信號可以導致神經元電位的變化，一旦電位高出一定值，就會引起神經元的激發，此神經元就會通過軸突傳出電信號。
而如果要用計算機模仿生物神經，就需要人工的神經網路有三個要素：（1）形式定義人工神經元；（2）給出人工神經元的連接方式，或者說給出網路結構；（3）給出人工神經元之間信號強度的定義。
歷史上第一個人工神經網路模型稱作M－P模型，非常簡單：
其中，表示神經元i在t時刻的狀態，為1表示激發態，為0表示抑制態；是神經元i和j之間的連接強度；表示神經元i的閾值，超過這個值神經元才能激發。
這個模型是最簡單的神經元模型。但是功能已經非常強大：此模型的發明人McCulloch和Pitts已經證明，不考慮速度和實現的復雜性，它可以完成當前數字計算機的任何工作。
以上這個M－P模型僅僅是一層的網路，如果從對一個平面進行分割的方面來考慮的話，M－P網路只能把一個平面分成個半平面，卻不能夠選取特定的一部分。而解決的辦法就是「多層前向網路」。
為了讓這種網路有合適的權值，必須給網路一定的激勵，讓它自己學習，調整。一種方法稱作「向後傳播演算法（Back Propagation，BP）」，其基本思想是考察最後輸出解和理想解的差異，調整權值，並把這種調整從輸出層開始向後推演，經過中間層，達到輸入層。
可見，神經網路是通過學習來達到解決問題的目的，學習沒有改變單個神經元的結構和工作方式，單個神經元的特性和要解決的問題之間也沒有直接聯系，這里學習的作用是根據神經元之間激勵與抑制的關系，改變它們的作用強度。學習樣本中的任何樣品的信息都包含在網路的每個權值之中。
BP演算法中有考察輸出解和理想解差異的過程，假設差距為w，則調整權值的目的就是為了使得w最小化。這就又包含了前文所說的「最小值」問題。一般的BP演算法採用的是局部搜索，比如最速下降法，牛頓法等，當然如果想要得到全局最優解，可以採用模擬退火，遺傳演算法等。當前向網路採用模擬退火演算法作為學習方法的時候，一般成為「波爾茲曼網路」，屬於隨機性神經網路。
在學習BP演算法學習的過程中，需要已經有一部分確定的值作為理想輸出，這就好像中學生在學習的時候，有老師的監督。如果沒有了監督，人工神經網路該怎麼學習？
就像沒有了宏觀調控，自由的市場引入了競爭一樣，有一種學習方法稱作「無監督有競爭的學習」。在輸入神經元i的若干個神經元之間開展競爭，競爭之後，只有一個神經元為1，其他均為0，而對於失敗的神經元，調整使得向對競爭有利的方向移動，則最終也可能在一次競爭中勝利；
人工神經網路還有反饋網路如Hopfield網路，它的神經元的信號傳遞方向是雙向的，並且引入一個能量函數，通過神經元之間不斷地相互影響，能量函數值不斷下降，最後能給出一個能量比較低的解。這個思想和模擬退火差不多。
人工神經網路應用到演算法上時，其正確率和速度與軟體的實現聯系不大，關鍵的是它自身的不斷學習。這種思想已經和馮·諾依曼模型很不一樣。 粒子群優化演算法(PSO)是一種進化計算技術(evolutionary computation)，1995 年由Eberhart 博士和kennedy 博士提出，源於對鳥群捕食的行為研究 。該演算法最初是受到飛鳥集群活動的規律性啟發，進而利用群體智能建立的一個簡化模型。粒子群演算法在對動物集群活動行為觀察基礎上，利用群體中的個體對信息的共享使整個群體的運動在問題求解空間中產生從無序到有序的演化過程，從而獲得最優解。
PSO同遺傳演算法類似，是一種基於迭代的優化演算法。系統初始化為一組隨機解，通過迭代搜尋最優值。但是它沒有遺傳演算法用的交叉(crossover)以及變異(mutation)，而是粒子在解空間追隨最優的粒子進行搜索。同遺傳演算法比較，PSO的優勢在於簡單容易實現並且沒有許多參數需要調整。目前已廣泛應用於函數優化，神經網路訓練，模糊系統控制以及其他遺傳演算法的應用領域。
PSO模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在那裡。但是他們知道當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。
PSO從這種模型中得到啟示並用於解決優化問題。PSO中，每個優化問題的解都是搜索空間中的一隻鳥。我們稱之為「粒子」。所有的粒子都有一個由被優化的函數決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然後粒子們就追隨當前的最優粒子在解空間中搜索。
PSO 初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pBest。另一個極值是整個種群目前找到的最優解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那麼在所有鄰居中的極值就是局部極值。 模擬退火，遺傳演算法，禁忌搜索，神經網路在解決全局最優解的問題上有著獨到的優點，並且，它們有一個共同的特點：都是模擬了自然過程。模擬退火思路源於物理學中固體物質的退火過程，遺傳演算法借鑒了自然界優勝劣汰的進化思想，禁忌搜索模擬了人類有記憶過程的智力過程，神經網路更是直接模擬了人腦。
它們之間的聯系也非常緊密，比如模擬退火和遺傳演算法為神經網路提供更優良的學習演算法提供了思路。把它們有機地綜合在一起，取長補短，性能將更加優良。
這幾種智能演算法有別於一般的按照圖靈機進行精確計算的程序，尤其是人工神經網路，是對計算機模型的一種新的詮釋，跳出了馮·諾依曼機的圈子，按照這種思想來設計的計算機有著廣闊的發展前景

❼ 怎麼指導遺傳演算法全局搜索性

這是一個非常簡單的遺傳演算法源代碼，是由Denis Cormier (North Carolina State University)開發的，Sita S.Raghavan (University of North Carolina at Charlotte)修正。代碼保證盡可能少，實際上也不必查錯。對一特定的應用修正此代碼，用戶只需改變常數的定義並且定義「評價函數」即可。注意代碼的設計是求最大值，其中的目標函數只能取正值；且函數值和個體的適應值之間沒有區別。該系統使用比率選擇、精華模型、單點雜交和均勻變異。如果用Gaussian變異替換均勻變異，可能得到更好的效果。代碼沒有任何圖形，甚至也沒有屏幕輸出，主要是保證在平台之間的高可移植性。讀者可以從ftp.uncc.e,目錄 coe/evol中的文件prog.c中獲得。要求輸入的文件應該命名為『gadata.txt』；系統產生的輸出文件為『galog.txt』。輸入的文件由幾行組成：數目對應於變數數。且每一行提供次序——對應於變數的上下界。如第一行為第一個變數提供上下界，第二行為第二個變數提供上下界，等等。#include <stdio.h>
#include <stdlib.h>
#include <math.h>/* Change any of these parameters to match your needs */#define POPSIZE 50 /* population size */
#define MAXGENS 1000 /* max. number of generations */
#define NVARS 3 /* no. of problem variables */
#define PXOVER 0.8 /* probability of crossover */
#define PMUTATION 0.15 /* probability of mutation */
#define TRUE 1
#define FALSE 0int generation; /* current generation no. */
int cur_best; /* best indivial */
FILE *galog; /* an output file */struct genotype /* genotype (GT), a member of the population */
{
double gene[NVARS]; /* a string of variables */
double fitness; /* GT's fitness */
double upper[NVARS]; /* GT's variables upper bound */
double lower[NVARS]; /* GT's variables lower bound */
double rfitness; /* relative fitness */
double cfitness; /* cumulative fitness */
};struct genotype population[POPSIZE+1]; /* population */
struct genotype newpopulation[POPSIZE+1]; /* new population; */
/* replaces the */
/* old generation *//* Declaration of proceres used by this genetic algorithm */void initialize(void);
double randval(double, double);
void evaluate(void);
void keep_the_best(void);
void elitist(void);
void select(void);
void crossover(void);
void Xover(int,int);
void swap(double *, double *);
void mutate(void);
void report(void);/***************************************************************/
/* Initialization function: Initializes the values of genes */
/* within the variables bounds. It also initializes (to zero) */
/* all fitness values for each member of the population. It */
/* reads upper and lower bounds of each variable from the */
/* input file `gadata.txt'. It randomly generates values */
/* between these bounds for each gene of each genotype in the */
/* population. The format of the input file `gadata.txt' is */
/* var1_lower_bound var1_upper bound */
/* var2_lower_bound var2_upper bound ... */
/***************************************************************/void initialize(void)
{
FILE *infile;
int i, j;
double lbound, ubound;if ((infile = fopen("gadata.txt","r"))==NULL)
{
fprintf(galog,"\nCannot open input file!\n");
exit(1);
}/* initialize variables within the bounds */for (i = 0; i < NVARS; i++)
{
fscanf(infile, "%lf",&lbound);
fscanf(infile, "%lf",&ubound); for (j = 0; j < POPSIZE; j++)
{
population[j].fitness = 0;
population[j].rfitness = 0;
population[j].cfitness = 0;
population[j].lower[i] = lbound;
population[j].upper[i]= ubound;
population[j].gene[i] = randval(population[j].lower[i],
population[j].upper[i]);
}
}fclose(infile);
}/***********************************************************/
/* Random value generator: Generates a value within bounds */
/***********************************************************/double randval(double low, double high)
{
double val;
val = ((double)(rand()%1000)/1000.0)*(high - low) + low;
return(val);
}/*************************************************************/
/* Evaluation function: This takes a user defined function. */
/* Each time this is changed, the code has to be recompiled. */
/* The current function is: x[1]^2-x[1]*x[2]+x[3] */
/*************************************************************/void evaluate(void)
{
int mem;
int i;
double x[NVARS+1];for (mem = 0; mem < POPSIZE; mem++)
{
for (i = 0; i < NVARS; i++)
x[i+1] = population[mem].gene[i];

population[mem].fitness = (x[1]*x[1]) - (x[1]*x[2]) + x[3];
}
}/***************************************************************/
/* Keep_the_best function: This function keeps track of the */
/* best member of the population. Note that the last entry in */
/* the array Population holds a of the best indivial */
/***************************************************************/void keep_the_best()
{
int mem;
int i;
cur_best = 0; /* stores the index of the best indivial */for (mem = 0; mem < POPSIZE; mem++)
{
if (population[mem].fitness > population[POPSIZE].fitness)
{
cur_best = mem;
population[POPSIZE].fitness = population[mem].fitness;
}
}
/* once the best member in the population is found, the genes */
for (i = 0; i < NVARS; i++)
population[POPSIZE].gene[i] = population[cur_best].gene[i];
}

❽ 全局擇優搜索演算法得到的解是最優解么

不一定的，那還得看你的啟發函數是否設置得合理