1.3 差分進化算法研究現狀

DE算法自產生至今，一向受到廣泛關注，研究者對其進行了大量的研究工作，取得了許多重要成果。Das[8-9]在進化計算領域的頂級期刊IEEE Transactions on Evolutionary Computation和Swarm and Evolutionary Computation上發表了對DE算法的最新研究進展綜述，系統地介紹了DE算法的基本概念、改進方法、理論現狀，以及在約束優化、多目標等方面的研究進展。童旅楊[7]從單目標優化、多目標優化和約束優化3個方面對DE算法的研究現狀進行了概述。

（1）單目標優化

根據DE算法的發展趨勢及采用的方法、策略的不同，DE算法單目標優化主要集中在算法的策略和參數的設置上。受粒子群思想的影響，Das等[10]設計了一種“DE/current-to-best/1”的變異策略來提高DE算法的尋優性能，從而達成平衡全局搜索和局部搜索的目標。Wang等[11]提出了一種組合差分進化（Composite DE，CoDE）算法，通過采用“DE/rand/1”“DE/rand/2”和“DE/current-to-rand/1”3種不同的變異和3種固定的控制參數組[F=1.0, CR=0.1]、[F=1.0, CR=0.9]和[F=0.8, CR=0.2]產生新的個體。Gong[12]提出了一種基于“ranking based”的變異操作，在這種模式中，排名最高的個體被選擇用來進行變異操作的幾率最大。Zhang[13]提出了一種自適應差分進化（JADE）算法，設計了一種“DE/current-to-pbest/1”的變異策略，該策略不但采用了種群中最優個體的信息，還盡可能運用種群中次好個體的信息來增加種群的多樣性；JADE算法還對歷史信息選擇性地進行存檔，用來提供進化方向信息；最重要的是提供了自適應參數來主動調試參數縮放因子F和交叉概率CR，進一步提高了算法的穩健性。Tanable[14-15]提出了基于成功歷史的自適應差分進化（Success-History Based Adaptive DE，SHADE）算法，該算法是JADE算法的改進算法，用歷史上的縮放因子F和交叉概率CR生成新的F和CR；他們又進一步提出了基于線性種群規?；喌腟HADE（L-SHADE）算法，L-SHADE算法是SHADE算法的改進算法，以種群線性遞減的方法來刪除不好的個體。L-SHADE算法在CEC2014比賽單目標優化競賽中取得了最好的成績。Wu等[16]同時用“DE/current-to-pbest/1”“DE/current-to-rand/1”和“DE/rand/1”3種不同的變異策略來產生新的個體，并且提出了多種群集成差分進化（MPEDE）算法，用一種獎勵的手段使好的變異策略在種群中的比例增大，同時運用了JADE的自適應參數自動調節參數F和CR。Liu等[17]提出了一種DADE的差分進化算法，通過二分法區分好的參數和壞的參數，從而自適應地產生更多好的參數，加快算法的收斂速度。Wang等[18]設計了一種ODE的算法，運用反向學習提高算法的收斂速率。

（2）多目標優化

對于多目標優化問題，沒有單一的解決方案可以同時使每個目標達到最優，此問題需要考慮在多目標之中找到最佳平衡點。Zhong[19]提出了一種帶隨機編碼策略的自適應多目標DE（AS-MODE）算法，其中種群中的每個個體都不是由精確解決方案表示的，而是由多元高斯帶有對角協方差的矩陣表示的。AS-MODE算法運用了簡單的“DE/rand/1/bin”生成實驗向量，參加變異過程的向量使用錦標賽淘汰手段進行篩選，而不是隨機挑選。AS-MODE算法在選擇過程中運用非支配排序方法，并且基于擁擠距離的操作對集合的解決方案進行排序，從頂部挑選出NP解決方案當作下一代的種群；除了DE的3個常用參數（F、CR和NP）之外，AS-MODE算法還引入了6個新參數。Ali等[20]提出了一種適用于多目標優化的DE新變體（MODEA），它首先使用不同的種群初始化技術生成兩個種群，每個種群的大小為NP，并從組合集合中選擇最佳的NP，第一個種群由解決方案從整個搜索空間隨機挑選出來，第二個種群由第一個成員的反向學習形成，方式類似于反向學習的DE算法[21]；然后將兩個種群合并，并根據非支配和擁擠距離排序選擇NP個頂端解決方案；并且運用“DE/rand/1”從非支配解決方案中挑選3個參與變異向量作為基礎執行變異操作[20]。Zhang等[22]設計出一種基于分解方法的多目標進化算法（MOEA/D），該算法處理多目標優化問題時采用另一種方法來引入新的思路，即通過加權手段把多目標問題分解成幾個單目標問題的聚合。Zhao等[23]引入了集成方法來取代基于分解方法的多目標差分進化算法[24]中鄰域尺寸參數的調整，并證明鄰域參數的集合產生了整體改進的性能。Qu等[25]結合正則化目標相加的多目標差分進化算法并進行了改善，在算法的選擇方法中增加了一個預選過程，通過去除不良解來改善收斂性。預選過程通過使用參考點來實現，由該參考點支配的所有解決方案都將被刪除；參考點從目標空間的中心開始，沿著搜索過程逐漸移動到原點。Denysiuk等[26]引入了一種求解多目標優化問題的DE變體，并將其命名為具有變異限制的多目標DE（Many-Objective Optimization Using Differential Evolution，MyO-DEMR），該算法使用Pareto支配的概念并加上反向世代距離度量來從父代和后代種群的集合中選擇下一代的種群，還利用限制DE變異中變異向量的策略改善在多峰問題上的收斂特性。

（3）約束優化

約束優化問題以找到可行解為前提，目標是找到最優解。Mallipeddi等[27]提供了帶有約束處理方法集成（Ensemble of Constraint Handling Techniques，ECHT）的DE算法，該算法中每個約束處理方法都有自己的種群，ECHT一個顯著特點是每個種群采用單獨的約束處理技術進行進化，不同的約束處理方法在搜索過程的不同階段都可能有效，而且ECHT能夠適應進化的要求。Gong等[28]在“ranking based”的變異操作方法上做出了改良，引入了自適應排序變異操作（Adaptive Ranking Mu tation Operator，ARMOR）的DE算法，根據當前狀態預判是否為非可行解、半可行解和可行解這3種狀態，并根據所處的狀態自適應調節變異操作。Liu等[29]引入了基于可行性規則和懲罰函數解決約束數值優化問題的混合DE與粒子群優化（PSO）算法。Sarder等[30]基于梯度修復的思想，與“DE/rand/1/bin”差分變異操作相結合，提出了基于DE的約束優化算法。如果由DE生成的單個候選解決方案是不可行的，則該算法應用梯度的修復方法將這些不可行的解決方案轉換為可行的解決方案；隨著世代數的增加，可行搜索空間與整個搜索空間之間的比率增加。Wang等[31]提出了基于雙目標框架的DE約束優化算法，并應用罰函數測量解的約束違反程度，該算法在求解約束問題上提供了一種新的思想。最近Saha等[32]通過使用DE作為基礎優化算法，提出了基于模糊規則的約束處理技術。Wu等[33]提出了一種等式約束和變量減少策略（Equality Constraint and Variable Reduction Strategy，ECVRS），該策略利用表達等式約束的等式來消除等式約束及約束優化問題的變量，從實驗結果可知，ECVRS在求解帶有等式約束條件問題時可以顯著提高DE算法的效率。

（4）離散優化

為求解離散優化問題，各種離散DE算法也相繼被提出。Pan等[34]提出了一種基于排列差異的離散差分進化（DDE）算法，并用于求解置換流水調度問題。Damak等[35]提出了一種基于排列加模式的離散DE算法，用于求解多模資源約束的工程調度問題。Wang等[36]提出了一種基于排列和求模運算的離散DE算法，以求解阻塞流水調度問題。Pan等[37]提出了一種混合離散DE算法，用于求解具有中間存儲的流水調度問題。Tasgetiren等[38]提出了基于破壞與重構變異操作的離散差分進化算法，求解帶有準備時間的總加權延遲時間的單機調度問題。Tasgetiren等[39]又提出了一種帶有并行種群的裝配離散差分進化算法，用于求解一般的旅行商問題。最近，姚芳等[40]提出了一種基于排列表示和取整變異的離散差分進化算法。

DE雖然在許多方面已經取得了一些成就，但也有一些不足之處。首先，不一樣的變異策略在不同類型的問題上發揮的作用有差異，然而單一的變異策略難以在復雜問題上得到較好的結果，因此如何根據不同問題選擇最優的變異策略具有一定的困難，如何基于已有的經驗和知識來設計多變異策略和自適應參數的DE算法，從而平衡局部搜索和全局搜索，還需要深入研究。其次，在求解多目標問題上，各類DE算法主要是基于靜態框架下的DE算法，影響了解集的多樣性和算法的收斂性能。變異策略和參數的選擇對收斂性和多樣性具有重大影響，進化過程中如何選擇變異策略和參數還需要深入研究。另外，如何加強算法的收斂性和提高Pareto解集的均勻性也是需要重點關注的問題。最后，DE算法本身是一種無約束優化算法，面對復雜的約束優化問題，如何設計有效的面向DE算法的約束處理方法還需要深入研究。另外，如何設計合適有效的算法來平衡約束條件和目標函數的關系也是需要考慮的。

針對上述DE算法存在的不足，本書從單目標優化、多目標優化、約束優化和離散優化4個方面開展了工作，通過對DE算法的深入研究提出了幾種新的DE算法。本書的主要內容如下。

第1章對最優化問題的研究意義進行了說明，概述了進化計算和差分進化算法的工作流程，并且進一步敘述了近些年差分進化算法的研究現狀和存在的問題。

第2～3章提出了兩種單目標差分優化算法。第2章主要對組合差分進化CoDE算法進行了改進，提出了改進的組合差分進化算法。第3章針對單目標優化中早熟和收斂慢的問題，提出了一種新的變異策略“DE/pbad–to–pbest/1”，該策略可以很好地解決早熟和收斂慢這兩大問題。

第4～5章提出了兩種面向約束的差分優化算法。第4章在第2章的基礎上將CoDE算法應用到了約束優化問題上，并對原始的Oracle罰函數方法進行了改進，將改進后的Oracle罰函數與CoDE算法相結合，提出了一種新的約束組合差分進化算法。第5章提出了基于替換和重置機制的多策略變異約束差分進化算法，運用多策略變異在約束處理技術的限定下考慮了目標函數的影響，平衡了約束條件和目標函數的關系，運用替換和重置機制增加種群中的多樣性使種群跳出不可行區域的局部解進一步平衡約束條件和目標函數。

第6～10章提出了5種面向多目標的差分進化算法。第6章針對DE算法求解多目標優化問題時收斂慢和均勻性欠佳等不足，提出了一種基于多策略排序變異的多目標差分進化算法，利用基于排序變異算子，促使快速接近真實的Pareto最優解的優點，同時多策略差分進化算子能有效保持算法的多樣性和分布性。第7章提出了用于求解多目標優化問題的一種基于外部歸檔和球面修剪機制的多目標差分進化算法，該算法采用外部歸檔集合來存儲進化過程中尋找到的非支配解，并引入了球面修剪機制。第8章在第7章的基礎上進一步研究多目標DE算法。在求解多目標優化問題的過程中，通過引入全局物理規劃策略更簡潔且有效地表達決策者偏好，促使進化種群能朝著決策者比較感興趣或者滿意的區域搜索。第9章提出了一種基于替換和重置機制的多策略變異約束差分進化算法，該算法利用改進切比雪夫（Tchebycheff）分解的方法把多目標優化問題變為許多單目標優化子問題；通過高效的非支配排序方法選擇具有良好收斂性和多樣性的解來指導差分進化過程；采用多策略變異方法來平衡進化過程中收斂性和多樣性。第10章針對多目標差分進化算法在求解問題時收斂慢和均勻性欠佳等不足，提出了一種改進的排序變異多目標差分進化算法，該算法將參與變異的3個父代個體中的最優個體作為基向量，并采用反向參數控制方法，在不同的優化階段動態調整參數值，同時引入改進的擁擠距離計算式來提升種群的多樣性。

第11～12章提出了兩種面向離散問題的差分進化算法。第11章針對現有離散差分進化算法在進化過程中會產生不可行解，需要借助修復操作來克服其可行性的不足，提出了一種采用位置關系的新型變異操作和新的交叉操作的排列差分進化算法。第12章以提高排列差分進化的搜索效率為目標，將禁忌搜索與排列差分進化算法結合，提出了一種基于禁忌列表的離散差分進化算法。