【正文】 色的數(shù)字 1是被變異操作后出現(xiàn)的）： 2022/8/21 111 ? 二進制編碼表示時的簡單變異操作是將 0與 1互換： 0變異為 1， 1變異為 0。 現(xiàn)在對 TSP的變異操作作簡單介紹，隨機產(chǎn)生一個 1至 n之間的數(shù) k，決定對回路中的第 k個城市的代碼 wk作變異操作，又產(chǎn)生一個 1至 n之間的數(shù) w，替代 wk，并將 wk加到尾部，得到： w1 w2 …… w k1 w wk+1 …… w n wk ? 這個串有 n+1個數(shù)碼，注意數(shù) w其實在此串中出現(xiàn)重復(fù)了，必須刪除與數(shù) w相重復(fù)的，得到合法的染色體 2022/8/21 112 ? 并不是所有被選擇了的染色體都要進行交叉操作和變異操作，而是以一定的概率進行，一般在程序設(shè)計中交叉發(fā)生的概率要比變異發(fā)生的概率選取得大若干個數(shù)量級， 交叉概率 取 ； 變異概率 取 至 。 種群的染色體總數(shù)叫 種群規(guī)模 ，它對算法的效率有明顯的影響，規(guī)模太小不得于進化，而規(guī)模太大將導(dǎo)致程序運行時間長。對不同的問題可能有各自適合的種群規(guī)模，通常種群規(guī)模為 30至 100。 另一個控制參數(shù)是 個體的長度 ，有定長和變長兩種。它對算法的性能也有影響。 2022/8/21 113 遺傳算法的基本原理 ? 遺傳算法類似于自然進化，通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機會。在遺傳算法中，通過隨機方式產(chǎn)生若干個所求解問題的數(shù)字編碼，即染色體，形成初始群體；通過適應(yīng)度函數(shù)給每個個體一個數(shù)值評價，淘汰低適應(yīng)度的個體，選擇高適應(yīng)度的個體參加遺傳操作，經(jīng)過遺傳操作后的個體集合形成下一代新的種群。對這個新種群進行下一輪進化。這就是遺傳算法的 基本原理 。 2022/8/21 114 ? 下面就是遺傳算法思想： (1) 初始化群體 。 (2) 計算群體上每個個體的適應(yīng)度值 。 (3) 按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進入下一代的個體 。 (4) 按概率 Pc進行交叉操作 。 (5) 按概率 Pc進行突變操作 。 (6) 沒有滿足某種停止條件，則轉(zhuǎn)第 (2)步，否則進入 (7)。 (7) 輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。 2022/8/21 115 ? 程序的停止條件最簡單的有如下二種：完成了預(yù)先給定的進化代數(shù)則停止；種群中的最優(yōu)個體在連續(xù)若干代沒有改進或平均適應(yīng)度在連續(xù)若干代基本沒有改進時停止。 根據(jù)遺傳算法思想可以畫出如右圖所示的簡單遺傳算法框圖： 2022/8/21 116 遺傳算法的收斂性 ? 一些研究人員對進化算法的運行機理進行過研究，Radolph在文獻 [1]中證明了一般的遺傳算法不一定收斂，只有每代保存了最優(yōu)個體時才收斂。在實際應(yīng)用中，使用了上述結(jié)論來保證收斂性。采用優(yōu)秀個體保護法就是將每代中的最優(yōu)個體，直接進入子代，相應(yīng)淘汰其子代中適應(yīng)度最差的個體，使種群規(guī)模不變。 對保存最優(yōu)個體時遺傳算法是收斂的結(jié)論的證明是通過對遺傳算法構(gòu)造馬爾柯夫 (markov)鏈，因為遺傳算法的進行過程是一個馬爾柯夫過程。 2022/8/21 117 ? 當(dāng)遺傳算法收斂時，求到的解通常只是所要解決問題的最優(yōu)解的一個近似解，或者叫滿意解。從數(shù)學(xué)分析的角度看，收斂過程是一個無限逼近過程，而計算過程是一個有限自動機，因此通過遺傳算法程序求得的解總是一個近似解。近似解與問題真正的最優(yōu)解的差是一個統(tǒng)計意義下的量，也就是說每次程序運行得到的解的質(zhì)量可能是有較大的差別的。 2022/8/21 118 遺傳算法的性能 ? 上面指出遺傳算法程序求得的解是一個滿意解，哪些因素會影響到解的質(zhì)量？這其實也是遺傳算法的性能問題。 首先要注意的是種群的規(guī)模要適當(dāng)，種群規(guī)模太小，種群中就沒有充分的多樣性，不利于適應(yīng)度值高的染色體的進化，致使算法得不到滿意的解?？梢哉J(rèn)為種群規(guī)模大有利于種群的進化，種群健壯發(fā)展，但染色體多，每進行一輪進化花費的機器時間就多，致使算法的效率低。 2022/8/21 119 ? 適應(yīng)度函數(shù)的構(gòu)造對遺傳算法的性能影響較大，由于適應(yīng)度是衡量染色體優(yōu)劣的準(zhǔn)則，有時優(yōu)劣染色體的適應(yīng)度值沒有拉開距離，必要提升優(yōu)良染色體的適應(yīng)度值，降低劣弱染色體的適應(yīng)度值，給優(yōu)良染色體很多的生存機會，達到提高進化速度的目標(biāo)?？梢越Y(jié)合所求解問題的實際情況對適應(yīng)度函數(shù)作適當(dāng)?shù)淖儞Q，提高選擇過程的效率。如下有一個線性變換： 2022/8/21 120 ? C1和 C2的選取主要依具體問題的情況而定，并應(yīng)滿足一定的約束條件 (例如變換后的適應(yīng)度值不能是負(fù)值等 )。 適應(yīng)度函數(shù)直接作用到了選擇操作，也就是說選擇操作的性能主要是由適應(yīng)度函數(shù)來決定，但是怎樣運用適應(yīng)度函數(shù)是需要研究的。 對遺傳算法的性能影響最大的也許是交叉和變異操作，有很多文獻對此進行了研究的改進。首先是交叉和變異操作并不是都要進行，對某些問題遺傳算法求解時其性能主要由交叉操作決定，甚至沒有變異操作時，算法的性能更好；而對另外的某些問題遺傳算法求解時其性能主要由變異操作決定，甚至不要交叉操作更合適。 2022/8/21 121 ? 交叉和變異操作的更重要的點是不同的問題要構(gòu)造一些性能更優(yōu)的交叉和變異操作，才能保證算法的高效率，構(gòu)造時往往需要對所要求解的問題進行分析和運用一些經(jīng)驗。 比如 TSP求解時，前面使用的交叉操作使回路中的左邊部分的城市改變較大，但對 TSP來說，對回路中的各個位置應(yīng)有同等的進行機會，于是有如下改進的交叉操作，將兩個被選出的染色體，都隨機地分成三段（兩個染色體的分法相同），再從三段中隨機地選取一段在兩染色體之間進行交換，形成新染色體。 2022/8/21 122 ? 求解 TSP的變異操作有如下更有效的方式： 隨機產(chǎn)生 1和 n之間的兩相異整數(shù) k和 m， 若 km，則將 (w1,w2,… ， wk, wk+1,… ， wm,… ， wn) 變?yōu)椋? (w1,w2,… ， wm, wm1 ,… ， wk+1, wk,… ， wn). 如果是 km，則將 (w1,w2,… ， wk, wk+1,… ， wm,… ， wn) 變?yōu)椋? (wm,wm1,…,w1,wm+1,…,wk 1,wn,wn1,… ， wk). 上述變換方法可簡單說成是 逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端 。 2022/8/21 123 ? 這個變異操作針對 TSP是非常適用的，仿真實驗表明，僅使用這一個變異操作，不使用其他的變異操作和任何交叉操作，構(gòu)造了改進的遺傳算法，發(fā)現(xiàn)其性能相當(dāng)不錯，進化的代數(shù)要增加少量，在解的質(zhì)量相當(dāng)?shù)那闆r下，花費的總機時要少，因為每一代花的時間少了很多。 交叉概率和變異概率選取也是遺傳算法的性能影響最大的因素之一，直接影響著收斂速度。我們著重討論變異概率，變異概率大會擴大搜索范圍，使搜索過程不陷入局部極小，但也可能使正朝著最優(yōu)解緩慢前進的個體改變方向，破壞好個體；變異概率大則對染色體的破壞大，因此常設(shè)定一大一小兩個變異概率，當(dāng)整個種群平均適應(yīng)度增長較快時，使用小變異概率；反之使用較大變異概率。對整個種群使用相同的變異概率，并不利于優(yōu)良個體的成長和劣個體的改良。 2022/8/21 124 進化算法 ? 進化算法包括遺傳算法、進化程序設(shè)計、進化規(guī)劃和進化策略等等，進化算法的基本框架還是簡單遺傳算法所描述的框架，但在進化的方式上有較大的差異，選擇、交叉、變異、種群控制等有很多變化，進化算法的大致框圖可描述如右圖所示： 同遺傳算法一樣，進化算法的收斂性也有一些結(jié)果，在文獻 [9]中證明了在保存最優(yōu)個體時通用的進化計算是收斂的。但進化算法的很多結(jié)果是從遺傳算法推過去的。 遺傳算法對交叉操作要看重一些，認(rèn)為變異操作是算法的輔助操作；而進化規(guī)劃和進化策略認(rèn)為在一般意義上說交叉并不優(yōu)于變異，甚至可以不要交叉操作。 2022/8/21 125 2022/8/21 126 展望 ? 遺傳算法作為一種對生物進化現(xiàn)象進行仿真的程序，取得了人工遺傳的模擬效果，具有自適應(yīng)性。在遺傳算法的結(jié)構(gòu)中遺傳操作和選擇機制是兩個重要的因素，其聯(lián)系可用“遺傳算法 =遺傳操作 +選擇過程”這個邏輯關(guān)系來表示。 如果一個應(yīng)用問題不能求得目標(biāo)函數(shù)的全局最優(yōu)值 ,而只能或只希望求一定意義下的“滿意解”，這時 ,可供選擇的方法之一自然是遺傳算法，因為遺傳算法比其他算法有更多的優(yōu)勢?？上驳氖?,近年來遺傳算法在商業(yè)應(yīng)用方面取得了一系列重要成果。遺傳算法的商業(yè)應(yīng)用五花八門 ,覆蓋面甚廣 ,比如通用電器公司的計算機輔助設(shè)計系統(tǒng) Engeneous,這是一個采用了遺傳算法以及其他傳統(tǒng)的優(yōu)化技術(shù)做為尋優(yōu)手段的混合系統(tǒng) (hybrid system)。Engeneous已成功地應(yīng)用于汽輪機設(shè)計 ,并改善了新的波音777發(fā)動機的性能，這是目前正在研究和應(yīng)用的一個重要方面。 2022/8/21 127 ? 遺傳算法具有隱并行性，它可容易改造成為并行 /分布式算法，用來解決那些復(fù)雜性問題。 到目前，遺傳算法的理論機制仍不是很清楚，這可能和生命科學(xué)的研究一樣，將是一個永恒的研究課題，但也是一個難題。已有很多學(xué)者對遺傳算法作了一些深入的研究，近幾十年來，遺傳算法的文獻已相當(dāng)多，由于本書篇幅所限，僅介紹了遺傳算法的一些基本知識。 2022/8/21 128 模擬退火算法 ? 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù) Metropolis準(zhǔn)則，粒子在溫度 T時趨于平衡的概率為 eΔE/(kT)，其中 E為溫度 T時的內(nèi)能， ΔE為其改變量， k為 Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E模擬為目標(biāo)函數(shù)值 f，溫度 T演化成控制參數(shù) t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i和控制參數(shù)初值 t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解 → 計算目標(biāo)函數(shù)差 → 接受或舍棄”的迭代，并逐步衰減 t值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表 (Cooling Schedule)控制，包括控制參數(shù)的初值 t及其衰減因子 Δt、每個 t值時的迭代次數(shù) L和停止條件 S。 2022/8/21 129 模擬退火算法的模型 ? 模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。 模擬退火的基本思想 : (1) 初始化：初始溫度 T(充分大 )，初始解狀態(tài) S(是算法迭代的起點 )， 每個 T值的迭代次數(shù) L (2) 對 k=1， …… ， L做第 (3)至第 6步： (3) 產(chǎn)生新解 S′ (4) 計算增量 Δt′=C(S′)C(S)，其中 C(S)為評價函數(shù) (5) 若 Δt′0則接受 S′作為新的當(dāng)前解，否則以概率exp(Δt′/T)接受 S′作為新的當(dāng)前解 . (6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。 終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。 (7) T逐漸減少，且 T0，然后轉(zhuǎn)第 2步。 2022/8/21 130 2022/8/21 131 2022/8/21 132 模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟： ? 第一步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進度表的選取有一定的影響。 ? 第二步是計算與新解所對應(yīng)的目標(biāo)函數(shù)差。因為目標(biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應(yīng)用而言，這是計算目標(biāo)函數(shù)差的最快方法。 2022/8/21 133 ? 第三步是判斷新解是否被接受 ,判斷的依據(jù)是一個接受準(zhǔn)則，最常用的接受準(zhǔn)則是 Metropo1is準(zhǔn)則 : 若 Δt′0則接受S′作為新的當(dāng)前解 S，否則以概率 exp(Δt′/T)接受 S′作為新的當(dāng)前解 S。 第四步是當(dāng)新解被確定接受時，用新解代替當(dāng)前解，這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標(biāo)函數(shù)值即可。此時，當(dāng)前解實現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開始下一輪試驗。而當(dāng)新解被判定為舍棄時，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗。 2022/8/21 134 ? 模擬退火算法與初始值無關(guān)，算法求得的解與初