改進(jìn)遺傳算法

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

2、則確定等，相應(yīng)地，為改進(jìn)簡(jiǎn)單遺傳算法的實(shí)際計(jì)算性能，很多的改進(jìn)工作也是從參數(shù)編碼、初始種群設(shè)定、適應(yīng)度函數(shù)標(biāo)定、遺傳操作算子、控制參數(shù)的選擇以及遺傳算法的結(jié)構(gòu)等方面提出的。基于不同的問(wèn)題，遺傳算法可以有不同的改進(jìn)和變形，這也是遺傳算法內(nèi)容豐富和作用強(qiáng)大的原因。人工智能及其應(yīng)用4改進(jìn)的遺傳算法 編碼方法的選擇 編碼的修復(fù) 適值函數(shù)的標(biāo)定 選擇策略 停止準(zhǔn)則的改進(jìn)1.1.編碼方法編碼方法 這里來(lái)介紹除了0-1編碼以為的其他三種重要的編碼方法 1.順序編碼順序編碼 順序編碼是用1到n的自然數(shù)來(lái)編碼，此種編碼不允許重復(fù)，又稱為自然數(shù)編碼，例如下面是一個(gè)染色體長(zhǎng)度為n=7的順序編碼： X=(2 3 1

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

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

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

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

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

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

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

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

11、， 是一個(gè)較小的數(shù)目的是使種群中最差的個(gè)體仍然有繁殖的機(jī)會(huì)，增加種群的多樣性。min(x)Fffmax(x)fminbf 最小化問(wèn)題對(duì)于最小化問(wèn)題 ，可以令a=-1， ，則適值函數(shù)為 其中， 也是一個(gè)較小的數(shù)，其意義與最大化問(wèn)題中的設(shè)置相同min(x)fmaxbfmax(x)Fff 動(dòng)態(tài)線性標(biāo)定動(dòng)態(tài)線性標(biāo)定 線性標(biāo)定中的參數(shù)隨著迭代次數(shù)的增加而變化時(shí)就得到了動(dòng)態(tài)線性標(biāo)定?？梢员硎鋈缦?其中，上標(biāo)k為迭代指標(biāo)，表明參數(shù)是隨著迭代次數(shù)的增加而變化的 最大化問(wèn)題 對(duì)于最大化問(wèn)題，可以令 =1， ，則適值函數(shù)為 kaminkkkbf minkkFffkkFa fb其中， 是第k代的最小目標(biāo)函數(shù)值， 是

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

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

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