【正文】 問題 。 ? （ 2） 遺傳算法對(duì)待求解問題的指標(biāo)函數(shù)沒有什么特殊的要求 ， 比如不要求諸如連續(xù)性 、 導(dǎo)數(shù)存在 、 單峰值假設(shè)等 。 甚至于不需要顯式的寫出指標(biāo)函數(shù) 。 ? （ 3） 在經(jīng)過編碼以后 ， 遺傳算法幾乎不需要任何與問題有關(guān)的知識(shí) ， 唯一需要的信息是適應(yīng)值的計(jì)算 。也不需要使用者對(duì)問題有很深入的了解和求解技巧 ，通過選擇 、 交配和變異等簡(jiǎn)單的操作求解復(fù)雜的問題 ， 是一個(gè)比較通用的優(yōu)化算法 。 ? （ 4） 遺傳算法具有天然的并行性 ， 適用于并行求解 。 收斂性定理： 如果在代的進(jìn)化過程中，遺傳算法每次保留到目前為止的最好解，并且算法以交配和變異為其隨機(jī)化操作，則對(duì)于一個(gè)全局最優(yōu)化問題，當(dāng)進(jìn)化代數(shù)趨于無窮時(shí)，遺傳算法找到最優(yōu)解的概率為 1。 遺傳算法的實(shí)現(xiàn)問題 ? 編碼 ? 評(píng)價(jià) ? 適應(yīng)函數(shù) ? 交配規(guī)則 ? 停止條件 編碼舉例：十桿桁架問題 100 kg 100 kg 30 30 30 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 假設(shè)每個(gè)桿的截面積在 10之間，在該范圍內(nèi)，有 16個(gè)可能的取值。這樣我們可以用 4位二進(jìn)制向量表示截面積的可能取值，其中 0000表示 ， 1111表示 10，余下的 14位二進(jìn)制向量表示其他的截面積的可能取值。這樣 10個(gè)桿，共用 40位二進(jìn)制向量表示一個(gè)十桿桁架問題的染色體。 例： 0010 1110 0001 0011 1011 0011 1111 0011 0011 1010 編碼舉例：旅行商問題 ? 對(duì)于 n個(gè)城市的旅行商問題，可以用一個(gè)矩陣來表示一個(gè)可能解。 ? 如果按行展開該矩陣，則該可能解可以用一個(gè) 4 4的二進(jìn)制向量表示為： 0100100000010010 ????????????01001000000100104321DCBA二進(jìn)制表示存在的問題 采用這樣的表示方法 ， 對(duì)于 n城市的旅行商問題 ， 至少需要用 n n位二進(jìn)制向量表示一個(gè)可能的旅行路線 。 一個(gè) n n位二進(jìn)制向量 ，所有可能的編碼個(gè)數(shù)為 ， 而一個(gè)對(duì)稱的 n城市旅行商問題的可能解個(gè)數(shù)為 n!/2， 只占編碼個(gè)數(shù)非常小的比例 。 以 n＝ 10為例 ， 編碼個(gè)數(shù)為可能解個(gè)數(shù)的 1023倍 。 可能解在整個(gè)狀態(tài)空間中 ， 是非常稀疏的 ， 交配和變異所產(chǎn)生的是大量的非可能解 。 nn?2遺傳算法的評(píng)價(jià) ? 定理 ，遺傳算法找到最優(yōu)解的概率為 1。即保證了遺傳算法的收斂性。但在實(shí)際計(jì)算時(shí)，希望隨時(shí)了解遺傳算法的進(jìn)展情況，監(jiān)視算法的變化趨勢(shì)。 當(dāng)前最好法 ? 該方法在每一代進(jìn)化過程中，記錄得到的最好解，通過最好解的變化，了解算法的變化趨勢(shì)。不同的算法之間，也可以通過該最好解的變化情況進(jìn)行橫向比較。 在線比較法 ? 該方法用當(dāng)前代中染色體的平均指標(biāo)函數(shù)值來刻劃算法的變化趨勢(shì)。計(jì)算方法如下： 其中 T為當(dāng)前代中染色體的個(gè)數(shù) 。 ???Ttlineon tfTv1_ )(1離線比較法 ? 該方法與在線比較法有些相似，但是用進(jìn)化過程中每代最好解的指標(biāo)函數(shù)值的平均值，來評(píng)價(jià)算法的進(jìn)化過程。計(jì)算方法如下： 其中 T是到目前為止的進(jìn)化代數(shù)， f*(t)是第 t代中，染色體的最好指標(biāo)函數(shù)值。 ???Ttlineo ff tfTv1*_ )(1適應(yīng)函數(shù) ? 一般情況下，我們可以直接選取問題的指標(biāo)函數(shù)作為適應(yīng)函數(shù)。如求函數(shù) f(x)的最大值，就可以直接采用 f(x)為適應(yīng)函數(shù)。但在有些情況下，函數(shù) f(x)在最大值附近的變化可能會(huì)非常小，以至于他們的適應(yīng)值非常接近，很難區(qū)分出那個(gè)染色體占優(yōu)。在這種情況下，希望定義新的適應(yīng)函數(shù)，要求該適應(yīng)函數(shù)與問題的指標(biāo)函數(shù)具有相同的變化趨勢(shì)，但變化的速度更快。 非線性加速適應(yīng)函數(shù) 其中 f(x)是問題的指標(biāo)函數(shù)， fmax是當(dāng)前得到的最優(yōu)指標(biāo)函數(shù)值， M是一個(gè)充分大的數(shù)。 ????????其他如果,)(,)(1)(39。m axm axMfxfxffxf線性加速適應(yīng)函數(shù) 上式中的第一個(gè)方程表示變換前后的平均值不變，第二個(gè)方程表示將當(dāng)前的最優(yōu)值放大為平均值的 M倍。 ?? ?? )()(39。 xfxf???????????????????????mxfMxfmxfmxfmiiimimiimii1111)()}({m a x)()(????二進(jìn)制編碼的交配規(guī)則 ? 雙親雙子法 a1 a2 ... ai ai+1 ... an b1 b2 ... bi bi+1 ... bn a1 a2 ... ai bi+1 ... bn b1 b2 ... bi ai+1 ... an 交配前 交配后 交配位置 ? 變化交配法 1 1 0 1 0 0 1 1 1 0 0 0 1 0 由于兩個(gè)父染色體的前三位完全一致，因此當(dāng)交配位選擇在前三位時(shí)，其子染色體將與兩個(gè)父染色體完全一致。變化交配法就是在隨機(jī)產(chǎn)生交配位時(shí)，排除掉這樣的交配位。 ? 多交配位法 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 整數(shù)編碼的交配規(guī)則 ? 下面以旅行商問題為例，介紹幾種整數(shù)編碼的交配規(guī)則。 常規(guī)交配法 ? 隨機(jī)選取一個(gè)交配位，子代 1交配位之前的基因選自父代 1交配位之間的基因，交配位之后的基因，從父代 2中按順序選取那些沒有出現(xiàn)過的基因。 交配位 交配位 父代 1： 1 2 3 4 5 6 7 8 子代 1： 1 2 3 4 5 7 8 6 父代 2： 5 2 1 7 3 8 4 6 子代 2： 5 2 1 7 3 4 6 8 ? 基于次序的交配法 父代 1: 1 2 3 4 5 6 7 8 9 10 父代 2: 5 9 2 4 6 1 10 7 3 8 所選位置 : * * * * 父代 1中與所選位置相對(duì)應(yīng)的數(shù)字為： 8。 從父代 2中找出這些數(shù)字 ， 并去除它們 ， 其中 b表示空位置： 父代 2: b 9 b 4 6 1 10 7 b b 用 8依次填入上述父代 2的空位置中 ， 得到子代 1： 子代 1: 2 9 3 4 6 1 10 7 5 8 基于位置的交配法 ? 首先隨機(jī)產(chǎn)生一組位置。對(duì)于這些位置上的基因，子代 1從父代 2中直接得到，子代 1的其他位置的基因，按順序從父代1中選取那些不相重的基因。子代 2也類似處理。如： 父代 1： 1 2 3 4 5 6 7 8 9 父代 2： 5 9 2 4 6 1 7 3 8 * * * * 子代 1： 1 9 2 4 6 5 7 3 8 基于部分映射的交配法 ? 對(duì)于兩個(gè)選定的父代染色體父代 1和父代2，隨機(jī)產(chǎn)生兩個(gè)位置，兩個(gè)父代在這兩個(gè)位置之間的基因產(chǎn)生對(duì)應(yīng)對(duì)，然后用這種對(duì)應(yīng)對(duì)分別去替換兩個(gè)父代的基因，從而產(chǎn)生兩個(gè)子代。 父代 1： 2 6 4 3 8 1 5 7 9 父代 2： 8 5 1 7 6 2 4 3 9 子代 1： 1 8 4 7 6 2 5 3 9 對(duì)應(yīng)對(duì)： 3:7 8:6 1:2 變異規(guī)則 ? 二進(jìn)制編碼中的變異 ? 整數(shù)編碼中的變異 二進(jìn)制編碼中的變異 ? 當(dāng)問題以二進(jìn)制編碼形式表示時(shí)，隨機(jī)的產(chǎn)生一個(gè)變異位，被選中的基因由“ 0”變?yōu)椤?1”，或者由“ 1”變?yōu)椤?0”。 變異前 變異后 1 1 0 1 1 0 1 1 1 0 1 0 0 1 變異位 整數(shù)編碼中的變異 ? 基于位置的變異 ? 隨機(jī)的產(chǎn)生兩個(gè)變異位，然后將第二個(gè)變異位上的基因移動(dòng)到第一變異位之前。 2 1 3 6 4 5 7 2 4 1 3 6 5 7 變異前 變異后 ? 基于次序的變異 ? 隨機(jī)的產(chǎn)生兩個(gè)變異位，然后交換這兩個(gè)變異位上的基因。 2 1 3 6 4 5 7 2 4 3 6 1 5 7 變異前 變異后 ? 打亂變異 ? 隨機(jī)選取染色體上的一段，然后打亂在該段內(nèi)的基因次序。 2 1 3 6 4 5 7 2 4 3 6 1 5 7 變異前 變異后 ? 逆序交換方式可以認(rèn)為是打亂變異的一個(gè)特例。 性能評(píng)價(jià) ? 如何對(duì)遺傳算法的性能進(jìn)行評(píng)價(jià)是一件很困難的事情，為此需要確定性能度量和一些具有代表性的函數(shù)。一般可以用達(dá)到最優(yōu)點(diǎn)時(shí)性能函數(shù)值的平均計(jì)算次數(shù)和計(jì)算所需要的時(shí)間來進(jìn)行度量。一些學(xué)者給出了如下的測(cè)試函數(shù)集，這些函數(shù)或者是多峰值的，或者是不連續(xù)的，或者是具有一定的噪聲的，對(duì)于求解他們的最小值具有一定的難度。 1010,)()](s i n1[)()(s i n)(:1122121221211111????????? ?????? ? ???ininiixkyykkyyknxfF ???55) ] } ,(s i n1[)()](s i n1[)()({ s i n)(:726251114262514231212?????????? ????innniiixxkkkxxkkkxxkkxfF???測(cè)試函數(shù)舉例 高級(jí)搜索小結(jié) ? 局部搜索 ? 模擬退火算法 ? 遺傳算法