第三章遺傳算法

第三章遺傳算法遺傳算法（GeneticAlgorithm）是一種通過自然進(jìn)化過程搜索最優(yōu)解的方法。過去30年中，在解決復(fù)雜的全局優(yōu)化問題方面，遺傳算法取得了成功的應(yīng)用，并受到了人們廣泛的關(guān)注。在優(yōu)化問題中，如果目標(biāo)函數(shù)是多峰的，或者搜索空間不規(guī)則，就要求所使用的算法必須具有高度的魯棒性，以避免在局部優(yōu)化解附近徘徊。遺傳算法的優(yōu)點(diǎn)恰好是擅長全局搜索。另外，遺傳算法本身并不要對(duì)優(yōu)化問題的性質(zhì)作一些深入的數(shù)學(xué)分析，從而對(duì)那些不太熟悉數(shù)學(xué)理論和算法的使用者來說，無疑是方便的。大家知道，生物遺傳物質(zhì)的主要載體是染色體，在遺傳算法中，染色體是一串?dāng)?shù)據(jù)（或數(shù)組），用來作為優(yōu)化問題的解的代碼，其本身不一定是解。遺傳算法一般經(jīng)過這樣幾個(gè)過程：首先，隨機(jī)產(chǎn)生一定數(shù)目的初始染色體，這些隨機(jī)產(chǎn)生的染色體組成一個(gè)種群。種群中染色體的數(shù)目稱為種群的大小或種群的規(guī)模。然后，用評(píng)價(jià)函數(shù)來評(píng)價(jià)每個(gè)染色體的優(yōu)劣，即染色體對(duì)環(huán)境的適應(yīng)程度（稱為適應(yīng)度），用來作為以后遺傳操作的依據(jù)。接著，進(jìn)行選擇過程，選擇過程的目的是為了從當(dāng)前種群中選出優(yōu)良的染色體。判斷染色體的優(yōu)良與否的準(zhǔn)則就是各自的適應(yīng)度，即染色體的適應(yīng)度越高，其被選擇的機(jī)會(huì)就越多。通過選擇過程，產(chǎn)生一個(gè)新的種群。對(duì)這種新的種群進(jìn)行交叉操作，交叉操作是遺傳算法中主要的遺傳操作之一。接著進(jìn)行變異操作，變異操作的目的是挖掘種群中的個(gè)體的多樣性，克服有可能陷入局部解的弊病。這樣，經(jīng)過上述運(yùn)算產(chǎn)生的染色體稱為后代。然后，對(duì)新的種群（即后代）重復(fù)進(jìn)行選擇、交叉和變異操作，經(jīng)過給定次數(shù)的迭代處理以后，把最好的染色體作為優(yōu)化問題的最優(yōu)解。遺傳算法已被廣泛應(yīng)用業(yè)于最優(yōu)控制、運(yùn)輸問題、調(diào)度、生產(chǎn)計(jì)劃、資源分配、統(tǒng)計(jì)及模式識(shí)別等，下面我們介紹一下遺傳算法的一些基本知識(shí)。第一節(jié)優(yōu)化問題的遺傳算法回顧一下單目標(biāo)規(guī)劃、多目標(biāo)規(guī)劃及目標(biāo)規(guī)劃模型的基本形式。在數(shù)學(xué)規(guī)劃中，目標(biāo)函數(shù)不一定是單峰的，可行域也不一定是凸集。最優(yōu)化問題的解有兩種表示方式：二進(jìn)制向量或浮點(diǎn)向量。使用二進(jìn)制向量作為一個(gè)染色體來表示決策變量的真實(shí)值，向量的長度依賴于要求的精度，但使用二進(jìn)制代碼的必要性已經(jīng)受到了批評(píng)。求解復(fù)雜優(yōu)化問題時(shí)，二進(jìn)制向量表示結(jié)構(gòu)有時(shí)不太方便。另一種表示方法是浮點(diǎn)向量，每一個(gè)染色體由一個(gè)浮點(diǎn)向量表示，其長度與解向量相同。這里用向量表示最優(yōu)化問題的解，其中是維數(shù)，則相應(yīng)的染色體也是。一、關(guān)于約束條件的處理對(duì)于約束條件的處理關(guān)鍵是（1）消除約束條件中的等式約束。例如假設(shè)，，通過解這個(gè)方程組，將變量用另外的變量表示，代入到模型中，就形成了一個(gè)沒有等式約束的維優(yōu)化問題。（2）設(shè)計(jì)恰當(dāng)?shù)倪z傳操作以保證所有新產(chǎn)生的染色體在可行域中。為了保證染色體的可行，必須對(duì)遺傳操作過程中得到的每一個(gè)染色體進(jìn)行檢查，對(duì)每一個(gè)優(yōu)化問題，最好設(shè)計(jì)一個(gè)C語言子函數(shù)，其輸出值為1表示染色體是可行的，0表示不可行。例如，對(duì)于約束條件，可以作如下的一個(gè)子函數(shù)：從開始循環(huán)若，返回0；直到結(jié)束返回1。最后值得注意的是，在設(shè)計(jì)程序時(shí)，應(yīng)該注意到一些隱含的約束，即有些雖然是可行解，但不可能是最優(yōu)解。例如數(shù)學(xué)規(guī)劃模型其中是可行域，但是我們知道最優(yōu)解一定在區(qū)間，所以為了減少程序的搜索空間，應(yīng)當(dāng)增加約束條件這類隱含約束一般不難發(fā)現(xiàn)，尤其對(duì)實(shí)際的管理問題。因此盡可能的增加隱含條件。二、初始化過程定義整數(shù)pop-size作為染色體的個(gè)數(shù)，并且隨機(jī)的產(chǎn)生pop-size個(gè)初始染色體。一般情況下，由于優(yōu)化問題的復(fù)雜性，解析底產(chǎn)生可行的染色體是困難的。此時(shí)，可以采用下述兩種方法之一作為初始過程。第一種方法：設(shè)決策者能夠給出可行域中的一個(gè)內(nèi)點(diǎn)，記為。定義一個(gè)足夠大的數(shù)，以保證遺傳操作遍及整個(gè)可行域。不僅在初始化過程中使用，而且在變異操作中也使用。按照下面的方法產(chǎn)生pop-size個(gè)染色體。在中隨機(jī)的選擇一個(gè)方向，如果滿足不等式約束，則將作為一個(gè)染色體，否則，置為0和之間的一個(gè)隨機(jī)數(shù)，直到可行為止。由于是內(nèi)點(diǎn)，所以在有限步內(nèi)，可以找到滿足不等式約束的可行解。重復(fù)以上過程pop-size次，從而產(chǎn)生pop-size個(gè)初始染色體。三、評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù)（記為）用來對(duì)種群中的每個(gè)染色體設(shè)定的一個(gè)概率，以使該染色體被選擇的可能性與種群中其它染色體的適應(yīng)性成比例，即通過輪盤賭，適應(yīng)性強(qiáng)的染色體被選擇產(chǎn)生后代的機(jī)會(huì)要大。第一種方法，設(shè)目前該代中的染色體為，可以根據(jù)染色體的序進(jìn)行再生分配，而不是根據(jù)其實(shí)際的目標(biāo)值。無論是何種數(shù)學(xué)規(guī)劃都可以作一個(gè)合理的假設(shè)，即在染色體中，決策者可以給出一個(gè)序的關(guān)系，使染色體由好到壞進(jìn)行重排，就是說，一個(gè)染色體越好，其序號(hào)越小。設(shè)參數(shù)給定，定義基于序的評(píng)價(jià)函數(shù)為，意味著染色體是最好的，說明是最差的。第二種方法是通過對(duì)適應(yīng)度的適當(dāng)縮放調(diào)整（稱為適應(yīng)度定標(biāo)）來設(shè)計(jì)評(píng)價(jià)函數(shù)。用（即染色體各自的目標(biāo)值）來表示原來的適應(yīng)度。Goldberg提出一種線性適應(yīng)度定標(biāo)方案，，其中，為新的適應(yīng)度，和為參數(shù)。這種方法實(shí)際上假定使用者了解目標(biāo)函數(shù)的性質(zhì)，從而才能設(shè)計(jì)出合理的參數(shù)和，這種情況下，評(píng)價(jià)函數(shù)定義為，四、選擇過程選擇過程是以旋轉(zhuǎn)賭輪pop-size次為基礎(chǔ)的。每次旋轉(zhuǎn)都為新的種群選擇一個(gè)染色體。賭輪是按每個(gè)染色體的適應(yīng)度進(jìn)行選擇染色體的。無論使用哪一種評(píng)價(jià)函數(shù)，選擇過程總可以寫成如下形式：步驟1對(duì)每個(gè)染色體，計(jì)算累計(jì)概率步驟2從區(qū)間中產(chǎn)生一個(gè)隨機(jī)數(shù)；步驟3若，則選擇的第個(gè)染色體，其中；步驟4重復(fù)步驟2和步驟3共pop-size次，這樣可以得到pop-size個(gè)復(fù)制的染色體。在上述過程中，并沒有要求滿足條件。實(shí)際上，可以用除以所有的，，使，新得到概率同樣與適應(yīng)度成比例。只要我們不介意概率方面解釋上的困難，這一點(diǎn)并沒有在遺傳過程中產(chǎn)生任何影響。五、交叉操作首先定義參數(shù)作為交叉操作的概率，這個(gè)概率說明種群中有期望值為，pop-size個(gè)染色體來進(jìn)行交叉操作。為確定交叉操作的父代，從到pop-size重復(fù)一下過程：從中產(chǎn)生隨機(jī)數(shù)，如果，則選擇作為一個(gè)父代。用表示上面選擇的父代，并把它們隨機(jī)的分成下面的對(duì)我們以為例解釋怎樣對(duì)上面所有的對(duì)進(jìn)行交叉操作。首先，從開區(qū)間中產(chǎn)生一個(gè)隨機(jī)數(shù)，然后按下列形式在和之間進(jìn)行交叉操作，并產(chǎn)生兩個(gè)后代和，如果可行域是凸的，這種凸組合交叉運(yùn)算在兩個(gè)父代可行的情況下，能夠保證兩個(gè)后代也是可行的。但是，在許多情況下，可行域不一定是凸的，活很難驗(yàn)證其凸性，此時(shí)必須驗(yàn)證每一后代的可行性。如果兩個(gè)后代均可行，則用它代替其父代。否則，保留其中可行的（如果存在的話），然后產(chǎn)生新的隨機(jī)數(shù)，重新進(jìn)行交叉操作（交叉操作時(shí)，隨機(jī)數(shù)是新選的，而父代還用和），直到得到兩個(gè)可行的后代或循環(huán)給定次數(shù)為止。無論如何，僅用可行的后代取代其父代。六、變異操作定義參數(shù)作為遺傳系統(tǒng)中的變異概率，這個(gè)概率表明總體中有期望值為，pop-size個(gè)染色體用來進(jìn)行變異操作。類似于交叉操作中選擇父代的過程，由到pop-size，重復(fù)下列過程：從區(qū)間中產(chǎn)生隨機(jī)數(shù)，如果，則選擇染色體作為變異的父代。對(duì)每一個(gè)選擇的父代，用表示，按下列方法進(jìn)行變異。在中隨機(jī)選擇變異方向，如果是不可行的，那么，置為0和之間的隨機(jī)數(shù)，直到其可行為止。其中是初始化過程定義的一個(gè)足夠大的數(shù)。如果在預(yù)先給定的迭代次數(shù)之內(nèi)沒有找到可行解，則置。無論為何值，總用代替。七、遺傳算法程序經(jīng)過選擇、交叉和變異操作，我們得到一個(gè)新的種群，準(zhǔn)備進(jìn)行下一代進(jìn)化。對(duì)上述步驟經(jīng)過給定的循環(huán)次數(shù)之后，遺傳算法終止。對(duì)一般優(yōu)化問題，遺傳算法可以歸納如下：遺傳算法程序輸入?yún)?shù)pop-size，交叉操作概率，變異概率；通過初始過程產(chǎn)生pop-size個(gè)染色體；重復(fù)對(duì)染色體進(jìn)行交叉和變異操作；計(jì)算所有染色體的評(píng)價(jià)函數(shù)；根據(jù)某種抽樣機(jī)制選擇染色體；直到滿足終止條件我們知道，最好的染色體不一定出現(xiàn)在最后一代中，所以在進(jìn)化開始，必須把最好的染色體保留下來，記為，如果在新的種群中又發(fā)現(xiàn)更好的染色體，則用它代替原有的染色體。在進(jìn)化完成之后，這個(gè)染色體就可以看作是優(yōu)化問題的解。八、遺傳算法與上升法上升法是直接法、剃度法和Hessian法的通稱。上升法首先在最優(yōu)解可能存在的地方選擇一個(gè)初始點(diǎn)，然后通過分析目標(biāo)函數(shù)的特性，由初始點(diǎn)移到一個(gè)新的點(diǎn)，然后再繼續(xù)這個(gè)過程。為了更好的理解遺傳算法，現(xiàn)在把上升法和遺傳算法比較。上升法搜索過程是確定的，通過產(chǎn)生一系列的點(diǎn)收斂到最優(yōu)解（有時(shí)是局部最優(yōu)解），而遺傳算法的搜索過程是隨機(jī)的，它產(chǎn)生一系列隨機(jī)種群序列。二者的主要差異可以歸納如下兩點(diǎn)：（1）上升法的初始點(diǎn)僅有一個(gè)，由決策者給出；遺傳算法的初始點(diǎn)有多個(gè)，隨機(jī)產(chǎn)生。（2）通過分析目標(biāo)函數(shù)的特性，上升法由一點(diǎn)產(chǎn)生一個(gè)新點(diǎn)；遺傳算法通過遺傳操作，在當(dāng)前的種群中經(jīng)過交叉、變異和選擇產(chǎn)生下一代種群。對(duì)同一個(gè)優(yōu)化問題，遺傳算法所使用的機(jī)時(shí)比上升法花費(fèi)的機(jī)時(shí)要多。但是遺傳算法可以處理一些上升法不能解決的復(fù)雜的優(yōu)化問題。第三節(jié)遺傳算法數(shù)字例子遺傳算法已被編制成C語言程序。在下面的例子中，使用的參數(shù)為：種群規(guī)模為30，交叉概率為0.2，變異概率為0.5，而評(píng)價(jià)函數(shù)中的參數(shù)。遺傳算法對(duì)于這些參數(shù)的設(shè)置是非常魯棒的，改變這些參數(shù)對(duì)所得的結(jié)果不會(huì)有太大的影響。例1單目標(biāo)規(guī)劃，考慮非凸集合上的優(yōu)化問題已經(jīng)知道目標(biāo)函數(shù)的最大值為，圖中的陰影部分表示可行域在處的橫截面。從圖總可以看到，可行域是非凸的。22112下面用遺傳算法求解此問題。用染色體來作為解的代碼。染色體的可行性由下面的檢驗(yàn)函數(shù)經(jīng)驗(yàn)：如果，返回0；如果，返回0；如果，返回0；返回1其中檢驗(yàn)函數(shù)值0表示不可行，1表示可行。容易知道可行域包含于下列超幾何體中。我們可以很容易從這樣的超幾何體中抽樣，例如取，，其中函數(shù)用來產(chǎn)生區(qū)間上的均勻分布的隨機(jī)函數(shù)。如果這個(gè)染色體不可行，則拒絕接受，由上面的，重新產(chǎn)生一個(gè)新的染色體，如果產(chǎn)生的染色體可行，則接受它作為種群的一名成員。經(jīng)過有限次抽樣以后，得到30個(gè)可行的染色體，，，，，，，，，，，，，，，直接計(jì)算，得到如下的初始適應(yīng)度的值，即目標(biāo)函數(shù)值，，，，，，，，，，，，，，，，，，，，從中可以發(fā)現(xiàn)，染色體是其中最好的染色體（最大），而染色體是其中最差的（最?。Ｔ诖舜芜M(jìn)化中，保留了染色體，記為。如果在以后的進(jìn)化過程中，發(fā)現(xiàn)比更好的染色體，則用它取代。根據(jù)染色體的目標(biāo)值，由好到壞重新排列染色體如下，根據(jù)評(píng)價(jià)函數(shù)：，其中參數(shù)。取，有，再由對(duì)每個(gè)染色體，計(jì)算累計(jì)概率：，，，，，，，，，，，，，，，，，，，，，，現(xiàn)在準(zhǔn)備旋轉(zhuǎn)賭輪30次。首先由計(jì)算機(jī)在區(qū)間上產(chǎn)生隨機(jī)數(shù)，得到0.0328，其大于，而小于，所以選擇染色體作為新種群的一名成員。第二次產(chǎn)生的隨機(jī)數(shù)為0.1284，大于，而小于，所以也被選中，經(jīng)過30次選擇之后，得到一個(gè)新的種群，，，，，，，，，，，，，，，接著，對(duì)新的種群進(jìn)行遺傳操作，即交叉操作。交叉概率，說明平均有6個(gè)染色體進(jìn)行交叉操作。從區(qū)間上產(chǎn)生隨機(jī)數(shù)，得到0.6437，大于，第一個(gè)染色體沒有選中。第二次產(chǎn)生的隨機(jī)數(shù)為0.1256，小于，第二個(gè)染色體被選中用來作為交叉操作的一個(gè)父代。這樣，經(jīng)過30次，選中10個(gè)染色體，，，，，，，，將它們隨機(jī)分成五組，，，，由于被選中的染色體是偶數(shù)個(gè)，所以容易配對(duì)，若為奇數(shù)個(gè)，只需去掉一個(gè)即可。由，（從開區(qū)間中產(chǎn)生一個(gè)隨機(jī)數(shù)）實(shí)現(xiàn)交叉操作，得到如