第七章人工智能

第七章高級搜索主要內(nèi)容局部搜索方法模擬退火算法遺傳算法7.1基本概念優(yōu)化與組合優(yōu)化問題很多問題屬于優(yōu)化問題，或者可以轉(zhuǎn)化為優(yōu)化問題如TSP問題，皇后問題優(yōu)化問題的描述設(shè)x是決策變量，D是x的定義域，f(x)是指標函數(shù)，g(x)是約束條件集合。則優(yōu)化問題可以表示為，求解滿足g(x)的f(x)最小值問題。如果在定義域D上，滿足條件g(x)的解是有限的，則優(yōu)化問題稱為組合優(yōu)化問題。算法的時間復雜度對于組合優(yōu)化問題，由于其可能的解是有限的，當問題的規(guī)模比較小時，總可以通過枚舉的方法獲得問題的最優(yōu)解，但當問題的規(guī)模比較大時，就難于求解了。常用的算法復雜度函數(shù)

輸入量n復雜性函數(shù)10203040100n10ns20ns30ns40ns100nsnlogn10ns26.0ns44.3ns64.1ns200nsn2100ns400ns900ns1.6us10us2n1.0us1.0ms1.1s18.3min4.0世紀n!3.6ms77.1年8.4×1013世紀2.6×1029世紀3.0×10139世紀時間復雜性函數(shù)比較（10億次/秒）一些難的組合優(yōu)化問題旅行商問題背包問題裝箱問題...尋求在可以接受的時間內(nèi)得到滿意解的方法鄰域的概念鄰域，簡單的說就是一個點附近的其他點的集合。在距離空間，鄰域就是以某一點為中心的圓。組合優(yōu)化問題的定義：設(shè)D是問題的定義域，若存在一個映射N，使得：則稱N(S)為S的鄰域。例：皇后問題S={Si}表示一個可能解，其中Si表示在第i行，第Si列有一個皇后。如四皇后問題的一個解：S=(2,4,1,3)

Q

QQ

Q

定義映射N為棋盤上任意兩個皇后的所在行或列進行交換，即S中任意兩個元素交換位置。例：當S=(2,4,1,3)時，其鄰域為：N(S)={(4,2,1,3),(1,4,2,3),(3,4,1,2),(2,1,4,3),(2,3,1,4),(2,4,3,1)}例：旅行商問題用一個城市的序列表示一個可能的解。通過交換兩個城市的位置獲取S的鄰居例：簡單交換方法設(shè)S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)則通過交換xi和xj兩個城市的位置可以得到S的一個鄰居：S'=(x1,x2,…xi-1,xj,xi+1,…,xj-1,xi,xj+1,…,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1例：逆序交換方法設(shè)xi、xj是選取的兩個城市，所謂的逆序交換方式是指，通過逆轉(zhuǎn)xi、xj兩個城市之間的城市次序來得到S的鄰居。設(shè)：S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)則：S'=(x1,x2,…xi-1,xi,xj-1,xj-2…,xi+1,xj,xj+1,…,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+17.2局部搜索算法基本思想：在搜索過程中，始終向著離目標最接近的方向搜索。目標可以是最大值，也可以是最小值。在后面的介紹中，如果沒有特殊說明，均假定是最小值。局部搜索算法（LocalSearch）1，隨機的選擇一個初始的可能解x0∈D，xb=x0，P=N(xb)；2，如果不滿足結(jié)束條件，則3，Begin4， 選擇P的一個子集P'，xn為P'中的最優(yōu)解5， 如果f(xn)<f(xb)，則xb＝xn，P=N(xb)，轉(zhuǎn)2；f(x)為指標函數(shù)。6， 否則P=P–P'，轉(zhuǎn)2。7，End8，輸出計算結(jié)果9，結(jié)束例：5城市旅行商問題●●●●●ABCDE71361071010965設(shè)初始的可能解：x0=(a,b,c,d,e)f(xb)=f(x0)=38通過交換兩個城市獲得領(lǐng)域P={(a,c,b,d,e),(a,d,c,b,e),(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}設(shè)每次隨機從P中選擇一個鄰居。第一次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,c,b,d,e),f(xn)=42,f(xn)>f(xb),P=P–{xn}={(a,d,c,b,e),(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}第二次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,d,c,b,e),f(xn)=45,f(xn)>f(xb),P=P–{xn}={(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}第三次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,e,c,d,b),f(xn)=44,f(xn)>f(xb),P=P–{xn}={(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d)}第四次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,b,d,c,e),f(xn)=44,f(xn)>f(xb),P=P–{xn}={(a,b,e,d,c),(a,b,c,e,d)}第五次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,b,e,d,c),f(xn)=34,f(xn)<f(xb),xb=(a,b,e,d,c),P={(a,e,b,d,c),(a,d,e,b,c),(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第六次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,e,b,d,c),f(xn)=44,f(xn)>f(xb),P=P–{xn}={(a,d,e,b,c),(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第七次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,d,e,b,c),f(xn)=39,f(xn)>f(xb),P=P–{xn}={(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第八次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,c,e,d,b),f(xn)=38,f(xn)>f(xb),P=P–{xn}={(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)}第九次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,b,d,e,c),f(xn)=38,f(xn)>f(xb),P=P–{xn}={(a,b,c,d,e),(a,b,e,c,d)}第十次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,b,c,d,e),f(xn)=38,f(xn)>f(xb),P=P–{xn}={(a,b,e,c,d)}第十一次循環(huán)從P中選擇一個元素，假設(shè)xn=(a,b,e,c,d),f(xn)=41,f(xn)>f(xb),P=P–{xn}={}P等于空，算法結(jié)束，得到結(jié)果為xb=(a,b,e,d,c),f(xb)=34。存在的問題局部最優(yōu)問題

解決方法每次并不一定選擇鄰域內(nèi)最優(yōu)的點，而是依據(jù)一定的概率，從鄰域內(nèi)選擇一個點，指標函數(shù)優(yōu)的點，被選中的概率比較大，而指標函數(shù)差的點，被選中的概率比較小。選擇概率的計算設(shè)求最大值：選擇概率的計算當求最小值時：局部搜索算法1（LocalSearch1）1，隨機的選擇一個初始的可能解x0∈D，xb=x0，P=N(xb)2，如果不滿足結(jié)束條件，則3，Begin4，對于所有的x∈P計算指標函數(shù)f(x)，并按照式（3）或者式（4）計算每一個點x的概率5，依計算的概率值，從P中隨機選擇一個點xn，xb＝xn，P=N(xb)，轉(zhuǎn)26，End7，輸出計算結(jié)果8，結(jié)束存在的問題步長問題初始值搜索到的最優(yōu)解解決方法變步長初始值搜索到的最優(yōu)解局部搜索算法2（LocalSearch2）1，隨機的選擇一個初始的可能解x0∈D，xb=x0，確定一個初始步長計算P=N(xb)2，如果不滿足結(jié)束條件，則3，Begin4， 選擇P的一個子集P'，xn為P'中的最優(yōu)解5，如果f(xn)<f(xb)，則xb＝xn6,按照某種策略改變步長，計算P=N(xb)，轉(zhuǎn)27， 否則P=P–P'，轉(zhuǎn)2。8，End9，輸出計算結(jié)果10，結(jié)束存在問題起始點問題AB全局最大值局部最大值解決方法隨機的生成一些初始點，從每個初始點出發(fā)進行搜索，找到各自的最優(yōu)解。再從這些最優(yōu)解中選擇一個最好的結(jié)果作為最終的結(jié)果。局部搜索算法3（LocalSearch3）1，k=02，隨機的選擇一個初始的可能解x0∈D，xb=x0，P=N(xb)3，如果不滿足結(jié)束條件，則4，Begin5， 選擇P的一個子集P'，xn為P'中的最優(yōu)解6， 如果f(xn)<f(xb)，則xb＝xn，P=N(xb)，轉(zhuǎn)37， 否則P=P–P'，轉(zhuǎn)3。8，End9，k=k+110，如果k達到了指定的次數(shù)，則從k個結(jié)果中選擇一個最好的結(jié)果輸出，否則轉(zhuǎn)（2）11，輸出結(jié)果12，結(jié)束多種方法的集成以上幾種解決方法可以結(jié)合在一起使用，比如第一、第二種方法的結(jié)合，就產(chǎn)生了我們將在后面介紹的模擬退火方法。皇后搜索算法（QueenSearch）1，隨機地將n個皇后分布在棋盤上，使得棋盤的每行、每列只有一個皇后。2，計算皇后間的沖突數(shù)conflicts。3，如果沖突數(shù)conflicts等于0，則轉(zhuǎn)（6）4，對于棋盤上的任意兩個皇后，交換他們的行或者列，如果交換后的沖突數(shù)conflicts減少，則接受這種交換，更新沖突數(shù)conflicts，轉(zhuǎn)3。5，如果陷入了局部極小，既交換了所有的皇后后，沖突數(shù)仍然不能下降，則轉(zhuǎn)1。6，輸出結(jié)果7，結(jié)束。不同規(guī)模下皇后問題的

平均求解時間皇后數(shù)1005001000200050001000030000平均時間（秒）551228170900100007.3模擬退火算法是局部搜索算法的一種擴展最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地將模擬退火算法用于求解組合優(yōu)化問題。基本思想是借用金屬的退化過程改進局部搜索算法固體退火過程溶解過程：隨著溫度的不斷上升，粒子逐漸脫離開其平衡位置，變得越來越自由，直到達到固體的溶解溫度，粒子排列從原來的有序狀態(tài)變?yōu)橥耆臒o序狀態(tài)。退火過程：隨著溫度的下降，粒子的熱運動逐漸減弱，粒子逐漸停留在不同的狀態(tài)，其排列也從無序向有序方向發(fā)展，直至到溫度很低時，粒子重新以一定的結(jié)構(gòu)排列。粒子不同的排列結(jié)構(gòu)，對應著不同的能量水平。如果退火過程是緩慢進行的，也就是說，溫度的下降如果非常緩慢的話，使得在每個溫度下，粒子的排列都達到一種平衡態(tài)，則當溫度趨于0（絕對溫度）時，系統(tǒng)的能量將趨于最小值。如果以粒子的排列或者相應的能量來表達固體所處的狀態(tài)，在溫度T下，固體所處的狀態(tài)具有一定的隨機性。一方面，物理系統(tǒng)傾向于能量較低的狀態(tài)，另一方面，熱運動又妨礙了系統(tǒng)準確落入低能狀態(tài)。Metropolis準則從狀態(tài)i轉(zhuǎn)換為狀態(tài)j的準則：如果E(j)≤E(i)，則狀態(tài)轉(zhuǎn)換被接受；如果E(j)＞E(i)，則狀態(tài)轉(zhuǎn)移被接受的概率為：其中E(i)、E(j)分別表示在狀態(tài)i、j下的能量，T是溫度，K＞0是波爾茲曼常數(shù)。在給定的溫度T下，當進行足夠多次的狀態(tài)轉(zhuǎn)換后，系統(tǒng)將達到熱平衡。此時系統(tǒng)處于某個狀態(tài)i的概率由波爾茲曼（Boltzmann）分布給出：（6）其中為歸一化因子，S是所有可能狀態(tài)的集合?？疾煲幌率剑?）隨溫度T的變化情況：同一溫度下，兩個能量不同的狀態(tài)高溫下的情況低溫下的情況當溫度下降時的情況在給定的溫度T下，設(shè)有i、j兩個狀態(tài)，E(i)＜E(j)：即在任何溫度T下，系統(tǒng)處于能量低的狀態(tài)的概率大于處于能量高的狀態(tài)的概率。

由于E(i)＜E(j)，所以該項小于1

當溫度趨于無窮時：其中|S|表示系統(tǒng)所有可能的狀態(tài)數(shù)。

當溫度很高時，系統(tǒng)處于各個狀態(tài)的概率基本相等，接近于平均值，與所處狀態(tài)的能量幾乎無關(guān)。

當溫度趨于0時：設(shè)Sm表示系統(tǒng)最小能量狀態(tài)的集合，Em是系統(tǒng)的最小能量。上式分子、分母同乘以當溫度趨近于0時，系統(tǒng)以等概率趨近于幾個能量最小的狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)的概率為0。以概率1達到能量最小的狀態(tài)。當溫度上升或下降時：系統(tǒng)落入低能量狀態(tài)的概率隨著溫度的下降單調(diào)上升，而系統(tǒng)落入高能量狀態(tài)的概率隨著溫度的下降單調(diào)下降。在高溫下，系統(tǒng)基本處于無序的狀態(tài)，基本以等概率落入各個狀態(tài)。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于系統(tǒng)落入高能量狀態(tài)的概率，這樣在同一溫度下，如果系統(tǒng)交換的足夠充分，則系統(tǒng)會趨向于落入較低能量的狀態(tài)。隨著溫度的緩慢下降，系統(tǒng)落入低能量狀態(tài)的概率逐步增加，而落入高能量狀態(tài)的概率逐步減少，使得系統(tǒng)各狀態(tài)能量的期望值隨溫度的下降單調(diào)下降，而只有那些能量小于期望值的狀態(tài)，其概率才隨溫度下降增加，其他狀態(tài)均隨溫度下降而下降。因此，隨著能量期望值的逐步下降，能量低于期望值的狀態(tài)逐步減少，當溫度趨于0時，只剩下那些具有最小能量的狀態(tài)，系統(tǒng)處于其他狀態(tài)的概率趨近于0。因此最終系統(tǒng)將以概率1處于具有最小能量的一個狀態(tài)。達到最小能量狀態(tài)的三個條件（1）初始溫度必須足夠高；（2）在每個溫度下，狀態(tài)的交換必須足夠充分；（3）溫度T的下降必須足夠緩慢。組合優(yōu)化問題與退火過程的類比固體退火過程組合優(yōu)化問題物理系統(tǒng)中的一個狀態(tài)組合優(yōu)化問題的解狀態(tài)的能量解的指標函數(shù)能量最低狀態(tài)最優(yōu)解溫度控制參數(shù)1，隨機選擇一個解i，k=0，t0=Tmax（初始溫度），計算指標函數(shù)f(i)。2，如果滿足結(jié)束條件，則轉(zhuǎn)（15）。3，Begin4， 如果在該溫度內(nèi)達到了平衡條件，則轉(zhuǎn)（13）。5， Begin6， 從i的鄰域N(i)中隨機選擇一個解j。7， 計算指標函數(shù)f(j)。8， 如果f(j)<f(i)，則i=j，f(i)=f(j)，轉(zhuǎn)（4）。9， 計算10， 如果Pt(i=>j)>Random(0,1)，則i=j，f(i)=f(j)。11， 轉(zhuǎn)（4）12， End13， tk+1=Drop(tk)，k=k+1。14，End15，輸出結(jié)果。16，結(jié)束。算法中的問題初始溫度的選取內(nèi)循環(huán)的結(jié)束條件，即每個溫度狀態(tài)交換何時結(jié)束外循環(huán)的結(jié)束條件，即溫度下降到什么時候結(jié)束溫度的下降方法在模擬退火過程中，給定溫度下狀態(tài)（解）的轉(zhuǎn)移可以看作是一個馬爾可夫鏈。對于任意兩個狀態(tài)i和j，我們用Pt(i,j)表示溫度t下，從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的一步轉(zhuǎn)移概率，則有：其中：Gt(i,j)是產(chǎn)生概率，表示從狀態(tài)i產(chǎn)生狀態(tài)j的概率。At(i,j)是接受概率，表示在狀態(tài)i產(chǎn)生狀態(tài)j后，接受狀態(tài)j的概率。定理7.1滿足條件的Gt(i,j)、At(i,j)舉例：

說明：條件2的后半部分除外，該條件與具體的問題有關(guān)。定理7.2：在定理1的條件下，如果對于任意兩個狀態(tài)

有：則有：定理7.3（放寬了定理1的條件）

Gt(i,j)、At(i,j)滿足定理1中除條件（2）以外的所有其他條件，并且：1，對于任意兩個狀態(tài)i、j，它們相互為鄰居或者相互都不為鄰居；2，對于任意i，Gt(i,j)滿足：3，狀態(tài)空間S對于鄰域是連通的；則與模擬退火算法相伴的時齊馬爾可夫鏈存在平穩(wěn)分布，其分布概率為：

算法的實現(xiàn)（1）初始溫度t0；（2）溫度t的衰減函數(shù)，即溫度的下降 方法；（3）算法的終止準則，用終止溫度tf或 者終止條件給出；（4）每個溫度t下的馬爾可夫鏈長度Lk。起始溫度的選?。?）一個合適的初始溫度，應保證平穩(wěn)分布中每一個狀態(tài)的概率基本相等，也就是接受概率P0近似等于1。在Metropolis準則下，即要求：如果我們給定一個比較大的接受概率P0，則：其中，可以有以下估計方式：起始溫度的選?。?）假設(shè)在t0下隨機的生成一個狀態(tài)序列，分別用m1和m2表示指標函數(shù)下降的狀態(tài)數(shù)和指標函數(shù)上升的狀態(tài)數(shù)，表示狀態(tài)增加的平均值。則m2個狀態(tài)中，被接受的個數(shù)為：所以平均接受率為：求解有：起始溫度的選?。?）模擬固體的升溫過程：（1）給定一個希望的初始接受概率P0，給定一個較低的初始溫度t0，比如t0＝1；（2）隨機的產(chǎn)生一個狀態(tài)序列，并計算該序列的接收率：如果接收率大于給定的初始接受概率P0，則轉(zhuǎn)（4）；（3）提高溫度，更新t0，轉(zhuǎn)（2）；（4）結(jié)束。溫度的下降方法（1）等比例下降溫度的下降方法（2）等值下降溫度的下降方法（3）由定理1我們知道，在一定的條件下，與模擬退火算法相伴的時齊馬爾可夫鏈存在平穩(wěn)分布。如果溫度每次下降的幅度比較小的話，則相鄰溫度下的平穩(wěn)分布應該變化不大，也就是說，對于任意一個狀態(tài)i，相鄰溫度下的平穩(wěn)分布應滿足：一個充分條件是：兩邊取對數(shù)，并整理得：用代替可得溫度的衰減函數(shù)：每一溫度下的停止準則（1）固定長度方法在每一個溫度下，都使用相同的Lk。Lk的選取與具體的問題相關(guān)，一般與鄰域的大小直接關(guān)聯(lián)，通常選擇為問題規(guī)模n的一個多項式函數(shù)。每一溫度下的停止準則（2）基于接受率的停止準則：規(guī)定一個接受次數(shù)R，在某一溫度下，只有被接受的狀態(tài)數(shù)達到R時，在該溫度下的迭代才停止，轉(zhuǎn)入下一個溫度。規(guī)定一個狀態(tài)接受率R，R等于該溫度下接受的狀態(tài)數(shù)除以總生成的總狀態(tài)數(shù)。如果接受率達到了R，則停止該溫度下的迭代，轉(zhuǎn)入下一個溫度。在迭代的過程中，若干相鄰的狀態(tài)稱為“一代”，如果相鄰兩代的解的指標函數(shù)差值小于規(guī)定的值的話，則停止該溫度下的迭代。算法的終止原則（1）零度法設(shè)定一個正常數(shù)e，當時tk<e時，算法結(jié)束。算法的終止原則（2）循環(huán)總控制法

給定一個指定的溫度下降次數(shù)K，當溫度的迭代次數(shù)達到K次時，則算法停止。算法的終止原則（3）無變化控制法如果在相鄰的n個溫度中，得到的解的指標函數(shù)值無任何變化，則說明算法已經(jīng)收斂。算法的終止原則（4）接受概率控制法給定一個小的概率值p，如果在當前溫度下除了局部最優(yōu)狀態(tài)外，其他狀態(tài)的接受概率小于p值，則算法結(jié)束。算法的終止原則（5）領(lǐng)域平均概率控制法設(shè)大小為N的一個領(lǐng)域，在鄰域內(nèi)一個狀態(tài)被接受的平均概率為1/N。設(shè)f0、f1為該領(lǐng)域中的局部最優(yōu)值和局部次最優(yōu)值。則次最優(yōu)解是除了局部最優(yōu)解以外接受概率最大的，其接受概率為：如果該概率值小于平均值1/N時，即：可以認為從局部最優(yōu)解跳出的可能性已經(jīng)很小了，因此可以終止算法。此時的終止溫度tf為：算法的終止原則（6）相對誤差估計法設(shè)溫度t時指標函數(shù)的期望值為：則當終止溫度<<1時，由泰勒展開近似有：由于：所以可用下式估計當前解與最優(yōu)解之間的誤差：或者使用相對于的相對誤差：實際計算時：其中：應用舉例——旅行商問題解的表示：n個城市的任何一種排列均是問題的一個可能解，表示為:指標函數(shù)(能量函數(shù))其中新解的產(chǎn)生采用第一節(jié)介紹的兩個城市間的逆序交換方式得到問題的一個新解。設(shè)當前解是，被選中要逆序交換的城市是第u和第v個到訪的城市，u<v。則逆序排列u和v之間的城市，得到問題的新解為：則兩個路徑的距離差為：新解的接受準則初始參數(shù)的確定康立山等人的方法：初始溫度t0=280；在每個溫度下采用固定的迭代次數(shù)，Lk=100n，n為城市數(shù)；溫度的衰減系數(shù)＝0.92，即tk+1=0.92×tk；算法的停止準則為：當相鄰兩個溫度得到的解無任何變化時算法停止。NirwanAnsari和EdwinHou的方法：初始溫度t0是這樣確定的：從t0=1出發(fā)，并以t0=1.05×t0對t0進行更新，直到接受概率大于等于0.9時為止，此時得到的溫度為初始溫度；在每個溫度下采用固定的迭代次數(shù)，Lk=10n，n為城市數(shù)；溫度的衰減系數(shù)＝0.95，即tk+1=0.95×tk；10城市旅行商問題求解結(jié)果

路徑長度出現(xiàn)次數(shù)平均轉(zhuǎn)移次數(shù)路徑最優(yōu)2.6919063952BCADEFGHIJ次優(yōu)2.752464056BCADEGFHIJ第三2.769104053DEFGHIJCBA最差2.89854497ABCDEFHIJG20城市旅行商問題求解結(jié)果

路徑長度出現(xiàn)次數(shù)平均轉(zhuǎn)移次數(shù)路徑最優(yōu)24.387928740ACLBIQFTMEPRGSOJHDKN次優(yōu)24.621678638ADCLBIQFTMEPRGSOJHKN第三25.17399902ANKDHIOJSGRPEMTFQBLC最差25.5015794AQFTMEPRGSJOIBLCDHKN7.4遺傳算法達爾文進化論：“物競天擇、適者生存”70年代由美國的密執(zhí)根大學的Holland教授首先提出近年來，遺傳算法作為一種有效的工具，已廣泛地應用于最優(yōu)化問題求解之中。生物進化與遺傳算法群體種群子群選擇婚配變異遭淘汰的群體生物進化中的概念遺傳算法中的作用環(huán)境適應函數(shù)適應性適應值函數(shù)適者生存適應函數(shù)值最大的解被保留的概率最大個體問題的一個解染色體解的編碼基因編碼的元素群體被選定的一組解種群根據(jù)適應函數(shù)選擇的一組解交配以一定的方式由雙親產(chǎn)生后代的過程變異編碼的某些分量發(fā)生變化的過程生物進化與遺傳算法之間的對應關(guān)系

遺傳算法的三個主要操作選擇交配變異“輪盤賭”法： 設(shè)群體的規(guī)模為N，F(xiàn)(xi)(i=1,...,N)是其中N個染色體的適應值。則第i個染色體被選中的概率由下式給出：選擇x1x2x3x4x5x6模擬“輪盤賭”算法（1）r=random(0,1)，s=0，i=0；（2）如果s≥r，則轉(zhuǎn)（4）；（3）s=s+p(xi)，i=i+1,轉(zhuǎn)（2）（4）xi即為被選中的染色體，輸出i（5）結(jié)束?！按_定性”法對于規(guī)模為N的群體，一個選擇概率為p(xi)的染色體xi被選擇次數(shù)的期望值e(xi)：

對于群體中的每一個xi，首先選擇次。這樣共得到個染色體。然后按照從大到小對染色體排序，依次取出個染色體，這樣就得到了N個染色體。交配交配發(fā)生在兩個染色體之間，由兩個被稱之為雙親的父代染色體，經(jīng)雜交以后，產(chǎn)生兩個具有雙親的部分基因的新的染色體。當染色體采用二進制形式編碼時，交配過程是以這樣一種形式進行的：a1a2...aiai+1...anb1b2...bibi+1...bna1a2...aibi+1...bnb1b2...biai+1...an交配前交配后交配位置變異變異發(fā)生在染色體的某一個基因上，當以二進制編碼時，變異的基因由0變成1，或者由1變成0。如對于染色體x=11001，如果變異位發(fā)生在第三位，則變異后的染色體變成了y=11101。遺傳算法（1）給定群體規(guī)模N，交配概率pc和變異概率pm，t＝0；（2）隨機生成N個染色體作為初始群體；（3）對于群體中的每一個染色體xi分別計算其適應值F(xi)；（4）如果算法滿足停止準則，則轉(zhuǎn)（10）；（5）對群體中的每一個染色體xi計算概率；（6）依據(jù)計算得到的概率值，從群體中隨機的選取N個染色體，得到種群；（7）依據(jù)交配概率pc從種群中選擇染色體進行交配，其子代進入新的群體，種群中未進行交配的染色體，直接復制到新群體中；（8）依據(jù)變異概率pm從新群體中選擇染色體進行變異，用變異后的染色體代替新群體中的原染色體；（9）用新群體代替舊群體，t=t+1，轉(zhuǎn)（3）；（10）進化過程中適應值最大的染色體，經(jīng)解碼后作為最優(yōu)解輸出；（11）結(jié)束。例：求函數(shù)的最大值其中x為[0,31]間的整數(shù)編碼：采用二進制形式編碼由于x的定義域是[0,31]間的整數(shù)，剛好可以用5位二進制數(shù)表示，因此可以用5位二進制數(shù)表示該問題的解，即染色體。如00000表示x＝0，10101表示x＝21，11111表示x＝31等適應函數(shù)：直接使用函數(shù)f(x)作為適應函數(shù)。假設(shè)群體的規(guī)模N＝4，交配概率pc＝100％，變異概率pm＝1％。設(shè)隨機生成的初始群體為：01101，11000，01000，10011選擇方法：“確定性”法序號群體適應值選擇概率（％）期望次數(shù)選中次數(shù)10110116914.440.58121100057649.231.972301000645.470.22041001136130.851.231第0代情況表序號種群交配對像交配位子代適應值1011012401100144211000141100162531100042110117294100113210000256第0代種群的交配情況序號群體適應值選擇概率（％）期望次數(shù)選中次數(shù)1011001448.210.33021100162535.621.42131101172941.561.66241000025614.600.581第1代情況表序號種群交配對像交配位子代適應值11100123110117292110111311001625