標籤: 暫無標籤

1進化策略

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

2(μ+λ)進化策略

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

重組和變異

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

相關評論

同義詞:暫無同義詞