2.2 組合差分進化算法及其改進

2.2.1 組合差分進化算法

鑒于向量產生策略和控制參數對DE算法的性能具有重要影響，且各有優勢，Wang等[4]提出了一種新的自適應DE算法——CoDE算法，該算法組合了幾種向量產生策略和特定的控制參數用于產生新的向量。CoDE算法中包含3種向量產生策略和3組控制參數。采用的3種向量產生策略分別如下[4]。

3組控制參數分別為：[F=1.0, Cr=0.1]，[F=1.0, Cr=0.9]，[F=0.8, Cr=0.2]。其中，F表示縮放因子，Cr表示交叉概率。

上述策略和參數設置經常用于許多版本的DE算法中，并且它們的有效性已經被大量的研究所證實。CoDE從控制參數集中隨機選擇一組參數，然后根據該組參數利用新向量產生策略候選池中的每個策略產生新的向量，再從新的3個向量中選擇最好的個體。這種思想如圖2-1所示。有關CoDE的更詳細的信息見文獻[4]。

從圖2-1可以看出，CoDE采用的是一種利用簡單的組合思想來實現自動搜索的方法。利用3種新向量產生策略和控制參數的優勢，以期達到更好的效果。除了向量產生策略和控制參數以外，CoDE的其他操作與傳統的DE算法沒有什么差別。

2.2.2 改進的算法

（1）改變生成策略法

盡管CoDE算法在連續優化領域已經顯示出優異的優化性能，但從文獻[4]的研究結果可以看出，文獻[5]提出JADE的性能僅次于提出的CoDE算法，特別是對于5個單模函數，除了其中1個單模函數與CoDE算法相當外，其他4個均優于CoDE算法。JADE的優異性能主要在于采用了一種貪婪的變異操作——“current-to-best/1”，該操作通過引入當前群體最優解的信息，加速了種群的快速收斂。而CoDE算法在求解單模函數時卻顯得有些力不從心。在CoDE算法新向量產生策略候選池的3種變異策略中，并沒有利用當前最優解的信息，因此，考慮從向量產生策略方面進行改進，以期得到好的結果。本章對CoDE算法的新個體產生策略集進行調整，將“current-to-best/1”操作引入進來。因“current-to-best/1”與CoDE算法原始個體產生策略集中的“current-to-rand/1”在形式上具有極大的相似性，因此，這里采用替換方式，即將CoDE算法中個體產生策略集中的“current-to-rand/1”替換成“current-to-best/1”，其他保持不變，并將修改版的CoDE算法命名為MCoDE算法。MCoDE算法新向量產生方式如圖2-2所示。

（2）擴展控制參數法

CoDE算法中控制參數采用隨機方式來選擇3組特定的參數。文獻[4]已對控制參數的選擇問題進行了研究，對采用自適應參數選擇方法和固定參數設置兩種情況下算法的性能進行了檢驗，結果顯示這兩種參數選擇方法都不能明顯改善CoDE算法的性能，并且這兩種方法的性能不超過采用隨機方式的CoDE算法。不同于從參數選擇方面進行改進，本章提出了一種增加控制參數的方式，以檢查增加控制參數的方式的改進效果。根據EPSDE[3]算法中有關縮放因子F和交叉概率Cr兩個參數的設置范圍：F在區間[0.4,0.9]進行選擇，步長為0.1，Cr在區間[0.1,0.9]進行選擇，步長為0.1。為了探討擴大參數選擇范圍對CoDE算法優化性能的影響，本章在原有CoDE算法控制參數庫的基礎上，增加了另外3組參數：[F=0.7, Cr=0.3]，[F=0.6, Cr=0.4]和[F=0.5, Cr=0.5]。將這種采用擴展參數方法的CoDE算法稱為MCoDE-P。MCoDE-P算法新向量產生方式如圖2-3所示。

從以上描述可以看出，除向量產生策略和控制參數選擇方法不同外，CoDE、MCoDE和MCoDE-P 3種組合差分進化算法采用的整體結構都是一樣的。在這里僅以MCoDE算法為例，介紹主要的實現步驟，具體如下。

步驟1：初始化控制參數庫和終止條件，設置種群大小（通常等于決策變量的個數），隨機產生初始化種群。

步驟2：對初始種群進行評估，并記錄最好個體的信息，設置進化代數G=0。

步驟3：對于每個個體，隨機從控制參數集中選擇一組控制參數，調用第2.2.2節中介紹的“rand/1/bin”“rand/2/bin”和“current-to-best/1”3種新向量產生策略產生3個新的向量。

步驟4：計算3個新向量的目標函數值，將最優個體作為嘗試向量。

步驟5：比較目標向量和新產生的向量的目標函數值，若優于，則用替換加入下一代種群中。

步驟6：判斷是否種群中所有的個體都執行完，若未執行完，則轉步驟3繼續執行，否則，執行步驟7。

步驟7：找出下一代種群中的最好個體，更新最好個體信息，G=G+1。

步驟8：判斷是否滿足終止條件，若滿足，則輸出最好個體信息及對應的目標函數值，執行完成，否則，轉步驟3繼續執行。

CoDE算法流程如圖2-4所示。

從圖2-4可以看出，上述標準的組合差分進化算法除了在向量產生策略和控制參數兩個方面有所不同外，與標準的差分進化算法并沒有太大的區別，仍然采用標準的差分進化算法的計算框架。CoDE算法保留了差分進化結構簡單、開放和天然并行性等優點，這些為進一步研究組合差分進化的擴展提供了便利。