應用鄰域搜索的多策略進化算法研究

發(fā)布時間：2020-08-29 09:00

　　在科學研究和工程項目中,很多實際問題都可轉化為對應的優(yōu)化問題來求解。作為一類有效的最優(yōu)化方法,進化算法通過模擬自然界中生物進化現(xiàn)象來搜索問題的最優(yōu)解,具有算法結構簡單,性能優(yōu)良等特點。相對于一些經典的最優(yōu)化方法,特別是基于梯度信息的方法,進化算法對問題的數(shù)學性質要求不高,甚至可直接用于黑盒優(yōu)化。然而,隨著社會經濟發(fā)展,優(yōu)化問題也日趨復雜,求解難度大大增加,使得進化算法的性能受到了極大挑戰(zhàn),容易出現(xiàn)早熟或陷入局部最優(yōu)等不足。事實上,就算法性能而言,影響進化算法性能的兩個重要因素是:全局勘探能力和局部開采能力,如何平衡好這兩種能力是提高算法性能的關鍵。為此,本文以平衡算法的全局勘探和局部開采能力為目標,著重研究了如何設計多策略機制用于提高進化算法的性能,避免單一策略帶來的搜索局限性;同時,為充分利用種群中優(yōu)秀個體的精英信息,還研究了如何應用鄰域搜索機制來改善算法性能。本文的主要工作及創(chuàng)新點如下:(1)在人工蜂群算法中,解搜索方程用于生成新的候選解,是影響算法性能的主要因素。然而,已有相關研究指出,該方程存在勘探能力強而開采能力弱的問題。為此,我們提出了一種基于隨機優(yōu)秀個體的新解搜索方程,試圖通過融合優(yōu)秀個體的精英信息來增強方程的開采能力。并且,為保持算法在勘探和開采能力上的平衡,我們設計了一種簡潔的多策略機制用于同時應用新舊方程,采用了IF-ELSE結構的方式來控制兩種方程的使用頻率。在22個典型的測試函數(shù)上開展數(shù)值實驗,與3種知名的改進人工蜂群算法進行對比,實驗結果表明該多策略機制能夠有效提高算法性能。(2)在差分進化算法中,變異策略是影響算法性能的重要因素,不同類型的變異策略適合求解的問題類型一般也不同。然而,經典差分進化算法僅采用單一的變異策略用于生成新的候選解,導致算法性能受到了極大限制。為此,我們提出了一種基于多子種群技術的多策略機制用于增強算法性能。在該機制中,根據個體的適應度值將種群分為三個子種群,每個子種群分別采用不同的變異策略,使得各子種群具備不同的搜索能力,力圖平衡整個種群的勘探和開采能力。在34個典型的測試函數(shù)上進行實驗,與包含7種差分進化算法在內的12種進化算法進行對比,實驗結果表明基于該多策略機制的差分進化算法能在大多數(shù)測試函數(shù)上取得更好結果。(3)在進化算法中,種群中的優(yōu)秀個體通常包含了可用于指導算法搜索的精英信息,合理有效地利用這些信息可推動整個種群朝著更好的方向進化。然而,如何利用這些信息是設計相關學習機制的難點。為此,我們引入了基于環(huán)形拓撲結構的鄰域搜索機制用于增強算法的性能。在該機制中,按個體下標索引的方式把種群中所有個體組織成環(huán)形結構,對每個個體定義了半徑為K的鄰域空間,在該鄰域空間內開展細粒度搜索,以期找到更好個體,充分發(fā)揮優(yōu)秀個體的引領作用。我們將該鄰域搜索機制分別應用于人工蜂群算法和差分進化算法,實驗結果表明該機制可有效地改善相應算法的性能,具有良好的普適性。(4)為進一步驗證本文提出的改進算法的性能,我們引入了3個實際優(yōu)化問題:無線傳感器網絡的覆蓋控制問題、調頻聲波的參數(shù)估計問題、以及擴頻雷達的波利相位編碼設計問題。對于無線傳感器網絡的覆蓋控制問題,我們采用本文提出的改進人工蜂群算法來解決,與經典人工蜂群算法相比,本文算法在覆蓋率上能提高2.12%。對于調頻聲波的參數(shù)估計問題和擴頻雷達的波利相位編碼設計問題,我們采用本文提出的改進差分進化算法來解決,與經典差分進化算法相比,本文算法在這兩個問題上的結果精度能分別提高92.22%和47.12%。
【學位單位】：江西師范大學
【學位級別】：碩士
【學位年份】：2019
【中圖分類】：TP18
【部分圖文】：

應用鄰域搜索的多策略進化算法研究