【正文】 ,1}L 給定目標(biāo)函數(shù) f，有 f(bi)，并且 76 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 8 0F(BI)∞ P 同時(shí) f(bi)≠f(bi+1) 求滿足下式 max{f(bi)|bi∈ {0,1}L} 的 bi。 遺傳算法的應(yīng)用 遺傳算法已經(jīng)在很多復(fù) 雜問(wèn)題（比如說(shuō) NP難題）、機(jī)器學(xué)習(xí)和簡(jiǎn)單的進(jìn)化規(guī)劃中得到了使用。 遺傳算法的優(yōu)勢(shì)在于他的并行性。 遺傳算法更容易實(shí)現(xiàn)。如果編碼方法也相同，那你只需要改變一下適應(yīng)度函數(shù)就可以了。 遺傳算法的缺點(diǎn)是它的計(jì)算時(shí)間太長(zhǎng)。當(dāng)然，對(duì)于今天的高速計(jì)算機(jī)來(lái)說(shuō)，這已經(jīng)不是個(gè)大問(wèn)題了。 其中： (1) 模式表示一些相似的模塊，它描述了在某些位置上具有相似結(jié)構(gòu)特征的個(gè)體編碼串的一個(gè)子集。 (3) 模式 H 中第一個(gè)確定基因值的位置和最后一個(gè)確定 基因值的位置之間的距離稱為該模式的模式定義長(zhǎng)度。 積木塊假設(shè) 模式定理說(shuō)明了具有某種結(jié)構(gòu)特征的模式在遺傳進(jìn)化過(guò)程中其樣本數(shù)將按指數(shù)級(jí)增加，這種模式具有低階，短的定義長(zhǎng)度，且平均適應(yīng)度高于群體平均適應(yīng)度的模式。 模式定理說(shuō)明了積木塊的樣本數(shù)呈指數(shù)級(jí)增長(zhǎng)，也說(shuō)明了用遺傳算法尋求最優(yōu)化樣本的可能性，但它并未指明遺傳算法一定能夠?qū)で蟮阶顑?yōu)樣本而積木塊假設(shè)卻說(shuō)明了遺傳算法 的這種能力。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 11 作用：積木塊假設(shè)說(shuō)明了用遺傳算法求解各類問(wèn)題的基本思想，即通過(guò)基因塊之間的相互拼接能夠產(chǎn)生出問(wèn)題更好的解。 編碼 定義：遺傳算法中如何描述問(wèn)題的可行解，即把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就稱為編碼 作用： 編碼是應(yīng)用遺傳算法時(shí)要解決的首要問(wèn)題，也是設(shè)計(jì)遺 傳算法時(shí)的一個(gè)關(guān)鍵步驟。由此看見(jiàn)，編碼方法在很大程度上決定了如何進(jìn)行群體的遺傳化運(yùn)算及遺傳進(jìn)化運(yùn)算效率。 在使用二進(jìn)制編碼時(shí)，每一個(gè)基因就是一個(gè)由 0或者 1組成的字符串。另一方面，這種方法對(duì)于很多問(wèn)題來(lái)都很不自然，所以有時(shí)候在交叉和變異結(jié)束后還要做一些調(diào)整。 假設(shè)有一個(gè)二近制編碼為 B=bmbm1…b2b1, 其對(duì)應(yīng)的格雷碼為 G=gmgm1..g2g1。 例如：若一個(gè)優(yōu)化問(wèn)題含有 5 個(gè)變量 xi ( I=1,2,…5) 每個(gè)變量都有其對(duì)應(yīng)的上下限[Umin,Umax],則 : X: 就表示一個(gè)體的基因型。 （ 2） 適合于精度要求較高的遺傳算法 （ 3） 便于較大空間的遺傳搜索 （ 4） 改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算效率 （ 5） 便于遺傳算法和經(jīng)典油畫(huà)方法的混合使用 （ 6） 便于設(shè)計(jì)針對(duì)問(wèn)題的專門知識(shí)的知識(shí)型遺傳算子 （ 7） 便于處理復(fù)雜的決策變量約束條件 值編碼（ Value Encoding） 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 13 在很多問(wèn)題中我們還可以采用直接的值編碼 ,也就是說(shuō)用一些比較復(fù)雜的數(shù)來(lái)編碼 ,比如說(shuō)實(shí)數(shù)。 在值編碼中，每個(gè)基因就是一串取值。 表 32值編碼串 基因 A 基因 B ABDJEIFJDHDIERJFDLDF 基因 C （ back） , (back), (right), (forward), (left) 編碼原則 （ 1） 應(yīng)使用能易于產(chǎn)生所求問(wèn)題相關(guān)的且具有低階短定義長(zhǎng)度模式的編碼方案。 求適應(yīng)度函數(shù) 評(píng)價(jià) 個(gè)體適應(yīng)度 定義：遺傳算法中使用適應(yīng)度這個(gè)概念來(lái)衡量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或接近或有助于找到最優(yōu)解的優(yōu)良程度。度量個(gè)體適應(yīng)度的函數(shù)叫做適應(yīng)度函數(shù)。 （ 2） 由個(gè)體表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。 適應(yīng)度尺度變換 在遺傳算法中各個(gè)個(gè)體被遺傳到下一代群體中的概率由該個(gè)體 的適應(yīng)度來(lái)決定。在遺傳算法運(yùn)行的初期階段，算法能夠?qū)σ? 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 14 些適應(yīng)度教高的個(gè)體進(jìn)行控制，降低其適應(yīng)度與其他個(gè)體適應(yīng)度之間的差異程度，從而限制其復(fù)制數(shù)量，以維護(hù)群體的多樣性。 適應(yīng)度尺度變換方法： （ 1） 線性尺度變換 公式為： F’’=aF+b （ 3－ 2） 其中， F 為原適應(yīng)度， F”為新適應(yīng)度， a,b 為系數(shù)。 F’max要等于原平均適應(yīng)度 Favg 的指定倍數(shù)。 （ 3） 指數(shù)尺度變換 公式為： F’=exp(βF) （ 34） 其中 β 決定了選擇的強(qiáng)制性， β 越小，原有適應(yīng)度較高的個(gè)體的新適應(yīng)度就越與其他個(gè)體的新適應(yīng)度相差越大，亦即越增加了選擇該個(gè)體的強(qiáng)制性。選擇操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上，選擇操作的目 的是為了避免基因缺失，提高全局收斂性和計(jì)算效率。各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 15 （ 2） 最優(yōu)保存 策略：當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，而是 它來(lái)替代掉本代群 體中經(jīng)過(guò)交叉變異等遺傳操作后所產(chǎn)生適應(yīng)度最低的個(gè)體。 最優(yōu)保存策略進(jìn)化模型的具體操作過(guò)程是： a. 找出當(dāng)前群體中適應(yīng)度最高的個(gè)體和適應(yīng)度最低的個(gè)體。 c. 用迄今為止的最好個(gè)體替換掉當(dāng)前群體中最差個(gè)體。 （ 3） 排序選擇 主要思想是：對(duì)群體中所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率，具體操作過(guò)如下： a. 對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行降序排序。 c. 以各個(gè)分配到的概率值做為其能夠遺傳到下一代的概率，基于這些概率值用比例選擇（賭輪選擇）的方法產(chǎn)生下一代群體?；蛟绞沁m應(yīng)環(huán)境，那么它被 選擇到的機(jī)會(huì)就越大。每一個(gè)基因所占的地方的大小和它的適應(yīng)度成正比。顯然，適應(yīng)度越大的基因被選到的機(jī)會(huì)就越大。 交叉算子 遺傳算法中的所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成 2 個(gè)新的個(gè)體，交叉運(yùn)算是遺傳算法區(qū)別其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。下面介紹集中適合于二進(jìn)制編碼個(gè)體或浮點(diǎn)數(shù)編碼個(gè)體的交叉算子： （ 1） 單點(diǎn)交叉：它是指?jìng)€(gè)體編碼串中只隨即設(shè)置一個(gè)交叉點(diǎn)然后在該點(diǎn)相互交換 2 個(gè)配 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 17 對(duì)個(gè)體的部分染色體。 （ 2） 雙點(diǎn)交叉和多點(diǎn)交叉：是指定個(gè)體編碼串中隨機(jī)設(shè)置 2 個(gè)或多個(gè)交叉點(diǎn)然后進(jìn)行部分基因交換。 例如： A: x x | x x x x x | x x x ?A’: x x | y y y y y| x x x B: y y | y y y y y | y y y?B’: y y | x x x x x| y y y 交叉點(diǎn) 1 交叉點(diǎn) 2 雙點(diǎn)交叉示意圖 11001011 + 11011111 = 11011111 圖（ 32） 均勻交叉算子 (Uniform Crossover):子代基因的每一個(gè)位點(diǎn)是隨機(jī)地來(lái)自于兩個(gè)父代基因中的一個(gè)的 。 位點(diǎn)轉(zhuǎn)換算子（ Bit Inversion）：選擇一些位點(diǎn)然后將這些地方的 0， 1互換； 圖（ 34） 在遺傳算法中使用變異算子的目的： 1 改善遺傳算法局部搜索能力 2 維持群體多樣性，防止出現(xiàn)早熟現(xiàn)象 變異算子的常用方法： a、基本位變異：指對(duì)個(gè)體基因串以變異概率隨機(jī)指定某一位或幾位基因座上的基因值做變異運(yùn)算 b、均勻變異：指分別用符合某一范圍內(nèi)隨機(jī)數(shù)，以某一較小概率來(lái)替換個(gè)體編碼串中各個(gè)基因座上的原有基因值。在進(jìn)行邊界變異操作時(shí)，隨機(jī)的取基因座的 2 個(gè)對(duì)應(yīng)邊界基因值之一去替換原來(lái) 的基因值。 遺傳算法的其他運(yùn)行參數(shù) （ 1） 編碼串長(zhǎng)度 L：使用二進(jìn)制來(lái)表示個(gè)體時(shí)，編碼串長(zhǎng)度 L 的選取與問(wèn)題所要求的求 解精度有關(guān)。 M 取值越小可提運(yùn)算速度但降低群體多樣性。一般建議范圍 20100。交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法，一般建議范圍是 。 （ 4） 變異概率 Pm。建議范圍是 100~1000 （ 6） 代溝 G：表示每一代群體中被替換掉的個(gè)體在全部個(gè)體中所占的百分比。 所求問(wèn)題為 f(x)=x+9*sin(4x)+8*cos(3x)的最大值 ， 其中 定義域?yàn)?5=x=12，采用二進(jìn)制編碼，選取種群個(gè)體數(shù)目為 20， 設(shè)定 二進(jìn)制編碼長(zhǎng)度為 10，交叉概率為 ，變異概率是 。 10位二進(jìn)制 編碼串可以表示為 0 到 1023 之間的 1024 個(gè)不同的數(shù)，故將 Umax Umin的定義域離散為 1023個(gè)均等的區(qū)域，包括兩個(gè)端點(diǎn)在內(nèi)共有 1024個(gè)不同的離散點(diǎn)。再將分別表示 Umax Umin 的二進(jìn)制編碼串聯(lián)在一起，組成一個(gè) 20 位長(zhǎng)的二進(jìn)制編碼串，它構(gòu)成了這個(gè)函數(shù)優(yōu)化問(wèn)題的染色體編碼方法。 例如：就表示為一個(gè)個(gè)體的基因型，其中前十位表示 Umax 后十位表示 Umin X: 11111111 00000000 2π 0 00000000…00000000=0 ? Umin 00000000…00000001=1 ? Umin+￡ … … … 11111111…11111111=2^l1 ? Umax 則二進(jìn)制編碼精度為： ￡ =UmaxUmin/2^l1 公式（ 41） 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 21 假設(shè)某一個(gè)個(gè)體編碼是 X: blbl1bl2…b2b1 確定解碼方法 Xi=Umin+ L ∑ bi* 2^( i1) * UmaxUmin/2^l 1 i=1 公式（ 42） 解碼時(shí)需先將 20 位長(zhǎng)的二進(jìn)制編碼串切斷為兩個(gè) 10 位長(zhǎng)的二進(jìn)制編碼串，然后分別將他們轉(zhuǎn)化為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為 Y1 Y2?；具z傳算法使用比例選擇算子來(lái)確定群體中各個(gè)個(gè)體遺傳到下一代群體中的數(shù)量。 （一）預(yù)先指定一個(gè)較小的數(shù)。 （三）當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。 （一）預(yù)先指定一個(gè)較大的數(shù)。 （三）當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值 根據(jù)適者生存原則選擇下一代的個(gè)體。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。以 (386) 為選中 bi 為下一代個(gè)體的次數(shù)。 b、適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少；甚至被淘汰。對(duì)于問(wèn)題求解角度來(lái)講，就是選擇出和最優(yōu)解較接近的中間解。 c. 在區(qū)間（ 0， S）上隨機(jī)的產(chǎn)生一個(gè)數(shù) r 從某個(gè)基因開(kāi)始，逐一取出基因來(lái)，把它的適應(yīng)度加到 s 上去（ s 開(kāi)始為 0），如果 s 大于 r，則停止循環(huán)并返回當(dāng)前基因； 當(dāng)然，第一步在計(jì)算中只需要執(zhí)行一次 因此基因越是適應(yīng)環(huán)境那么它被選擇到的機(jī)會(huì)就越大。在選中的位置實(shí)行交換。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。 假如鄰接基因座之間的關(guān)系能夠提供比較好的個(gè)體性狀和較高的個(gè)體適應(yīng)的話則這個(gè)單點(diǎn)交叉操作破壞這種個(gè)體性狀和降低個(gè)體適應(yīng)度的可能性最小 變異運(yùn)算 使用第三章的基本位變異 算子確定遺 根據(jù)生物遺傳中基因變異的原理，以變異概率 Pm 對(duì)某些個(gè)體的某些位執(zhí)行變異。變異概率 Pm 與生物變異極小的情況一致，所以， Pm的取值較小，一般取 。 單靠變異不能在求 解中得到好處。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。 遺傳算法的運(yùn)行參數(shù) 群體大小： M （ 20100） 終止代數(shù)： T （ 100500） 交叉概率： Pc （ ） 變異概率： Pm () 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 24 算例驗(yàn)證 【問(wèn)題】求 f(x)= 11*sin(6*x)+7*cos(5*x)的最大值，其中 0=x=2*pi 【分析】選擇二進(jìn) 制編碼，種群中的個(gè)體數(shù)目為 20，二進(jìn)制編碼長(zhǎng)度為 10，交叉概率為,變異概率為 X（個(gè)體表現(xiàn)型值） : Y（目標(biāo)函數(shù)值） : FINAL(最優(yōu)解 )= 由圖 可見(jiàn)，遺傳代數(shù)較小時(shí)， 交叉概率較大時(shí)圖象局部最優(yōu)解分散， 全局最優(yōu)解緩慢收斂。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 26 【分析】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為 50，二進(jìn)制編碼長(zhǎng)度為 10，交叉概率為,變異概率為 X（個(gè)體表現(xiàn)型值） :