現(xiàn)代優(yōu)化算法

1、 遺傳算法及其模擬計(jì)算遺傳算法及其模擬計(jì)算 一一 遺傳算法遺傳算法 其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度信息。 它的應(yīng)用范圍非常廣泛，尤其適合于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題，可廣泛用于組合優(yōu)化，機(jī)器學(xué)習(xí)，自適應(yīng)控制，規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域，從而確立了它在21世紀(jì)的智能計(jì)算技術(shù)中的關(guān)鍵地位。 1 遺傳算法的基本步驟 遺傳算法流程圖如下：集團(tuán)中個(gè)體適應(yīng)度的檢測評(píng)估選擇交叉變異圖1 遺傳算法的基本流程編碼和初始集團(tuán)生成 一、編碼一、編碼 遺傳算法主要是通過遺傳操作對(duì)群體中具有某種結(jié)構(gòu)形式的個(gè)體施加結(jié)重組處理，從而不斷地搜索出群體中個(gè)體間結(jié)構(gòu)相似性，由此

2、可見，遺傳算法不能直接處理問題空間參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體。這一轉(zhuǎn)換操作就叫做編碼。 二、二、 初始群體的生成初始群體的生成 遺傳操作是對(duì)于多個(gè)體同時(shí)進(jìn)行的。初始群體的設(shè)定可采取如下策略： (1) 根據(jù)問題固有的知識(shí)，設(shè)法確定最優(yōu)解所占空間在整個(gè)問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。 (2) 先隨機(jī)生成一定數(shù)目的個(gè)體，然后從中挑出最好的個(gè)體加到初始群體當(dāng)中去。這種過程不斷迭代，直到初始群體中個(gè)數(shù)達(dá)到了預(yù)先確定的規(guī)模。 三、適應(yīng)度函數(shù)三、適應(yīng)度函數(shù) 適應(yīng)度函數(shù)表明個(gè)體或解的優(yōu)劣性。不同的問題，適應(yīng)性函數(shù)的定義方式也不同。這一操作是借用了

3、達(dá)爾文的自然選擇原則，即個(gè)體適應(yīng)度越高，其被選擇的個(gè)體越多。 四、遺傳操作四、遺傳操作 遺傳操作是模擬生物基因遺傳的操作。在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務(wù)就是對(duì)群體的個(gè)體按照他們對(duì)環(huán)境適應(yīng)的程度（適應(yīng)度評(píng)估）施加一定的操作，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過程，從優(yōu)化搜索的角度而言，遺傳操作可以使問題的解，一代又一代地優(yōu)化，并逼近最優(yōu)解。遺傳算法的基本操作包括以下三個(gè)基本算子：選擇，交叉,變異。 （一）選擇：（一）選擇：選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代為下一代繁殖子孫。進(jìn)行選擇的原則是適應(yīng)性強(qiáng)的個(gè)體為下一代貢獻(xiàn)一個(gè)或多個(gè)后代的概率大。 適應(yīng)度比例方法(

4、fitness proportional model) 適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的選擇方法，他也叫賭輪或蒙特卡羅（monte carlo）選擇。 設(shè)群體的大小為n，其中個(gè)體i的適應(yīng)度值為 ,則i被選擇的概率為 顯然，概率 反映個(gè)體i的適應(yīng)度在總和中所占的比例，個(gè)體的適應(yīng)度越大，其被選擇的概率就越高，反之亦然，計(jì)算出群體中各個(gè)個(gè)體的選擇概率后，就可以決定那些個(gè)體可以被選出。if1niijjpffip（二）交叉（二）交叉：交換操作是遺傳算法中最主要的遺傳操作。在遺傳算法中使用交叉算子來產(chǎn)生新的個(gè)體?；窘徊嫠阕尤缦拢簡吸c(diǎn)交叉（one-point crossover），它是指在

5、個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。雙點(diǎn)交叉（twopoint crossover）是指在個(gè)體編碼串中隨機(jī)設(shè)置了二交叉點(diǎn)，然后再進(jìn)行部分基因交換。基本交叉算子如下：單點(diǎn)交叉（one-point crossover），它是指在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。雙點(diǎn)交叉（twopoint crossover）是指在個(gè)體編碼串中隨機(jī)設(shè)置了二交叉點(diǎn)，然后再進(jìn)行部分基因交換。雙點(diǎn)交叉了的具體操作過程是：在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)；交換兩個(gè)個(gè)體在所設(shè)定的兩個(gè)交叉點(diǎn)之間的部分染色體。 （三）變異（三）變

6、異：變異首先在群體中隨機(jī)選擇一個(gè)個(gè)體，對(duì)于選中的個(gè)體以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的值。遺傳算法導(dǎo)入變異的目的有兩個(gè)：一是使遺傳算法具有局部的隨機(jī)搜索能力。二是使遺傳算法可維持群體的多樣性，以預(yù)防出現(xiàn)群體未成熟收斂現(xiàn)象。1基本變異算子 2逆轉(zhuǎn)變異算子（inversion operator） 11011110111010 變 異1000100110100101 01 逆 轉(zhuǎn) 遺傳算法的模擬計(jì)算遺傳算法的模擬計(jì)算 下面解釋用遺傳算法求函數(shù) 的最大值的一些重要步驟.這里只介紹第一代群體的生成過程與結(jié)果.(1)編碼編碼 由于在該例中 ,因此將變量 編碼為5位長的二進(jìn)制形式.如 可表示為 .(

7、2)初始群體的生成初始群體的生成 隨機(jī)產(chǎn)生初始群體的每個(gè)個(gè)體,群體的大小為4(如下表). 2( ),0,31f xx x0,31xx13x 01101xx(3)適應(yīng)度計(jì)算適應(yīng)度計(jì)算 將每個(gè)個(gè)體 的函數(shù)值 作為該個(gè)體的適應(yīng)度.如個(gè)體01101的適應(yīng)度為 .(4)選擇選擇 計(jì)算每個(gè)個(gè)體的適應(yīng)度所占的比例 ,并以此作為相應(yīng)的選擇概率.表的第5列給出了每個(gè)個(gè)體的選擇概率.由此概率可計(jì)算出每個(gè)個(gè)體選擇的次數(shù).也可采用輪盤賭方式來決定每個(gè)個(gè)體的選擇份數(shù).賭輪按每個(gè)個(gè)體適應(yīng)度的比例分配,轉(zhuǎn)動(dòng)賭輪4次,就可決定各自的選擇份數(shù).如表中第7列.結(jié)果反映出,優(yōu)秀個(gè)體2獲得了最多的生存繁殖機(jī)會(huì),最差個(gè)體3被淘汰.每次選擇都對(duì)個(gè)體進(jìn)行一次復(fù)制,由此得到的4份復(fù)制送到配對(duì)庫,以備配對(duì)繁殖.x( )f x2(13)13169fijff (5)交叉與變異交叉與變異 這里采用簡單交叉操作:首先對(duì)配對(duì)庫中的個(gè)體進(jìn)行隨機(jī)配對(duì);其次,在配對(duì)個(gè)體中隨機(jī)設(shè)定交叉處,配對(duì)個(gè)體彼此交換部分信息(如表).于是得到4個(gè)新個(gè)體,這4個(gè)新個(gè)體就形成了新一代群體.比較新舊群體,不難發(fā)現(xiàn)新群體中個(gè)體適應(yīng)度的平均值和最大值都有明顯