進化策略

ES作為一種求解參數優化問題的方法，模仿生物進化原理，假設不論基因發生何種變化，產生的結果（性狀）總遵循零均值、某一方差的高斯分佈。進化策略和遺傳演演算法（GA）是進化演演算法（EAs）的兩類重要變種。這兩種主流方法的不同之處在於解的表示以及搜索和選擇運算元的設計。GA常使用二進位或整數編碼，與此相比，ES常基於真實值編碼。GA和EA之間的一個顯著差別在於選擇運算元。在ES中，父代選擇是無偏的，即，當前種群的每一個個體有著相同的概率被選擇用以重組。此外，倖存者的確定性選擇是ES的驅動力。不過最近幾十年湧現出了許多混合方法。一方面，使用整數編碼的ES被開發用於組合優化問題的求解。另一方面，也有人提出了使用ES選擇模型的GA。

對於組合優化問題，有人建議使用(μ+λ)-ES 。(μ+λ)-ES 的種群概念如下：搜索開始時，建立一個初始種群 POP0，包含μ個個體。從初始種群開始，迭代計算一系列種群。在每一次迭代iter中，從當前代POPiter產生 λ個子代。在每種情況下，用三步計算產生一個子代：（1）從當前代POPiter中選擇兩個個體，作為父代用於重組。父代的選擇是無偏的。（2）通過所選父代的重組，產生一個新個體。（3）對新個體施行變異和評估。在迭代結束時，從λ個子代與μ個POPiter代個體組成的集合中，選擇μ個個體形成新一代種群POPiter+1。現在，將解的質量作為選擇的標準：即，選擇μ個具有最高質量的個體來代替當前代。商μ/λ被稱為選擇壓，其值越小，說明選擇壓越大，反之亦然。以下以資源受限項目調度問題（RCPSP）的進化策略為例，說明進化策略的具體演演算法。

1.初始種群的表示和計算

每個個體代表待求解項目調度問題的一個可行調度。使用活動列表來表示。活動列表是滿足優先關係的，亦即，任意活動必須位於它所有緊前活動之後。為了產生一個活動列表，使用了經過修改的由Hartmannyu於2002描述的基於優先規則的抽樣啟髮式方法。一個個體通過串列調度生成方案解碼成一個調度。串列調度生成方案按以下方式來從活動列表構建調度：活動按列表指定的順序來調度。從而，每項活動被分配到最早的滿足優先關係和資源約束的開始時間。待調度活動的最早可行開始時間的計算考慮了資源的可獲得量。

2.評估

通過其所代表的調度的解的質量來評估每個個體。解的質量用工期（在RCPSP情形下）來衡量。

3.重組和變異

重組用Hartmann於1998年開發的兩點交叉來實現。它從兩個被選擇出的父代個體中計算產生一個新的滿足優先約束的活動列表。在變異的框架下，通過一個著名的局部搜索技術在四個步驟下改變活動列表：（1）通過個體活動的左移對活動列表進行隨機修改。（2）解碼經過修改的活動列表，並計算其所表示的調度。（3）通過個體活動列表的前向和後向移動來修改調度。（4）用經過修改的調度計算一個新的活動列表。在第一步中，對活動列表中的每項活動，嘗試以概率p隨機移動若干位置。在位置移動之後，再進行一次移動，以確保該活動出現在列表中它的所有緊前活動之後。在第二步解碼活動列表之後，嘗試改善活動列表所代表的調度，這是第三步。為了達到改善的目的，首先對調度施加前向移動，然後施加後向移動。在第四步中，改善的調度能夠精確轉化為一個編碼的活動列表。為了實現這一目的，讓活動以其開始時間的順序依次進入活動列表。如果兩項活動開始時間相同，則按照活動編號的升序依次進入。