改進遺傳算法

1、遺傳算法的改進遺傳算法的改進遺傳算法存在的問題遺傳算法存在的問題1. 適應度函數(shù)標定方式多種多樣，沒有一個簡潔通用的方法2. 遺傳算法的早熟現(xiàn)象（即很快收斂到局部最優(yōu)解而不是全局最優(yōu)解）是迄今為止最難處理的關鍵問題。3. 快要接近最優(yōu)解時在最優(yōu)解附近左右擺動，收斂較慢。開始時進化速度很快，甚至以指數(shù)級進化速度朝著最優(yōu)解方向前進，但不久以后，進化速度就會變慢，臨近全局最優(yōu)解時則可能是幾百代、上千代才向目標逼近一小步，有時甚至停滯不前，出現(xiàn)早熟收斂。 遺傳遺傳算法改進方法算法改進方法基于以上介紹可知，遺傳算法通常需要解決以下問題：確定編碼方案，適應度函數(shù)標定，選擇遺傳操作方式和相關控制參數(shù)，停止準

2、則確定等，相應地，為改進簡單遺傳算法的實際計算性能，很多的改進工作也是從參數(shù)編碼、初始種群設定、適應度函數(shù)標定、遺傳操作算子、控制參數(shù)的選擇以及遺傳算法的結構等方面提出的?；诓煌膯栴}，遺傳算法可以有不同的改進和變形，這也是遺傳算法內容豐富和作用強大的原因。人工智能及其應用4改進的遺傳算法 編碼方法的選擇 編碼的修復 適值函數(shù)的標定 選擇策略 停止準則的改進1.1.編碼方法編碼方法 這里來介紹除了0-1編碼以為的其他三種重要的編碼方法 1.順序編碼順序編碼 順序編碼是用1到n的自然數(shù)來編碼，此種編碼不允許重復，又稱為自然數(shù)編碼，例如下面是一個染色體長度為n=7的順序編碼： X=(2 3 1

3、5 4 7 6) 對于有7個城市的旅行商問題，城市序號為1,2，.，7，則上述編碼可以表示一個行走的路線。該編碼方法具有廣泛的適應范圍，如指派問題、旅行商問題和單機調度等問題。 2.實數(shù)編碼實數(shù)編碼對于染色體X=（x1,x2,，xi,xn）,1in, ，則稱該染色體為實數(shù)編碼。實數(shù)編碼具有精度高、便于大空間搜索、運算簡單的特點，特別適合于實優(yōu)化問題，但是反應不出基因的特征。 3.整數(shù)編碼整數(shù)編碼 對于染色體X=（x1,x2,，xi,xn）,1ini, ni 為第i位基因的最大取值，則稱染色體為整數(shù)編碼。顯然不同位置上的基因取值可以不同。整數(shù)編碼可以適應于新產品投入、時間優(yōu)化和伙伴挑選等問題。

4、ixR2.2.不合法編碼的修復不合法編碼的修復 對于普通的二進制編碼，通常的交叉和變異不會改變編碼的合法性，但是對于順序編碼、實數(shù)編碼，會造成編碼的不合法或者超出可行域，因此必須對不合法的編碼進行處理，通常的處理手段為拒絕或者修復。下面介紹修復的方法。 順序編碼的合法性修復 實數(shù)編碼的合法性修復1. 順序編碼的修復順序編碼的修復 順序編碼的合法性修復策略主要包括：交叉修復策略部分映射交叉順序交叉循環(huán)交叉變異修復策略換位變異移位變異交叉修復策略之部分映射交叉交叉修復策略之部分映射交叉 部分映射交叉主要用于解決雙切點交叉引起的非法性?？梢越鉀Q子代的基因重復和部分基因的丟失問題，保證基因的多樣性。其

5、主要步驟為：選則切點，交換中間部分確定映射關系將未交換部分按映射關系恢復合法性交叉修復策略之順序交叉交叉修復策略之順序交叉 順序交叉是部分映射交叉的變形，相當于使用了不同的映射關系。其可以較好的保留相鄰關系、先后關系，但是不能保留位值特征，可以用來解決旅行商之類的拓撲問題。u旅行商問題 在尋求單一旅行者由起點出發(fā)，通過所有給定的需求點之后，最后再回到原點的最小路徑成本順序交叉的步驟如下： 選則切點， 交換中間部分 從第二個切點后的第一個基因開始分別列出兩個原來染色體的基因順序，直到列完 劃掉各自交換部分的基因 按劃掉后的相對順序從后開始補齊原來的染色體的基因交叉修復策略之循環(huán)交叉交叉修復策略之

6、循環(huán)交叉 循環(huán)交叉的基本思想是子串位置上的值必須與父母相同位置上的值相一致。簡單來說，就是父母代在進行交叉運算時按某種方式交換某些相同位置的基因，其余位置的基因不變，組成子代。這種交叉方式適合于解決指派問題。u在滿足特定指派要求條件下，使指派方案總體效果最佳。其修復策略較麻煩，需要時可以查找文獻，大家需要記住的是：循環(huán)交叉是用來解決指派這一類的問題的循環(huán)交叉是用來解決指派這一類的問題的2.變異修復變異修復策略策略 簡單的二進制變異時候只需要把變成，變成，而順序編碼的變異策略不能這樣進行，一般由下面兩種策略：換位變異換位變異是隨機在染色體上選則兩個基因，交換它們的基因值移位變異移位變異是任意選則

7、一個基因，將其移到最前面。3.實數(shù)實數(shù)編碼的合法性修復之凸組合編碼的合法性修復之凸組合交叉交叉 實數(shù)編碼的交叉操作（單切點交叉、雙切點交叉）通常不會改變其合法性問題。但是，有時會導致解碼后的值超出可行域。針對這樣的問題，產生了凸組合交叉。簡單來說，就是直接引用凸集理論，將父母兩個染色體對應的看成兩個點，其子代只能位于這兩個點的連線上。如：有雙親P1=（x1,x2,x3,，xn）P2=（y1,y2,x3,，yn）則可以產生的兩個后代是：C1=aP1+(1-a)P2C2=(1-a)P1+aP2這里，a要保證大于0且小于1. 這樣做的不好處是導致種群的基因向中間匯聚，導致基因的分散性不好，逐步丟失很

8、多基因。這是與基因的多樣性相違背。4.實數(shù)編碼的合法性修復之變異實數(shù)編碼的合法性修復之變異不同于二進制編碼，實數(shù)編碼的變異可以是任意的，通常有如下兩種變異方法：位值變異向梯度方向變異位值變異是隨機選取染色體上某一位基因，在其上加上一個變異補補償D，通常便已步長是按一定規(guī)律產生的呈一定分布規(guī)律的隨機數(shù)向梯度方向的變異較好的考慮了問題本身的性質，效率比較高簡單來說，就是把某個染色體看成一個具有n個分量的點，然后求目標函數(shù)在這個點處的梯度 對于最大化問題，就是染色體本身加上這個點處的梯度乘以一個隨機數(shù)（0到1之間） 對于最小化問題，就是染色體本身加上這個點處的負梯度乘以一個隨機數(shù)（0到1之間）3.適

9、值適值函數(shù)的標定函數(shù)的標定1.1.標定的目的標定的目的 將目標函數(shù)映射為適值函數(shù)，從而能夠直接將適值函數(shù)與群體中的個體優(yōu)劣相聯(lián)系。 對目標函數(shù)進來標定，來調節(jié)選擇壓力。2.選擇壓力的概念 選擇壓力是指種群中好、壞個體被選中的概率之差，如果差別較大，則稱選擇壓力大例如：五個染色體構成的一個種群，其目標函數(shù)值分別為 f1=1010,f2=1008,f3=1002,f4=1005,f5=1015 因為5個個體的適應值相差不大，選中概率基本上在0.2左右，概率差別很小，即選擇壓力小，這將導致遺傳算法的選優(yōu)功能被弱化。所以要對目標函數(shù)進行標定，來調節(jié)選擇壓力。 可以進行如下標定：F=f -1000，這時

10、標定后的染色體被選中的概率差別大幅度增加，即選擇壓力增大了，通過以上分析可以看到，適值函數(shù)的標定可以調節(jié)選擇壓力的大小，而通過調節(jié)選擇壓力的大小能夠實現(xiàn)遺傳算法中局部搜索和廣域搜索的調節(jié)。一般來說，遺傳算法在開始時應該注重廣域搜索，通過使用較小的選擇壓力來實現(xiàn)，隨著迭代的進行，逐步偏重于局部搜索，通過使用較大的選擇壓力來實現(xiàn)2.2.適值得標定方法適值得標定方法 線性標定 動態(tài)線性標定 冪律標定 對數(shù)標定 指數(shù)標定線性標定線性標定標定方法：F=af+b其中，f為目標函數(shù)，F(xiàn)為標定后的適值函數(shù)，參數(shù)a和b要根據(jù)不同的問題進行設定。 最大化問題 對于最大化問題 ，可以令a=1, ，則適值函數(shù)為 其中

11、， 是一個較小的數(shù)目的是使種群中最差的個體仍然有繁殖的機會，增加種群的多樣性。min(x)Fffmax(x)fminbf 最小化問題對于最小化問題 ，可以令a=-1， ，則適值函數(shù)為 其中， 也是一個較小的數(shù)，其意義與最大化問題中的設置相同min(x)fmaxbfmax(x)Fff 動態(tài)線性標定動態(tài)線性標定 線性標定中的參數(shù)隨著迭代次數(shù)的增加而變化時就得到了動態(tài)線性標定。可以表述如下 其中，上標k為迭代指標，表明參數(shù)是隨著迭代次數(shù)的增加而變化的 最大化問題 對于最大化問題，可以令 =1， ，則適值函數(shù)為 kaminkkkbf minkkFffkkFa fb其中， 是第k代的最小目標函數(shù)值， 是

12、一個較小的數(shù)，目的與線性標定中的 相同， 是使種群中最差的個體仍然有一點點繁殖的機會，從而增加種群的多樣性。 最小化問題 對于最小化問題 ，可以令a=-1，b= ，則適值函數(shù)為 其中， 也是一個較小的數(shù)，其意義和最大化問題設置相同。minkfkmin(x)fmaxkkfmaxkkFff kk 對于調節(jié)選擇壓力的作用 的引入能夠調節(jié)選擇壓力，即好壞個體選擇概率的差，使廣域搜索范圍寬，保持種群的多樣性，而局部搜索細致，保持收斂性。 在算法開始運行的時候，希望選擇壓力較小，所以 取值較大，使不同個體間的選擇概率相差不大，到種群進化的后期，希望選擇壓力較大，所以 取值較小，使不同個體間的選擇概率相差變

13、大，種群將很快達到收斂，從而解決了在最優(yōu)解附近收斂較慢的問題。kkkk 冪律標定冪律標定冪律標定是采用如下的構造方式 其中， 是用來調節(jié)選擇壓力的， 1時，選擇壓力加大， 1時，選擇壓力減小，此標定比較費時，要針對不同問題使用。Ff 對數(shù)標定對數(shù)標定對數(shù)標定可以用于縮小目標函數(shù)值得差別，其一般形式為參數(shù)a和b根據(jù)具體問題而定。 指數(shù)指數(shù)標定標定指數(shù)標定作用是擴大目標函數(shù)的差值，其一般形式為 參數(shù)a、b和c根據(jù)具體問題而定。ln+bFafe +cbfFa4.選擇策略選擇策略傳統(tǒng)的遺傳算法的選擇和遺傳是以前進行的，即使后代不如父代，也無法糾正，現(xiàn)在改變選擇策略，先遺傳后選擇，這樣做的好處是樣本空間

14、擴大了，可供選擇的個體增多了。一般有三種選擇策略：截斷選擇順序選擇正比選擇截斷選擇截斷選擇選擇最好的前T個個體，讓每一個有1/T的選擇概率，即平均每個得到NP/T個繁殖機會。例如：NP=100，T=50，那么前50個染色體每個的選擇概率為1/50，每個染色體平均被選中兩次不足之處的是在適應值得排序上要花費較多的時間。順序順序選擇選擇從好到壞排序NP個個體，然后定義最好個體的選擇概率為q，在根據(jù)公式 ，可以計算出第j個個體的選擇概率。1(j)q(1 q)jp優(yōu)點：選擇概率可以離線計算，可以節(jié)省算法執(zhí)行時間，同時選擇壓力可調缺點：選擇概率固定化，導致在算法的執(zhí)行過程中選擇壓力不可調節(jié)。正比選擇正比選擇其選擇方式和旋輪法一樣，即每個個體被選中進行遺傳運算的概率為該個體的適應值和群體中所有個體的適應值總和的比例，只是跟傳統(tǒng)的遺傳算法不同的是選擇操作是在遺傳操作之后進行，用動態(tài)標定來調節(jié)選擇壓力在基本