第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
圖3.3差分向量4 .(X,，g—Ubest，G—i)的方向拓展（b )
由圖3.3可知，合理地加入父代中的校驗個體，從進化的全局來看，不僅不影響原進化的進行，而且降低了子代種群中校驗個體落入區域C內的概率。在種群進化的後期雖“擾動” 了原全局搜索的方向，但以一定的計算開銷換來更高的概率，來規避局部最優區域附近的迭 代搜索，使算法在搜尋精度和求解速度上取得了更佳的均衡。
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
圖3.3差分向量4 .(X,，g—Ubest，G—i)的方向拓展（b )
由圖3.3可知，合理地加入父代中的校驗個體，從進化的全局來看，不僅不影響原進化的進行，而且降低了子代種群中校驗個體落入區域C內的概率。在種群進化的後期雖“擾動” 了原全局搜索的方向，但以一定的計算開銷換來更高的概率，來規避局部最優區域附近的迭 代搜索，使算法在搜尋精度和求解速度上取得了更佳的均衡。
3.2.2控制參數的自適應調整
根據以上改進方案的介紹，本文改進的進DE算法需要控制的關鍵參數有： 接下來介紹相應的參數調整策略。
(1) 自適應調整
根據第一章的介紹，一些目標跟蹤的研究工作中引入PSO算法，並取得了不錯的跟蹤效 果。PSO算法獨特的記憶機制，不僅實時地參考粒子本身最優的歷史信息，還參考當前種群 中最優的粒子信息。類似的，分析DE算法中個體的更新過程知，由於父代個體只有進化成
功才被更新，所以每個個體在當前代都是歷史最優的。關於&，^；2的自適應調整，本文選擇
類似以往工作[78]中模擬PSO信息交互機制的方式：
^ ( Xbest，G )2 = (3.6) f+f、Xbest，G )
其中，f = [^f(X,，G) + f(Xrt，G) + f(X嘆G)j/3。係數能夠根據X,，G、Xbest，G及隨機選擇的個體的適度值動態地調整，取得全局搜索方向和局部搜索方向之間的平衡。
但在進化的後期，種群進化趨於完全，個體特性趨於平穩，上述參數控制效果會逐漸減
弱。^，巧2的係數趨於相同，使算法在後期的局部搜索階段，沒有動態地投入更大的係數比
重。一個最簡單的參數控制方案，就是在種群的進化過程中，i和分別保持動態遞減和 動態遞增的趨勢。最常見的是線性調節方式[80][81]，如文獻[81]提出一種線性控制的策略如下：
Ft+1^max=Pt J(3.7）
Ch == CR+H(3.8）
其中，&，％分別是變異尺度因子和交叉概率因子的初始值。
儘管這樣的參數控制方向是正確的，但還存在不足之處：如果在迭代搜索後期還沒找到全局解，算法很容易早熟收斂。一些工作如JADE、SaDE等提出了 f，C^.隨機選取的原則，
即通過不同的分佈隨機地調整，一定程度上避免了因控制參數的不合理造成的早熟收斂問題。 這些參數調節方案經過大量的實驗仿真，得出了一些值得參考的結論。如Storn[58]等在文獻中 指出，尺度因子巧取值位於[〇.4，1]區間時，優化效果較明顯，初始值一般設置為0.5;根據JADE
算法的仿真結論，交叉概率選在0.6〜0.9之間時優化效果最佳。其他類似的研究工作也驗 證了這樣的參數區間的有效性。
需要強調的是，本論文的目的是將改進後的DE算法應用於目標跟蹤中，因此對算法的 求解速度有很高的要求。儘管當前關於參數自適應的改進工作，都或多或少地取得了很好的 效果，但這些參數調整方案往往需要更多的計算，有的參數計算方式甚至比DE算法本身的 進化計算更復雜，由此帶來的計算時間和開銷，往往不適合目標跟蹤的實時應用。此外，當 前很多參數改進的研究工作，都取得了很好的結論，可以利用這些現有的結論，設計一種更 簡單的參數調整方案，可起到“事半功倍”的效果。
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
圖3.3差分向量4 .(X,，g—Ubest，G—i)的方向拓展（b )
由圖3.3可知，合理地加入父代中的校驗個體，從進化的全局來看，不僅不影響原進化的進行，而且降低了子代種群中校驗個體落入區域C內的概率。在種群進化的後期雖“擾動” 了原全局搜索的方向，但以一定的計算開銷換來更高的概率，來規避局部最優區域附近的迭 代搜索，使算法在搜尋精度和求解速度上取得了更佳的均衡。
3.2.2控制參數的自適應調整
根據以上改進方案的介紹，本文改進的進DE算法需要控制的關鍵參數有： 接下來介紹相應的參數調整策略。
(1) 自適應調整
根據第一章的介紹，一些目標跟蹤的研究工作中引入PSO算法，並取得了不錯的跟蹤效 果。PSO算法獨特的記憶機制，不僅實時地參考粒子本身最優的歷史信息，還參考當前種群 中最優的粒子信息。類似的，分析DE算法中個體的更新過程知，由於父代個體只有進化成
功才被更新，所以每個個體在當前代都是歷史最優的。關於&，^；2的自適應調整，本文選擇
類似以往工作[78]中模擬PSO信息交互機制的方式：
^ ( Xbest，G )2 = (3.6) f+f、Xbest，G )
其中，f = [^f(X,，G) + f(Xrt，G) + f(X嘆G)j/3。係數能夠根據X,，G、Xbest，G及隨機選擇的個體的適度值動態地調整，取得全局搜索方向和局部搜索方向之間的平衡。
但在進化的後期，種群進化趨於完全，個體特性趨於平穩，上述參數控制效果會逐漸減
弱。^，巧2的係數趨於相同，使算法在後期的局部搜索階段，沒有動態地投入更大的係數比
重。一個最簡單的參數控制方案，就是在種群的進化過程中，i和分別保持動態遞減和 動態遞增的趨勢。最常見的是線性調節方式[80][81]，如文獻[81]提出一種線性控制的策略如下：
Ft+1^max=Pt J(3.7）
Ch == CR+H(3.8）
其中，&，％分別是變異尺度因子和交叉概率因子的初始值。
儘管這樣的參數控制方向是正確的，但還存在不足之處：如果在迭代搜索後期還沒找到全局解，算法很容易早熟收斂。一些工作如JADE、SaDE等提出了 f，C^.隨機選取的原則，
即通過不同的分佈隨機地調整，一定程度上避免了因控制參數的不合理造成的早熟收斂問題。 這些參數調節方案經過大量的實驗仿真，得出了一些值得參考的結論。如Storn[58]等在文獻中 指出，尺度因子巧取值位於[〇.4，1]區間時，優化效果較明顯，初始值一般設置為0.5;根據JADE
算法的仿真結論，交叉概率選在0.6〜0.9之間時優化效果最佳。其他類似的研究工作也驗 證了這樣的參數區間的有效性。
需要強調的是，本論文的目的是將改進後的DE算法應用於目標跟蹤中，因此對算法的 求解速度有很高的要求。儘管當前關於參數自適應的改進工作，都或多或少地取得了很好的 效果，但這些參數調整方案往往需要更多的計算，有的參數計算方式甚至比DE算法本身的 進化計算更復雜，由此帶來的計算時間和開銷，往往不適合目標跟蹤的實時應用。此外，當 前很多參數改進的研究工作，都取得了很好的結論，可以利用這些現有的結論，設計一種更 簡單的參數調整方案，可起到“事半功倍”的效果。
因此在以往參數調整研究結論的基礎上，為了減小因參數的自適應調整帶來的額外開銷， 本文采用線性控制和信息交互的方式相結合的方式，如下公式所示：
Fi = F〇+F(3.9)
Fi2=F0+Fi2(3.10)
其中，分別對應於式（3.5)(3.6)的心盡。如下所示：
F0 =Fmn +1 —DU -G)/G(3.11 )
CR0=Cm-CRJ*G(3.12)
其中，G為當前的進化代數。值得注意的是，F^FmxpCRm^CRmx和其他參數一樣，同樣需
要合理設置。本文利用現有改進工作的結論，設置最合理的區間範圍。同時，在後期的目標 跟蹤試驗中，根據所測試的數據集的特性，針對性的調整。
根據之後算法的性能仿真知，這樣簡化的參數“擬合”方式，一方面保證了 線性遞增，
CR.線性遞減的趨勢，另一方面，節省計算開銷和搜索時間，提高了算法求解速度，為目標 跟蹤的有效應用提供條件。
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
圖3.3差分向量4 .(X,，g—Ubest，G—i)的方向拓展（b )
由圖3.3可知，合理地加入父代中的校驗個體，從進化的全局來看，不僅不影響原進化的進行，而且降低了子代種群中校驗個體落入區域C內的概率。在種群進化的後期雖“擾動” 了原全局搜索的方向，但以一定的計算開銷換來更高的概率，來規避局部最優區域附近的迭 代搜索，使算法在搜尋精度和求解速度上取得了更佳的均衡。
3.2.2控制參數的自適應調整
根據以上改進方案的介紹，本文改進的進DE算法需要控制的關鍵參數有： 接下來介紹相應的參數調整策略。
(1) 自適應調整
根據第一章的介紹，一些目標跟蹤的研究工作中引入PSO算法，並取得了不錯的跟蹤效 果。PSO算法獨特的記憶機制，不僅實時地參考粒子本身最優的歷史信息，還參考當前種群 中最優的粒子信息。類似的，分析DE算法中個體的更新過程知，由於父代個體只有進化成
功才被更新，所以每個個體在當前代都是歷史最優的。關於&，^；2的自適應調整，本文選擇
類似以往工作[78]中模擬PSO信息交互機制的方式：
^ ( Xbest，G )2 = (3.6) f+f、Xbest，G )
其中，f = [^f(X,，G) + f(Xrt，G) + f(X嘆G)j/3。係數能夠根據X,，G、Xbest，G及隨機選擇的個體的適度值動態地調整，取得全局搜索方向和局部搜索方向之間的平衡。
但在進化的後期，種群進化趨於完全，個體特性趨於平穩，上述參數控制效果會逐漸減
弱。^，巧2的係數趨於相同，使算法在後期的局部搜索階段，沒有動態地投入更大的係數比
重。一個最簡單的參數控制方案，就是在種群的進化過程中，i和分別保持動態遞減和 動態遞增的趨勢。最常見的是線性調節方式[80][81]，如文獻[81]提出一種線性控制的策略如下：
Ft+1^max=Pt J(3.7）
Ch == CR+H(3.8）
其中，&，％分別是變異尺度因子和交叉概率因子的初始值。
儘管這樣的參數控制方向是正確的，但還存在不足之處：如果在迭代搜索後期還沒找到全局解，算法很容易早熟收斂。一些工作如JADE、SaDE等提出了 f，C^.隨機選取的原則，
即通過不同的分佈隨機地調整，一定程度上避免了因控制參數的不合理造成的早熟收斂問題。 這些參數調節方案經過大量的實驗仿真，得出了一些值得參考的結論。如Storn[58]等在文獻中 指出，尺度因子巧取值位於[〇.4，1]區間時，優化效果較明顯，初始值一般設置為0.5;根據JADE
算法的仿真結論，交叉概率選在0.6〜0.9之間時優化效果最佳。其他類似的研究工作也驗 證了這樣的參數區間的有效性。
需要強調的是，本論文的目的是將改進後的DE算法應用於目標跟蹤中，因此對算法的 求解速度有很高的要求。儘管當前關於參數自適應的改進工作，都或多或少地取得了很好的 效果，但這些參數調整方案往往需要更多的計算，有的參數計算方式甚至比DE算法本身的 進化計算更復雜，由此帶來的計算時間和開銷，往往不適合目標跟蹤的實時應用。此外，當 前很多參數改進的研究工作，都取得了很好的結論，可以利用這些現有的結論，設計一種更 簡單的參數調整方案，可起到“事半功倍”的效果。
因此在以往參數調整研究結論的基礎上，為了減小因參數的自適應調整帶來的額外開銷， 本文采用線性控制和信息交互的方式相結合的方式，如下公式所示：
Fi = F〇+F(3.9)
Fi2=F0+Fi2(3.10)
其中，分別對應於式（3.5)(3.6)的心盡。如下所示：
F0 =Fmn +1 —DU -G)/G(3.11 )
CR0=Cm-CRJ*G(3.12)
其中，G為當前的進化代數。值得注意的是，F^FmxpCRm^CRmx和其他參數一樣，同樣需
要合理設置。本文利用現有改進工作的結論，設置最合理的區間範圍。同時，在後期的目標 跟蹤試驗中，根據所測試的數據集的特性，針對性的調整。
根據之後算法的性能仿真知，這樣簡化的參數“擬合”方式，一方面保證了 線性遞增，
CR.線性遞減的趨勢，另一方面，節省計算開銷和搜索時間，提高了算法求解速度，為目標 跟蹤的有效應用提供條件。
(2) 盡的自適應調整的動態調整需要考慮兩點：
首先，盡需要在進化的後期引入且數值要小。畢竟種群進化到後期是以局部搜索為主，“退化”的差分向量能有效地增加種群多樣性，使得算法後期搜索新空間的能力加強，但不可破壞中後期成熟個體的解結構信息，以免造成前期進化開銷的浪費。
其次，廠3的設置和種群的多樣性建立直接聯繫。參考當前種群整體的多樣性信息和位置
信息，可大大提高算法的搜尋速度和精度。本文在算法的後期，在引入盡時實時考察所有個
體的位置信息和適度值信息，用於“退化”的差分向量的係數調整。
關於多樣性信息和位置信息的計算，本文使用文獻[82]的方式，如下
1 NP DPC =-Xji(G +1})1 NP7FC =斤寫U (X(G)) - / (X(G +1)))2
其中，PC,FC分別代表種群的位置多樣性和適度值多樣性。
為了更好地應用PC, FC包含的信息，本文采用類似文獻[82]中壓縮的方式。最終參數巧3 的形式如下：
其中，奐c=1 —(1 + PC)*e—PC，2FC=1 —(1 + PC)*e—FC，且 APC，AFCe(0，1)。
根據文獻[82]中的結論，PC,FC都很小時，進化算法到了後期階段，算法以收斂速度和 搜尋精度性能為主。而正是在此時，通過引入U^，G—1來拓展搜索方向，並通過參數盡的動態 調整，實現多個性能之間的均衡。
係數&的自適應調整，充分利用了種群的多樣性信息和位置信息，在算法的後期進一步 提高了全局搜索的概率。通過少量的計算開銷，規避了原種群向局部最優解附近的盲目進化。
20
本文設計的算法實現步驟如下：
基於進化方向拓展的DE算法實現步驟（TaDE)
1:初始化種群P、控制參數^，^，^，^^，^、集合人^。
2:計算種群P個體的適度值，找到X並驗證算法的終止條件。否則G = G+1。
best，G
3:種群進化更新：產生校驗個體U (前期）。
i，G
(iv) 變異：按照式（3.11)(3.12)(3.14)動態調整參數。
從集合P和A中分別選出差分個體Xrt，G，X嘆G。
根照式（3.2)進行變異操作。
(v) 交叉：根照式（2.9)進行交叉操作。
(vi) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
4：種群進化更新：產生校驗個體U。（中後期）。
i，G
(i) 變異：按照式（3.11)(3.12)(3.17)(3.14)動態調整參數。
從集合P，A，U中分別選出差分個體Xh^XuaUmw。
根照式（3.4)進行變異操作。
(ii) 交叉：根照式（2.9)進行交叉操作。
(iii) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
U進入下一代種群或集合U。
i，G
5：返回2,直到滿足算法的終止條件。
3.3算法仿真及性能分析
3.3.1算法性能評價規則
(1)函數評價次數（Function Evaluation，FE)
算法在迭代過程中，每個個體進化後都需要計算關於某函數的適度值，進行一次函數評 價。因此，在種群進化過程中記錄當前函數評價的總次數。當/(X)-/^^)^或視 >視_ 時，算法終止迭代。
(2) 尋優成功率
尋優成功率可衡量算法的可靠性。當前循環的輸出結果與理論最優值之間的誤差滿足設 定的閾值時，當前循環的搜索結果收斂，算法尋優成功。#次算法循環中，若搜索結果收斂
n次，尋優成功率為^。
N
(3) 平均最優適應度
優化算法某一次的尋優精度往往具有不穩定性。因此對算法進行多次測試，最終所有最 優個體適度值的平均值，即為平均最優適應度。
(4) 最優個體進化趨勢曲線
進化趨勢曲線直觀地呈現出進化算法的尋優過程和最優解的變化情況。
3.3.2測試函數及初始化
本文選擇式（3.16) - (3.19)四個測試函數（Rastrigin, Ackley, Griewank, Rosenbrock)來
衡量改進算法的尋優性能：
D
Kx) = Z[x2 -10cos(2冗x)+10](3.16)
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
圖3.3差分向量4 .(X,，g—Ubest，G—i)的方向拓展（b )
由圖3.3可知，合理地加入父代中的校驗個體，從進化的全局來看，不僅不影響原進化的進行，而且降低了子代種群中校驗個體落入區域C內的概率。在種群進化的後期雖“擾動” 了原全局搜索的方向，但以一定的計算開銷換來更高的概率，來規避局部最優區域附近的迭 代搜索，使算法在搜尋精度和求解速度上取得了更佳的均衡。
3.2.2控制參數的自適應調整
根據以上改進方案的介紹，本文改進的進DE算法需要控制的關鍵參數有： 接下來介紹相應的參數調整策略。
(1) 自適應調整
根據第一章的介紹，一些目標跟蹤的研究工作中引入PSO算法，並取得了不錯的跟蹤效 果。PSO算法獨特的記憶機制，不僅實時地參考粒子本身最優的歷史信息，還參考當前種群 中最優的粒子信息。類似的，分析DE算法中個體的更新過程知，由於父代個體只有進化成
功才被更新，所以每個個體在當前代都是歷史最優的。關於&，^；2的自適應調整，本文選擇
類似以往工作[78]中模擬PSO信息交互機制的方式：
^ ( Xbest，G )2 = (3.6) f+f、Xbest，G )
其中，f = [^f(X,，G) + f(Xrt，G) + f(X嘆G)j/3。係數能夠根據X,，G、Xbest，G及隨機選擇的個體的適度值動態地調整，取得全局搜索方向和局部搜索方向之間的平衡。
但在進化的後期，種群進化趨於完全，個體特性趨於平穩，上述參數控制效果會逐漸減
弱。^，巧2的係數趨於相同，使算法在後期的局部搜索階段，沒有動態地投入更大的係數比
重。一個最簡單的參數控制方案，就是在種群的進化過程中，i和分別保持動態遞減和 動態遞增的趨勢。最常見的是線性調節方式[80][81]，如文獻[81]提出一種線性控制的策略如下：
Ft+1^max=Pt J(3.7）
Ch == CR+H(3.8）
其中，&，％分別是變異尺度因子和交叉概率因子的初始值。
儘管這樣的參數控制方向是正確的，但還存在不足之處：如果在迭代搜索後期還沒找到全局解，算法很容易早熟收斂。一些工作如JADE、SaDE等提出了 f，C^.隨機選取的原則，
即通過不同的分佈隨機地調整，一定程度上避免了因控制參數的不合理造成的早熟收斂問題。 這些參數調節方案經過大量的實驗仿真，得出了一些值得參考的結論。如Storn[58]等在文獻中 指出，尺度因子巧取值位於[〇.4，1]區間時，優化效果較明顯，初始值一般設置為0.5;根據JADE
算法的仿真結論，交叉概率選在0.6〜0.9之間時優化效果最佳。其他類似的研究工作也驗 證了這樣的參數區間的有效性。
需要強調的是，本論文的目的是將改進後的DE算法應用於目標跟蹤中，因此對算法的 求解速度有很高的要求。儘管當前關於參數自適應的改進工作，都或多或少地取得了很好的 效果，但這些參數調整方案往往需要更多的計算，有的參數計算方式甚至比DE算法本身的 進化計算更復雜，由此帶來的計算時間和開銷，往往不適合目標跟蹤的實時應用。此外，當 前很多參數改進的研究工作，都取得了很好的結論，可以利用這些現有的結論，設計一種更 簡單的參數調整方案，可起到“事半功倍”的效果。
因此在以往參數調整研究結論的基礎上，為了減小因參數的自適應調整帶來的額外開銷， 本文采用線性控制和信息交互的方式相結合的方式，如下公式所示：
Fi = F〇+F(3.9)
Fi2=F0+Fi2(3.10)
其中，分別對應於式（3.5)(3.6)的心盡。如下所示：
F0 =Fmn +1 —DU -G)/G(3.11 )
CR0=Cm-CRJ*G(3.12)
其中，G為當前的進化代數。值得注意的是，F^FmxpCRm^CRmx和其他參數一樣，同樣需
要合理設置。本文利用現有改進工作的結論，設置最合理的區間範圍。同時，在後期的目標 跟蹤試驗中，根據所測試的數據集的特性，針對性的調整。
根據之後算法的性能仿真知，這樣簡化的參數“擬合”方式，一方面保證了 線性遞增，
CR.線性遞減的趨勢，另一方面，節省計算開銷和搜索時間，提高了算法求解速度，為目標 跟蹤的有效應用提供條件。
(2) 盡的自適應調整的動態調整需要考慮兩點：
首先，盡需要在進化的後期引入且數值要小。畢竟種群進化到後期是以局部搜索為主，“退化”的差分向量能有效地增加種群多樣性，使得算法後期搜索新空間的能力加強，但不可破壞中後期成熟個體的解結構信息，以免造成前期進化開銷的浪費。
其次，廠3的設置和種群的多樣性建立直接聯繫。參考當前種群整體的多樣性信息和位置
信息，可大大提高算法的搜尋速度和精度。本文在算法的後期，在引入盡時實時考察所有個
體的位置信息和適度值信息，用於“退化”的差分向量的係數調整。
關於多樣性信息和位置信息的計算，本文使用文獻[82]的方式，如下
1 NP DPC =-Xji(G +1})1 NP7FC =斤寫U (X(G)) - / (X(G +1)))2
其中，PC,FC分別代表種群的位置多樣性和適度值多樣性。
為了更好地應用PC, FC包含的信息，本文采用類似文獻[82]中壓縮的方式。最終參數巧3 的形式如下：
其中，奐c=1 —(1 + PC)*e—PC，2FC=1 —(1 + PC)*e—FC，且 APC，AFCe(0，1)。
根據文獻[82]中的結論，PC,FC都很小時，進化算法到了後期階段，算法以收斂速度和 搜尋精度性能為主。而正是在此時，通過引入U^，G—1來拓展搜索方向，並通過參數盡的動態 調整，實現多個性能之間的均衡。
係數&的自適應調整，充分利用了種群的多樣性信息和位置信息，在算法的後期進一步 提高了全局搜索的概率。通過少量的計算開銷，規避了原種群向局部最優解附近的盲目進化。
20
本文設計的算法實現步驟如下：
基於進化方向拓展的DE算法實現步驟（TaDE)
1:初始化種群P、控制參數^，^，^，^^，^、集合人^。
2:計算種群P個體的適度值，找到X並驗證算法的終止條件。否則G = G+1。
best，G
3:種群進化更新：產生校驗個體U (前期）。
i，G
(iv) 變異：按照式（3.11)(3.12)(3.14)動態調整參數。
從集合P和A中分別選出差分個體Xrt，G，X嘆G。
根照式（3.2)進行變異操作。
(v) 交叉：根照式（2.9)進行交叉操作。
(vi) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
4：種群進化更新：產生校驗個體U。（中後期）。
i，G
(i) 變異：按照式（3.11)(3.12)(3.17)(3.14)動態調整參數。
從集合P，A，U中分別選出差分個體Xh^XuaUmw。
根照式（3.4)進行變異操作。
(ii) 交叉：根照式（2.9)進行交叉操作。
(iii) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
U進入下一代種群或集合U。
i，G
5：返回2,直到滿足算法的終止條件。
3.3算法仿真及性能分析
3.3.1算法性能評價規則
(1)函數評價次數（Function Evaluation，FE)
算法在迭代過程中，每個個體進化後都需要計算關於某函數的適度值，進行一次函數評 價。因此，在種群進化過程中記錄當前函數評價的總次數。當/(X)-/^^)^或視 >視_ 時，算法終止迭代。
(2) 尋優成功率
尋優成功率可衡量算法的可靠性。當前循環的輸出結果與理論最優值之間的誤差滿足設 定的閾值時，當前循環的搜索結果收斂，算法尋優成功。#次算法循環中，若搜索結果收斂
n次，尋優成功率為^。
N
(3) 平均最優適應度
優化算法某一次的尋優精度往往具有不穩定性。因此對算法進行多次測試，最終所有最 優個體適度值的平均值，即為平均最優適應度。
(4) 最優個體進化趨勢曲線
進化趨勢曲線直觀地呈現出進化算法的尋優過程和最優解的變化情況。
3.3.2測試函數及初始化
本文選擇式（3.16) - (3.19)四個測試函數（Rastrigin, Ackley, Griewank, Rosenbrock)來
衡量改進算法的尋優性能：
D
Kx) = Z[x2 -10cos(2冗x)+10](3.16)
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
圖3.3差分向量4 .(X,，g—Ubest，G—i)的方向拓展（b )
由圖3.3可知，合理地加入父代中的校驗個體，從進化的全局來看，不僅不影響原進化的進行，而且降低了子代種群中校驗個體落入區域C內的概率。在種群進化的後期雖“擾動” 了原全局搜索的方向，但以一定的計算開銷換來更高的概率，來規避局部最優區域附近的迭 代搜索，使算法在搜尋精度和求解速度上取得了更佳的均衡。
3.2.2控制參數的自適應調整
根據以上改進方案的介紹，本文改進的進DE算法需要控制的關鍵參數有： 接下來介紹相應的參數調整策略。
(1) 自適應調整
根據第一章的介紹，一些目標跟蹤的研究工作中引入PSO算法，並取得了不錯的跟蹤效 果。PSO算法獨特的記憶機制，不僅實時地參考粒子本身最優的歷史信息，還參考當前種群 中最優的粒子信息。類似的，分析DE算法中個體的更新過程知，由於父代個體只有進化成
功才被更新，所以每個個體在當前代都是歷史最優的。關於&，^；2的自適應調整，本文選擇
類似以往工作[78]中模擬PSO信息交互機制的方式：
^ ( Xbest，G )2 = (3.6) f+f、Xbest，G )
其中，f = [^f(X,，G) + f(Xrt，G) + f(X嘆G)j/3。係數能夠根據X,，G、Xbest，G及隨機選擇的個體的適度值動態地調整，取得全局搜索方向和局部搜索方向之間的平衡。
但在進化的後期，種群進化趨於完全，個體特性趨於平穩，上述參數控制效果會逐漸減
弱。^，巧2的係數趨於相同，使算法在後期的局部搜索階段，沒有動態地投入更大的係數比
重。一個最簡單的參數控制方案，就是在種群的進化過程中，i和分別保持動態遞減和 動態遞增的趨勢。最常見的是線性調節方式[80][81]，如文獻[81]提出一種線性控制的策略如下：
Ft+1^max=Pt J(3.7）
Ch == CR+H(3.8）
其中，&，％分別是變異尺度因子和交叉概率因子的初始值。
儘管這樣的參數控制方向是正確的，但還存在不足之處：如果在迭代搜索後期還沒找到全局解，算法很容易早熟收斂。一些工作如JADE、SaDE等提出了 f，C^.隨機選取的原則，
即通過不同的分佈隨機地調整，一定程度上避免了因控制參數的不合理造成的早熟收斂問題。 這些參數調節方案經過大量的實驗仿真，得出了一些值得參考的結論。如Storn[58]等在文獻中 指出，尺度因子巧取值位於[〇.4，1]區間時，優化效果較明顯，初始值一般設置為0.5;根據JADE
算法的仿真結論，交叉概率選在0.6〜0.9之間時優化效果最佳。其他類似的研究工作也驗 證了這樣的參數區間的有效性。
需要強調的是，本論文的目的是將改進後的DE算法應用於目標跟蹤中，因此對算法的 求解速度有很高的要求。儘管當前關於參數自適應的改進工作，都或多或少地取得了很好的 效果，但這些參數調整方案往往需要更多的計算，有的參數計算方式甚至比DE算法本身的 進化計算更復雜，由此帶來的計算時間和開銷，往往不適合目標跟蹤的實時應用。此外，當 前很多參數改進的研究工作，都取得了很好的結論，可以利用這些現有的結論，設計一種更 簡單的參數調整方案，可起到“事半功倍”的效果。
因此在以往參數調整研究結論的基礎上，為了減小因參數的自適應調整帶來的額外開銷， 本文采用線性控制和信息交互的方式相結合的方式，如下公式所示：
Fi = F〇+F(3.9)
Fi2=F0+Fi2(3.10)
其中，分別對應於式（3.5)(3.6)的心盡。如下所示：
F0 =Fmn +1 —DU -G)/G(3.11 )
CR0=Cm-CRJ*G(3.12)
其中，G為當前的進化代數。值得注意的是，F^FmxpCRm^CRmx和其他參數一樣，同樣需
要合理設置。本文利用現有改進工作的結論，設置最合理的區間範圍。同時，在後期的目標 跟蹤試驗中，根據所測試的數據集的特性，針對性的調整。
根據之後算法的性能仿真知，這樣簡化的參數“擬合”方式，一方面保證了 線性遞增，
CR.線性遞減的趨勢，另一方面，節省計算開銷和搜索時間，提高了算法求解速度，為目標 跟蹤的有效應用提供條件。
(2) 盡的自適應調整的動態調整需要考慮兩點：
首先，盡需要在進化的後期引入且數值要小。畢竟種群進化到後期是以局部搜索為主，“退化”的差分向量能有效地增加種群多樣性，使得算法後期搜索新空間的能力加強，但不可破壞中後期成熟個體的解結構信息，以免造成前期進化開銷的浪費。
其次，廠3的設置和種群的多樣性建立直接聯繫。參考當前種群整體的多樣性信息和位置
信息，可大大提高算法的搜尋速度和精度。本文在算法的後期，在引入盡時實時考察所有個
體的位置信息和適度值信息，用於“退化”的差分向量的係數調整。
關於多樣性信息和位置信息的計算，本文使用文獻[82]的方式，如下
1 NP DPC =-Xji(G +1})1 NP7FC =斤寫U (X(G)) - / (X(G +1)))2
其中，PC,FC分別代表種群的位置多樣性和適度值多樣性。
為了更好地應用PC, FC包含的信息，本文采用類似文獻[82]中壓縮的方式。最終參數巧3 的形式如下：
其中，奐c=1 —(1 + PC)*e—PC，2FC=1 —(1 + PC)*e—FC，且 APC，AFCe(0，1)。
根據文獻[82]中的結論，PC,FC都很小時，進化算法到了後期階段，算法以收斂速度和 搜尋精度性能為主。而正是在此時，通過引入U^，G—1來拓展搜索方向，並通過參數盡的動態 調整，實現多個性能之間的均衡。
係數&的自適應調整，充分利用了種群的多樣性信息和位置信息，在算法的後期進一步 提高了全局搜索的概率。通過少量的計算開銷，規避了原種群向局部最優解附近的盲目進化。
20
本文設計的算法實現步驟如下：
基於進化方向拓展的DE算法實現步驟（TaDE)
1:初始化種群P、控制參數^，^，^，^^，^、集合人^。
2:計算種群P個體的適度值，找到X並驗證算法的終止條件。否則G = G+1。
best，G
3:種群進化更新：產生校驗個體U (前期）。
i，G
(iv) 變異：按照式（3.11)(3.12)(3.14)動態調整參數。
從集合P和A中分別選出差分個體Xrt，G，X嘆G。
根照式（3.2)進行變異操作。
(v) 交叉：根照式（2.9)進行交叉操作。
(vi) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
4：種群進化更新：產生校驗個體U。（中後期）。
i，G
(i) 變異：按照式（3.11)(3.12)(3.17)(3.14)動態調整參數。
從集合P，A，U中分別選出差分個體Xh^XuaUmw。
根照式（3.4)進行變異操作。
(ii) 交叉：根照式（2.9)進行交叉操作。
(iii) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
U進入下一代種群或集合U。
i，G
5：返回2,直到滿足算法的終止條件。
3.3算法仿真及性能分析
3.3.1算法性能評價規則
(1)函數評價次數（Function Evaluation，FE)
算法在迭代過程中，每個個體進化後都需要計算關於某函數的適度值，進行一次函數評 價。因此，在種群進化過程中記錄當前函數評價的總次數。當/(X)-/^^)^或視 >視_ 時，算法終止迭代。
(2) 尋優成功率
尋優成功率可衡量算法的可靠性。當前循環的輸出結果與理論最優值之間的誤差滿足設 定的閾值時，當前循環的搜索結果收斂，算法尋優成功。#次算法循環中，若搜索結果收斂
n次，尋優成功率為^。
N
(3) 平均最優適應度
優化算法某一次的尋優精度往往具有不穩定性。因此對算法進行多次測試，最終所有最 優個體適度值的平均值，即為平均最優適應度。
(4) 最優個體進化趨勢曲線
進化趨勢曲線直觀地呈現出進化算法的尋優過程和最優解的變化情況。
3.3.2測試函數及初始化
本文選擇式（3.16) - (3.19)四個測試函數（Rastrigin, Ackley, Griewank, Rosenbrock)來
衡量改進算法的尋優性能：
D
Kx) = Z[x2 -10cos(2冗x)+10](3.16)
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
圖3.3差分向量4 .(X,，g—Ubest，G—i)的方向拓展（b )
由圖3.3可知，合理地加入父代中的校驗個體，從進化的全局來看，不僅不影響原進化的進行，而且降低了子代種群中校驗個體落入區域C內的概率。在種群進化的後期雖“擾動” 了原全局搜索的方向，但以一定的計算開銷換來更高的概率，來規避局部最優區域附近的迭 代搜索，使算法在搜尋精度和求解速度上取得了更佳的均衡。
3.2.2控制參數的自適應調整
根據以上改進方案的介紹，本文改進的進DE算法需要控制的關鍵參數有： 接下來介紹相應的參數調整策略。
(1) 自適應調整
根據第一章的介紹，一些目標跟蹤的研究工作中引入PSO算法，並取得了不錯的跟蹤效 果。PSO算法獨特的記憶機制，不僅實時地參考粒子本身最優的歷史信息，還參考當前種群 中最優的粒子信息。類似的，分析DE算法中個體的更新過程知，由於父代個體只有進化成
功才被更新，所以每個個體在當前代都是歷史最優的。關於&，^；2的自適應調整，本文選擇
類似以往工作[78]中模擬PSO信息交互機制的方式：
^ ( Xbest，G )2 = (3.6) f+f、Xbest，G )
其中，f = [^f(X,，G) + f(Xrt，G) + f(X嘆G)j/3。係數能夠根據X,，G、Xbest，G及隨機選擇的個體的適度值動態地調整，取得全局搜索方向和局部搜索方向之間的平衡。
但在進化的後期，種群進化趨於完全，個體特性趨於平穩，上述參數控制效果會逐漸減
弱。^，巧2的係數趨於相同，使算法在後期的局部搜索階段，沒有動態地投入更大的係數比
重。一個最簡單的參數控制方案，就是在種群的進化過程中，i和分別保持動態遞減和 動態遞增的趨勢。最常見的是線性調節方式[80][81]，如文獻[81]提出一種線性控制的策略如下：
Ft+1^max=Pt J(3.7）
Ch == CR+H(3.8）
其中，&，％分別是變異尺度因子和交叉概率因子的初始值。
儘管這樣的參數控制方向是正確的，但還存在不足之處：如果在迭代搜索後期還沒找到全局解，算法很容易早熟收斂。一些工作如JADE、SaDE等提出了 f，C^.隨機選取的原則，
即通過不同的分佈隨機地調整，一定程度上避免了因控制參數的不合理造成的早熟收斂問題。 這些參數調節方案經過大量的實驗仿真，得出了一些值得參考的結論。如Storn[58]等在文獻中 指出，尺度因子巧取值位於[〇.4，1]區間時，優化效果較明顯，初始值一般設置為0.5;根據JADE
算法的仿真結論，交叉概率選在0.6〜0.9之間時優化效果最佳。其他類似的研究工作也驗 證了這樣的參數區間的有效性。
需要強調的是，本論文的目的是將改進後的DE算法應用於目標跟蹤中，因此對算法的 求解速度有很高的要求。儘管當前關於參數自適應的改進工作，都或多或少地取得了很好的 效果，但這些參數調整方案往往需要更多的計算，有的參數計算方式甚至比DE算法本身的 進化計算更復雜，由此帶來的計算時間和開銷，往往不適合目標跟蹤的實時應用。此外，當 前很多參數改進的研究工作，都取得了很好的結論，可以利用這些現有的結論，設計一種更 簡單的參數調整方案，可起到“事半功倍”的效果。
因此在以往參數調整研究結論的基礎上，為了減小因參數的自適應調整帶來的額外開銷， 本文采用線性控制和信息交互的方式相結合的方式，如下公式所示：
Fi = F〇+F(3.9)
Fi2=F0+Fi2(3.10)
其中，分別對應於式（3.5)(3.6)的心盡。如下所示：
F0 =Fmn +1 —DU -G)/G(3.11 )
CR0=Cm-CRJ*G(3.12)
其中，G為當前的進化代數。值得注意的是，F^FmxpCRm^CRmx和其他參數一樣，同樣需
要合理設置。本文利用現有改進工作的結論，設置最合理的區間範圍。同時，在後期的目標 跟蹤試驗中，根據所測試的數據集的特性，針對性的調整。
根據之後算法的性能仿真知，這樣簡化的參數“擬合”方式，一方面保證了 線性遞增，
CR.線性遞減的趨勢，另一方面，節省計算開銷和搜索時間，提高了算法求解速度，為目標 跟蹤的有效應用提供條件。
(2) 盡的自適應調整的動態調整需要考慮兩點：
首先，盡需要在進化的後期引入且數值要小。畢竟種群進化到後期是以局部搜索為主，“退化”的差分向量能有效地增加種群多樣性，使得算法後期搜索新空間的能力加強，但不可破壞中後期成熟個體的解結構信息，以免造成前期進化開銷的浪費。
其次，廠3的設置和種群的多樣性建立直接聯繫。參考當前種群整體的多樣性信息和位置
信息，可大大提高算法的搜尋速度和精度。本文在算法的後期，在引入盡時實時考察所有個
體的位置信息和適度值信息，用於“退化”的差分向量的係數調整。
關於多樣性信息和位置信息的計算，本文使用文獻[82]的方式，如下
1 NP DPC =-Xji(G +1})1 NP7FC =斤寫U (X(G)) - / (X(G +1)))2
其中，PC,FC分別代表種群的位置多樣性和適度值多樣性。
為了更好地應用PC, FC包含的信息，本文采用類似文獻[82]中壓縮的方式。最終參數巧3 的形式如下：
其中，奐c=1 —(1 + PC)*e—PC，2FC=1 —(1 + PC)*e—FC，且 APC，AFCe(0，1)。
根據文獻[82]中的結論，PC,FC都很小時，進化算法到了後期階段，算法以收斂速度和 搜尋精度性能為主。而正是在此時，通過引入U^，G—1來拓展搜索方向，並通過參數盡的動態 調整，實現多個性能之間的均衡。
係數&的自適應調整，充分利用了種群的多樣性信息和位置信息，在算法的後期進一步 提高了全局搜索的概率。通過少量的計算開銷，規避了原種群向局部最優解附近的盲目進化。
20
本文設計的算法實現步驟如下：
基於進化方向拓展的DE算法實現步驟（TaDE)
1:初始化種群P、控制參數^，^，^，^^，^、集合人^。
2:計算種群P個體的適度值，找到X並驗證算法的終止條件。否則G = G+1。
best，G
3:種群進化更新：產生校驗個體U (前期）。
i，G
(iv) 變異：按照式（3.11)(3.12)(3.14)動態調整參數。
從集合P和A中分別選出差分個體Xrt，G，X嘆G。
根照式（3.2)進行變異操作。
(v) 交叉：根照式（2.9)進行交叉操作。
(vi) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
4：種群進化更新：產生校驗個體U。（中後期）。
i，G
(i) 變異：按照式（3.11)(3.12)(3.17)(3.14)動態調整參數。
從集合P，A，U中分別選出差分個體Xh^XuaUmw。
根照式（3.4)進行變異操作。
(ii) 交叉：根照式（2.9)進行交叉操作。
(iii) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
U進入下一代種群或集合U。
i，G
5：返回2,直到滿足算法的終止條件。
3.3算法仿真及性能分析
3.3.1算法性能評價規則
(1)函數評價次數（Function Evaluation，FE)
算法在迭代過程中，每個個體進化後都需要計算關於某函數的適度值，進行一次函數評 價。因此，在種群進化過程中記錄當前函數評價的總次數。當/(X)-/^^)^或視 >視_ 時，算法終止迭代。
(2) 尋優成功率
尋優成功率可衡量算法的可靠性。當前循環的輸出結果與理論最優值之間的誤差滿足設 定的閾值時，當前循環的搜索結果收斂，算法尋優成功。#次算法循環中，若搜索結果收斂
n次，尋優成功率為^。
N
(3) 平均最優適應度
優化算法某一次的尋優精度往往具有不穩定性。因此對算法進行多次測試，最終所有最 優個體適度值的平均值，即為平均最優適應度。
(4) 最優個體進化趨勢曲線
進化趨勢曲線直觀地呈現出進化算法的尋優過程和最優解的變化情況。
3.3.2測試函數及初始化
本文選擇式（3.16) - (3.19)四個測試函數（Rastrigin, Ackley, Griewank, Rosenbrock)來
衡量改進算法的尋優性能：
D
Kx) = Z[x2 -10cos(2冗x)+10](3.16)
i=1i=1
為更直觀地顯示各測試函數的特徵，本文畫出各測試函數的三維圖，如圖3.4所示。根
據圖3.4顯示，各測試函數典型複雜且各具特色。f〇s(X)簡單平滑，雖為單峰函數，但變量 之間相互關聯，基於梯度信息的全局搜索方向並不時時準確，傳統優化方法求解困難。
fas(X)，fck(X)和•41(x)均是多峰函數，最小值均位於0;但存在多個局部極值，全局最優
解搜尋困難。特別地，函數fri(X)的局部極小值與全局最小值差別比較小，欺騙性較強。
22
(c) Griewank 函數（d) Rosenbrock 函數
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
圖3.3差分向量4 .(X,，g—Ubest，G—i)的方向拓展（b )
由圖3.3可知，合理地加入父代中的校驗個體，從進化的全局來看，不僅不影響原進化的進行，而且降低了子代種群中校驗個體落入區域C內的概率。在種群進化的後期雖“擾動” 了原全局搜索的方向，但以一定的計算開銷換來更高的概率，來規避局部最優區域附近的迭 代搜索，使算法在搜尋精度和求解速度上取得了更佳的均衡。
3.2.2控制參數的自適應調整
根據以上改進方案的介紹，本文改進的進DE算法需要控制的關鍵參數有： 接下來介紹相應的參數調整策略。
(1) 自適應調整
根據第一章的介紹，一些目標跟蹤的研究工作中引入PSO算法，並取得了不錯的跟蹤效 果。PSO算法獨特的記憶機制，不僅實時地參考粒子本身最優的歷史信息，還參考當前種群 中最優的粒子信息。類似的，分析DE算法中個體的更新過程知，由於父代個體只有進化成
功才被更新，所以每個個體在當前代都是歷史最優的。關於&，^；2的自適應調整，本文選擇
類似以往工作[78]中模擬PSO信息交互機制的方式：
^ ( Xbest，G )2 = (3.6) f+f、Xbest，G )
其中，f = [^f(X,，G) + f(Xrt，G) + f(X嘆G)j/3。係數能夠根據X,，G、Xbest，G及隨機選擇的個體的適度值動態地調整，取得全局搜索方向和局部搜索方向之間的平衡。
但在進化的後期，種群進化趨於完全，個體特性趨於平穩，上述參數控制效果會逐漸減
弱。^，巧2的係數趨於相同，使算法在後期的局部搜索階段，沒有動態地投入更大的係數比
重。一個最簡單的參數控制方案，就是在種群的進化過程中，i和分別保持動態遞減和 動態遞增的趨勢。最常見的是線性調節方式[80][81]，如文獻[81]提出一種線性控制的策略如下：
Ft+1^max=Pt J(3.7）
Ch == CR+H(3.8）
其中，&，％分別是變異尺度因子和交叉概率因子的初始值。
儘管這樣的參數控制方向是正確的，但還存在不足之處：如果在迭代搜索後期還沒找到全局解，算法很容易早熟收斂。一些工作如JADE、SaDE等提出了 f，C^.隨機選取的原則，
即通過不同的分佈隨機地調整，一定程度上避免了因控制參數的不合理造成的早熟收斂問題。 這些參數調節方案經過大量的實驗仿真，得出了一些值得參考的結論。如Storn[58]等在文獻中 指出，尺度因子巧取值位於[〇.4，1]區間時，優化效果較明顯，初始值一般設置為0.5;根據JADE
算法的仿真結論，交叉概率選在0.6〜0.9之間時優化效果最佳。其他類似的研究工作也驗 證了這樣的參數區間的有效性。
需要強調的是，本論文的目的是將改進後的DE算法應用於目標跟蹤中，因此對算法的 求解速度有很高的要求。儘管當前關於參數自適應的改進工作，都或多或少地取得了很好的 效果，但這些參數調整方案往往需要更多的計算，有的參數計算方式甚至比DE算法本身的 進化計算更復雜，由此帶來的計算時間和開銷，往往不適合目標跟蹤的實時應用。此外，當 前很多參數改進的研究工作，都取得了很好的結論，可以利用這些現有的結論，設計一種更 簡單的參數調整方案，可起到“事半功倍”的效果。
因此在以往參數調整研究結論的基礎上，為了減小因參數的自適應調整帶來的額外開銷， 本文采用線性控制和信息交互的方式相結合的方式，如下公式所示：
Fi = F〇+F(3.9)
Fi2=F0+Fi2(3.10)
其中，分別對應於式（3.5)(3.6)的心盡。如下所示：
F0 =Fmn +1 —DU -G)/G(3.11 )
CR0=Cm-CRJ*G(3.12)
其中，G為當前的進化代數。值得注意的是，F^FmxpCRm^CRmx和其他參數一樣，同樣需
要合理設置。本文利用現有改進工作的結論，設置最合理的區間範圍。同時，在後期的目標 跟蹤試驗中，根據所測試的數據集的特性，針對性的調整。
根據之後算法的性能仿真知，這樣簡化的參數“擬合”方式，一方面保證了 線性遞增，
CR.線性遞減的趨勢，另一方面，節省計算開銷和搜索時間，提高了算法求解速度，為目標 跟蹤的有效應用提供條件。
(2) 盡的自適應調整的動態調整需要考慮兩點：
首先，盡需要在進化的後期引入且數值要小。畢竟種群進化到後期是以局部搜索為主，“退化”的差分向量能有效地增加種群多樣性，使得算法後期搜索新空間的能力加強，但不可破壞中後期成熟個體的解結構信息，以免造成前期進化開銷的浪費。
其次，廠3的設置和種群的多樣性建立直接聯繫。參考當前種群整體的多樣性信息和位置
信息，可大大提高算法的搜尋速度和精度。本文在算法的後期，在引入盡時實時考察所有個
體的位置信息和適度值信息，用於“退化”的差分向量的係數調整。
關於多樣性信息和位置信息的計算，本文使用文獻[82]的方式，如下
1 NP DPC =-Xji(G +1})1 NP7FC =斤寫U (X(G)) - / (X(G +1)))2
其中，PC,FC分別代表種群的位置多樣性和適度值多樣性。
為了更好地應用PC, FC包含的信息，本文采用類似文獻[82]中壓縮的方式。最終參數巧3 的形式如下：
其中，奐c=1 —(1 + PC)*e—PC，2FC=1 —(1 + PC)*e—FC，且 APC，AFCe(0，1)。
根據文獻[82]中的結論，PC,FC都很小時，進化算法到了後期階段，算法以收斂速度和 搜尋精度性能為主。而正是在此時，通過引入U^，G—1來拓展搜索方向，並通過參數盡的動態 調整，實現多個性能之間的均衡。
係數&的自適應調整，充分利用了種群的多樣性信息和位置信息，在算法的後期進一步 提高了全局搜索的概率。通過少量的計算開銷，規避了原種群向局部最優解附近的盲目進化。
20
本文設計的算法實現步驟如下：
基於進化方向拓展的DE算法實現步驟（TaDE)
1:初始化種群P、控制參數^，^，^，^^，^、集合人^。
2:計算種群P個體的適度值，找到X並驗證算法的終止條件。否則G = G+1。
best，G
3:種群進化更新：產生校驗個體U (前期）。
i，G
(iv) 變異：按照式（3.11)(3.12)(3.14)動態調整參數。
從集合P和A中分別選出差分個體Xrt，G，X嘆G。
根照式（3.2)進行變異操作。
(v) 交叉：根照式（2.9)進行交叉操作。
(vi) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
4：種群進化更新：產生校驗個體U。（中後期）。
i，G
(i) 變異：按照式（3.11)(3.12)(3.17)(3.14)動態調整參數。
從集合P，A，U中分別選出差分個體Xh^XuaUmw。
根照式（3.4)進行變異操作。
(ii) 交叉：根照式（2.9)進行交叉操作。
(iii) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
U進入下一代種群或集合U。
i，G
5：返回2,直到滿足算法的終止條件。
3.3算法仿真及性能分析
3.3.1算法性能評價規則
(1)函數評價次數（Function Evaluation，FE)
算法在迭代過程中，每個個體進化後都需要計算關於某函數的適度值，進行一次函數評 價。因此，在種群進化過程中記錄當前函數評價的總次數。當/(X)-/^^)^或視 >視_ 時，算法終止迭代。
(2) 尋優成功率
尋優成功率可衡量算法的可靠性。當前循環的輸出結果與理論最優值之間的誤差滿足設 定的閾值時，當前循環的搜索結果收斂，算法尋優成功。#次算法循環中，若搜索結果收斂
n次，尋優成功率為^。
N
(3) 平均最優適應度
優化算法某一次的尋優精度往往具有不穩定性。因此對算法進行多次測試，最終所有最 優個體適度值的平均值，即為平均最優適應度。
(4) 最優個體進化趨勢曲線
進化趨勢曲線直觀地呈現出進化算法的尋優過程和最優解的變化情況。
3.3.2測試函數及初始化
本文選擇式（3.16) - (3.19)四個測試函數（Rastrigin, Ackley, Griewank, Rosenbrock)來
衡量改進算法的尋優性能：
D
Kx) = Z[x2 -10cos(2冗x)+10](3.16)
i=1i=1
為更直觀地顯示各測試函數的特徵，本文畫出各測試函數的三維圖，如圖3.4所示。根
據圖3.4顯示，各測試函數典型複雜且各具特色。f〇s(X)簡單平滑，雖為單峰函數，但變量 之間相互關聯，基於梯度信息的全局搜索方向並不時時準確，傳統優化方法求解困難。
fas(X)，fck(X)和•41(x)均是多峰函數，最小值均位於0;但存在多個局部極值，全局最優
解搜尋困難。特別地，函數fri(X)的局部極小值與全局最小值差別比較小，欺騙性較強。
22
(c) Griewank 函數（d) Rosenbrock 函數
第三章基於進化方向拓展的DE算法研究
根據第二章關於DE算法的介紹及改進工作的總結知，對於不同的優化問題或特定的應用領域，DE算法依然有很大的改進空間。對於控制參數的自適應改進，許多的研究工作都取得了很好的效果。對於Storn等提出的十餘種變異策略，也有多種形式的改進。顯然，不同的改進方案具有不同的優勢和劣勢。往往其中一種改進方案，在解決了種群多樣性缺失等問題時，在算法的精度或速度上又無法取得較好地平衡。反之亦然。
本章通過分析DE算法後期進化緩慢的根本原因，提出了基於進化方向拓展的自適應差 分進化算法（Improved adaptive differential evolution algorithm with advanced eliminative trial individuals, TaDE)。改進的進化算法不僅能自適應地調節控制參數，同時能夠在進化階段動 態地拓展搜索方向，使得種群能更快地進化成熟，為後續目標跟蹤的成功應用打下基礎。
3.1引言
如第二章所述，參數的合理控制對DE算法的性能有很大的影響。種群在進化過程中， 參數的自適應控制能夠通過“外部”的動態修正，最大限度地保證生成的校驗向量優於父代的目標向量X$，完成一次成功地進化更新。這樣，不會造成進化計算的浪費，以保持算法的有效性。但再巧妙再隨機地參數控制，往往也無法從根本上避免DE算法固有的進化 停滯問題。
通過分析知，造成該問題的根本原因在於DE算法本身的迭代更新機制。種群中的個體 通過變異、交叉操作產生校驗向量後，的適度值只有低於父代向量X$才能進入下一代的種群中。成功地取代父代向量才被稱為子代，否則只能作為一個校驗向量被“淘汰”。
取代X$需要一個特定的等待時間，即所謂的“進化停滯”。隨著進化的不斷進行，種群日益趨於成熟，個體能夠進化的“空間”範圍越來越小，導致了“進化停滯”時間逐漸增加。 從概率上來說，適度值差異逐漸減小並趨於平穩的種群，在下一代得到成功進化的概率也隨 之減小。如圖3-1所示。其中個體xa，分別為^和^的子代個體。由圖可知，
/(•〇>/(•〇>"> /(xb),即個體的進化方向是：。個體能夠進化的區間範圍為：而個體^能夠進化的區間範圍為：的，^2]。顯然'成功進化成^的概率要遠小於'進化成'的概率，對應的，^則比'需要更長的進化時間。
圖3.1 個體的適度值與進化成功的概率間的關係
此外，由於DE算法在選擇階段採用嚴苛的貪婪選擇機制，又加劇了種群在中後期的“進化停滯”效應。當子代進化區間的範圍變得越來越窄時，產生校驗向量的適度值低於父代的 概率也變得越來越小，能成功進化的個體也逐漸減少。此時算法需要花費更多的時間迭代搜 索，來完成一次成功地進化。
因此，DE算法的種群進化過程是一個矛盾的過程。一方面，種群希望在每一代的進化中， 都能得到有效地進化。則種群的多樣性必不可少。另一方面，隨著進化的持續進行，有限數 目的種群加之貪婪選擇機制，使得種群的多樣性又難以維持。
3.2 DE算法的改進思路
3.2.1進化方向的拓展
根據上一章的介紹，DE算法在進化的中後期，為避免算法的早熟收斂問題，需合理增加 種群的多樣性來實現全局空間的搜索。本文在之前工作[78]的基礎上，通過引入父代中被淘汰 的個體來進一步拓展原種群的進化方向。
(1)淘汰種群個體的引入
當種群進化到中後期時，算法的主要目是局部搜索以滿足求解精度。基於局部搜索策略 的（LSDE[79])算法是一種常見的提高算法求解精度的方法。LSDE算法主要思想是在的鄰域進行一系列的局部搜索來確定最終的X'。其他類似LSDE的改進工作本質相同，在搜best ,G尋精度上均得到一定的提高。但局部收斂問題依然無法充分避免。為此，JADE算法從100^% 個最優個體中隨機選擇一個作為XbestG ;同時在下一代的變異操作中，各差分個體的隨機選取，不僅來自子代種群，還來自父代被淘汰的種群個體（通過集合A保存）。因此，最終產生 的校驗向量多樣性增加，進一步避免了算法的局部收斂。
本文結合文獻[61][79]工作的改進思想，在JADE的基礎上，進行改進。
首先，JADE算法在變異操作中，用於差分向量計算的個體，是從原種群P和集合A的 並集中隨機的選擇。但這樣的隨機方式，導致A集合在後期的進化中沒有被充分地利用。因 此，本文在變異策略上做了如下改進：
V,,G = X,,G + 巧.(X^G _ X,,G ) + 巧2. (Xrt,G _ Xn,G )(3.1)
其中個體的選擇，來自原種群P，而非PUA。X,.2,c個體的選擇直接從集合A中選取，
保證進化中後期集合A中的多樣性被充分利用。如圖3.2所示，本文通過引入成的差
— — —
分向量F；2<Xac-X^c)(圖中a)，作為原進化算法一個拓展的搜索方向。
— — —
圖3.2 差分向量F^2 .(Xr1，G—Xr2，G)的方向拓展（a )
其次，與JADE算法不同的是，本文對進化的週期進行分段，並對各階段種群的變異操
作動態調整，以更好地適應種群進化情況。在種群整個進化週期，JADE算法是一直從當前
種群最優的100^%中隨機選一個作為X^p。但對於進化到後期的種群來說，個體間的差異
性逐漸減小並趨於成熟，群體的“質量”都較高。JADE算法僅從100^%個最優的種群中隨
機選擇，對於其他100^%以外的個體來說，有失“公平”。如圖3.2中所示，Xrt々，X_和X^
一樣，都位於同一區域D，個體間的特性差異較小。
因此，本文在進化的中後期階段，改進的變異操作如式（3.3)所示：
V.，G sX^+F^X。_X,，G)+F2-(XaG-X一，腿（3.2)
V.，G =又,，0+盡-(又_ _X,，G)+F2-(XaG—X一，臓（3.3)
其中，又_從100^%個最優的個體及原種群中適度值“平均”的個體中隨機選擇。通過淘汰的父代個體Xn，c的引入及進化週期的分段，使得種群多樣性增加，進化速度得到進一步提升。
(2)淘汰校驗個體的引入
為進一步豐富原種群的多樣性，現考慮父代中另外一種被淘汰的個體，即種群在經過變 異、交叉等操作後形成的校驗個體。既然被淘汰的X#可引入到子代種群中，那進化期間被淘汰的校驗個體同樣可以利用。
顯然，引入進化失敗的校驗個體，間接地使種群出現一定的“倒退”，不符合進化算法“優 勝劣汰”的本質。個體既然按照既定好的變異策略和參數調整方案進化失敗了，自然要被舍 棄。但在種群進化的後期階段，所有個體基本進化成熟且位於全局解的鄰域空間，種群嘗試 變異出的校驗個體同樣具有很高的“質量”。若依然採取類似進化前期苛刻的貪心選擇機制， 直接丟棄校驗個體是迭代計算的一種浪費。相反，通過引入父代中失敗的校驗個體，可為下 一代種群的進化提供反饋信息，子代根據反饋信息可進一步提高成功進化的概率。
此外，當前所有的關於DE改進工作都是從正向的思路去解決解決，即通過參數調整， 進化過程或變異策略的改進，讓正常的進化趨勢穩步順利地進行。倘若優化問題的局部最優 和全局最優解在空間上很接近（如圖3.2中的區域A、C)，這時往往需要適當地“延緩”算 法當前局部空間探索的速度，再次參照全局空間探索的方向，以避免算法在極值區域進行過 多的局部搜索。本文加入被淘汰的校驗個體形成的“逆向”拓展搜索方向，可實現上述目的。 因此，對式（3.3)進一步改進如下：
Vg =Xi,G +巧.（X-G —Xi,G) + F；2 .(Xhg —Xag)
+ F3-(XhG- u ㈣ G—
其中，U^g—1表示父代進化中被淘汰的最優的校驗個體。F；3《X,G-Ubest,G—1)可稱為“退化”
—>
的差分向量，如下圖b所示：
——
圖3.3差分向量4 .(X,，g—Ubest，G—i)的方向拓展（b )
由圖3.3可知，合理地加入父代中的校驗個體，從進化的全局來看，不僅不影響原進化的進行，而且降低了子代種群中校驗個體落入區域C內的概率。在種群進化的後期雖“擾動” 了原全局搜索的方向，但以一定的計算開銷換來更高的概率，來規避局部最優區域附近的迭 代搜索，使算法在搜尋精度和求解速度上取得了更佳的均衡。
3.2.2控制參數的自適應調整
根據以上改進方案的介紹，本文改進的進DE算法需要控制的關鍵參數有： 接下來介紹相應的參數調整策略。
(1) 自適應調整
根據第一章的介紹，一些目標跟蹤的研究工作中引入PSO算法，並取得了不錯的跟蹤效 果。PSO算法獨特的記憶機制，不僅實時地參考粒子本身最優的歷史信息，還參考當前種群 中最優的粒子信息。類似的，分析DE算法中個體的更新過程知，由於父代個體只有進化成
功才被更新，所以每個個體在當前代都是歷史最優的。關於&，^；2的自適應調整，本文選擇
類似以往工作[78]中模擬PSO信息交互機制的方式：
^ ( Xbest，G )2 = (3.6) f+f、Xbest，G )
其中，f = [^f(X,，G) + f(Xrt，G) + f(X嘆G)j/3。係數能夠根據X,，G、Xbest，G及隨機選擇的個體的適度值動態地調整，取得全局搜索方向和局部搜索方向之間的平衡。
但在進化的後期，種群進化趨於完全，個體特性趨於平穩，上述參數控制效果會逐漸減
弱。^，巧2的係數趨於相同，使算法在後期的局部搜索階段，沒有動態地投入更大的係數比
重。一個最簡單的參數控制方案，就是在種群的進化過程中，i和分別保持動態遞減和 動態遞增的趨勢。最常見的是線性調節方式[80][81]，如文獻[81]提出一種線性控制的策略如下：
Ft+1^max=Pt J(3.7）
Ch == CR+H(3.8）
其中，&，％分別是變異尺度因子和交叉概率因子的初始值。
儘管這樣的參數控制方向是正確的，但還存在不足之處：如果在迭代搜索後期還沒找到全局解，算法很容易早熟收斂。一些工作如JADE、SaDE等提出了 f，C^.隨機選取的原則，
即通過不同的分佈隨機地調整，一定程度上避免了因控制參數的不合理造成的早熟收斂問題。 這些參數調節方案經過大量的實驗仿真，得出了一些值得參考的結論。如Storn[58]等在文獻中 指出，尺度因子巧取值位於[〇.4，1]區間時，優化效果較明顯，初始值一般設置為0.5;根據JADE
算法的仿真結論，交叉概率選在0.6〜0.9之間時優化效果最佳。其他類似的研究工作也驗 證了這樣的參數區間的有效性。
需要強調的是，本論文的目的是將改進後的DE算法應用於目標跟蹤中，因此對算法的 求解速度有很高的要求。儘管當前關於參數自適應的改進工作，都或多或少地取得了很好的 效果，但這些參數調整方案往往需要更多的計算，有的參數計算方式甚至比DE算法本身的 進化計算更復雜，由此帶來的計算時間和開銷，往往不適合目標跟蹤的實時應用。此外，當 前很多參數改進的研究工作，都取得了很好的結論，可以利用這些現有的結論，設計一種更 簡單的參數調整方案，可起到“事半功倍”的效果。
因此在以往參數調整研究結論的基礎上，為了減小因參數的自適應調整帶來的額外開銷， 本文采用線性控制和信息交互的方式相結合的方式，如下公式所示：
Fi = F〇+F(3.9)
Fi2=F0+Fi2(3.10)
其中，分別對應於式（3.5)(3.6)的心盡。如下所示：
F0 =Fmn +1 —DU -G)/G(3.11 )
CR0=Cm-CRJ*G(3.12)
其中，G為當前的進化代數。值得注意的是，F^FmxpCRm^CRmx和其他參數一樣，同樣需
要合理設置。本文利用現有改進工作的結論，設置最合理的區間範圍。同時，在後期的目標 跟蹤試驗中，根據所測試的數據集的特性，針對性的調整。
根據之後算法的性能仿真知，這樣簡化的參數“擬合”方式，一方面保證了 線性遞增，
CR.線性遞減的趨勢，另一方面，節省計算開銷和搜索時間，提高了算法求解速度，為目標 跟蹤的有效應用提供條件。
(2) 盡的自適應調整的動態調整需要考慮兩點：
首先，盡需要在進化的後期引入且數值要小。畢竟種群進化到後期是以局部搜索為主，“退化”的差分向量能有效地增加種群多樣性，使得算法後期搜索新空間的能力加強，但不可破壞中後期成熟個體的解結構信息，以免造成前期進化開銷的浪費。
其次，廠3的設置和種群的多樣性建立直接聯繫。參考當前種群整體的多樣性信息和位置
信息，可大大提高算法的搜尋速度和精度。本文在算法的後期，在引入盡時實時考察所有個
體的位置信息和適度值信息，用於“退化”的差分向量的係數調整。
關於多樣性信息和位置信息的計算，本文使用文獻[82]的方式，如下
1 NP DPC =-Xji(G +1})1 NP7FC =斤寫U (X(G)) - / (X(G +1)))2
其中，PC,FC分別代表種群的位置多樣性和適度值多樣性。
為了更好地應用PC, FC包含的信息，本文采用類似文獻[82]中壓縮的方式。最終參數巧3 的形式如下：
其中，奐c=1 —(1 + PC)*e—PC，2FC=1 —(1 + PC)*e—FC，且 APC，AFCe(0，1)。
根據文獻[82]中的結論，PC,FC都很小時，進化算法到了後期階段，算法以收斂速度和 搜尋精度性能為主。而正是在此時，通過引入U^，G—1來拓展搜索方向，並通過參數盡的動態 調整，實現多個性能之間的均衡。
係數&的自適應調整，充分利用了種群的多樣性信息和位置信息，在算法的後期進一步 提高了全局搜索的概率。通過少量的計算開銷，規避了原種群向局部最優解附近的盲目進化。
20
本文設計的算法實現步驟如下：
基於進化方向拓展的DE算法實現步驟（TaDE)
1:初始化種群P、控制參數^，^，^，^^，^、集合人^。
2:計算種群P個體的適度值，找到X並驗證算法的終止條件。否則G = G+1。
best，G
3:種群進化更新：產生校驗個體U (前期）。
i，G
(iv) 變異：按照式（3.11)(3.12)(3.14)動態調整參數。
從集合P和A中分別選出差分個體Xrt，G，X嘆G。
根照式（3.2)進行變異操作。
(v) 交叉：根照式（2.9)進行交叉操作。
(vi) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
4：種群進化更新：產生校驗個體U。（中後期）。
i，G
(i) 變異：按照式（3.11)(3.12)(3.17)(3.14)動態調整參數。
從集合P，A，U中分別選出差分個體Xh^XuaUmw。
根照式（3.4)進行變異操作。
(ii) 交叉：根照式（2.9)進行交叉操作。
(iii) 選擇：根據式（2.10)進行選擇操作。
X進入下一代種群或集合A。
i，G
U進入下一代種群或集合U。
i，G
5：返回2,直到滿足算法的終止條件。
3.3算法仿真及性能分析
3.3.1算法性能評價規則
(1)函數評價次數（Function Evaluation，FE)
算法在迭代過程中，每個個體進化後都需要計算關於某函數的適度值，進行一次函數評 價。因此，在種群進化過程中記錄當前函數評價的總次數。當/(X)-/^^)^或視 >視_ 時，算法終止迭代。
(2) 尋優成功率
尋優成功率可衡量算法的可靠性。當前循環的輸出結果與理論最優值之間的誤差滿足設 定的閾值時，當前循環的搜索結果收斂，算法尋優成功。#次算法循環中，若搜索結果收斂
n次，尋優成功率為^。
N
(3) 平均最優適應度
優化算法某一次的尋優精度往往具有不穩定性。因此對算法進行多次測試，最終所有最 優個體適度值的平均值，即為平均最優適應度。
(4) 最優個體進化趨勢曲線
進化趨勢曲線直觀地呈現出進化算法的尋優過程和最優解的變化情況。
3.3.2測試函數及初始化
本文選擇式（3.16) - (3.19)四個測試函數（Rastrigin, Ackley, Griewank, Rosenbrock)來
衡量改進算法的尋優性能：
D
Kx) = Z[x2 -10cos(2冗x)+10](3.16)
i=1i=1
為更直觀地顯示各測試函數的特徵，本文畫出各測試函數的三維圖，如圖3.4所示。根
據圖3.4顯示，各測試函數典型複雜且各具特色。f〇s(X)簡單平滑，雖為單峰函數，但變量 之間相互關聯，基於梯度信息的全局搜索方向並不時時準確，傳統優化方法求解困難。
fas(X)，fck(X)和•41(x)均是多峰函數，最小值均位於0;但存在多個局部極值，全局最優
解搜尋困難。特別地，函數fri(X)的局部極小值與全局最小值差別比較小，欺騙性較強。
22
(c) Griewank 函數（d) Rosenbrock 函數
圖3.4 各測試函數的三維圖
本文的TaDE算法是基於JADE算法的基礎上進行改進的，因此通過上述四個測試函數， 對兩算法的性能並進行對比。此外，本文還和經典的DE算法，SaDE算法進行對比。為了保 證比較的公平性，本文中的參數戶和JADE算法中相同，均設置為0.05。初始化為0.5。
分別初始化為0.4和1。Cfl分別初始化為0.6和0.9。其中DE/rand/1/bin中
的參數按照文獻[61]中推薦的設置為F=0.5，C^ =0.9。種群規模WP=30。所有測試函
數均獨立進行30次。Gmx=1000。所有算法在進化Gmax代後終止迭代。