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